Pattern Matching for Program Generation: A User Manual
Ted J. Biggerstaff · 1998
The Anticipatory Optimization Generation (AOG) system is built to generate custom programs using largescale, 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., <-). They also include a number of more specialize operators such as operators that span sections of an AST, bind the remainder of a list, perform top-down and bottom-up tree searches, rename local variables, use dynamically computed variable values as patterns, invoke and use rule sets, navigate object struct...