doc/manual/match-ref.tex

   1 \section{Extension {\tt match}: structural pattern matching}
   2 Pattern matching is an extremely pleasant and powerful way to handle tree-like
   3 structures, such as ASTs. Unsurprisingly, it's a feature found in most
   4 ML-inspired languages, which excel at compilation-related tasks. There is a
   5 pattern matching extension for metalua, which is extremely useful for most
   6 meta-programming purposes.
   7
   8 \subsection{Purpose}
   9
  10 First, to clear a common misconception: structural pattern matching has
  11 absolutely nothing to do with regular expresssions matching on strings: it works
  12 on arbitrary structured data.
  13
  14 When manipulating trees, you want to check whether they have a certain structure
  15 (e.g. a `Local{ } node with as first child a list of variables whose tags are
  16 `Id{ }); when you've found a data that matches a certain pattern, you want to
  17 name the interesting sub-parts of it, so that you can manipulate them easily;
  18 finally, most of the time, you have a series of different possible patterns, and
  19 you want to apply the one that matches a given data. These are the needs
  20 addressed by pattern matching: it lets you give a list of ({\tt pattern ->
  21   code\_to\_execute\_if\_match}) associations, selects the first matching
  22 pattern, and executes the corresponding code. Patterns both describe the
  23 expected structures and bind local variables to interesting parts of the data.
  24 Those variables' scope is obviously the code to execute upon matching success.
  25
  26 \paragraph{Match statement}
  27 A match statement has the form:
  28
  29 \begin{verbatim}
  30 match <some_value> with
  31 | <pattern_1> -> <block_1>
  32 | <pattern_2> -> <block_2>
  33 ...
  34 | <pattern_n> -> <block_n>
  35 end
  36 \end{verbatim}
  37
  38 The first vertical bar after the "with" is optional; moreover, a pattern can
  39 actually be a list of patterns, separated by bars. In this case, it's enough for
  40 one of them to match, to get the block to be executed:
  41
  42 \begin{verbatim}
  43 match <some_value> with
  44 | <pattern_1> | <pattern_1_bis > -> <block_1>
  45 ...
  46 end
  47 \end{verbatim}
  48
  49 When the match statement is executed, the first pattern which matches
  50 {\tt<some\_value>} is selected, the corresponding block is executed, and all
  51 other patterns and blocks are ignored. If no pattern matches, an error
  52 {\tt"mismatch"} is raised. However, we'll see it's easy to add a catch-all
  53 pattern at the end of the match, when we want it to be failproof.
  54
  55 \subsection{Pattern definitions}
  56
  57 \paragraph{Atomic literals}
  58 Syntactically, a pattern is mostly identical to the values it matches: numbers,
  59 booleans and strings, when used as patterns, match identical values.
  60
  61 \begin{verbatim}
  62 match x with
  63 | 1 -> print 'x is one'
  64 | 2 -> print 'x is two'
  65 end
  66 \end{verbatim}
  67
  68 \paragraph{Tables}
  69 Tables as patterns match tables with the same number of array-part elements, if
  70 each pattern field matches the corresponding value field. For instance, \{1, 2,
  71 3\} as a pattern matches \{1, 2, 3\} as a value. Pattern \{1, 2, 3\} matches
  72 value \{1, 2, 3, foo=4\}, but pattern \{1, 2, 3, foo=4\} doesn't match value
  73 \{1, 2, 3\}: there can be extra hash-part fields in the value, not in the
  74 pattern. Notice that field 'tag' is a regular hash-part field, therefore \{1, 2,
  75 3\} matches `Foo\{1, 2, 3\} (but not the other way around). Of course, table
  76 patterns can be nested. The table keys must currently be integers or strings.
  77 It's not difficult to add more, but the need hasn't yet emerged.
  78
  79 If you want to match tables of arbitrary array-part size, you can add a "..." as
  80 the pattern's final element. For instance, pattern \{1, 2, ...\} will match all
  81 table with at least two array-part elements whose two first elements are 1 and
  82 2.
  83
  84 \paragraph{Identifiers}
  85 The other fundamental kind of patterns are identifiers: they match everything,
  86 and bind whatever they match to themselves. For instance, pattern {1, 2, x} will
  87 match value {1, 2, 3}, and in the corresponding block, local variable x will be
  88 set to 3. By mixing tables and identifiers, we can already do interesting
  89 things, such as getting the identifiers list out of a local statement, as
  90 mentionned above:
  91
  92 \begin{verbatim}
  93 match stat with
  94 | `Local{ identifiers, values } ->
  95    table.foreach(identifiers, |x| print(x[1])
  96 ... -- other cases
  97 end
  98 \end{verbatim}
  99
 100 When a variable appears several times in a single pattern, all the elements they
 101 match must be equal, in the sense of the "==" operator. For instance, pattern \{
 102   x, x \} will match value \{ 1, 1 \}, but not \{ 1, 2 \}. Both values would be
 103 matched by pattern \{ x, y \}, though. A special identifier is "\_", which doesn't
 104 bind its content. Even if it appears more than once in the pattern, matched
 105 value parts aren't required to be equal. The pattern "\_" is therefore the
 106 simplest catch-all one, and a match statement with a "{\tt| \_ ->}" final
 107 statement will never throw a "mismatch" error.
 108
 109 \paragraph{Guards}
 110
 111 Some tests can't be performed by pattern matching. For these cases, the pattern
 112 can be followed by an "if" keyword, followed by a condition.
 113
 114 \begin{verbatim}
 115 match x with
 116 | n if n%2 == 0 -> print 'odd'
 117 | _ -> print 'even'
 118 end
 119 \end{verbatim}
 120
 121 Notice that the identifiers bound by the pattern are available in the guard
 122 condition. Moreover, the guard can apply to several patterns:
 123
 124 \begin{verbatim}
 125 match x with
 126 | n | {n} if n%2 == 0 -> print 'odd'
 127 | _ -> print 'even'
 128 end
 129 \end{verbatim}
 130
 131 \paragraph{Multi-match}
 132
 133 If you want to match several values, let's say 'a' and 'b', there's an easy way:
 134
 135 \begin{verbatim}
 136 match {a,b} with
 137 | {pattern_for_a, pattern_for_b} -> block
 138 ...
 139 end
 140 \end{verbatim}
 141
 142 However, it introduces quite a lot of useless tables and checks. Since this kind
 143 of multiple matches are fairly common, they are supported natively:
 144
 145 \begin{verbatim}
 146 match a, b with
 147 | pattern_for_a, pattern_for_b -> block
 148 ...
 149 end
 150 \end{verbatim}
 151
 152 This will save some useless tests and computation, and the compiler will
 153 complain if the number of patterns doesn't match the number of values.
 154
 155 \paragraph{String regular expressions}
 156 There is a way to use Lua's regular exressions with match, through the division
 157 operator ``/'': the left operand is expected to be a literal string, interpreted
 158 as a regular expression. The variables it captures are stored in a table, which
 159 is matched as a value against the right-hand-side operand. For instance, the
 160 following case succeeds when {\tt foo} is a string composed of 3 words separated
 161 by spaces. In case of success, these words are bound to variables {\tt w1}, {\tt
 162   w2} and {\tt w3} in the executed block:
 163
 164 \begin{verbatim}
 165 match foo with
 166 | "^(%w+) +(%w+) +(%w+)$"/{ w1, w2, w3 } ->
 167    do_stuff (w1, w2, w3)
 168 end
 169 \end{verbatim}
 170
 171 \subsection{Examples}
 172 There are quite a lot of samples using match in the metalua distribution, and
 173 more will come in the next one. Dig in the samples for fairly simple usages, or
 174 in the standard libs for more advanced ones. Look for instance at examples
 175 provided with the {\tt walk} library.