From Wikisource
Jump to navigation Jump to search
This page has been validated.
Steele and Sussman March 10, 1976 30 LAMBDA: The Ultimate Imperative


The lambda calculus was originally developed by Alonzo Church as a formal axiomatic system of logic. [Church 41] Happily, it may be re-interpreted in several interesting ways as a model for computation.

The term "call-by-need" is due to Wadsworth. [Wadsworth 71] This technique is similar to the "delay rule" of Vuillemin. [Vuillemin 74]

Reynolds uses the term "continuation" in [Reynolds 72]. Church clearly understood the use of continuations; it is the only way to get anything accomplished at all in pure lambda calculus! For example, examine his definition of ordered pairs and triads on page 30 of [Church 41]. In SCHEME notation, this is:

[M, N] means
(LAMBDA (A) (A M N))
21 means
22 means

where 21 e.g. selects the first element of a pair. (Note that these functions are isomorphic to CONS, CAR, and CDR!)

Most modern LISP systems, such as MacLISP [Moon 74] and InterLISP [Teitelman 74], scope variables dynamically. They often provide a special feature (the FUNARG device) for lexical scoping, but in most implementations this feature is not completely general.

This example is from [Friedman 75]. Landin uses a similar technique to describe streams in [Landin 65]. Henderson and Morris [Henderson 76] present several examples in this vein, including an elegant solution to the samefringe problem of Hewitt [Hewitt 74] [Smith 75].

CPL is described in [Barron 63] and [Buxton 66]. BCPL is a simplified version of CPL intended for systems programming. [Richards 69] [Richards 74] Also related to CPL is the language C, in which UNIX is written.

If the variable to be set is VAR or VAL, then this does not work because of the so-called environment problem. However, a compiler can choose the variables VAR and VAL to be different from all other variable names.