Lambda the Ultimate

I may be wrong, but I think pattern matching predates ML. I generally associate the technique with logic languages and unification. Languages like Oz and Erlang, both descendents of Prolog, have pattern matching without static typing.

As an example, I've been tinkering with EOPL. And since there's a call for more code on Ltu, here's a snippet of Alice ML code for section 1.3:

datatype expression = Id of symbol
                    | Lambda of symbol * expression
                    | Apply of expression * expression

fun occurs_free (var, Id sym)             = (var = sym)
  | occurs_free (var, Lambda(id, body))   = (id <> var) andalso occurs_free(var, body)
  | occurs_free (var, Apply(rator, rand)) = occurs_free(var, rator) orelse occurs_free(var, rand)

val f = Apply(Lambda("x", Id "x"), Id "y")
val a = occurs_free("x", f)
val b = occurs_free("y", f)

And here's a similar snippet for Oz:

fun {OccursFree Var Exp}
   case Exp
   of [id Sym]           then (Var == Sym)
   [] [lambda Id Body]   then {Not (Id == Var)} andthen {OccursFree Var Body}
   [] [apply Rator Rand] then {OccursFree Var Rator} orelse {OccursFree Var Rand}
   end
end

F = [apply [lambda x [id x]] [id y]]
A = {OccursFree x F}
B = {OccursFree y F}

The EOPL authors also introduce a define-datatype syntax for Scheme in chapter 2 that accomplishes much the same.

There appears to be some ambiguity about pattern matching here. Mathematicians for centuries have used case analysis to define functions:

signum(x) =  
        -1      (x<0)
         0      (x=0)
         1      (x>0)

which is semantiaclly equivalent to a lisp COND or a chain of nested IFs.

Structure-matching showed up in many early AI languages but finds, as Chris points out, its apotheosis in unification and
Prolog.

Full-fledged string pattern-matching, equivalent to parsing, showed up in Comit and SNOBOL but I don't know of any (until Cduce) that used it for either pattern-based invocation or argument destructuring.

One could go further: consider "pattern unification" in which you equate two grammar-like patterns, a la Snobol, complete with logical variables for some of the terminals, and the result is another such pattern, also perhaps with variables, which expresses the language which is the intersection of the two.

Josh

version 0.3 of metalua just shipped, with new doc, new site, new samples. http://metalua.luaforge.net