• Subject: Pattern matching tutorial in Metalua [was: Metalua: Lua + full macros]
• From: Fabien <fleutot+lua@...>
• Date: Thu, 16 Nov 2006 14:45:05 +0100

On 11/14/06, Peter Kümmel <syntheticpp@gmx.net> wrote:
Metalua looks very interesting!
[...]
I hope you will add more examples because
the examples in your docs are really trivial

As promised, here is another, less trivial tutorial about extending metalua. In this one, we add structural pattern matching to the language.

The tutorial: http://luaforge.net/docman/view.php/227/166/tutorial.match.pdf
Associated sources: http://luaforge.net/docman/view.php/227/167/tutorial.match.src.tgz

Structural pattern matching is a sort of switch statement, put under a triple dose of steroids, taken from ML dialects. Unlike regular switch, which simply discriminate on a scalar value, SPM uses patterns to describe the general shape of a piece of data, and executes the first block of code whose associated pattern matches the tested term.

What the extension does is compiling the patterns into a series of nested tests, so that they can be compiled for the regular lua 5.1 VM.

In case you kept fond memories of your CS lectures on lambda calculus, here is a lambda calculus evaluator, used to implement SK combinators, written with the pattern matching extension described in the tutorial:

------------------------------------------------------------
-{ dofile "match.luac" } -- load syntax extension

-- A WHNF beta reduction function for lambda calculus, straight back from good ole CS lectures:
function beta_reduce (t)
match t with
| `Application{ func, arg } ->
match beta_reduce (func) with
| `Lambda{ param, body }  ->
return beta_reduce(replace (arg, param, body))
| anything_else           -> return anything_else
end
| anything_else -> return anything_else
end
end

-- Variable substitution in lambda terms:
function replace(arg, param, body)
match body with
| `Application{ a_func, a_arg } -> return `Application{
replace(arg, param, a_func),
replace(arg, param, a_arg) }
| `Variable{ x } -> if x == param then return arg else return body end
| `Lambda{ l_param, l_body } ->
if l_param == param then return body
else return `Lambda{ l_param, replace (arg, param, l_body) } end
| anything_else -> return anything_else
end
end

-- Definition of SK combinators:
-- (http://en.wikipedia.org/wiki/SKI_combinator_calculus)

S = `Lambda{ "x", `Lambda{ "y", `Lambda{ "z",
`Application{ `Application{ `Variable "x", `Variable "z" },
`Application{ `Variable "y", `Variable "z" } } } } }

K = `Lambda{ "x", `Lambda{ "y", `Variable "x" } }

-- Check whether I is still equal to SKK.

I = `Application{ `Application{ S, K }, K }

ifoobar = beta_reduce(`Application{I, `Variable "FOOBAR"})
assert(ifoobar.tag == "Variable" and ifoobar[1] == "FOOBAR")
------------------------------------------------------------

If you're not a big fan of lambda-calculus, you can still check the tutorial about runtime type-checking (http://luaforge.net/docman/view.php/227/164/tutorial.typecheck.pdf ) I plan to present another couple of pragmatic extensions as tutorials, at least exceptions and classes.