Pattern matching

[Jeff]

Here is a quick way to use letex and unify to create a simple pattern matching syntax like those used in ocaml, erlang, haskell, et al.  We use unify to match the pattern, so variables assigned in the pattern must be capitalized.  These will be expanded in the body expression, so use capitals there as well.

Code Select Expand

(define-macro (letify)
  (let ((pattern (eval (args 0))) (expr (args 1)))
       (eval (expand (list letex pattern expr) 'pattern 'expr))))

(define-macro (when)
  (letn ((var (args 0))
         (pattern (args 1 0))
         (expr (args 1 1))
         (unification (unify pattern (eval var)))
         (next (2 (args))))
        (cond
          (unification (eval (expand '(letify 'unification expr) 'unification 'expr)))
          ((null? next) (throw-error (string "Match failed against " x)))
          (true (eval (cons 'when (cons var next)))))))

(define (foo x)
  (when x
    ((A B C) (map println '(A B C)))
    ((A B C D) (map println '(A B C D)))
    ((A B C D E F) (map println '(A B C D E)))))

(foo '('THE 'QUICK 'BROWN 'FOX))
(foo '(1 2 3 4 5))

The function foo is now defined in terms of the pattern of the argument, x.  The two test expressions at the bottom evaluate:

Code Select Expand

THE
QUICK
BROWN
FOX

user error : Match failed against (1 2 3 4 5)
called from user defined function foo

When the match fails, it throws an error.  This could be easily modified to evaluate to nil, but then you could not distinguish between a failed match and a successful match whose body evaluates to nil.

[cormullion]

for the less multilingual of us, Jeff, could you expand a bit on

simple pattern matching syntax like those used in ocaml, erlang, haskell, et al

not sure what the 'context' is here as I only heard of these languages, not seen them...

[Jeff]

In most functional languages, functions are not single definitions.  A function is defined in terms of the arguments.  So, if you wanted a function that could add up to three numbers, you would define:

Code Select Expand

function add () = 0
function add (a) = a
function add (a, b) = a + b
function add (a, b, c) = a + b + c

These would be the function add() with four different arities (arity is the number of arguments it accepts.  When add is then called against a series of arguments, the arguments are matched against the pattern of arguments named in the series of definitions of add().  In most, there is an infix cons operator (lisp uses prefix operators, so you have (+ 3 4) instead of (3 + 4), which uses infix) that can be used to break apart a list so that you can define something like add recursively:

Code Select Expand

function add() = 0
function add(n) = n
function add(first|rest) = first + add(rest)

...assuming that | is the cons operator here, as it is in many functional languages (well, the ones I know at least).



The pattern matching generally uses unify to create variable associations, so that add([1,2,3]) in the first set of definitions would map to (a=1,b=2,c=3).



newLISP has unify and letex, but they don't work so well together without an intermediate step, even though letex *should* accept an argument like ((A 1) (B 2) (C 3)) -- actually, it does accept that if typed directly into the function, but it seems to work like a macro- if you do not send the evaluated list value then it will throw an error.



At any rate, my when definition uses unify to pattern match the arguments passed and then execute different blocks of code based on which pattern matches, substituting the values of those matched variables (the results of unify) for their occurrences in the expr passed as the second argument (so using ((A 1) (B 2) (C 3)) for (map println '(A B C)) expands to (map println '(1 2 3)).



Ok, I'm done.  Class, don't forget to read chapters five and six in your books and prepare for the quiz on Friday.

[cormullion]

Class, don't forget to read chapters five and six in your books and prepare for the quiz on Friday.

:-) Thanks. Can I have an extension till Monday - this is quite hard stuff for me...