Using Pattern Matching in Rewriting Rules

As mentioned above, rewriting rules are specified in FAUST source by function definitions of the form

  f(pattern) = expression;

where f is any valid function name, and both pattern and expression are arbitrary expressions in the FAUST language. The FAUST compiler stores all rewriting rules in the lexical order they were specified (since lexical order determines pattern-matching precedence). When an instance of f(arg) is encountered in the FAUST source, the argument arg is compared, in Block Diagram Normal Form, to the first defined pattern for f, also in BDNF. The nodes of the BDNF are compared and traversed in the standard order (top-down, left-to-right), and the match is successful when (1) all nodes and non-variable leaves match literally, and (2) the free variables in the pattern (if any) ``greedily'' match subtrees in arg. After an unsuccessful match, additional patterns for f are tried, until a match is found. After a successful match, any free variables in pattern are bound to their matching subtrees in arg, and expression is evaluated and inserted in place of f(arg). We will illustrate an example below using Lisp tree syntax.