Pattern Matching

Given a pattern and an input, matching must:

  1. Test whether the input matches the pattern. A common convention is to let pattern variables begin with ? to distinguish variables from constant parts of the pattern.

  2. Return variable bindings: how the input matches the pattern.

Consider the following case:

Pattern:      (- ?x (- ?y))

Input: (- (sin theta) (- w))

The input matches the pattern; the bindings should be:

 ( (?x . (sin theta))
   (?y . w) )
This format is an association list, or alist for short. The form ( x . y) , called a dotted pair, is produced by (cons x y) . (A dotted pair is just an ordinary pair. It may be printed with a dot because the cdr points to something other than another pair. Note that (?x . (sin theta)) will be printed as (?x sin theta).)

Contents    Page-10    Prev    Next    Page+10    Index