Home     Overview     Materials     Assignments     Problem Set Submission     Software
CS212 Handouts
The Environment Model

An environment is an association of names with values. To understand how Scheme resolves variable names, we must understand how environments are created and used.

Definitions

Binding

A binding is an association of a single name (a variable) with a value. We denote such a binding by name:value.

Frame

A frame is an unordered set of bindings, no two of which bind the same name. For example, a frame might consist of the bindings x:10, y:15, z:(4 5 6).

Environment

An environment consists of an ordered sequence of one or more frames. The frames are arranged in a linear order starting from the "youngest'' frame, the one associated with the procedure currently running, back to the "oldest'' frame. Different frames can bind different sets of names, and two frames in an environment may have different bindings for the same name.

The environment consisting of the oldest frame alone is called the global environment. It contains the bindings of the Scheme language primitives such as + and lambda. It is always there from the time of system startup and never disappears.

The Lookup Rule

When searching an environment for a given name, Scheme starts at the youngest frame and continues searching older and older frames until a binding with that name is found. If there is no binding in any frame for that name, a special value is returned indicating that the name is not bound to anything in the environment. This procedure is called lookup.

Evaluation Rules

When an expression is evaluated, it is always evaluated in the context of some environment. The appropriate evaluation rule is determined by the type of expression that is being evaluated.

Identifiers (Variables)

The value of an identifier with respect to a given environment is the value given by the first frame containing a binding for that variable in the lookup order as described above. The value is undefined if there is no frame containing a binding for that name. This rule is often referred to as the lookup rule. In other words, look in the youngest frame of the environment for a binding of the given name. If there is no binding in this frame, go on to the next frame and look there. Continue in this fashion until a binding for the name is found, or until the frames are exhausted. Return the value that is found.

Global Definitions

Evaluating a define expression always adds a binding to the oldest (global) frame, bypassing all other frames in the environment. Thus all bindings done with define are global definitions. If there are bindings for the name in younger frames, they are ignored. The new binding associates the given name with the value that results from evaluating the given expression in the whole environment. No useful value is returned. Recall that this does not apply to an internal define, since internal defines are just another way of representing letrec.

Assignments

Evaluating (set! var expr) in a given environment uses the lookup rule to find the first binding of the variable var, then changes that binding to a new value. The new value is the result of evaluating expr in the given environment. Thus the environment structure is changed by changing the value of the first binding found for the given name. No useful value is returned.

Lambdas

The result of evaluating a lambda expression with respect to a given environment is to create a new procedure object consisting of

     

  1. The formal parameters of the lambda.

     

  2. The body of the lambda.

     

  3. A pointer to the environment in which the lambda expression was evaluated.
This is called a closure.

Conceptually, a procedure object is just the text of the lambda expression together with a pointer to the environment where the lambda expression was evaluated. That is, the procedure object stores the parameters and the code (which were both part of the lambda expression) along with the environment where the lambda expression was evaluated (which was not part of the lambda expression). Note that evaluating a lambda expression just creates a procedure object; it does not evaluate the body of the lambda at that point! That happens only later, when the procedure gets applied. This is essentially the same as the evaluation of lambda expressions in the substitution model, only here there is additionally an environment pointer.

The reason the environment pointer is included in closures is that we need a means of resolving identifiers that occur in the body of the method that are not parameters. We would like the values of these identifiers to be the ones in effect when the method was created, not when it is called.

Let

Evaluating a let expression
(let ((name1 exp1)
      (name2 exp2)
      ...
      (namek expk)) body)

in an environment creates a single frame that binds each expi. This single frame is created after evaluating each expi, and the frame holds all the bindings namei:expi. The body is then evaluated in the context of this new environment that starts at this single frame. Evaluating a let statement is essentially the same as applying a procedure (see below).

On the other hand, evaluating a let* expression

(let* ((name1 exp1)
       (name2 exp2)
       ...
       (namek expk)) body)
in an environment creates a sequence of new frames with the specified bindings. Each successive expi is evaluated in the environment containing the new frames created by the first i-1 bindings. A new frame is then created with the single binding namei:expi and appended to the front of the environment. Finally the body is evaluated in the environment with the k new frames.

This is not quite equivalent to creating a procedure object with one parameter for each name (see the Application Rule below), since here the bindings are done sequentially and k different frames are created, whereas in the case of procedures, only one new frame is created with all the bindings.

Lastly, evaluating a letrec expression

(letrec ((name1 exp1)
         (name2 exp2)
         ...
         (namek expk)) body)

in an environment creates a new frame and temporarily binds each namei to a null value. Each expi is then evaluated in this environment. After all expis are evaluated, the null values are replaced such that there exists a binding for each namei:expi. It is important that each expi be a lambda statement, since looking up another namej while evaluating expi before it is bound would cause unpredictable results.

Compound Expressions

To evaluate a compound expression in some environment, first evaluate all the subexpressions in that environment, and then apply the value of the first to the remaining values. The value of the first had better be a function, or an error results.

Application Rule

To apply a compound procedure to a list of values, i.e. to call a procedure with a specified set of values for the parameters:
  1. Create a new frame containing a binding for each formal parameter of the procedure bound to the corresponding argument value. Add this new frame to the front of the environment in the closure of the procedure being applied. This is the environment in which the procedure object was created, as discussed above under the evaluation of method expressions; it is not the environment in which the application takes place!

    Note that the only operations that create frames are the application of a procedure and let and its variants.

     

  2. Evaluate the body of the procedure with respect to the new environment created in step 1.

Application of primitive procedures is done directly by Scheme. When reasoning using the environment model, we handle application of primitive procedures the same way as we did in the substitution model: just substitute the value.




Valid HTML 4.0!CS212 Home Page
© 1999 Cornell University Computer Science
Last Modified: 3/23/99 by Brandon Bray