|Sussman and Steele||December 22, 1975||10||SCHEME Programming Examples|
- constant atoms, which match themselves only.
(THV x), which matches any single element in the expression consistently. We may abbreviate this as
?xby means of a LISP reader macro character.
(THV* x), which matches any segment of zero or more elements in the expression consistently. We may abbreviate this as
The matcher returns either
NIL, meaning no match is possible, or a list of two items, an alist specifying the bindings of the match variables, and a continuation to call, if you don't like this particular set of bindings, which will attempt to find another match. Thus, for example, the invocation
(MATCH '(A !B ?C ?C !B !E) '(A X Y Q Q X Y Z Z X Y Q Q X Y R))
would return the result
(((E (Z Z X Y Q Q X Y R)) (C Q) (B X Y)) <continuation1>)
<continuation1> as a function of no arguments would produce the result
(((E (R)) (C Z) (B (X Y Q Q X Y))) <continuation2>)
<continuation2> would produce
MATCH function makes use of two auxiliary functions called
NREST. The former returns a list of the first n elements of a given list, while the latter returns the tail of the given list after the first n elements.
(DEFINE NFIRST (LAMBDA (E N) (IF (= N 0) NIL (CONS (CAR E) (NFIRST (CDR E) (- N 1)))))) (DEFINE NREST (LAMBDA (E N) (IF (= N 0) E (NREST (CDR E) (- N 1)))))
MATCH function also uses a subfunction called
MATCH1 which takes four arguments: the tail of the pattern yet to be matched; the tail of the expression yet to be matched; the alist of match bindings made so far; and a continuation to call if the match fails at this point. A subfunction of
MATCH*, handles the matching of segments of the expression against
THV* match variables. It is in the matching of segments that the