Incorporating static analysis in a combinator-based compiler (Q1823653)

The denotational definition of a programming language typically specifies the runtime behaviour of the language constructs. Therefore, such a definition may be easily translated into an interpreter. This implementation may be inefficient, but it is guaranteed to be correct with respect to the formal definition. An example of such a method is the so-called ``combinator-based'' compiling method: source programs are translated into trees of combinators. Three techniques are studied how restructuring a denotational definition can lead to a more efficient interpreter: (1) Static replacement converts run-time type checking operations into static ones. (2) Factoring rearranges the semantic clauses so that static type checking is performed prior to dynamic interpretation. (3) Finally, a continuation semantics is written in combinator terms, and associative properties may be used to rotate the trees. The technique is illustrated by applying it to a simple expression language EL. In a special section, the authors discuss an imperative language with loops. The paper shows that a program improvement technique used by realistic compilers can be rigorously described in a denotational framework.