A Lazy to Strict Language Compiler

Abstract

The evaluation strategies of programming languages can be broadly categorised as strict or lazy. A common approach to strict evaluation is to implement a call-by-value semantics that always evaluates expressions when they are bound to variables, while lazy evaluation is often implemented as call-by-need semantics that evaluates expressions when they are needed for some computation. Lazy semantics makes use of a data structure called thunk that contains an expression, whose evaluation has become suspended, together with its environment. This thesis presents (1) a Haskell de nition of the existing semantics of CakeML, a strict programming language, (2) a Haskell de nition of a lazy semantics for the pure part of CakeML, and (3) a Haskell implementation of a compiler that compiles lazy CakeML to strict CakeML as de ned in (1) and (2). The compiler makes use of stateful features in strict CakeML to optimise evaluation so that each thunk is evaluated at most once, simulating a call-by-need semantics.