| 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!x.
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>)
where calling <continuation1> as a function of no arguments would produce the result
(((E (R)) (C Z) (B (X Y Q Q X Y))) <continuation2>)
where calling <continuation2> would produce NIL.
The MATCH function makes use of two auxiliary functions called NFIRST and 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)))))
The main 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, called MATCH*, handles the matching of segments of the expression against THV* match variables. It is in the matching of segments that the
