4.1.1 The Core of the Evaluator - SICP Comparison Edition

Permalink copied!

Figure 4.2 The evaluate–apply cycle exposes the essence of a computer language.

The evaluation process can be described as the interplay between two functions: evaluate and apply.

The function evaluate

The function evaluate takes as arguments a program component—a statement or expression[1]—and an environment. It classifies the component and directs its evaluation. The function evaluate is structured as a case analysis of the syntactic type of the component to be evaluated. In order to keep the function general, we express the determination of the type of a component abstractly, making no commitment to any particular representation for the various types of components. Each type of component has a syntax predicate that tests for it and an abstract means for selecting its parts. This abstract syntax makes it easy to see how we can change the syntax of the language by using the same evaluator, but with a different collection of syntax functions.

Primitive expressions

For literal expressions, such as numbers, evaluate returns their value.
The function evaluate must look up names in the environment to find their values.

Combinations

For a function application, evaluate must recursively evaluate the function expression and the argument expressions of the application. The resulting function and arguments are passed to apply, which handles the actual function application.
An operator combination is transformed into a function application and then evaluated.

Syntactic forms

A conditional expression or statement requires special processing of its parts, so as to evaluate the consequent if the predicate is true, and otherwise to evaluate the alternative.
A lambda expression must be transformed into an applicable function by packaging together the parameters and body specified by the lambda expression with the environment of the evaluation.
A sequence of statements requires evaluating its components in the order in which they appear.
A block requires evaluating its body in a new environment that reflects all names declared within the block.
A return statement must produce a value that becomes the result of the function call that gave rise to the evaluation of the return statement.
A function declaration is transformed into a constant declaration and then evaluated.
A constant or variable declaration or an assignment must call evaluate recursively to compute the new value to be associated with the name being declared or assigned. The environment must be modified to reflect the new value of the name.

Here is the declaration of evaluate:

function evaluate(component, env) {
    return is_literal(component)
           ? literal_value(component)
           : is_name(component)
           ? lookup_symbol_value(symbol_of_name(component), env)
           : is_application(component)
           ? apply(evaluate(function_expression(component), env),
                   list_of_values(arg_expressions(component), env))
           : is_operator_combination(component)
           ? evaluate(operator_combination_to_application(component),
                      env)
           : is_conditional(component)
           ? eval_conditional(component, env)
           : is_lambda_expression(component)
           ? make_function(lambda_parameter_symbols(component),
                           lambda_body(component), env)
           : is_sequence(component)
           ? eval_sequence(sequence_statements(component), env)
           : is_block(component)
           ? eval_block(component, env)
           : is_return_statement(component)
           ? eval_return_statement(component, env)
           : is_function_declaration(component)
           ? evaluate(function_decl_to_constant_decl(component), env)
           : is_declaration(component)
           ? eval_declaration(component, env)
           : is_assignment(component)
           ? eval_assignment(component, env)
           : error(component, "unknown syntax -- evaluate");
}

For clarity, evaluate has been implemented as a case analysis using conditional expressions. The disadvantage of this is that our function handles only a few distinguishable types of statements and expressions, and no new ones can be defined without editing the declaration of evaluate. In most interpreter implementations, dispatching on the type of a component is done in a data-directed style. This allows a user to add new types of components that evaluate can distinguish, without modifying the declaration of evaluate itself. (See exercise 4.3.)

The representation of names is handled by the syntax abstractions. Internally, the evaluator uses strings to represent names, and we refer to such strings as symbols. The function symbol_of_name used in evaluate extracts from a name the symbol by which it is represented.

Apply

The function apply takes two arguments, a function and a list of arguments to which the function should be applied. The function apply classifies functions into two kinds: It calls apply_primitive_function to apply primitives; it applies compound functions by evaluating the block that makes up the body of the function. The environment for the evaluation of the body of a compound function is constructed by extending the base environment carried by the function to include a frame that binds the parameters of the function to the arguments to which the function is to be applied. Here is the declaration of apply:

function apply(fun, args) {
    if (is_primitive_function(fun)) {
        return apply_primitive_function(fun, args);
    } else if (is_compound_function(fun)) {
        const result = evaluate(function_body(fun),
                                extend_environment(
                                    function_parameters(fun),
                                    args,
                                    function_environment(fun)));
        return is_return_value(result)
               ? return_value_content(result)
               : undefined;
    } else {
        error(fun, "unknown function type -- apply");
    }
}

In order to return a value, a JavaScript function needs to evaluate a return statement. If a function terminates without evaluating a return statement, the value undefined is returned. To distinguish the two cases, the evaluation of a return statement will wrap the result of evaluating its return expression into a return value. If the evaluation of the function body yields such a return value, the content of the return value is retrieved; otherwise the value undefined is returned.[2]

Function arguments

When evaluate processes a function application, it uses list_of_values to produce the list of arguments to which the function is to be applied. The function list_of_values takes as an argument the argument expressions of the application. It evaluates each argument expression and returns a list of the corresponding values:[3]

function list_of_values(exps, env) {
    return map(arg => evaluate(arg, env), exps);
}

Conditionals

The function eval_conditional evaluates the predicate part of a conditional component in the given environment. If the result is true, the consequent is evaluated, otherwise the alternative is evaluated:

function eval_conditional(component, env) {
    return is_truthy(evaluate(conditional_predicate(component), env))
           ? evaluate(conditional_consequent(component), env)
           : evaluate(conditional_alternative(component), env);
}

Note that the evaluator does not need to distinguish between conditional expressions and conditional statements.

The use of is_truthy in eval_conditional highlights the issue of the connection between an implemented language and an implementation language. The conditional_predicate is evaluated in the language being implemented and thus yields a value in that language. The interpreter predicate is_truthy translates that value into a value that can be tested by the conditional expression in the implementation language: The metacircular representation of truth might not be the same as that of the underlying JavaScript.[4]

Sequences

The function eval_sequence is used by evaluate to evaluate a sequence of statements at the top level or in a block. It takes as arguments a sequence of statements and an environment, and evaluates the statements in the order in which they occur. The value returned is the value of the final statement, except that if the evaluation of any statement in the sequence yields a return value, that value is returned and the subsequent statements are ignored.[5]

function eval_sequence(stmts, env) {
    if (is_empty_sequence(stmts)) {
        return undefined;
    } else if (is_last_statement(stmts)) {
        return evaluate(first_statement(stmts), env);
    } else {
        const first_stmt_value = 
            evaluate(first_statement(stmts), env);
        if (is_return_value(first_stmt_value)) {
            return first_stmt_value;
        } else {
            return eval_sequence(rest_statements(stmts), env);
        }
    }
}

Blocks

The function eval_block handles blocks. The variables and constants (including functions) declared in the block have the whole block as their scope and thus are scanned out before the body of the block is evaluated. The body of the block is evaluated with respect to an environment that extends the current environment by a frame that binds each local name to a special value, "*unassigned*". This string serves as a placeholder, before the evaluation of the declaration assigns the name its proper value. An attempt to access the value of the name before its declaration is evaluated leads to an error at run time (see exercise 4.12), as stated in footnote undefined in chapter 1.

function eval_block(component, env) {
    const body = block_body(component);
    const locals = scan_out_declarations(body);
    const unassigneds = list_of_unassigned(locals);
    return evaluate(body, extend_environment(locals,
                                             unassigneds, 
                                             env));
}
function list_of_unassigned(symbols) {
    return map(symbol => "*unassigned*", symbols);
}

The function scan_out_declarations collects a list of all symbols representing names declared in the body. It uses declaration_symbol to retrieve the symbol that represents the name from the declaration statements it finds.

function scan_out_declarations(component) {
    return is_sequence(component)
           ? accumulate(append,
                        null,
                        map(scan_out_declarations,
                            sequence_statements(component)))
           : is_declaration(component)
           ? list(declaration_symbol(component))
           : null;
}

We ignore declarations that are nested in another block, because the evaluation of that block will take care of them. The function scan_out_declarations looks for declarations only in sequences because declarations in conditional statements, function declarations, and lambda expressions are always in a nested block.

Return statements

The function eval_return_statement is used to evaluate return statements. As seen in apply and the evaluation of sequences, the result of evaluation of a return statement needs to be identifiable so that the evaluation of a function body can return immediately, even if there are statements after the return statement. For this purpose, the evaluation of a return statement wraps the result of evaluating the return expression in a return value object.[6]

function eval_return_statement(component, env) {
    return make_return_value(evaluate(return_expression(component),
                                      env));
}

Assignments and declarations

The function eval_assignment handles assignments to names. (To simplify the presentation of our evaluator, we are allowing assignment not just to variables but also—erroneously—to constants. Exercise 4.11 explains how we could distinguish constants from variables and prevent assignment to constants.) The function eval_assignment calls evaluate on the value expression to find the value to be assigned and calls assignment_symbol to retrieve the symbol that represents the name from the assignment. The function eval_assignment transmits the symbol and the value to assign_symbol_value to be installed in the designated environment. The evaluation of an assignment returns the value that was assigned.

function eval_assignment(component, env) {
    const value = evaluate(assignment_value_expression(component),
                           env);
    assign_symbol_value(assignment_symbol(component), value, env);
    return value;
}

Constant and variable declarations are both recognized by the is_declaration syntax predicate. They are treated in a manner similar to assignments, because eval_block has already bound their symbols to "*unassigned*" in the current environment. Their evaluation replaces "*unassigned*" with the result of evaluating the value expression.

function eval_declaration(component, env) {
    assign_symbol_value(
        declaration_symbol(component), 
        evaluate(declaration_value_expression(component), env),
        env);
    return undefined;
}

The result of evaluating the body of a function is determined by return statements, and therefore the return value undefined in eval_declaration only matters when the declaration occurs at the top level, outside of any function body. Here we use the return value undefined to simplify the presentation; exercise 4.8 describes the real result of evaluating top-level components in JavaScript.

Exercise 4.1 Notice that we cannot tell whether the metacircular evaluator evaluates argument expressions from left to right or from right to left. Its evaluation order is inherited from the underlying JavaScript: If the arguments to pair in map are evaluated from left to right, then list_of_values will evaluate argument expressions from left to right; and if the arguments to pair are evaluated from right to left, then list_of_values will evaluate argument expressions from right to left.

Write a version of list_of_values that evaluates argument expressions from left to right regardless of the order of evaluation in the underlying JavaScript. Also write a version of list_of_values that evaluates argument expressions from right to left.

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.

[1] There is no need to distinguish between statements and expressions in our evaluator. For example, we do not differentiate between expressions and expression statements; we represent them identically and consequently they are handled in the same way by the evaluate function. Similarly, our evaluator does not enforce JavaScript's syntactic restriction that statements cannot appear inside expressions other than lambda expressions.

[2] This test is a deferred operation, and thus our evaluator will give rise to a recursive process even if the interpreted program should give rise to an iterative process according to the description in section 1.2.1. In other words, our metacircular evaluator implementation of JavaScript is not tail-recursive. Sections 5.4.2 and 5.5.3 show how to achieve tail recursion using a register machine.

[3] We chose to implement list_of_values using the higher-order function map, and we will use map in other places as well. However, the evaluator can be implemented without any use of higher-order functions (and thus could be written in a language that doesn't have higher-order functions), even though the language that it supports will include higher-order functions. For example, list_of_values can be written without map as follows:

function list_of_values(exps, env) {
    return is_null(exps)	
           ? null
           : pair(evaluate(head(exps), env), 
                  list_of_values(tail(exps), env));
}

[4] In this case, the language being implemented and the implementation language are the same. Contemplation of the meaning of is_truthy here yields expansion of consciousness without the abuse of substance.

[5] The treatment of return statements in eval_sequence reflects the proper result of evaluating function applications in JavaScript, but the evaluator presented here does not comply with the ECMAScript specification for the value of a program that consists of a sequence of statements outside of any function body. Exercise 4.8 addresses this issue.

[6] The application of the function make_return_value to the result of evaluating the return expression creates a deferred operation, in addition to the deferred operation created by apply. See footnote 2 for details.

< Previous

Next >

4.1.1 The Core of the Evaluator