4.1.1 The Core of the Evaluator - SICP Comparison Edition

Permalink copied!

Original		JavaScript
Figure 4.1 The `eval`–`apply` cycle exposes the essence of a computer language.		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 procedures: functions: eval evaluate and apply.

Eval The function evaluate

In JavaScript's strict mode—our preferred way to run JavaScript programs—the name eval cannot be declared in user programs. It is reserved for a related but quite different pre-declared function. We opt for the complete word evaluate as a replacement.

Eval The function evaluate takes as arguments a program component—a statement or expression[1]—and an environment. and an environment. It classifies the expression component and directs its evaluation. Eval The function evaluate is structured as a case analysis of the syntactic type of the expression component to be evaluated. In order to keep the procedure function general, we express the determination of the type of an expression a component abstractly, making no commitment to any particular representation for the various types of expressions. components. Each type of expression component has a predicate 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 procedures. functions.

Primitive expressions

Original		JavaScript
For self-evaluating expressions, such as numbers, `eval` returns the expression itself. For literal expressions, such as numbers, `evaluate` returns their value. `Eval` The function `evaluate` must look up variables names in the environment to find their values. Special forms For quoted expressions, `eval` returns the expression that was quoted. An assignment to (or a definition of) a variable must recursively call `eval` to compute the new value to be associated with the variable. The environment must be modified to change (or create) the binding of the variable. An if expression 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 procedure by packaging together the parameters and body specified by the `lambda` expression with the environment of the evaluation. A `begin` expression requires evaluating its sequence of expressions in the order in which they appear. A case analysis (`cond`) is transformed into a nest of `if` expressions and then evaluated. Combinations For a procedure application, `eval` must recursively evaluate the operator part and the operands of the combination. The resulting procedure and arguments are passed to `apply`, which handles the actual procedure application. Here is the definition of `eval`: (define (eval exp env) (cond ((self-evaluating? exp) exp) ((variable? exp) (lookup-variable-value exp env)) ((quoted? exp) (text-of-quotation exp)) ((assignment? exp) (eval-assignment exp env)) ((definition? exp) (eval-definition exp env)) ((if? exp) (eval-if exp env)) ((lambda? exp) (make-procedure (lambda-parameters exp) (lambda-body exp) env)) ((begin? exp) (eval-sequence (begin-actions exp) env)) ((cond? exp) (eval (cond->if exp) env)) ((application? exp) (apply (eval (operator exp) env) (list-of-values (operands exp) env))) (else (error "Unknown expression type - - EVAL" exp))))		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, eval evaluate has been implemented as a case analysis using cond. conditional expressions. The disadvantage of this is that our procedure function handles only a few distinguishable types of statements and expressions, and no new ones can be defined without editing the definition of eval. declaration of evaluate. In most Lisp interpreter implementations, dispatching on the type of an expression a component is done in a data-directed style. This allows a user to add new types of expressions that eval components that evaluate can distinguish, without modifying the definition of eval declaration of evaluate itself. (See exercise 4.6.)

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

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

Original

JavaScript

(define (apply procedure arguments) (cond ((primitive-procedure? procedure) (apply-primitive-procedure procedure arguments)) ((compound-procedure? procedure) (eval-sequence (procedure-body procedure) (extend-environment (procedure-parameters procedure) arguments (procedure-environment procedure)))) (else (error "Unknown procedure type - - APPLY" procedure))))

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"); } }

The name arguments is reserved in JavaScript's strict mode. We chose args instead.

Original		JavaScript
		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]

Procedure Function arguments

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

Original	JavaScript
`(define (list-of-values exps env) (if (no-operands? exps) '() (cons (eval (first-operand exps) env) (list-of-values (rest-operands exps) env))))`	`function list_of_values(exps, env) { return map(arg => evaluate(arg, env), exps); }`

Conditionals

Eval-if The function eval_conditional evaluates the predicate part of an if expression a conditional component in the given environment. If the result is true, eval-if evaluates the consequent, otherwise it evaluates the alternative: the consequent is evaluated, otherwise the alternative is evaluated:

Original	JavaScript
`(define (eval-if exp env) (if (true? (eval (if-predicate exp) env)) (eval (if-consequent exp) env) (eval (if-alternative exp) env)))`	`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 true? is_truthy in eval-if eval_conditional highlights the issue of the connection between an implemented language and an implementation language. The if-predicate conditional_predicate is evaluated in the language being implemented and thus yields a value in that language. The interpreter predicate true? is_truthy translates that value into a value that can be tested by the if conditional expression in the implementation language: The metacircular representation of truth might not be the same as that of the underlying SchemeJavaScript.[5]

Sequences

Original		JavaScript
`Eval-sequence` is used by `apply` to evaluate the sequence of expressions in a procedure body and by `eval` to evaluate the sequence of expressions in a `begin` expression. It takes as arguments a sequence of expressions and an environment, and evaluates the expressions in the order in which they occur. The value returned is the value of the final expression. `(define (eval-sequence exps env) (cond ((last-exp? exps) (eval (first-exp exps) env)) (else (eval (first-exp exps) env) (eval-sequence (rest-exps exps) env))))`		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.[6] `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); } } }`

Original		JavaScript
		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.17), as stated in footnote 4 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.[7] `function eval_return_statement(component, env) { return make_return_value(evaluate(return_expression(component), env)); }`

Assignments and definitions declarations

The following procedure function eval_assignment handles assignments to variables. names. (To simplify the presentation of our evaluator, we are allowing assignment not just to variables but also—erroneously—to constants. Exercise 4.16 explains how we could distinguish constants from variables and prevent assignment to constants.) It calls eval to find the value to be assigned and transmits the variable and the resulting value to set-variable-value! to be installed in the designated environment. 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.

Original	JavaScript
`(define (eval-assignment exp env) (set-variable-value! (assignment-variable exp) (eval (assignment-value exp) env) env) 'ok)`	`function eval_assignment(component, env) { const value = evaluate(assignment_value_expression(component), env); assign_symbol_value(assignment_symbol(component), value, env); return value; }`

Original		JavaScript
Definitions of variables are handled in a similar manner.[8] `(define (eval-definition exp env) (define-variable! (definition-variable exp) (eval (definition-value exp) env) env) 'ok)` We have chosen here to return the symbol `ok` as the value of an assignment or a definition.[9]		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.13 describes the real result of evaluating top-level components in JavaScript.

Original		JavaScript
Exercise 4.1 Notice that we cannot tell whether the metacircular evaluator evaluates operands from left to right or from right to left. Its evaluation order is inherited from the underlying Lisp: If the arguments to `cons` in `list-of-values` are evaluated from left to right, then `list-of-values` will evaluate operands from left to right; and if the arguments to `cons` are evaluated from right to left, then `list-of-values` will evaluate operands from right to left. Write a version of `list-of-values` that evaluates operands from left to right regardless of the order of evaluation in the underlying Lisp. Also write a version of `list-of-values` that evaluates operands 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.		Exercise 4.2 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 could have simplified the application? clause in eval by using map (and stipulating that operands returns a list) rather than writing an explicit list-of-values procedure. We chose not to use map here to emphasize the fact that the evaluator can be implemented without any use of higher-order procedures (and thus could be written in a language that doesn't have higher-order procedures), even though the language that it supports will include higher-order procedures.

[4] 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)); }

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

[6] 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.13 addresses this issue.

[7] 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.

[8] This implementation of define ignores a subtle issue in the handling of internal definitions, although it works correctly in most cases. We will see what the problem is and how to solve it in section 4.1.6.

[9] As we said when we introduced define and set!, these values are implementation-dependent in Scheme—that is, the implementor can choose what value to return.

< Previous

Next >

4.1.1 The Core of the Evaluator

Eval The function evaluate

Primitive expressions

Special forms

Combinations

Combinations

Syntactic forms

Apply

Procedure Function arguments

Conditionals

Sequences

Blocks

Return statements

Assignments and definitions declarations