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; Bigloo's ``pattern
matching compiler'' provides this. The technique used is described in
details in [QueinnecGeffroy92], and the code generated can be considered
optimal
1 due to the way this ``pattern
compiler'' was obtained.
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 and structures,
record types, and classes.
7.1 Bigloo pattern matching facilities
|
Only two special forms are provided for this in Bigloo:
match-case
and
match-lambda.
| match-case key clause... | bigloo syntax |
The argument key may be any expression and each clause has the form
(pattern s-expression...)
|
Semantics: 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 expressions in that clause are evaluated from left to right in an
environment where the pattern variables are bound to the corresponding
subparts of the datum, 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 datum, 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 is eq?.
(match-case '(a b a)
((?x ?x) 'foo)
((?x ?- ?x) 'bar))
=> bar
|
|
The following syntax is also available:
| match-lambda clause... | bigloo syntax |
It 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
|
|
The syntax for <pattern> is:
<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
of patterns.
| <pat> ... a (possibly empty) repetition
of <pat> in a list.
| #(<pat> ... <patn>) a vector of n elements.
| #{<struct> <pat> ... } a structure.
| (isa <class> (<id> <pat>) ...) a class instance.
| ?<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, check 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.
?- 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.
#{foo (?- . ?-) (? integer?)} matches any structure or
record foo whose first and second fields are respectively a pair and an
integer. You can provide only the fields you want to test. The order is not
relevant.
Remark: ??- 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.
The
isa pattern matches instances of Bigloo classes. The syntax is:
(isa <class-name> (<field-name> <pattern>) ...)
|
Each
(<field-name> <pattern>) pair matches the named field against
the given pattern. Fields not mentioned are ignored, allowing partial
matching. If no fields are specified, only the type is checked.
The type check uses
isa?, so a pattern
(isa point ...) will
match instances of
point and any subclass of
point.
(define-class point (x (default 0)) (y (default 0)))
(define-class point3d::point (z (default 0)))
;; Basic field binding
(match-case (instantiate::point (x 3) (y 4))
((isa point (x ?x) (y ?y)) (list x y)))
=> (3 4)
;; Partial matching (only check some fields)
(match-case (instantiate::point3d (x 1) (y 2) (z 3))
((isa point3d (z ?z)) z))
=> 3
;; Type-only check (no fields)
(match-case (instantiate::point (x 1) (y 2))
((isa point) 'yes)
(else 'no))
=> yes
;; Literal values in fields
(match-case (instantiate::point (x 0) (y 5))
((isa point (x 0) (y ?y)) y)
(else 'fail))
=> 5
;; Subclass matching via inheritance
(match-case (instantiate::point3d (x 1) (y 2) (z 3))
((isa point (x ?x) (y ?y)) (list x y)))
=> (1 2)
|
Class patterns compose freely with other pattern combinators:
;; or: match multiple class types
(match-case obj
((or (isa point3d (z ?v)) (isa point (x ?v))) v))
;; and: bind the whole object and destructure
(match-case obj
((and ?whole (isa point (x ?x) (y ?y)))
(list whole x y)))
;; not: match non-instances
(match-case obj
((not (isa point)) 'not-a-point)
(else 'is-a-point))
;; Predicates inside fields
(match-case obj
((isa point (x (and ?x (? positive?)))) x))
;; Nested class patterns
(define-class segment
(start (default #unspecified))
(end (default #unspecified)))
(match-case seg
((isa segment (start (isa point (x ?x1) (y ?y1)))
(end (isa point (x ?x2) (y ?y2))))
(list x1 y1 x2 y2)))
;; Repeated variables (equality constraint across fields)
(define-class rect (width (default 0)) (height (default 0)))
(match-case (instantiate::rect (width 5) (height 5))
((isa rect (width ?s) (height ?s)) s)
(else 'not-square))
=> 5
|