patternmatching.tex

\chapter{Pattern Matching}\label{patternmatching}

Given a Factor sequence or primitive type you can pattern match and
create bindings to symbols with a special format. Any symbol that
begins with a `?' character is used as a pattern match variable, and
binds to the value in a matching sequence. Here's a simple example:

\wordtable{
\vocabulary{match}
\ordinaryword{match}{match~( value1 value2 -- bindings )}
}

\begin{alltt}
USE: match

MATCH-VARS: ?a ?b ?c ;

\{ 1 2 3 \} \{ ?a ?b ?c \} match . 
  \textbf{H\{ \{ ?a 1 \} \{ ?b 2 \} \{ ?c 3 \} \}}
\end{alltt}

The two sequences match in that they are both sequences with three
items. So the result is a hashtable containing the pattern match
variables as keys and the values of those variables in the second
sequence as the value. If items in the sequence are not pattern match
variables then they must match exactly:

\begin{alltt}
\{ 1 2 3 \} \{ 1 2 ?a \} match .
  \textbf{H\{ \{ ?a 3 \} \}}

\{ 1 2 3 \} \{ 2 2 ?a \} match .
  \textbf{f}
\end{alltt}


The second example doesn't match as the first element in both
sequences is not the value `2'.

Matching works recursively too:

\begin{alltt}
\{ 1 2 \{ 3 4 \} \{ 5 6 \} \} \{ 1 2 ?a \{ ?b ?c \} \} match .
  \textbf{H\{ \{ ?a \{ 3 4 \} \} \{ ?b 5 \} \{ ?c 6 \} \}}
\end{alltt}


This type of pattern matching is very useful for deconstructing
messages sent to distributed factor objects. But even more useful is
to be able to have something like \verb|cond| but working directly with
patterns. This is what \verb|match-cond| does. It takes a sequence and an
array of arrays. Each sub-array contains the pattern to match the
sequence against, and a quotation to execute if that pattern
matched. The quotation is executed with the hashtable result of the
pattern match bound in the current namespace scope, allowing easy
retrieval of the pattern match variables.

\wordtable{
\vocabulary{match}
\ordinaryword{match-cond}{match-cond~( assoc -- )}
}

It sounds complex but is actually very easy in practice. Here what an
example `counter' process might look like using \verb|match-cond|:

\begin{verbatim}
USING: match concurrency.messaging ;

SYMBOL: increment
SYMBOL: decrement
SYMBOL: get
MATCH-VARS: ?value ?from ?tag ;

: counter ( value -- )
  receive {
    { { increment ?value } [ ?value + ] }
    { { decrement ?value } [ ?value - ] }
    { { get ?from }        [ dup ?from send ] }
    { _                    [ "Unmatched message" print flush ] }
  } match-cond counter ;
\end{verbatim}

This is a process that keeps track of a count value. You can send
messages to increment or decrement the count by an amount, or to get
the value and send it back to the calling process. So sends/receives
look like:

\begin{alltt}
USING: threads ;

[ 0 counter ] "counter" spawn
\{ increment 5 \} over send
\{ decrement 10 \} over send
[ get , self , ] \{ \} make swap send receive .
  \textbf{-5}
\end{alltt}

One thing to be aware of with \verb|match-cond| is that calls in the
quotation side of a condition are not tail recursive. So the following
looks equivalent to the previous counter example but is not tail
recursive and will consume call stack space on each message,
eventually failing when it overflows:

\begin{verbatim}
: counter ( value -- )
  receive {
    { { increment ?value } [ ?value + counter ] }
    { { decrement ?value } [ ?value - counter ] }
    { { get ?from }        [ dup ?from send counter ] }
    { _                    [ "Unmatched message" print flush counter ] }
  } match-cond ;
\end{verbatim}

Pattern matching on tuples, and the repeating presence of match
variables also works:

\begin{alltt}
TUPLE: person first last ;
MATCH-VARS: ?first ?last ;

T\{ person f "chris" "double" \} T\{ person f ?first ?last \} match .
  \textbf{H\{ \{ ?first "chris" \} \{ ?last "double" \} \}}

\{ "one" "two" "one" "two" \} \{ ?a ?b ?a ?b \} match .
  \textbf{H\{ \{ ?a "one" \} \{ ?b "two" \} \}}

\{ "1" "two" "one" "two" \} \{ ?a ?b ?a ?b \} match .
  \textbf{f}
\end{alltt}