Page:Scheme - An interpreter for extended lambda calculus.djvu/23

From Wikisource
Jump to: navigation, search
This page has been proofread, but needs to be validated.
Sussman and Steele December 22, 1975 22 Some Implementation Issues

evaluates to

(BETA (LAMBDA <vars> <body>) E)
in environment
E

When a closure is to be applied to some arguments:

((BETA (LAMBDA <vars> <body>) E1) <args>)
in environment
E2

this is performed by reducing the application expression to

<body>
in environment
Pairlis[<vars> <args in E2> E1]

That is, any free variables in the closed lambda expression refer to the environment as of the time of closure (E1), not as of the time of application (E2), whereas the arguments are evaluated in the application environment as expected.

This notion of closure has gone by many other names in other contexts. In LISP, for example, such a closure has been traditionally known as a funarg. ALGOL has several related ideas. Every ALGOL procedure is, at the time of its invocation, essentially a "downward funarg". In addition, expressions which are passed by name instead of by value are closed through the use of mechanisms called thunks [Ingerman]. It turns out that an actor (other than a cell or a serializer) is also a closure. Hewitt [Smith and Hewitt] describes an actor as consisting of a script, which is code to be executed, and a set of acquaintances, which are other actors which it knows about. We contend that the script is in fact identical to the lambda expression in a closure, and that the set of acquaintances is in effect an environment. As an example, consider the following code for cons; taken from [Smith and Hewitt] (cf. [Fischer]):

[CONS ≡
    (≡> [=A =B]
        (CASES
           (≡> FIRST?
               A)
           (≡> REST?
               B)
           (≡> LIST?
               YES)))]

When the form (cons x y) is evaluated, the result is an (evaluated) cases statement, which is a receiver ready to accept a message such as "first?" or "rest?". This resulting receiver evidently knows about the actors x and y as being bound to the variables a and b; it is evidently a closure of the cases script plus a set of acquaintances which includes x and y (as well as "first?" and "rest?" and "yes", for example; PLASMA considers such "constant acquaintances" to be part of the set, whereas in SCHEME we might prefer to consider them part of the script). Once we realize that it is a closure and nothing more, we can see easily how to express the same semantics in SCHEME: