The Pattern Language

This document describes the pattern language supported by Scheme Power Tools. The language was inspired by the pattern matcher in 6.945.


Scheme Power Tools implements a simple and powerful pattern language, enabling straightforward Haskell-style pattern matching. It does so through the plet, plet*, pdefine and pcase macros. For general information on how to use these macros, you can refer to the documentation. This document describes the pattern language used by the above macros.

In a Nutshell

On the most basic level, the pattern language supports literals, variables (simple and segment), and list/pair combinators. All patterns are implicitly quasiquoted, so the pattern n matches the symbol n, while ,n matches whatever n evaluates to in the current environment.


A literal pattern only matches datums equal? to a given Scheme object. For example, the pattern 1 only matches the number 1.

Simple Variables

Simple variables match any datum that (optionally) satisfies the given predicate. A simple variable is declared by preceding its name with a question mark ?, e.g. ?my-var. To specify the optional predicate, use the (? [name] [predicate]) syntax, remembering that patterns are implicitly quasiquoted. For example, if you want to have a variable x which only matches even numbers, you would write (? x ,even?).

If the given variable is already bound to a value, as might be the case if you have multiple variables with the same name in a pattern, a datum matches if and only if it's equal? to the value already bound.

If you want a variable that matches anything and don't want to bind it to a name, simply write ?.

Segment Variables

Segment variables can occur only within lists, and match sublists of arbitrary length. Intuitively, a segment variable will attempt to match any valid sublist until either the entire pattern matches or all sublists have been unsuccessfully tried.

To declare a segment variable, use the ?? prefix, e.g. ??prefix. Similarly to simple variables, you can also specify a predicate (?? [name] [predicate]). For example, to match only non-empty sublists, you could write (?? non-empty (compose not null?)).

To match a segment but not bind it to a name, write ??.

List Patterns

List patterns are used to combine multiple patterns into a pattern that matches elements of a list. For example, the pattern (1 2 ?x) will only match lists of length 3, with the first two elements 1, 2 and an arbitrary 3rd element which will be bound to the symbol x.

List patterns can contain segment variables. For example, (??prefix 1 ??suffix) will match any list containing 1.

Pair Patterns

Pair patterns are composed of car and cdr patterns, and match a datum if and only if those two patterns match. A pair pattern is declared using the (car-pattern . cdr-pattern) syntax. For example, (?x . ?y) will match any pair and bind car and cdr to the symbols x and y, respectively.

It is theoretically possible to combine pair patterns to match lists, instead of using list patterns directly. While this may indeed be preferable in some cases, keep in mind that segment variables cannot be used as car or cdr patterns within pair patterns.

The Pattern Grammar

Formally, a pattern is defined as follows:
      pattern           -> literal | simple-variable | list-pattern | pair-pattern
      literal           -> any Scheme atom
      simple-variable   -> ? | ?[name] | (? [name] ,[predicate])
      list-pattern      -> () | (lpattern) | (lpattern ... lpattern)
      lpattern          -> pattern | segment-variable
      segment-variable  -> ?? | ??[name] | (?? [name] ,[predicate])
      pair-pattern      -> (pattern . pattern)

Scheme Power Tools Documentation
(c) Maciej Pacula 2010-2011