Pattern Matching

How do you write functions that deal with a variant datatype? Irken has a builtin vcase special form (similar to a Scheme case), that covers the branches of a datatype constructor. Here's how the length function looks using vcase:

(define (length l)
  (let loop ((l l)
	     (n 0))
    (vcase list l
       ((:nil) n)
       ((:cons _ tl)
	(loop tl (+ n 1))))))

And here's a version using pattern matching:

(define length
    ()       -> 0
    (_ . tl) -> (+ 1 (length tl)))

(length '(1 2 3 4 5))

Wow, that looks a lot cleaner! (There's actually something a little unfair about the comparison that I will explain later). The vcase special form isn't really needed or used in Irken; however pattern matching expressions are translated automatically by the compiler into vcase expressions.

Notice a few things about this definition of length. First, there is no argument list; the name of the function follows define unadorned. That's because names for the formal arguments are superfluous - the patterns destructure the cases, (optionally) binding variables to the objects inside each branch.

Secondly, you see some of the builtin language support for the list datatype. Normally, the patterns would have to be written like this:

(define length1
  (list:nil)       -> 0
  (list:cons _ tl) -> (+ 1 (length1 tl)))

The empty list () corresponds to (list:nil), and (_ . tl) corresponds to (list:cons _ tl). (If you're from the ML/Haskell world, (hd . tl) is the same thing as [hd::tl]).

A third thing to note are the wildcard variables, denoted with underscores (_). These are "don't cares", and internally the compiler doesn't even bother to look at them or bind them.

Let's look at another example of pattern matching on something other than lists.

(include "lib/core.scm")

(datatype tree
  (:empty)
  (:node 'a (tree 'a) (tree 'a))
  )

(define indent
  0 -> #f
  n -> (begin (print-string "  ") (indent (- n 1)))
  )

(define tree/print
  d (tree:empty)               -> #f
  d (tree:node val left right) -> (begin
				    (indent d)
				    (tree/print (+ d 1) left)
				    (print val)
				    (print-string "\n")
				    (tree/print (+ d 1) right)))

(let ((t (tree:node
	  5
	  (tree:node 7 (tree:empty) (tree:node 12 (tree:empty) (tree:empty)))
	  (tree:node 9 (tree:empty) (tree:empty))
	  )))
  (tree/print 0 t)
  )

The datatype tree defines a simple binary tree. A tree is either empty, or a node containing an object of type 'a (i.e., this datatype is polymorphic), and two more trees of that same type - the left and right branches of that node.

The tree/print function uses a helper for indenting its output. We've defined it succinctly using pattern matching. The indent function takes a single integer argument - the amount of indentation to print. The base case of zero simply returns a boolean, which becomes the return type of the whole function. The second case binds the argument to the variable n, which is then used to print two spaces before recursively calling indent.

The tree/print function itself takes two arguments - a depth argument d and the tree to print. It prints the left side of the tree first (indented by one step), the value of that node, then finally the right tree.

Complex Patterns

Patterns can be nested, and consist of multiple datatypes. This sample function is used to balance red-black trees, and is based on Okasaki's "Purely Functional Data Structures":

(define lbalance
  (tree:red (tree:red A B k0 v0) C k1 v1) D k2 v2 -> (tree:red (tree:black A B k0 v0) (tree:black C D k2 v2) k1 v1)
  (tree:red A (tree:red B C k1 v1) k0 v0) D k2 v2 -> (tree:red (tree:black A B k0 v0) (tree:black C D k2 v2) k1 v1)
                                          A B k v -> (tree:black A B k v))

This function is from a parser for Python:

(define p-for-stmt
  ;; for_stmt: 'for' exprlist 'in' testlist ':' suite ['else' ':' suite]
  (_ (item:nt _ _ vars) _ (item:nt _ _ src) _ (item:nt _ _ body) (item:nt _ _ else))
    -> {t='for p=(params:none) subs=(LIST (p-testlist vars) (p-testlist src) (p-suite body) (p-else else)) range=NR}
  x -> (perror "p-for-stmt" x)
  )

Patterns can match against records:

(define thing
  {a=x b=2} -> x
  {a=3 b=y} -> y
  {a=m b=n} -> (+ m n)
  )

and literals:

(define xmas?
  1 _         'partridge -> #t
  2 "laying"  'geese     -> #t
  3 "french"  'hens      -> #t
  4 "collie"  'birds     -> #t
  4 "calling" 'birds     -> #t
  5 "golden"  'rings     -> #t
  ...
  _ _ _ -> #f
  )

Patterns are checked in order, so place a more specific pattern before a more general one.

The match special form

Sometimes you want to pattern match somewhere other than the arguments to a defined function. The match special form facilitates this:

(match <exp0> <exp1> ... with
  <pat0> <pat1> ... -> <result0>
  <pat0> <pat1> ... -> <result1>
  )

  (match (+ 1 x) y with
     12 z -> (+ z 9)
     15 9 -> 0
     x  y -> (+ x y)
     )

---

Next: Macros