A COMPARISON OF APPROACHES TO COMPILING FUNCTIONAL PROGRAMMING LANGUAGES

Abstract

The extensive dependence of modern-day society on large software systems places a premium on tools for producing programs that are guaranteed to perform in the way expected of them. Functional programming languages take on a special importance in this setting. Such languages provide a high level of abstraction that makes it easier to construct complex programs and to simultaneously ensure that they possess certain mathematical properties related to their correctness. However, the practical use of such languages depends also on the ability to transform programs written in them into low-level instructions that can be run efficiently on existing computers. For this project, I have investigated two classical and influential models of compilation for functional languages. The first is based on a virtual machine called the Categorical Abstract Machine, and the second uses a programming technique called continuation-passing style to transform programs into a form that is easy to run on regular hardware. I have implemented these approaches for a small but representative fragment of functional programming languages. I am now using these implementations to understand the essential differences between the two approaches and how these differences impact efficiency. To my knowledge, such a comparison has not been made before and thus constitutes an original contribution.