Pattern Matching for Program Generation: A User Manual

The Anticipatory Optimization Generation (AOG) system is built to generate custom programs using large-scale, programmatic transformations (versus pure pattern-based transformations) that operate on Abstract Syntax Trees (ASTs). Because of the scale of the AOG transformations and the often-complex program reorganizations that they enable, the transformations must operate on the low-level physical formats of the ASTs and simultaneously accommodate high degrees of variation in the ASTs. However, both the physical details of and variations within an AST are irrelevant to the AOG system in the same sense that both the physical details of and variations within a database format are irrelevant to a database management system. In both cases, only the logical structure is relevant. Database management systems introduce logical schemas to hide the details and variations in the format of their databases. Similarly, the AOG pattern matcher introduces a pattern notation that performs the analogous service for ASTs. It hides the details of and variations within an AST from the large-scale transformations that must operate on the AST and thereby reduces the complexity of the transformation code. The pattern notation is embedded in the Lisp language and provides a set of Prolog-like operators for performing complex matching and inference logic. The operators include analogs to the Prolog operators and, or, not, mark, cut, bind, is, succeed, fail, prove, and rule definition (i.e., This user manual describes the pattern notation and the operation of the pattern matching system that evaluates that notation. It also includes a number of extended examples drawn from the AOG system that illustrate the use of the pattern notation in the context of transformation-based program generation.