Last week I released Scheme Power Tools (SPT) – an assorted collection of Scheme utilities. Since then, I have received a few requests to implement pattern matching. Pattern matching is a boilerplate-reducing feature that I greatly missed from Haskell, so given the popular demand I decided to add it to SPT. After a weekend of coding, the latest release supports Haskell-style, native pattern matching out of the box. You can view the documentation here, with the pattern language described here. Special thanks go to Matt Peddie, who originally suggested this feature, and to Gerry Sussman for the 6.945 pattern matcher, which inspired this implementation.

Pattern-Directed Dispatch (pdefine)

SPT implements a macro, pdefine, which allows for multiple function definitions, each with different argument patterns. As a “hello, world” of pattern matching, here’s how one can use pdefine to define the factorial function:

(pdefine (fact 0) 1)
(pdefine (fact ?n) (* n (fact (-1+ n))))

Multiple-argument functions are supported as well. For example, to implement vector addition where a vector is a cons pair of coordinates, you can use a “pair” pattern that binds each component to a name:

(pdefine (vector-add (?x1 . ?x2) (?y1 . ?y2))
         (cons (+ x1 y1) (+ x2 y2)))

Easy enough. The pattern language also supports segment variables (denoted ??[name]), which match sublists of arbitrary length – a feature which sets SPT apart from the mainstream pattern-matching languages like Haskell. Segment variables do a search over the possible sublists until either the entire pattern matches, or all possible sublists have been tried. For example, one might use segment variables to implement a function which checks whether a list contains a number, anywhere in the list:

(pdefine (has-number? (??prefix (? num ,number?) ??suffix)) #t)
(pdefine (has-number? ?obj) #f)

Similarly, segment variables can be used to implement map:

(pdefine (my-map ?func ()) '()) ; base case: empty list
(pdefine (my-map ?func (?first ??rest))
         (cons (func first) (my-map func rest)))

Pattern Let (plet)

In addition to pdefine, Scheme Power Tools also implements plet and plet*, which are like their off-the-shelf counterparts let and let*, but with support for arbitrary patterns in place of variables. For example:

 (define (vector-add x y)
   (plet (((?x1 . ?x2) x)
          ((?y1 . ?y2) y))
         (cons (+ x1 y1) (+ x2 y2))))

Pattern Case (pcase)

Pattern case (pcase) allow the user to execute different code depending on what pattern matches the given datum (see documentation for more details). For example, the snippet below uses pcase to check whether a list contains the specified element:

(define (find elt a-list)
  (pcase a-list
         ((??prefix ,elt ??suffix) elt)
         (? #f)))   ; default case

Wrapping Up

As always, I hope you find Scheme Power Tools useful. I welcome all suggestions and feature requests, and of course let me know of your experiences!

6 responses

Do you want to comment?

Comments RSS and TrackBack Identifier URI ?

Nice work!

February 3, 2011 3:38 am

My Standard Prelude includes a somewhat different implementation of pattern matching.

February 3, 2011 3:06 pm

Thanks Maciek; I can’t wait to try it out!

P.S. Feel free to use my real name :)

February 3, 2011 5:23 pm

I hope you like it! I wanted to use your real name, but my girlfriend said it would be slightly creepy 😉

February 3, 2011 5:28 pm

Is this not just a reinvention of pmatch.scm?

February 5, 2011 10:44 pm

Hi Eric,

It’s more featured – it supports segment variables and pattern-directed function dispatch. I aimed for expressiveness, while the focus of pmatch.scm seems to be efficiency.


February 5, 2011 11:48 pm

Comment now!