A COMPARISON OF APPROACHES TO COMPILING FUNCTIONAL PROGRAMMING LANGUAGES

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.This research was supported by the Undergraduate Research Opportunities Program (UROP). This work has been partially supported by an REU supplement to the National Science Foundation grant CCF-0917140. Opinions, findings and conclusions or recommendations that are manifest in this material are those of the participants and do not necessarily reflect the views of the NSF