Deriving Practical Implementations of First-class Functions

Date and time: 
Fri, Feb 19 2021 - 9:00am to 10:30am
Zachary Sullivan
University of Oregon
  • Zena Ariola (Chair)
  • Boyana Norris
  • Michal Young

I explore 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.