Pattern matching is a key feature of most modern functional programming
languages since it allows clean and secure code to be
written. Internally, "pattern-matching forms" should be translated
(compiled) into cascades of "elementary tests" where code is made as
efficient as possible, avoiding redundant tests; STklos
"pattern matching compiler" provides this 1.
The technique used is described in details in
, and the code generated can be
The "pattern language" allows the expression of a wide variety
of patterns, including:
- Non-linear patterns: pattern variables can appear more than
once, allowing comparison of subparts of the datum (through ???)
- Recursive patterns on lists: for example, checking that the
datum is a list of zero or more
as followed by zero or more
- Pattern matching on lists as well as on vectors.
6.1 STklos Pattern Matching Facilities
Only two special forms are provided for this in STklos:
(match-case <key> <clause> ...)
The argument key may be any expression and each clause has the form
A match-case expression is evaluated as follows:
(<pattern> <expression> ...)
<key> is evaluated
and the result is compared with each successive pattern. If the
in some clause yields a match, then the
<expression>s in that clause are
evaluated from left to right in an environment where the pattern variables
are bound to the corresponding subparts of
<key>, and the result of the
last expression in that clause is returned as the result of the
match-case expression. If no pattern in any clause matches the
then, if there is an
else clause, its expressions are evaluated and
the result of the last is the result of the whole
expression; otherwise the result of the
The equality predicate used for tests is
(match-case '(a b a)
((?x ?x) 'foo)
((?x ?- ?x) 'bar)) ⇒ bar
(match-case '(a (b c) d)
((?x ?y) (list 'length=2 y x))
((?x ?y ?z) (list 'length=3 z y x)))
⇒ (length=3 d (b c) a)
(match-lambda <clause> ...)
match-lambda expands into a lambda-expression expecting an argument
which, once applied to an expression, behaves exactly like a
((?x ?x) 'foo)
((?x ?- ?x) 'bar))
'(a b a)) ⇒ bar
The syntax for
<pattern> ==> Matches:
<atom> the <atom>.
| (kwote <atom>) any expression eq? to <atom>.
| (and <pat1> ... <patn>) if all of <pati> match.
| (or <pat1> ... ...<patn>) if any of <pat1> through <patn> matches.
| (not <pat>) if <pat> doesn't match.
| (? <predicate>) if <predicate> is true.
| (<pat1> ... <patn>) a list of n elements. Here, ... is a
meta-character denoting a finite repetition
| <pat> ... a (possibly empty) repetition
of <pat> in a list.
| #(<pat> ... <patn>) a vector of n elements.
| ?<id> anything, and binds id as a variable.
| ?- anything.
| ??- any (possibly empty) repetition of anything
in a list.
| ???- any end of list.
kwote must be quoted in order to be treated as
literals. This is the only justification for having the
kwote pattern since, by convention, any atom which is
not a keyword is quoted.
Explanations Through Examples
?- matches any s-expr.
a matches the atom
?a matches any expression, and binds the variable
(? integer?) matches any integer.
(a (a b)) matches the only list
'(a (a b)).
???- can only appear at the end of a list, and always succeeds.
(a ???-) is equivalent to
(a . ?-).
- when occurring in a list,
??- matches any
sequence of anything:
(a ??- b) matches any list whose
a and last
(a ...) matches any list of
a's, possibly empty.
(?x ?x) matches any list of length 2 whose
eq to its
((and (not a) ?x) ?x) matches any list of length
car is not eq to
'a but is
eq to its
#(?- ?- ???-) matches any vector whose length is at least 2.
... patterns can
not appear inside a vector, where you should use
#(a ??- b) or
#(a...) are invalid
#(a ???-) is valid and matches any
vector whose first element is the atom
1: The "pattern matching compiler" has been written by Jean-Marie Geffroy
and is part of the Manuel Serrano's Bigloo compiler 
since several years. The code (and documentation) included in STklos
has been stolen from the Bigloo package v2.4 (the only difference
between both package is the pattern matching of structures which is
absent in STklos).