Control Flow
In order to make the use of the UNIFICATION library easier, a few utility macros are provided. The macros MATCH, MATCHING, and MATCH-CASE can be used to unify two (or more) objects and then to build a lexical environment where the variables present in the to objects (or templates) are bound to the values resulting from the application of UNIFY.
- MATCH is a "single shot" macro. It does one unification and executes forms in an appropriate lexical environment.
- MATCH-CASE is equivalent to CASE. It tries to match a single object (or template) against a set of clauses. The forms associated to the first clause for which there is a successful unification, are then executed within an appropriate lexical environment.
- MATCHING is equivalent to COND. Each clause contains a head consisting of two objects to be unified. The first clause whose head unifies sucessfully has its associated forms executed within an appropriate lexical environment.
There are also the macro MATCHF and MATCHF-CASE, which do not evaluate the pattern; they can be used to produce more streamlined code.
Examples
These macros allow the construction of interesting pattern matching like code.
(defun factorial (x)
(match-case (x)
(0 1)
(#T(number ?n) (* ?n (factorial (1- ?n))))
(otherwise (error "Incorrect match for ~S." x))))
Or consider the more interesting piece of code from a not-so hypothetical Red-Black tree implementation (cfr. [O98].) The function BALANCE is the key part of the rebalancing act played by Red-Black trees.
(defstruct (tree-node (:conc-name tn-)
(:constructor mk-tn (color left elem right)))
color
left
elem
right)
(defun balance (&rest balancing-arguments)
(match-case (balancing-arguments)
((:black #T(tree-node tn-color :red
tn-left #T(tree-node tn-color :red
tn-left ?a
tn-elem ?x
tn-right ?b)
tn-elem ?y
tn-right ?c)
?z
?d)
(mk-tn :red (mk-tn :black ?a ?x ?b) ?y (mk-tn :black ?c ?z ?d)))
((:black #T(tree-node tn-color :red
tn-left ?a
tn-elem ?x
tn-right #T(tree-node tn-color :red
tn-left ?b
tn-elem ?y
tn-right ?c))
?z
?d)
(mk-tn :red (mk-tn :black ?a ?x ?b) ?y (mk-tn :black ?c ?z ?d)))
((:black ?a
?x
#T(tree-node tn-color :red
tn-left #T(tree-node tn-color :red
tn-left ?b
tn-elem ?y
tn-right ?c)
tn-elem ?z
tn-right ?d))
(mk-tn :red (mk-tn :black ?a ?x ?b) ?y (mk-tn :black ?c ?z ?d)))
((:black ?a
?x
#T(tree-node tn-color :red
tn-left ?b
tn-elem ?y
tn-left #T(tree-node tn-color :red
tn-left ?c
tn-elem ?z
tn-right ?d)))
(mk-tn :red (mk-tn :black ?a ?x ?b) ?y (mk-tn :black ?c ?z ?d)))
((?color ?left ?elem ?right)
(mk-tn ?color ?left ?elem ?right))))
This version of BALANCE is more verbose than the one given in [O98], but it preserves the general elegance of the ML implementation.
Control Flow Dictionary
Notes
Other Forms
It would be obvious to add the macros EMATCH-CASE and CMATCH-CASE, for symmetry with ECASE and CCASE. Also, MATCHING could be renamed to MATCH-COND.
Current Implementation Details
The current implementations of MATCHING and MATCH-CASE do not handle user supplied environments yet.
References
[O98] C. Okasaki, Purely Functional Data Structures, Cambridge University Press, 1998.