4.1.3 Evaluator Data Structures - SICP Comparison Edition

Permalink copied!

In addition to defining the external syntax of expressions, 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 procedures functions and environments and the representation of true and false.

Testing of predicates

Original		JavaScript
For conditionals, we accept anything to be true that is not the explicit `false` object.		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]

Original	JavaScript
`(define (true? x) (not (eq? x false))) (define (false? x) (eq? x false))`	`function is_truthy(x) { return is_boolean(x) ? x : error(x, "boolean expected, received"); } function is_falsy(x) { return ! is_truthy(x); }`

Representing procedures functions

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

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

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

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

Original	JavaScript
`(define (make-procedure parameters body env) (list 'procedure parameters body env)) (define (compound-procedure? p) (tagged-list? p 'procedure)) (define (procedure-parameters p) (cadr p)) (define (procedure-body p) (caddr p)) (define (procedure-environment p) (cadddr p))`	`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); }`

Original		JavaScript
		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 variables symbols with their corresponding values. We use the following operations for manipulating environments:

Original		JavaScript
`(lookup-variable-value` var env`)` returns the value that is bound to the symbol var in the environment env, or signals an error if the variable is unbound. `(extend-environment` variables values base-env `)` returns a new environment, consisting of a new frame in which the symbols in the list variables are bound to the corresponding elements in the list values, where the enclosing environment is the environment base-env. `(define-variable!` var value env `)` adds to the first frame in the environment env a new binding that associates the variable var with the value value. `(set-variable-value!` var value env `)` changes the binding of the variable var in the environment env so that the variable is now bound to the value value, or signals an error if the variable is unbound.		`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 cdr tail of the list. The empty environment is simply the empty list.

Original	JavaScript
`(define (enclosing-environment env) (cdr env)) (define (first-frame env) (car env)) (define the-empty-environment '())`	`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 variables names bound in that frame and a list of the associated values.[2]

Original	JavaScript
`(define (make-frame variables values) (cons variables values)) (define (frame-variables frame) (car frame)) (define (frame-values frame) (cdr frame)) (define (add-binding-to-frame! var val frame) (set-car! frame (cons var (car frame))) (set-cdr! frame (cons val (cdr frame))))`	`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 variables symbols with values, we make a frame consisting of the list of variables symbols and the list of values, and we adjoin this to the environment. We signal an error if the number of variables symbols does not match the number of values.

Original	JavaScript
`(define (extend-environment vars vals base-env) (if (= (length vars) (length vals)) (cons (make-frame vars vals) base-env) (if (< (length vars) (length vals)) (error "Too many arguments supplied" vars vals) (error "Too few arguments supplied" vars vals))))`	`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 variable symbol in an environment, we scan the list of variables symbols in the first frame. If we find the desired variable, symbol, we return the corresponding element in the list of values. If we do not find the variable symbol in the current frame, we search the enclosing environment, and so on. If we reach the empty environment, we signal an unbound variable "unbound name" error.

Original

JavaScript

(define (lookup-variable-value var env) (define (env-loop env) (define (scan vars vals) (cond ((null? vars) (env-loop (enclosing-environment env))) ((eq? var (car vars)) (car vals)) (else (scan (cdr vars) (cdr vals))))) (if (eq? env the-empty-environment) (error "Unbound variable" var) (let ((frame (first-frame env))) (scan (frame-variables frame) (frame-values frame))))) (env-loop env))

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

Original		JavaScript
To set a variable to a new value in a specified environment, we scan for the variable, just as in `lookup-variable-value`, and change the corresponding value when we find it.		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.

Original

JavaScript

(define (set-variable-value! var val env) (define (env-loop env) (define (scan vars vals) (cond ((null? vars) (env-loop (enclosing-environment env))) ((eq? var (car vars)) (set-car! vals val)) (else (scan (cdr vars) (cdr vals))))) (if (eq? env the-empty-environment) (error "Unbound variable - - SET!" var) (let ((frame (first-frame env))) (scan (frame-variables frame) (frame-values frame))))) (env-loop env))

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

Original		JavaScript
To define a variable, we search the first frame for a binding for the variable, and change the binding if it exists (just as in `set-variable-value!`. If no such binding exists, we adjoin one to the first frame. `(define (define-variable! var val env) (let ((frame (first-frame env))) (define (scan vars vals) (cond ((null? vars) (add-binding-to-frame! var val frame)) ((eq? var (car vars)) (set-car! vals val)) (else (scan (cdr vars) (cdr vals))))) (scan (frame-variables frame) (frame-values frame))))`

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 Lisp JavaScript system, the speed of the evaluator's environment operations—especially that of variable 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 procedures functions set-variable-value!, define-variable!, and lookup-variable-value lookup_symbol_value and assign_symbol_value can be expressed in terms of more abstract procedures a more abstract function for traversing the environment structure. Define abstractions that capture the common patterns and redefine the three procedures in terms of these abstractions. Define an abstraction that captures the common pattern and redefine the two functions in terms of this abstraction.

Exercise 4.11

Original		JavaScript
Scheme allows us to create new bindings for variables by means of `define`, but provides no way to get rid of bindings. Implement for the evaluator a special form `make-unbound!` that removes the binding of a given symbol from the environment in which the `make-unbound!` expression is evaluated. This problem is not completely specified. For example, should we remove only the binding in the first frame of the environment? Complete the specification and justify any choices you make.		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.

Original		JavaScript
		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? 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] 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 in the following code: abstraction: set-variable-value! and define-variable! use set-car! to directly modify the values in a frame. The function assign_symbol_value below uses set_head to directly modify the values in a frame. The purpose of the frame procedures functions is to make the environment-manipulation procedures 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

Testing of predicates

Representing procedures functions

Representing return values

Operations on Environments