An efficient interpreter for the lambda-calculus

摘要

A call-by-need reduction algorithm for the LAMBDA-calculus is presented. Call-by-need is as efficient as call-by-value and is equivalent to call-by-name in languages without side effects. The algorithm, which is the core of a running system, is presented by illustrating successive transformations of a straightforward implementation of the classical definition of reduction in the LAMBDA-calculus. All notions and algorithms are introduced as LISP code.