The pattern matcher in the files `patmatch.lsp` and
`patm.lsp` transforms an input expression repeatedly
using patterns until a fixed-point is reached (i.e., no further
transforms can be applied).

Transformation is accomplished by calling the function `trans`:

(trans input 'kind)where

Patterns are defined by calling `(redefpatterns kind transforms)`:

(redefpatterns 'opt '( ((+ 0 ?x) ?x) ... ))

Each transform is a list of an input pattern and an output pattern, with
optional extra elements.
Variables are denoted by symbols that begin with a question mark, e.g.
`?x` .

Dot notation may be used to match the remainder of a list, e.g. the transform:

((progn nil . ?s) (progn . ?s))will get rid of a

Partial evaluation is performed on many subexpressions whose operands are constant. For example, the transform:

((+ ?n (+ ?m ?x)) (+ (+ ?n ?m) ?x))where

In some cases, it is necessary to make some tests before deciding whether to apply a transformation. The optional third element of a pattern is a test predicate; the pattern is only applied if the test is satisfied:

((+ ?n (+ ?m ?x)) (+ (+ ?n ?m) ?x)) (and (numberp ?n) (numberp ?m)) )

Some transformations require computations to be done on input variables. This is done by defining new variables (not used in the input pattern) as computed values derived from input variables. These computations are specified in a list as the fourth element of a transform:

( (?newvar value) ...)where

For example, to combine nested progn's containing arbitrary numbers of statements, the following pattern could be used:

((progn (progn . ?u) . ?v) (progn . ?w) t ((?w (append ?u ?v))))In this case, the new variable

A second example shows the use of substitutions in a computation:

((intersection (subset (function (lambda (?x) ?p)) ?s) (subset (function (lambda (?y) ?q)) ?s)) (subset (function (lambda (?x) (and ?p ?qq))) ?s) t ((?qq (subst ?x ?y ?q)))) ; where ?qq is ?q with ?x substituted for ?y

Sometimes there is a need to introduce new variables in a pattern.
This can be done by using `(gentemp)` to generate
a new symbol and bind it to a new variable.

It is legitimate to introduce new "function names" that serve only
to trigger patterns and that eventually are removed from the output
by being transformed into something else. The "function" `fn-args`
is used in this way in the `lisptoc` patterns.

There are several conventions used in the `lisptoc` patterns:

- Some patterns begin with an empty string,
`""`. This prevents the output of these patterns from matching any other pattern. - The form
`#\Return`causes the printing program`cpr`to insert a newline and then to tab over to the current tab stop. - The form
`#\Tab`causes the tab stop to be increased by 2 columns; this will be in effect for subsequent occurrences of`#\Return`within the list in which the`#\Tab`appears.

patmatch.lsp Simple matcher, as in lecture slides patm.lsp More powerful matcher features pats.lsp Starter set of patterns patex.lsp Examples for use in optimization exercise