Realistic Compilation By Program Transformation

Conference Record of the Sixteenth Annual ACM Symposium on Principles of Programming Languages (POPL'89). 281--292, 1989, http://citeseer.nj.nec.com/kelsey89realistic.html

The paper describes the process of compiling high-level programs to machine language programs by means of a chain of simple program transformations. A high-level program is first translated into an intermediate language, the call-by-value lambda calculus with an implicit store. An intermediate language program is then simplified during several stages. The end result is an intermediate language program that can be interpreted as a machine language program.

The stages of compilation are

• Making the program linear: each subexpression is given an explicit name

• Adding explicit continuations: functions are transformed to ContinuationPassingStyle^?

• Simplifying the program: local transformations such as BetaReduction^? and global transformations such as ConstantPropagation^?

• Adding explicit environments: free variables are turned into bound variables that are passed around explicitly

• Identifier renaming / RegisterAllocation^?: the set of variables used to name expressions are reduced to match the set of machine registers.