Both humans and automatic programming systems construct new programs by reuse of knowledge, much of it in the form of patterns:
Another important capability is transformation of programs, e.g.
for optimization. A transformation can often be modeled
as a pair of patterns: an input pattern, containing variables, that is
matched against the given code, and an output pattern that represents
the form of the code after transformation:
(- (- ?x ?y)) &rarr (- ?y ?x)
We will represent variables as symbols that begin with ?.
Transformation patterns are also called rewrite rules.