We derive a simple abstract machine for lazy evaluation of the lambda calculus, starting from Launchbury's natural semantics. Lazy evaluation here means non-strict evaluation with sharing of argument evaluation, that is, call-by-need. The machine we derive is a lazy version of Krivine's abstract machine, which was originally designed for call-by-name evaluation. We extend it with datatype constructors and base values, so the nal machine implements all dynamic aspects of a lazy functional language.
Later, REF developed an abstract machine for the λ-calculus with lazy evaluation starting from Launchbury's natural semantics, where lazy evaluation means non-strict evaluation with sharing of argument evaluation, i.e., call-by-need.
Deriving a Lazy Abstract Machine
Journal of Functional Programming
Computer Science