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

Jump to navigation Jump to 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

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 ) ) ``` in environment ```E ```

instead of reducing it by performing

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

we reduce it to

 ``` ``` in environment ```E'=Pairlis[ * 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 ) ``` in environment ```E ``` 