Maciej Pacula

Introducing Scheme Pattern Matching

Introduction

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!