Chapter First Class Pattern Matching

Strategies for Program Transformation
[ Previous | Up | Next ]


So far we have assumed the basic actions applied by strategies are rewrite rules. However, taking a closer look at rules, we see that they are actually composed from several ingredients, i.e., matching the pattern in the left-hand side, verifying the side conditions, and instantiating the pattern on the right-hand side. In addition, a rule implicitly delimits the scope of the variables that it uses. If we take rules apart and make their components available as first-class strategy actions, many interesting idioms can be expressed directly.

This chapter introduces the strategy actions match (?p), build (p), and scope ({x1,...,xn:s}), and shows how unconditional and conditional rewrite rules can be expressed in terms of these actions. Many other language constructs that involve matching can also be expressed in terms of these operations.



  • Rule for explicit pattern matching is missing
  • Rule for term project should use where