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

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

Section 4: Some Implementation Issues[edit]

The key problem is efficiency. Although it is easy to build an inefficient interpreter which straightforwardly performs expression substitutions; such an interpreter performs much unnecessary copying of intermediate expressions. The standard solution to this problem is to use an auxiliary structure, called the environment, which represents a set of virtual substitutions. Thus, when evaluating an expression of the form

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

instead of reducing it by performing

Subst[<args> <vars> <body>]

we reduce it to

<body>
in environment
E'=Pairlis[<vars> <args>* E]

where pairlis creates a new environment E' in which the <vars> are logically paired with (i.e. "bound to") the corresponding <args>* (the precise meaning of <args>* will be explained presently), and in which any variables not in <vars> are bound as they were in E.

When using environments, it is necessary to keep them straight. For example, the following expression should manage to evaluate to 7:

(((LAMBDA (X) (LAMBDA (Y) (+ X Y))) 3) 4)

A substitution interpreter would cause the free occurrence of x in the inner lambda expression to be replaced by 3 before applying that lambda expression to 4. An interpreter which uses environments must arrange for the expression (+ x y) to be evaluated in an environment such that x is bound to 3 and y is bound to 4. This implies that when the inner lambda expression is applied to 4, there must be associated with it an environment in which x is bound to 3. In order to solve this problem we introduce the notion of a closure [McCarthy] [Moses] which is a data structure containing a lambda expression, and an environment to be used when that lambda expression is applied to arguments. We will notate a closure using the beta construct (our own notation, but isomorphic to the LISP funarg construct) as follows:

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

When a lambda expression is to be evaluated, because it was passed as an argument, it evaluates to a closure of that lambda expression in the environment it is evaluated in (i.e., the environment it was passed from):

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