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
proceduresfunctions
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
proceduresfunctions
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
procedurefunction
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
proceduresfunctions
are constructed from parameters,
procedurefunction
bodies, and environments using the constructor
make-procedure: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); }
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
variablessymbols
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
cdrtail
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
variablesnames
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
variablessymbols
with values, we make a frame consisting of the list of
variablessymbols
and the list of values, and we adjoin this to the environment. We signal
an error if the number of
variablessymbols
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
variablesymbol
in an environment, we scan the list of
variablessymbols
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
variablesymbol
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.
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.
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.14.) In a
production-quality
LispJavaScript
system, the speed of the evaluator's environment
operations—especially that of
variablesymbol
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.14
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.15
The
proceduresfunctionsset-variable-value!,
define-variable!, and
lookup-variable-valuelookup_symbol_value and
assign_symbol_value
can be expressed in terms of
more abstract proceduresa 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.
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.
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.
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.
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.
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.
Original
JavaScript
Exercise 4.18
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
proceduresfunctions
is to make the environment-manipulation
proceduresfunctions
easy to read.
[3]
The drawback of this representation (as
well as the variant in
exercise 4.14) 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.