Pattern Matching Implementation

The pattern matching facility in FAUST operates on block-diagram expressions in FAUST Block-Diagram Normal Form (BDNF), which is the low-level FAUST expression format appearing in compile-time errors and drawn in scalable vector graphics (.svg) files generated by the faust -svg option.

BDNF expressions can be viewed as trees. The leaves of these trees are numbers and primitive block diagrams such as +, _, !, abs, sin, etc. The nodes of the trees are the five operations of the Block-Diagram Algebra (BDA) (, $\vert$ : $\vert$ <: $\vert$ :> $\vert$ ~).

A pattern is a FAUST expression optionally containing free variables. A FAUST expression is a pattern when it appears as a function argument on the left-hand side of a function definition:

  f(pattern) = expression;

Such function definitions specify rewriting rules such that when f(pattern) is recognized elsewhere, it is replaced by expression with any free variables in the pattern replaced by what they matched in the expression. If there are no free variables in the pattern, then the pattern will only match block diagrams whose BDNF is identical.

For example, the pattern (a) consists of only the free variable a, which will match any expression. The pattern (2*a) = (2,a:*) can be represented as a tree consisting of a `:' node at the top, a `,' node as its left child, and the `*' operator leaf as its right child. The `,' node in turn has the left-leaf `2' and right-leaf `a' (a free variable).