# Page:Scheme - An interpreter for extended lambda calculus.djvu/11

 Sussman and Steele December 22, 1975 10 SCHEME Programming Examples

1. constant atoms, which match themselves only.
2. `(THV x)`, which matches any single element in the expression consistently. We may abbreviate this as `?x` by means of a LISP reader macro character.
3. `(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