Generating a pattern matching compiler by partial evaluation

Partial evaluation can be used for automatic generation of compilers and was first implemented in [10]. Since partial evaluation was extended to higher order functional languages [9] [2] it has become possible to write denotational semantics definitions of languages and implement these with very few changes in the language treated by partial evaluators. In this paper we use this technique to generate a compiler for a small strict combinator language with pattern matching. First, a simple denotational specification for the language is written and a compiler is generated. This first compiler turns out not to generate too efficient code. By changing the denotational specification, new compilers that generate more efficient code are obtained. This process can be described as generating optimizing compilers by changing specifications. The optimization concerns generation of object code for pattern matching and the final compiler does in fact generate very efficient code for this. Specifically, it treats non-uniform function definitions in a satisfactory way. The optimization performed can be viewed as being equivalent to the well-known compiler optimization called common subexpression elimination