1. Environment Data Structure¶

In a pure \(\lambda\)-calculus interpreter:

When evaluating a function call, the (values of the) arguments are actually substituted for the formal parameters (depending on the reduction strategy: normal order or applicative order) in the body of the function.

In our applied \(\lambda\)-calculus interpreter:

We guarantee that substitution remains a valid way to reason about function behavior, but we move away from the substitution model for the implementation of the interpreter and adopt an environment-based model of evaluation, in which values are bound to identifiers (variable names).

Conceptually, an environment is a (possibly empty) set of variable-value pairs. We’ll represent this set itself and each pair in it as an array. For example:

E = [ ]    // the empty environment

E = [ ["y",4], ["x",5], ["f",<sqr_fn>] ]
           // the environment in which y is bound to 4
           //                          x is bound to 5
           //                          f is bound to the squaring function

In reality, there is more than one environment, since there is more than one scope. For example, the variable “x” may be bound to the value 5 in one scope but it may be bound to the squaring function in another scope.

In JavaScript, each function defines its own scope. Since function definitions can be nested inside other functions, scopes (and thus environments) may be nested as well. We will represent this hierarchical structure of the environment using nested arrays. For example, for the following JavaScript code segment:

function f(x,y) {
  return function (x) {
      return function (y,z) {
         // compute with x,y,z (**)
       };
    };
}
var id = function (x) { return x; };
f(1,2)("hi")(true, id);

the nested arrays for the environment would be:

[ "Env",                  // our usual tag

  [ ["y",true],           // the set of bindings in the innermost scope,
    ["z",id]],            // i.e., the top of the stack of environments

  [ "Env",                // the sets of bindings in all of the outer scopes,
                          // i.e.,the rest of the stack of environments
    [["x","hi"]],         //          .
                          //          .
    [ "Env",              //          .
      [["x",1],["y",2]],  //          .
      ["EmptyEnv"]]]]     //          .

An environment contains the bindings of variables to values. An Integer is one kind of value. But what kind of value is a function abstraction?

It is a function definition with a list of formal parameters, a body, and a closure that wraps up an anonymous function definition together with the current environment, that is, the one existing at the time the function is defined.

In programming languages, a denoted value is any kind of value that can be bound to a variable name. So, an environment is just a mapping from identifiers (e.g., “x” and “g”) to denoted values.

The types of denoted values vary from programming language to programming language. In SLang 1, the only types of denoted value are numbers and closures.

As usual, we will represent these denoted values with arrays whose first element is the tag “Num” or “Clo”, respectively.

This means that, if we had been faithful to our representation of environments in E1 above, we would have shown a binding of 5 to “x” as:

[ “x”, [ “Num”, 5 ] ]

instead of

[ “x”, 5 ]

2. Determining Values Bound to a Variable¶

The following problem provides practice determining which value a SLang 1 variable is bound to. To earn credit for it, you must complete this randomized problem correctly three times in a row.

3. Evaluation of Expression Within an Environment¶

The following problem provides practice fully evaluating SLang 1 expressions. To earn credit for it, you must complete this randomized problem correctly three times in a row.

4. Determining Denoted Values in SLang 1¶

The following problem gives you practice with denoted values in the SLang 1 interpreter. To earn credit for it, you must complete this randomized problem correctly three times in a row.