Deriving Practical Implementations from First-Class Functions
Zachary J. Sullivan
Committee: Zena M. Ariola (chair)
Area Exam(Feb 2021)
Keywords: compilers, interpreters, lambda-calculus

This document explores the ways in which a practical implementation is derived from Church's calculus of lambda-conversion, i.e. the core of functional programming languages today like Haskell, Ocaml, Racket, and even Javascript. Despite the implementations being based on the calculus, the languages and their semantics that are used in compilers today vary greatly from their original inspiration. I show how incremental changes to Church's semantics yield the intermediate theories of explicit substitutions, operational semantics, abstract machines, and compilation through intermediate languages, e.g. CPS, on the way to what is seen in modern functional language implementations. Throughout, a particular focus is given to the effect of evaluation strategy which separates Haskell and its implementation from the other languages listed above.