## matchable

This extension implements Andrew Wright's pattern matching macros.

### Overview

Pattern matching allows complicated control decisions based on data structure to be expressed in a concise manner. Pattern matching is found in several modern languages, notably Standard ML, Haskell and Miranda.

This wiki page is based on Andrew Wright's paper Pattern Matching for Scheme.

### Interface

*[syntax]*

`(match exp (pat body …) …)`

The basic form of pattern matching expression, where `exp` is an expression, `pat` is a pattern, and `body` is one or more expressions (like the body of a lambda-expression). The `match` form matches its first subexpression against a sequence of patterns, and branches to the `body` corresponding to the first pattern successfully matched.

For example, the following code defines the usual `map` function:

(definemap (lambda(f l) (match l [() '()] [(x . y) (cons (f x) (map f y))] )))

The first pattern `()` matches the empty list. The second pattern `(x . y)` matches a pair, binding `x` to the first component of the pair and `y` to the second component of the pair.

*[syntax]*

`(match-lambda (pat body …) …)`

*[syntax]*

`(match-lambda* (pat body …) …)`

The `match-lambda` and `match-lambda*` forms are convenient combinations of `match` and `lambda`, and can be explained as follows:

(match-lambda (pat body …) …) --> (lambda(x) (match x (pat body …) …)) (match-lambda* (pat body …) …) --> (lambdax (match x (pat body) …))

where `x` is a unique variable.

The `match-lambda` form is convenient when defining a single argument function that immediately destructures its argument. The `match-lambda*` form constructs a function that accepts any number of arguments; the patterns of `match-lambda*` should be lists.

For example, the `map` procedure can be written as:

(definemap (match-lambda* [(_ ()) '()] [(f (x . y)) (cons (f x) (map f y))] ))

*[syntax]*

`(match-let [var] ((pat exp) …) body …)`

*[syntax]*

`(match-let* ((pat exp) …) body …)`

*[syntax]*

`(match-letrec ((pat exp) …) body …)`

The `match-let`, `match-let*` and `match-letrec` forms generalize Scheme's `let`, `let*`, `letrec`, and `define` expressions to allow patterns in the binding position rather than just variables. For example, the following expression:

(match-let (((x y z) (list 1 2 3)) ((a b c) (list 4 5 6))) body …)

binds `x` to 1, `y` to 2, `z` to 3, `a` to 4, `b` to 5, and `c` to 6 in `body …`. These forms are convenient for destructuring the result of a function that returns multiple values as a list or vector. As usual for `letrec`, pattern variables bound by `match-letrec` should not be used in computing the bound value.

Analogously to named `let`, `match-let` accepts an optional loop variable `var` before the binding list, turning `match-let` into a general looping construct.

### Pattern Matching Expressions

The complete syntax of the pattern matching expressions follows:

exp ::= (match exp clause …) | (match-lambda clause …) | (match-lambda* clause …) | (match-let ([pat exp] …) body) | (match-let* ([pat exp] …) body) | (match-letrec ([pat exp] …) body) | (match-let var ([pat exp] …) body) clause ::= [pat body] | [pat (=> identifier) body] pat ::= identifier matches anything, and binds identifier as a variable | _ anything | () itself (the empty list) | #t itself | #f itself | string an `equal?' string | number an `equal?' number | character an `equal?' character | 's-expression an `equal?' s-expression | (pat-1 … pat-n) a proper list of n elements | (pat-1 … pat-n . pat-n+1) a list of n or more elements | (pat-1 … pat-n pat-n+1 ...) a proper list of n+k or more elements [1] | #(pat-1 … pat-n) a vector of n elements | #(pat-1 … pat-n pat-n+1 ...) a vector of n+k or more elements | ($ struct pat-1 … pat-n) a structure | (= field pat) a field of a structure | (and pat-1 … pat-n) if all of pat-1 through pat-n match | (or pat-1 … pat-n) if any of pat-1 through pat-n match | (not pat-1 … pat-n) if none of pat-1 through pat-n match | (? predicate pat-1 … pat-n) if predicate true and pat-1 through pat-n all match | (set! identifier) anything, and binds identifier as a setter | (get! identifier) anything, and binds identifier as a getter | (pat-1 *** pat-2) a tree pattern | `qp a quasipattern qp ::= () itself (the empty list) | #t itself | #f itself | string an `equal?' string | number an `equal?' number | character an `equal?' character | symbol an `equal?' symbol | (qp-1 … qp-n) a proper list of n elements | (qp-1 … qp-n . qp-n+1) a list of n or more elements | (qp-1 … qp-n qp-n+1 ...) a proper list of n+k or more elements | #(qp-1 … qp-n) a vector of n elements | #(qp-1 … qp-n qp-n+1 ...) a vector of n+k or more elements | ,pat a pattern | ,@pat a pattern, spliced

#### Optional "=>" failure procedure syntax

The `match`, `match-lambda`, and `match-lambda*` forms allow the optional syntax `(=> identifier)` between the pattern and the body of a clause. When the pattern match for such a clause succeeds, the `identifier` is bound to a *failure procedure* of zero arguments within the `body`. If this procedure is invoked, it jumps back to the pattern matching expression, and resumes the matching process as if the pattern had failed to match. The `body` must not mutate the object being matched, otherwise unpredictable behavior may result.

### Patterns

`identifier`- matches anything, and binds a variable of this name to the matching value in the
`body`. Excludes the reserved names`? , = _ ... and or not set! get!`. `_`- matches anything, without binding any variables.
`()`,`#t`,`#f`,`string`,`number`,`character`, '`s-expression`- These constant patterns match themselves, i.e., the corresponding value must be
`equal?`to the pattern. `(pat-1 … pat-n)`- matches a proper list of
`n`elements that match`pat-1`through`pat-n`. `(pat-1 … pat-n . pat-n+1)`- matches a (possibly improper) list of at least
`n`elements that ends in something matching`pat-n+1`. `(pat-1 … pat-n pat-n+1 ...)`- matches a proper list of
`n`or more elements, where each element of the tail matches`pat-n+1`. Each pattern variable in`pat-n+1`is bound to a list of the matching values. For example, the expression:

(match '(let([x 1][y 2]) z) [('let((binding values) ...) exp) body ...])

binds `binding` to the list `'(x y)`, `values` to the list `'(1 2)`, and `exp` to `'z` in the body of the `match`-expression. For the special case where `pat-n+1` is a pattern variable, the list bound to that variable may share with the matched value.

`(pat-1 … pat-n pat-n+1 ___)`- This pattern means the same thing as the previous pattern.
`#(pat-1 … pat-n)`- matches a vector of length
`n`, whose elements match`pat-1`through`pat-n`. `#(pat-1 … pat-n pat-n+1 ...)`- matches a vector of length
`n`or more, where each element beyond`n`matches`pat-n+1`. `($ struct pat-1 … pat-n)`- matches a structure declared with
`define-record`or`define-record-type`. `(= field pat)`- is intended for selecting a field from a structure.
*field*may be any expression; it is applied to the value being matched, and the result of this application is matched against`pat`. `(and pat-1 … pat-n)`- matches if all of the subpatterns match. At least one subpattern must be present. This pattern is often used as
`(and x pat)`to bind`x`to to the entire value that matches`pat`(cf.*as-patterns*in ML or Haskell). `(or pat-1 … pat-n)`- matches if any of the subpatterns match. At least one subpattern must be present. All subpatterns must bind the same set of pattern variables.
`(not pat-1 … pat-n)`- matches if none of the subpatterns match. At least one subpattern must be present. The subpatterns may not bind any pattern variables.
`(? predicate pat-1 … pat-n)`- In this pattern,
`predicate`must be an expression evaluating to a single argument function. This pattern matches if`predicate`applied to the corresponding value is true, and the subpatterns`pat-1 ... pat-n`all match. The`predicate`should not have side effects, as the code generated by the pattern matcher may invoke predicates repeatedly in any order. The`predicate`expression is bound in the same scope as the match expression, i.e., free variables in`predicate`are not bound by pattern variables. `(set! identifier)`- matches anything, and binds
`identifier`to a procedure of one argument that mutates the corresponding field of the matching value. This pattern must be nested within a pair, vector, box, or structure pattern. For example, the expression:

(definex (list 1 (list 2 3))) (match x [(_ (_ (set! setit))) (setit 4)])

mutates the `cadadr` of `x` to 4, so that `x` is `'(1 (2 4))`.

`(get! identifier)`- matches anything, and binds
`identifier`to a procedure of zero arguments that accesses the corresponding field of the matching value. This pattern is the complement to`set!`. As with`set!`, this pattern must be nested within a pair, vector, box, or structure pattern. ``qp`- Quasiquote introduces a quasipattern, in which identifiers are considered to be symbolic constants. Like Scheme's quasiquote for data,
`unquote`(,) and`unquote-splicing`(,@) escape back to normal patterns.

### Record Structures Pattern

The `$` pattern handles native record structures and SRFI-9 records transparently.

### Tree Pattern

Here we allow patterns of the form

(x *** y)

to represent the pattern y located somewhere in a tree where the path from the current object to y can be seen as a list of the form (X …). Y can immediately match the current object in which case the path is the empty list. In a sense it's a 2-dimensional version of the ... pattern.

As a common case the pattern (_ *** y) can be used to search for Y anywhere in a tree, regardless of the path used.

## Examples

You can find examples in:

- the original paper by Andrew Wright,
- introductory article An Introduction To Lispy Pattern Matching by Moritz Heidkamp.

## About this extension

### Author

### Repository

This egg is hosted on the CHICKEN Subversion repository:

https://anonymous@code.call-cc.org/svn/chicken-eggs/release/5/matchable

If you want to check out the source code repository of this egg and you are not familiar with Subversion, see this page.

### License

Public domain

### History

- 1.2
- Update to upstream (thanks to Pietro Cerutti)
- 1.1
- Fixes record matching for the new type tags introduced in 5.1
- 1.0
- initial release for CHICKEN 5, based on version 2.7 from CHICKEN 4