Jeremy W. Sherman

stay a while, and listen


Compiling Imperative and Functional Languages [PDF]

Thesis for B.A. Math / Computer Science granted by New College of Florida in 2008. Sponsored by Dr. Karsten Henckell.

Computers operate at a very low level of abstraction. People think in terms of higher-level abstractions. Programming languages let people describe a computation using higher-level abstractions in such a way that the description can be translated into something a computer can execute. This translation is performed algorithmically by a program called a compiler.

This thesis looks at how a compiler carries out this translation for two very different types of programming languages, the imperative and the functional. Imperative languages reflect the concept of computation that is built into modern von Neumann computers, while functional languages conceive of computation as a process of symbolic rewriting. The functional model of computation is utterly different from the von Neumann model, but programs written in functional languages must ultimately run on von Neumann machines.

The thesis focuses throughout on optimizing program representation for execution on modern von Neumann computers. A case study of the Glasgow Haskell compiler provides a concrete example of functional language compilation.