\subsection{Structural pattern matching}\r
+\r
+FIXME: refer to the official match extension instead of re-explaining\r
+what pattern matching is about.\r
+\r
\subsubsection{Basic principles}\r
In many languages, including Lua, ``pattern matching'' generally\r
refers to the ability to:\r
\verb|binopfuncs| which associate an operator name with the corresponding\r
function. The evaluator would be written:\r
\r
-\begin{verbatim}\r
+\begin{Verbatim}[fontsize=\scriptsize]\r
+\r
function eval(t)\r
match t with\r
| `Op{ op, a, b } -> return binopfuncs[op](eval(a), eval(b))\r
| `Variable{ v } -> return values[v]\r
end\r
end\r
-\end{verbatim}\r
+\end{Verbatim}\r
\r
\subsubsection{Pattern compilation}\r
\r
\r
For instance, consider the following pattern:\r
\r
-\begin{verbatim}\r
+\begin{Verbatim}[fontsize=\scriptsize]\r
+\r
{ tag = "Foo", 10, { 20 }, { x = a }, b }\r
-\end{verbatim}\r
+\end{Verbatim}\r
\r
It corresponds to the series of tests and assignments on the left:\r
\r
\begin{minipage}{6cm}\r
-\begin{verbatim}\r
+\begin{Verbatim}[fontsize=\scriptsize]\r
+\r
let v1 = <tested_term>\r
type(v1) == "table"\r
let v2 = v1.tag\r
local b = v2\r
\r
\r
-\end{verbatim}\r
+\end{Verbatim}\r
\end{minipage}\r
\begin{minipage}{6cm}\r
-\begin{verbatim}\r
+\begin{Verbatim}[fontsize=\scriptsize]\r
+\r
let v1 = tested_term\r
if type(v1) == "table" then\r
let v2 = v1.tag\r
local b = v2\r
<inner_term>\r
end ... end -- (16 times)\r
-\end{verbatim}\r
+\end{Verbatim}\r
\end{minipage}\r
~\\~\\\r
\r
This is done by a \verb|parse_pattern()| function, which does just what\r
is described in the bullet list above:\r
\r
-\begin{verbatim}\r
+\begin{Verbatim}[fontsize=\scriptsize]\r
+\r
-------------------------------------------------------------------\r
-- Turn a pattern into a list of conditions and assignations,\r
-- stored into [acc]. [n] is the depth of the subpattern into the\r
else error "Invalid pattern type" end\r
end\r
-------------------------------------------------------------------\r
-\end{verbatim}\r
+\end{Verbatim}\r
\r
This function relies on the following helper functions:\r
\begin{itemize}\r
recursive functions). \verb|acc| is the list filled by the\r
\verb|accumulate()| function:\r
\r
-\begin{verbatim}\r
+\begin{Verbatim}[fontsize=\scriptsize]\r
+\r
-------------------------------------------------------------------\r
-- Turn a list of tests and assignations into [acc] into a\r
-- single term of nested conditionals and assignments.\r
return { it, unpack (inside) }\r
end\r
end\r
-\end{verbatim}\r
+\end{Verbatim}\r
\r
To fully understand this function, one must remember that test\r
operations are translated into {\tt`Op\{ <opname>, <arg1>, <arg2>\}}\r
finish with a ``\verb|return|'', so that other cases are skipped upon\r
successful matching. To sum up, we will translate this:\r
\r
-\begin{verbatim}\r
+\begin{Verbatim}[fontsize=\scriptsize]\r
+\r
match <foo> with\r
| <pattern_1> -> <x1>\r
| <pattern_2> -> <x2>\r
...\r
| <pattern_n> -> <xn>\r
end\r
-\end{verbatim}\r
+\end{Verbatim}\r
\r
\noindent into this:\r
\r
-\begin{verbatim}\r
+\begin{Verbatim}[fontsize=\scriptsize]\r
+\r
repeat\r
local v1, v2, ... vx -- variables used to store subpatterns\r
let v1 = <tested_term>\r
...\r
if <compilation of pattern_n> ... then xn; break end\r
until true\r
-\end{verbatim}\r
+\end{Verbatim}\r
\r
First, we add final \verb|break| statements where required, and we\r
compile all (pattern, block) pairs:\r
\r
-\begin{verbatim}\r
+\begin{Verbatim}[fontsize=\scriptsize]\r
+\r
-------------------------------------------------------------------\r
-- parse all [pattern ==> block] pairs. Result goes in [body].\r
-------------------------------------------------------------------\r
local compiled_case = collapse (1, case[2])\r
for _, x in ipairs (compiled_case) do table.insert (body, x) end\r
end\r
-\end{verbatim}\r
+\end{Verbatim}\r
\r
\noindent Then, we can just splice it into the appropriate quote:\r
\r
-\begin{verbatim}\r
+\begin{Verbatim}[fontsize=\scriptsize]\r
+\r
-------------------------------------------------------------------\r
local local_vars = { }\r
for i = 1, max_n do table.insert (local_vars, var(i)) end\r
until true }\r
return result\r
-------------------------------------------------------------------\r
-\end{verbatim}\r
+\end{Verbatim}\r
\r
There is one point to notice in this quote: \verb|body| is used where\r
a statement is expected, although it contains a {\em list} if\r
actually the same syntax as OCaml's, except that we introduced an\r
explicit {\tt end} terminator, to stay homogeneous with Lua.}: \r
\r
-\begin{verbatim}\r
+\begin{Verbatim}[fontsize=\scriptsize]\r
+\r
match <foo> with\r
<pattern> -> block\r
| <pattern> -> block\r
...\r
| <pattern> -> block\r
end\r
-\end{verbatim}\r
+\end{Verbatim}\r
\r
For this, we need to declare new keywords \verb|match|,\r
\verb|with| and \verb|->|. Then, we build the (pattern, block) parser\r
optional ``\verb+|+'' before the first case, so that all cases line up\r
nicely:\r
\r
-\begin{verbatim}\r
+\begin{Verbatim}[fontsize=\scriptsize]\r
+\r
----------------------------------------------------------------------\r
mlp.lexer:add{ "match", "with", "->" }\r
\r
"end",\r
builder = |x| match_parser (x[1], x[3]) }\r
----------------------------------------------------------------------\r
-\end{verbatim}\r
+\end{Verbatim}\r
\r
\noindent Now, if you try this\ldots\ it won't work! Indeed, Metalua\r
needs to know what keywords might terminate a block of statements. In\r
this case, it doesn't know that ``\verb+|+'' can terminate a block. We\r
need therefore to add the following statement:\r
\r
-\begin{verbatim}\r
+\begin{Verbatim}[fontsize=\scriptsize]\r
+\r
mlp.block.terminators:add "|"\r
-\end{verbatim}\r
+\end{Verbatim}\r
\r
\noindent Finally that's it, we have implemented a working pattern\r
matching system in 75 lines of code!\r
It is sometimes desirable to add arbitrary conditions for a pattern to\r
match, conditions which might no be expressed by a pattern. OCaml\r
allows to add them with a ``\verb|when|'' keyword:\r
-\begin{verbatim}\r
+\begin{Verbatim}[fontsize=\scriptsize]\r
+\r
match n with\r
| 0 -> print "zero"\r
| n when n%2 == 0 -> print "even number"\r
| _ -> print "odd number"\r
end\r
-\end{verbatim}\r
+\end{Verbatim}\r
I'd advise you to prefer {\tt if} as a dedicated keyword, rather than\r
{\tt when}: it's unambiguous in this context, and saves a keyword\r
reservation. \r
in the following example, any ADT whose tag is \verb|"RepeatMe"| will\r
be replaced by two occurrences of itself, while others will remain\r
unchanged:\r
-\begin{verbatim}\r
+\begin{Verbatim}[fontsize=\scriptsize]\r
+\r
match something with\r
| `RepeatMe{ ... } as r -> { r, r }\r
| x -> x\r
end\r
-\end{verbatim}\r
+\end{Verbatim}\r
``\verb|as|'' will have to be declared as an infix operator, whose\r
meaning will remain undefined in expressions which are not patterns.\r
\r
i.e. that variables don't appear more than once in the pattern. People\r
might be tempted to write things like this to check whether a tree is\r
symmetric:\r
-\begin{verbatim}\r
+\begin{Verbatim}[fontsize=\scriptsize]\r
+\r
match t with\r
| `Tree{ x, x } -> print "Symmetric!"\r
| `Tree{ x, y } -> print "Not symmetric"\r
| `Leaf{ _ } -> print "Symmetric!"\r
end\r
-\end{verbatim}\r
+\end{Verbatim}\r
However, this would work in Prolog but not with our pattern matching,\r
as two occurences of the same variable in the pattern don't cause an\r
equality test to be added. We should detect such non-linear variables,\r
variables, except for {\tt\_}. The first pattern in the list to match\r
the tested term does the binding. Patterns are separated by\r
``\verb+|+''. Example:\r
-\begin{verbatim}\r
+\begin{Verbatim}[fontsize=\scriptsize]\r
+\r
match x with\r
| 1 | 2 | 3 -> print(x)\r
| n -> print "more than 3"\r
end\r
-\end{verbatim}\r
+\end{Verbatim}\r
(Hint: put the block in a local function. $2^{\mathrm{nd}}$ hint: sort\r
bound variables, e.g. by lexicographic order. Or much simpler and\r
more effective: convert your code generator to gotos+labels first).\r
projects / metalua.git / blobdiff