Compilation techniques for functional and object-oriented languages


Basic techniques and overviews of whole compilers

S. L. Peyton-Jones, The implementation of functional programming languages, Prentice-Hall, 1987.

A. Appel, Compiling with continuations, Cambridge University Press, 1992.

C. Chambers, J. Dean, and D. Grove, Whole program optimization of object-oriented languages, technical report 96-06-02, University of Washington, 1996.

C. Queinnec, Lisp in small pieces, Cambridge University Press, 1996.

Intermediate languages and translation to C

S. L. Peyton-Jones, T. Nordin, D. Oliva, C--: a portable assembly language, Workshop Implementing Functional Languages, LNCS, 1998. Available at simonpj/c--.html with other C-- documents.

H. J. Boehm and M. Weiser, Garbage collection in an uncooperative environment, Software Practice and Experience 18(9), 1988.

J. Bartlett, Scheme->C, a portable Scheme-to-C compiler, research report 89/1, DEC WRL, 1989.

M. Pettersson, Simulating tailcalls in C, chapter 9 of Compiling Natural Semantics, PhD thesis 413, Linköping University, 1995.

Flow analyses

O. Shivers, Control-flow analysis of higher-order languages, PhD thesis, CMU, 1991; Control-flow analysis in Scheme, Programming Language Design and Implementation, 1988.

N. Heintze, Set-based analysis of ML programs, Lisp and Functional Programming, 1994.

J. Plevyak and A. Chien, Precise concrete type inference for object-oriented languages, OOPSLA, 1994.

J. Dean and D. Grove and C. Chambers, Optimization of object-oriented programs using static class hierarchy analysis, European Conference on Object-Oriented Programming, 1995.

J. M. Ashley, The effectiveness of flow analysis for inlining, International Conference on Functional Programming, 1997.

G. DeFouw, D. Grove and C. Chambers, Fast interprocedural class analysis, Principles of Programming Languages, 1998.

Register allocation and spilling

R. Burger, O. Waddell, R. K. Dybvig, Register allocation using lazy saves, eager restores, and greedy shuffling, Programming Language Design and Implementation, 1995.

P. A. Steenkiste and J. L. Hennessy, A simple interprocedural register allocation algorithm and its effectiveness for Lisp, ACM TOPLAS, 11(1), 1989.

Cache behavior of heap allocation

A. Appel, Z. Shao, An empirical and analytic study of stack vs. heap cost for languages with closures, Journal of Functional Programming 6(1), 1996.

M. Reinhold, Cache performance of garbage-collected programs, Programming Language Design and Implementation, 1994.

Unboxing data representations

S. L. Peyton-Jones, J. Launchbury, Unboxed values as first-class citizens in a non-strict functional language, Functional Programming and Computer Architecture, 1991.

X. Leroy, Unboxed objects and polymorphic typing, Principles of Programming Languages, 1992.

Z. Shao, J. Reppy, A. Appel, Unrolling lists, Lisp and Functional Programming, 1994.

J. Goubault, Generalized boxing, congruences and partial inlining, Static Analysis Symposium, 1994.

Z. Shao and A. Appel, A type-based compiler for Standard ML, Programming Language Design and Implementation, 1995.

D. Tarditi, G. Morrisett, P. Cheng, C. Stone, R. Harper, P. Lee, TIL: a type-directed optimizing compiler for ML, Programming Language Design and Implementation, 1996.

Z. Shao, Flexible representation analysis, International Conference on Functional Programming, 1997.

Instruction scheduling and alias analysis

M. Pouzet, The program compaction revisited: the functional framework, EURO-PAR'95, LNCS 966, 1995.

A. Diwan, K. McKinley, J. Moss, Type-based alias analysis, Programming Language Design and Implementation, 1998.

Web pages for some compilers


Standard ML of New Jersey, Bell Labs,

Objective Caml, INRIA,


Chez Scheme, Cadence Research Systems,

Bigloo, U. Nice,


Glasgow Haskell Compiler (GHC), U. Glasgow,

HBC, U. Chalmers,

``Pure OO'' languages

Cecil/Vortex, U. Washington,

Self, Sun Microsystems,


Harissa, IRISA,

TurboJ, The Open Group,