Realistic Compilation By Program Transformation

Program-Transformation.Org: The Program Transformation Wiki
by RichardKelsey? and PaulHudak?

Conference Record of the Sixteenth Annual ACM Symposium on Principles of Programming Languages (POPL'89). 281--292, 1989,


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.

CategoryReview, CategoryTransformation | -- EelcoVisser - 04 Jun 2001