STklos Reference Manual : (version 2.10)

6. Pattern Matching

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 code (and documentation) included in STklos has been stolen from the Bigloo package v4.5 (the only difference between both package is the pattern matching of structures which is absent in STklos.

The technique used is described in details in C. Queinnec and J-M. Geffroy paper [QuG92], and the code generated can be considered optimal

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 eq?)
Recursive patterns on lists: for example, checking that the datum is a list of zero or more as followed by zero or more `bs.
Pattern matching on lists as well as on vectors.

6.1. The Pattern Language

The syntax for <pattern> is:

[:small]

<pattern>	Matches:
<atom>	the <atom>.
(kwote <atom>)	any expression eq? to <atom>.
(and <pat₁> … <pat_n>)	if all of <pati> match.
(or <pat₁> … …<pat_n>)	if any of <pat₁> through <pat_n> matches.
(not <pat>)	if <pat> doesn’t match.
(? <predicate>)	if <predicate> is true.
(<pat₁> … <pat_n>)	a list of n elements. Here, … is a meta-character denoting a finite repetition of patterns.
<pat> …	a (possibly empty) repetition of <pat> in a list.
#(<pat> … <pat_n>)	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.

Matches:

<atom>

the <atom>.

(kwote <atom>)

any expression eq? to <atom>.

(and <pat₁> … <pat_n>)

if all of <pati> match.

(or <pat₁> … …<pat_n>)

if any of <pat₁> through <pat_n> matches.

(not <pat>)

if <pat> doesn’t match.

(? <predicate>)

if <predicate> is true.

(<pat₁> … <pat_n>)

a list of n elements. Here, … is a meta-character denoting a finite repetition of patterns.

<pat> …

a (possibly empty) repetition of <pat> in a list.

#(<pat> … <pat_n>)

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.

Remark: and, or, not and 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.
?a matches any expression, and binds the variable a to this expression.
(? 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. For instance, (a ???-) is equivalent to (a . ?-).
when occurring in a list, ??- matches any sequence of anything: (a ??- b) matches any list whose car is a and last car is b.
(a …) matches any list of `a’s, possibly empty.
(?x ?x) matches any list of length 2 whose car is eq to its cadr.
((and (not a) ?x) ?x) matches any list of length 2 whose car is not eq to 'a but is eq to its cadr.
#(?- ?- ???-) matches any vector whose length is at least 2.

??- and … patterns can not appear inside a vector, where you should use ???-
For example, #(a ??- b) or #(a…) are invalid patterns, whereas #(a ???-) is valid and matches any vector whose first element is the atom a.

6.2. STklos Pattern Matching Facilities

Only two special forms are provided for this in STklos: match-case and match-lambda.

STklos syntax

(match-case <key> <clause> …)

The argument key may be any expression and each clause has the form

(<pattern> <expression> ...)

A match-case expression is evaluated as follows: <key> is evaluated and the result is compared with each successive pattern. If the <pattern> 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 <key>, then, if there is an else clause, its expressions are evaluated and the result of the last is the result of the whole match-case expression; otherwise the result of the match-case expression is unspecified.

The equality predicate used for tests is eq?.

(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)

STklos syntax

(match-lambda <clause> …)

match-lambda expands into a lambda-expression expecting an argument which, once applied to an expression, behaves exactly like a match-case expression.

((match-lambda
  ((?x ?x) 'foo)
  ((?x ?- ?x) 'bar))
 '(a b a))           => bar

1. Documentation about hygienic macros has been stolen in the SLIB manual

1. In fact define-module on a given name defines a new module only the first time it is invoked on this name. By this way, interactively reloading a module does not define a new entity, and the other modules which use it are not altered.

2. This transcript uses the default toplevel loop which displays the name of the current module in the evaluator prompt.

1. Under Unix, you can simply connect to a listening socket with the telnet of netcat command. For the given example, this can be achieved with netcat localhost 12345

2. Port 13, if open, can be used for testing: making a connection to it permits to know the distant system’s idea of the time of day.

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 [Bigloo]