4.1.3 Evaluator Data Structures - SICP Comparison Edition

Permalink copied!

In addition to defining the representation of components, the evaluator implementation must also define the data structures that the evaluator manipulates internally, as part of the execution of a program, such as the representation of functions and environments and the representation of true and false.

Testing of predicates

In order to limit the predicate expressions of conditionals to proper predicates (expressions that evaluate to a boolean value) as we do throughout this book, we insist here that the function is_truthy gets applied only to boolean values, and we accept only the boolean value true to be truthy. The opposite of is_truthy is called is_falsy.[1]

function is_truthy(x) {
    return is_boolean(x) 
           ? x
           : error(x, "boolean expected, received");
}
function is_falsy(x) { return ! is_truthy(x); }

Representing functions

To handle primitives, we assume that we have available the following functions:

apply_primitive_function($fun$, $args$) applies the given primitive function to the argument values in the list $args$ and returns the result of the application.
is_primitive_function($fun$) tests whether $fun$ is a primitive function.

These mechanisms for handling primitives are further described in section 4.1.4.

Compound functions are constructed from parameters, function bodies, and environments using the constructor make_function:

function make_function(parameters, body, env) {
    return list("compound_function", parameters, body, env);
}
function is_compound_function(f) {
    return is_tagged_list(f, "compound_function");
}
function function_parameters(f) { return list_ref(f, 1); }

function function_body(f) { return list_ref(f, 2); }

function function_environment(f) { return list_ref(f, 3); }

Representing return values

We saw in section 4.1.1 that the evaluation of a sequence terminates when a return statement is encountered, and that the evaluation of a function application needs to return the value undefined if the evaluation of the function body does not encounter a return statement. In order to recognize that a value resulted from a return statement, we introduce return values as evaluator data structures.

function make_return_value(content) {
    return list("return_value", content);
}
function is_return_value(value) {
    return is_tagged_list(value, "return_value");
}
function return_value_content(value) {
    return head(tail(value));
}

Operations on Environments

The evaluator needs operations for manipulating environments. As explained in section 3.2, an environment is a sequence of frames, where each frame is a table of bindings that associate symbols with their corresponding values. We use the following operations for manipulating environments:

lookup_symbol_value($symbol$, $env$) returns the value that is bound to $symbol$ in the environment $env$, or signals an error if $symbol$ is unbound.
extend_environment($symbols$, $values$, $base$-$env$) returns a new environment, consisting of a new frame in which the symbols in the list $symbols$ are bound to the corresponding elements in the list $values$, where the enclosing environment is the environment $base$-$env$.
assign_symbol_value($symbol$, $value$, $env$) finds the innermost frame of $env$ in which $symbol$ is bound, and changes that frame so that $symbol$ is now bound to $value$, or signals an error if $symbol$ is unbound.

To implement these operations we represent an environment as a list of frames. The enclosing environment of an environment is the tail of the list. The empty environment is simply the empty list.

function enclosing_environment(env) { return tail(env); }

function first_frame(env) { return head(env); }

const the_empty_environment = null;

Each frame of an environment is represented as a pair of lists: a list of the names bound in that frame and a list of the associated values.[2]

function make_frame(symbols, values) { return pair(symbols, values); }

function frame_symbols(frame) { return head(frame); }

function frame_values(frame) { return tail(frame); }

To extend an environment by a new frame that associates symbols with values, we make a frame consisting of the list of symbols and the list of values, and we adjoin this to the environment. We signal an error if the number of symbols does not match the number of values.

function extend_environment(symbols, vals, base_env) {
    return length(symbols) === length(vals)
           ? pair(make_frame(symbols, vals), base_env)
           : error(pair(symbols, vals), 
                   length(symbols) < length(vals)
                   ? "too many arguments supplied"
                   : "too few arguments supplied");
}

This is used by apply in section 4.1.1 to bind the parameters of a function to its arguments.

To look up a symbol in an environment, we scan the list of symbols in the first frame. If we find the desired symbol, we return the corresponding element in the list of values. If we do not find the symbol in the current frame, we search the enclosing environment, and so on. If we reach the empty environment, we signal an "unbound name" error.

function lookup_symbol_value(symbol, env) {
    function env_loop(env) {
        function scan(symbols, vals) {
            return is_null(symbols)
                   ? env_loop(enclosing_environment(env))
                   : symbol === head(symbols)
                   ? head(vals)
                   : scan(tail(symbols), tail(vals));
        }
        if (env === the_empty_environment) {
            error(symbol, "unbound name");
        } else {
            const frame = first_frame(env);
            return scan(frame_symbols(frame), frame_values(frame));
        }
    }
    return env_loop(env);
}

To assign a new value to a symbol in a specified environment, we scan for the symbol, just as in lookup_symbol_value, and change the corresponding value when we find it.

function assign_symbol_value(symbol, val, env) {
    function env_loop(env) {
        function scan(symbols, vals) {
            return is_null(symbols)
                   ? env_loop(enclosing_environment(env))
                   : symbol === head(symbols)
                   ? set_head(vals, val)
                   : scan(tail(symbols), tail(vals));
        } 
        if (env === the_empty_environment) {
            error(symbol, "unbound name -- assignment");
        } else {
            const frame = first_frame(env);
            return scan(frame_symbols(frame), frame_values(frame));
        }
    }
    return env_loop(env);
}

The method described here is only one of many plausible ways to represent environments. Since we used data abstraction to isolate the rest of the evaluator from the detailed choice of representation, we could change the environment representation if we wanted to. (See exercise 4.9.) In a production-quality JavaScript system, the speed of the evaluator's environment operations—especially that of symbol lookup—has a major impact on the performance of the system. The representation described here, although conceptually simple, is not efficient and would not ordinarily be used in a production system.[3]

Exercise 4.9 Instead of representing a frame as a pair of lists, we can represent a frame as a list of bindings, where each binding is a symbol-value pair. Rewrite the environment operations to use this alternative representation.

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

Exercise 4.10 The functions lookup_symbol_value and assign_symbol_value can be expressed in terms of a more abstract function for traversing the environment structure. Define an abstraction that captures the common pattern and redefine the two functions in terms of this abstraction.

Exercise 4.11 Our language distinguishes constants from variables by using different keywords—const and let—and prevents assignment to constants. However, our interpreter does not make use of this distinction; the function assign_symbol_value will happily assign a new value to a given symbol, regardless whether it is declared as a constant or a variable. Correct this flaw by calling the function error whenever an attempt is made to use a constant on the left-hand side of an assignment. You may proceed as follows:

Introduce predicates is_constant_declaration and is_variable_declaration that allow you to distinguish the two kinds. As shown in section 4.1.2, parse distinguishes them by using the tags "constant_declaration" and "variable_declaration".
Change scan_out_declarations and (if necessary) extend_environment such that constants are distinguishable from variables in the frames in which they are bound.
Change assign_symbol_value such that it checks whether the given symbol has been declared as a variable or as a constant, and in the latter case signals an error that assignment operations are not allowed on constants.
Change eval_declaration such that when it encounters a constant declaration, it calls a new function, assign_constant_value, which does not perform the check that you introduced in assign_symbol_value.
If necessary, change apply to ensure that assignment to function parameters remains possible.

Exercise 4.12

JavaScript's specification requires an implementation to signal a runtime error upon an attempt to access the value of a name before its declaration is evaluated (see the end of section 3.2.4). To achieve this behavior in the evaluator, change lookup_symbol_value to signal an error if the value it finds is "*unassigned*".
Similarly, we must not assign a new value to a variable if we have not evaluated its let declaration yet. Change the evaluation of assignment such that assignment to a variable declared with let signals an error in this case.

Exercise 4.13 Prior to ECMAScript 2015's strict mode that we are using in this book, JavaScript variables worked quite differently from Scheme variables, which would have made this adaptation to JavaScript considerably less compelling.

Before ECMAScript 2015, the only way to declare a local variable in JavaScript was using the keyword var instead of the keyword let. The scope of variables declared with var is the entire body of the immediately surrounding function declaration or lambda expression, rather than just the immediately enclosing block. Modify scan_out_declarations and eval_block such that names declared with const and let follow the scoping rules of var.
When not in strict mode, JavaScript permits undeclared names to appear to the left of the = in assignments. Such an assignment adds the new binding to the global environment. Modify the function assign_symbol_value to make assignment behave this way. The strict mode, which forbids such assignments, was introduced in JavaScript in order to make programs more secure. What security issue is addressed by preventing assignment from adding bindings to the global environment?

[1] Conditionals in full JavaScript accept any value, not just a boolean, as the result of evaluating the predicate expression. JavaScript's notion of truthiness and falsiness is captured by the following variants of is_truthy and is_falsy:

function is_truthy(x) { return ! is_falsy(x); }

function is_falsy(x) {
    return (is_boolean(x) && !x )                  ||
           (is_number(x) && (x === 0 || x !== x )) ||
           (is_string(x) && x === "")              ||
           is_null(x)                              ||
           is_undefined(x);
}

The test x !== x is not a typo; the only JavaScript value for which x !== x yields true is the value NaN (Not a Number), which is considered to be a falsy number (also not a typo), along with 0. The numerical value NaN is the result of certain arithmetic border cases such as 0 / 0.

The terms truthy and falsy were coined by Douglas Crockford, one of whose books (Crockford 2008) inspired this JavaScript adaptation.

[2] Frames are not really a data abstraction: The function assign_symbol_value below uses set_head to directly modify the values in a frame. The purpose of the frame functions is to make the environment-manipulation functions easy to read.

[3] The drawback of this representation (as well as the variant in exercise 4.9) is that the evaluator may have to search through many frames in order to find the binding for a given variable. (Such an approach is referred to as deep binding.) One way to avoid this inefficiency is to make use of a strategy called lexical addressing, which will be discussed in section 5.5.6.

< Previous

Next >

4.1.3 Evaluator Data Structures