Using Transformations in the Implementation of Higher-order Functions

Many different techniques are needed in an optimising compiler-constant folding, program transformation, semantic analysis and optimisation, code generation and so on. The authors propose a uniform framework for all these activities. Every computation in the program to be compiled is classified as either compile-time or run-time and the run-time parts are translated into an easily manipulable form-categorical combinators. The authors set up a framework for defining operations on these intermediate forms, and show how it can be used to define concisely two forwards analyses (strictness, constant propagation), a backwards analysis (liveness), and even code generation. Both compile- and run-time parts can also be transformed. Every technique presented is illustrated using a simple running example, and the emphasis throughout is on intuition rather than absolute formality