1.1 Evaluation Model

Scheme evaluation can be viewed as the simplification of expressions to obtain values. For example, just as an elementary-school student simplifies

1 + 1 = 2

Scheme evaluation simplifies

  (+ 1 1) → 2

The arrow → above replaces the more traditional = to emphasize that evaluation proceeds in a particular direction towards simpler expressions. In particular, a value is an expression that evaluation simplifies no further, such as the number 2.

1.1.1 Sub-expression Evaluation and Continuations

Some simplifications require more than one step. For example:

  (- 4 (+ 1 1)) → (- 4 2) → 2

An expression that is not a value can always be partitioned into two parts: a redex, which is the part that changed in a single-step simplification (highlighted), and the continuation, which is the surrounding expression context. In (- 4 (+ 1 1)), the redex is (+ 1 1), and the continuation is (- 4 []), where [] takes the place of the redex. That is, the continuation says how to “continue” after the redex is reduced to a value.

Before some things can be evaluated, some sub-expressions must be evaluated; for example, in the application (- 4 (+ 1 1)), the application of - cannot be reduced until the sub-expression (+ 1 1) is reduced.

Thus, the specification of each syntactic form specifies how (some of) its sub-expressions are evaluated, and then how the results are combined to reduce the form away.

The dynamic extent of an expression is the sequence of evaluation steps during which an expression contains the redex.

1.1.2 Tail Position

An expression expr1 is in tail position with respect to an enclosing expression expr2 if, whenever expr1 becomes a redex, its continuation is the same as was the enclosing expr2’s continuation.

For example, the (+ 1 1) expression is not in tail position with respect to (- 4 (+ 1 1)). To illustrate, we use the notation C[expr] to mean the expression that is produced by substituting expr in place of [] in the continuation C:

  C[(- 4 (+ 1 1))] → C[(- 4 2)]

In this case, the continuation for reducing (+ 1 1) is C[(+ 4 [])], not just C.

In contrast, (+ 1 1) is in tail position with respect to (if (zero? 0) (+ 1 1) 3), because, for any continuation C,

  C[(if (zero? 0) (+ 1 1) 3)] → C[(if #t (+ 1 1) 3)] → C[(+ 1 1)]

The steps in this reduction sequence are driven by the definition of if, and they do not depend on the continuation C. The “then” branch of an if form is always in tail position with respect to the if form. Due to a similar reduction rule for if and #f, the “else” branch of an if form is also in tail position.

Tail-position specifications provide a guarantee about the asymptotic space consumption of a computation. In general, the specification of tail positions goes with each syntactic form, like if.

1.1.3 Multiple Return Values

A Scheme expression can evaluate to multiple values, in the same way that a procedure can accept multiple arguments.

Most continuations expect a particular number of result values. Indeed, most continuations, such as (+ [] 1) expect a single value. The continuation (let-values ([(x y) []]) expr) expects two result values; the first result replaces x in the body expr, and the second replaces y in expr. The continuation (begin [] (+ 1 2)) accepts any number of result values, because it ignores the result(s).

In general, the specification of a syntactic form inidicates the number of values that it produces and the number that it expects from each of its sub-expression. In addtion, some procedures (notably values) produce multiple values, and some procedures (notably call-with-values) create continuations internally that accept a certain number of values.

1.1.4 Top-Level Variables

Given

x = 10

then an algebra student simplifies x + 1 as follows:

x + 1 = 10 + 1 = 11

Scheme works much the same way, in that a set of top-level variables are available for substitutions on demand during evaluation. For example, given

  (define x 10)

then

  (+ x 1) → (+ 10 1) → 11

In Scheme, the way definitions appear is just as important as the way that they are used. Scheme evaluation thus keeps track of both definitions and the current expression, and it extends the set of definitions in response to evaluating forms such as define.

Each evaluation step, then, takes the current set of definitions and program to a new set of definitions and program. Before a define can be moved into the set of definitions, its right-hand expression must be reduced to a value.

			defined:
			evaluate:		(begin (define x (+ 9 1)) (+ x 1))
	→		defined:
			evaluate:		(begin (define x 10) (+ x 1))
	→		defined:		(define x 10)
			evaluate:		(begin (void) (+ x 1))
	→		defined:		(define x 10)
			evaluate:		(+ x 1)
	→		defined:		(define x 10)
			evaluate:		(+ 10 1)
	→		defined:		(define x 10)
			evaluate:		11

Using set!, a program can change the value associated with an existing top-level variable:

			defined:		(define x 10)
			evaluate:		(begin (set! x 8) x)
	→		defined:		(define x 8)
			evaluate:		(begin (void) x)
	→		defined:		(define x 8)
			evaluate:		x
	→		defined:		(define x 8)
			evaluate:		8

1.1.5 Objects and Imperative Update

In addition to set! for imperative update of top-level variables, various procedures enable the modification of elements within a compound data structure. For example, vector-set! modifies the content of a vector.

To allow such modifications to data, we must distingiush between values, which are the results of expressions, and objects, which hold the data referenced by a value.

A few kinds of objects can serve directly as values, including booleans, (void), and small exact integers. More generally, however, a value is a reference to an object. For example, a value can be a reference to a particular vector that currently holds the value 10 in its first slot. If an object is modified, then the modification is visible through all copies of the value that reference the same object.

In the evaluation model, a set of objects must be carried along with each step in evaluation, just like the definition set. Operations that create objects, such as vector, add to the set of objects:

			objects:
			defined:
			evaluate:		(begin (define x (vector 10 20))        (define y x)        (vector-set! x 0 11)        (vector-ref y 0))
	→		objects:		(define <o1> (vector 10 20))
			defined:
			evaluate:		(begin (define x <o1>)        (define y x)        (vector-set! x 0 11)        (vector-ref y 0))
	→		objects:		(define <o1> (vector 10 20))
			defined:		(define x <o1>)
			evaluate:		(begin (void)        (define y x)        (vector-set! x 0 11)        (vector-ref y 0))
	→		objects:		(define <o1> (vector 10 20))
			defined:		(define x <o1>)
			evaluate:		(begin (define y x)        (vector-set! x 0 11)        (vector-ref y 0))
	→		objects:		(define <o1> (vector 10 20))
			defined:		(define x <o1>)
			evaluate:		(begin (define y <o1>)        (vector-set! x 0 11)        (vector-ref y 0))
	→		objects:		(define <o1> (vector 10 20))
			defined:		(define x <o1>) (define y <o1>)
			evaluate:		(begin (void)        (vector-set! x 0 11)        (vector-ref y 0))
	→		objects:		(define <o1> (vector 10 20))
			defined:		(define x <o1>) (define y <o1>)
			evaluate:		(begin (vector-set! x 0 11)        (vector-ref y 0))
	→		objects:		(define <o1> (vector 10 20))
			defined:		(define x <o1>) (define y <o1>)
			evaluate:		(begin (vector-set! <o1> 0 11)        (vector-ref y 0))
	→		objects:		(define <o1> (vector 11 20))
			defined:		(define x <o1>) (define y <o1>)
			evaluate:		(begin (void)        (vector-ref y 0))
	→		objects:		(define <o1> (vector 11 20))
			defined:		(define x <o1>) (define y <o1>)
			evaluate:		(vector-ref y 0)
	→		objects:		(define <o1> (vector 11 20))
			defined:		(define x <o1>) (define y <o1>)
			evaluate:		(vector-ref <o1> 0)
	→		objects:		(define <o1> (vector 11 20))
			defined:		(define x <o1>) (define y <o1>)
			evaluate:		11

The distinction between a top-level variable and an object reference is crucial. A top-level variable is not a value; each time a variable expression is evaluated, the value is extracted from the current set of definitions. An object reference, in contrast is a value, and therefore needs no further evaluation. The model evaluation steps above use angle-bracketed <o1> for an object reference to distinguish it from a variable name.

A direct object reference can never appear in a text-based source program. A program representation created with datum->syntax-object, however, can embed direct references to existing objects.

1.1.6 Object Identity and Comparisons

The eq? operator compares two values, returning #t when the values refer to the same object. This form of equality is suitable for comparing objects that support imperative update (e.g., to determine that the effect of modifying an object through one reference is visible through another reference). Also, an eq? test evaluates quickly, and eq?-based hashing is more lightweight than equal?-based hashing in hash tables.

In some cases, however, eq? is unsuitable as a comparison operator, because the generation of objects is not clearly defined. In particular, two applications of + to the same two exact integers may or may not produce results that are eq?, although the results are always equal?. Similarly, evaluation of a lambda form typically generates a new procedure object, but it may re-use a procedure object previously generated by the same source lambda form.

The behavior of a datatype with respect to eq? is generally specified with the datatype and its associated procedures.

1.1.7 Garbage Collection

In the program state

			objects:		(define <o1> (vector 10 20)) (define <o2> (vector 0))
			defined:		(define x <o1>)
			evaluate:		(+ 1 x)

evaluation cannot depend on <o2>, because it is not part of the program to evaluate, and it is not referenced by any definition that is accessible in the program. The object <o2> may therefore be removed from the evaluation by garbage collection.

A few special compound datatypes hold weak references to objects. Such weak references are treated specially by the garbage collector in determining which objects are reachable for the remainder of the computation. If an object is reachable only via a weak reference, then the object can be reclaimed, and the weak reference is replaced by a different value (typically #f).

1.1.8 Procedure Applications and Local Variables

Given

f(x) = x + 10

then an algebra student simplifies f(1) as follows:

f(7) = 7 + 10 = 17

The key step in this simplification is take the body of the defined function f, and then replace each x with the actual value 1.

Scheme procedure application works much the same way. A procedure is an object, so evaluating (f 7) starts with a variable lookup:

			objects:		(define <p1> (lambda (x) (+ x 10)))
			defined:		(define f <p1>)
			evaluate:		(f 7)
	→		objects:		(define <p1> (lambda (x) (+ x 10)))
			defined:		(define f <p1>)
			evaluate:		(<p1> 7)

Unlike in algebra, however, the value associated with an argument can be changed in the body of a procedure by using set!, as in the example (lambda (x) (begin (set! x 3) x)). Since the value associated with x can be changed, an actual value for cannot be substituted for x when the procedure is applied.

Instead, a new location is created for each variable on each application. The argument value is placed in the location, and each instance of the variable in the procedure body is replaced with the new location:

			objects:		(define <p1> (lambda (x) (+ x 10)))
			defined:		(define f <p1>)
			evaluate:		(<p1> 7)
	→		objects:		(define <p1> (lambda (x) (+ x 10)))
			defined:		(define f <p1>) (define xloc 7)
			evaluate:		(+ xloc 10)
	→		objects:		(define <p1> (lambda (x) (+ x 10)))
			defined:		(define f <p1>) (define xloc 7)
			evaluate:		(+ 7 10)
	→		objects:		(define <p1> (lambda (x) (+ x 10)))
			defined:		(define f <p1>) (define xloc 7)
			evaluate:		17

A location is the same as a top-level variable, but when a location is generated, it (conceptually) uses a name that has not been used before and that cannot not be generated again or accessed directly.

Generating a location in this way means that set! evaluates for local variables in the same way as for top-level variables, because the local variable is always replaced with a location by the time the set! form is evaluated:

			objects:		(define <p1> (lambda (x) (begin (set! x 3) x)))
			defined:		(define f <p1>)
			evaluate:		(f 7)
	→		objects:		(define <p1> (lambda (x) (begin (set! x 3) x)))
			defined:		(define f <p1>)
			evaluate:		(<p1> 7)
	→		objects:		(define <p1> (lambda (x) (begin (set! x 3) x)))
			defined:		(define f <p1>) (define xloc 7)
			evaluate:		(begin (set! xloc 3) xloc)
	→		objects:		(define <p1> (lambda (x) (begin (set! x 3) x)))
			defined:		(define f <p1>) (define xloc 3)
			evaluate:		(begin (void) xloc)
	→		objects:		(define <p1>