Semantics-Directed Compilation of Non-Linear Patterns

This paper describes the automatic derivation of compiled patterns and of a pattern compiler by partial evaluation. Compiling a pattern is achieved by specializing a pattern matching program with respect to the pattern. Generating a pattern compiler is achieved by specializing the specializer with respect to the pattern matching program, i.e., by self-applying the partial evaluator. The compiled patterns and the compiler are semantics-based because they are obtained using meaning-preserving transformations upon the definitional pattern matching program and the partial evaluator. The results are unexpectedly good: not only all are the operations depending on the pattern (syntax analysis, resolution of cross-references due to the non-linearity) performed at compile time, but whereas the general pattern matcher builds the substitution environment incrementally and for nothing in case of failure, compiled patterns perform all the structural and equality tests first, and build the result on..