With the introduction of set!expressions
and beginexpressions
we have covered most
of Scheme's kernel language. In DrScheme, this portion is called
Advanced Student Scheme. Considering the complexity of set!
, this
is a good place to summarize our programming language
in the spirit of
intermezzo 1. Following the organization of that intermezzo, we discuss the
vocabulary, the grammar, and the meaning of Advanced Student Scheme. The
last subsection explains what kind of errors we may encounter in
Advanced Student Scheme.
The foundation of any language is its vocabulary. In Beginning Student Scheme, we distinguish four categories of words: variables, constants, primitive functions, and keywords. The classification ignores parentheses but we know that every compound phrase is surrounded by a pair of parentheses, and that every atomic phrase stands on its own.
Advanced Student Scheme respects this basic classification, though it
contains four important new keywords: local
, lambda
,
set!
, and begin
. The first two are important for
organizing and abstracting programs; the last two are important for the
computation of effects. Still, keywords per se have no
meaning. They are road signs that tell us what is ahead so that we can
orient ourselves. It is the grammar and the meaning of a language that
explains the role of the keywords.
Even though Scheme is a fullfledged language with as much power as any other programming language, its designers have kept its grammar simple. The grammar of Advanced Student Scheme, which is most of Scheme, is only a few lines longer than that of Beginning Student Scheme.
Figure 111 contains the essential grammar of the
Advanced Student Scheme language.^{71} It extends
Intermediate Student Scheme with three new forms of expressions:
lambdaexpressions, set!expressions, and beginexpressions. The specification of localexpressions
refers to the category of definitions, which refers back to the category of
expressions. A lambdaexpression consists of a sequence of variables, enclosed in
parentheses, and an expression. Similarly, a set!expression consists of a
variable and an expression. Finally, a beginexpression is just a sequence of
expressions prefixed with the keyword begin
to distinguish it from
an application.
Since functions are values now, the grammar of Advanced Student Scheme is also simpler than that of Beginning Student Scheme in one regard. Specifically, it merges the lines for primitive and function application into a single line. The new line specifies applications, which are now sequences of expressions enclosed in parentheses. Owing to the inclusion of primitive operations into the set of expressions,
(+ 1 2)
is still an expression. After all, +
is now an expression, and so
are 1
and 2
. The application of define
d
functions works similarly:
(f 1 2)
The first expression is a variable, and the others are numbers. The application is thus a legal expression.
Unfortunately, a language grammar can only specify the large contours of what is a legal sentence construction. It cannot express restrictions that require some knowledge about the context of a phrase. Advanced Student Scheme requires a few such restrictions:
In a lambdaexpression no variable may occur twice in the parameter sequence.
In a localexpression no definition may introduce the same variable as any other definition in the same sequence.
A set!expression must occur in the lexical scope of a define
that
introduces the set!expression's lefthand side.
In addition, the old restriction applies that keywords cannot be used as variables.
Consider the following definition, which uses the new constructs:
(define switch (local ((definestruct hide (it)) (define state (makehide 1))) (lambda () (begin (set! state (makehide ( 1 (hideit state)))) state))))
The definition introduces the variable switch
. The righthand side
of the definition is a localexpression. It in turn defines the structure
hide
and the variable state
, which stands for an instance
of hide
. The body of the localexpression is a lambdaexpression, whose parameter
sequence is empty. The function's body consists of a beginexpression with two
expressions: a set!expression and an expression that consists of just the
variable state
.
All expressions in our program satisfy the necessary restrictions. First,
the localexpression introduces four names that are distinct: makehide
,
hide?
, hideit
, and state
. Second, the parameter
list of the lambdaexpression is empty, so there is no possible conflict. Finally,
the set!expression's variable is the local
ly defined variable
state
, so it is legal, too.
Exercise 38.2.1. Determine whether the following phrases are syntactically legal or illegal programs:
1. (define (f x) (begin (set! y x) x)) 2. (define (f x) (begin (set! f x) x)) 3. (local ((definestruct hide (it)) (define makehide 10)) (hide? 10)) 4. (local ((definestruct loc (con)) (define loc 10)) (loc? 10)) 5. (define f (lambda (x y x) (* x y z))) (define z 3.14)
Explain why a phrase is legal or illegal. Solution
When we first used Advanced Student Scheme, we did so because we wanted to deal with functions as ordinary values. The evaluation rules barely changed. We just agreed to allow expressions in the first position of an application and to deal with the names of functions as values.
The extension of the language with set!expressions required another change to
our rules. Now definitions that associate variables and values can change
over the course of an evaluation. The informal rules we've used so far deal
with changes to the definition of state variables, because they matter the
most. But the rules are informal and imprecise, so a precise description of
how the addition of set!
changes the meaning of the language must
be our primary concern.
Let's recall how we determine the meaning of a program. A program consists
of two parts: a collection of definitions and an expression. The goal is to
evaluate the expression, which means to determine the expression's
value.^{72} In
Beginning Student Scheme, the collection of values consists of all
the constants plus lists. Only one list has a concise representation: the
empty one. All other lists are written down as a series of
cons
tructed lists.
The evaluation of an expression consists of a series of steps. At each step we use the laws of arithmetic and algebra to simplify a subexpression. This yields another expression. We also say that we REWRITE the first expression into the second. If the second expression is a value, we are finished.
The introduction of set!expressions into our programming language requires a few small adjustments and extensions to this process:
Instead of rewriting just an expression, we must now rewrite definitions and expressions. More precisely, each step changes the expression and possibly the definition of a state variable. To make these effects as obvious as possible, each stage in an evaluation displays the definitions of state variables and the current expression.
Furthermore, it is no longer possible to apply the laws of arithmetic and algebra whenever or wherever we want. Instead, we must determine the subexpression that we must evaluate if we wish to make progress. This rule still leaves us with choices. For example, when we rewrite an expression such as
(+ (* 3 3) (* 4 4))
we may choose to evaluate (* 3 3)
and then (* 4 4)
or
vice versa. Fortunately, for such simple expressions, the choice
doesn't affect the final outcome, so we don't have to supply a complete
unambigous rule. In general, though, we rewrite subexpressions in a
lefttoright and toptobottom order. At each stage in the evaluation,
we best start by underlining the subexpression that must be evaluated
next.
Suppose the underlined subexpression is a set!expression. By the
restrictions on set!expressions, we know that there is a define
for
the lefthand side of the subexpression. That is, we face the
following situation:
(define x aValue)
...
... (set! x anotherValue)
...
= (define x anotherValue)
...
... (void) ...
The equation indicates that the program changes in two ways. First, the
variable definition is modified. Second, the underlined set!expression is
replaced by (void)
, the invisible value.
The next change concerns the replacement of variables in expressions with the value in their definition. Until now, we could replace a variable with its value wherever we thought it was convenient or necessary. Indeed, we just thought of the variable as a shorthand for the value. With set!expressions in the language, this is no longer possible. After all, the evaluation of a set!expression modifies the definition of a state variable, and if we replace a variable with its value at the wrong time, we get the wrong value.
Suppoe that the underlined expression is a (state) variable. Then we know that we can't make any progress in our evaluation until we have replaced the variable with the current value in its definition. This suggests the following revised law for variable evaluation:
(define x aValue)
...
... x
...
= (define x aValue)
...
... aValue ...
In short, substitute the value in a state variable definition for the state variable only when the value is needed for this particular occurrence of the state variable.
Last, but not least, we also need a rule for beginexpressions. The simplest one says to drop the first subexpression if it is a value:
(begin v exp1 ... expn) = (begin exp1 ... expn)
That means we also need a rule for dropping begin
completely:
(begin exp) = exp
In addition, we use a rule for dropping several values at once:
(begin v1 ... vm exp1 ... expn) = (begin exp1 ... expn)
But this is only a convenience.
Although the laws are more complicated than those of Beginning Student Scheme, they are still manageable.
Let's consider some examples. The first one demonstrates how the order of evaluation of subexpressions makes a difference:
(define x 5) (+ (begin(set! x 11)
x) x) = (define x 11) (+ (begin (void)x
) x) = ... = (define x 11) (+ 11x
) = (define x 11)(+ 11 11)
The program consists of one definition and one addition, which is to be
evaluated. One of the addition's arguments is a set!expression that mutates
x
; the other is just x
. By evaluating the subexpressions
of the addition from left to right, the mutation takes place before we
replace the second subexpression with its value. As a result, the outcome
is 22
. If we had evaluated the addition from right to left, the
result would have been 16
. To avoid such problems, we use the
fixed ordering but give ourselves more freedom when no state variables are
involved.
The second example illustrates how a set!expression that occurs in a localexpression actually affects a toplevel definition:
(define (makecounter x0)
(local ((define counter x0)
(define (increment)
(begin
(set! counter (+ counter 1))
counter)))
increment))
((makecounter 0)
)
The program again consists of a single definition and an expression that is to be evaluated. The latter, however, is an application nested in an application. The inner application is underlined, because we must evaluate it to make progress. Here are the first few steps:
= (define (makecounter x0) (local ((define counter x0) (define (increment) (begin (set! counter (+ counter 1)) counter))) increment)) ((local ((define counter 0) (define (increment) (begin (set! counter (+ counter 1)) counter))) increment)) = (define (makecounter x0) (local ((define counter x0) (define (increment) (begin (set! counter (+ counter 1)) counter))) increment)) (define counter1 0) (define (increment1) (begin (set! counter1 (+ counter1 1)) counter1)) (increment1)
The evaluation of the localexpression created additional toplevel expressions. One of them introduces a state variable; the others define functions.
The second part of the evaluation determines what (increment1)
accomplishes:
(define counter1 0)(increment1)
= (define counter1 0) (begin (set! counter1 (+counter1
1)) counter1) = (define counter1 0) (begin (set! counter1(+ 0 1)
) counter1) = (define counter1 0) (begin(set! counter1 1)
counter1) = (define counter1 1) (begin (void)counter1
) = (define counter1 1) 1
During the evaluation, we replace counter1
with its value
twice. First, the second step replaces counter1
with 0
,
its value at that point. Second, we substitute 1
for
counter1
during the last step, which is its new
value.
Exercise 38.3.1. Underline the subexpression that must be evaluated next in the following expressions:
1. (define x 11) (begin (set! x (* x x)) x) 2. (define x 11) (begin (set! x (cond [(zero? 0) 22] [else (/ 1 x)])) 'done) 3. (define (run x) (run x)) (run 10) 4. (define (f x) (* pi x x)) (define a1 (f 10)) (begin (set! a1 ( a1 (f 5))) 'done) 5. (define (f x) (set! state ( 1 state))) (define state 1) (f (f (f)))
Explain why the expression must be evaluated. Solution
Exercise 38.3.2. Confirm that the underlined expressions must be evaluated next:
1. (define x 0) (define y 1) (begin(set! x 3)
(set! y 4) (+ (* x x) (* y y))) 2. (define x 0) (set! x (cond [(zero?x
) 1] [else 0])) 3. (define (f x) (cond [(zero? x) 1] [else 0])) (begin(set! f 11)
f)
Rewrite the three programs to show the next state. Solution
Exercise 38.3.3. Evaluate the following programs:
1. (define x 0) (define (bump delta) (begin (set! x (+ x delta)) x)) (+ (bump 2) (bump 3)) 2. (define x 10) (set! x (cond [(zeor? x) 13] [else (/ 1 x)])) 3. (define (makebox x) (local ((define contents x) (define (new y) (set! contents y)) (define (peek) contents)) (list new peek))) (define B (makebox 55)) (define C (makebox 'a)) (begin ((first B) 33) ((second C)))
Underline for each step the subexpression that must be evaluated next. Show only those steps that involve a localexpression or a set!expression. Solution
In principle, we could work with the rules we just discussed. They cover
the common cases, and they explain the behavior of the programs we have
encountered. They do not explain, however, how an assignment works when the
lefthand side refers to a define
d function. Consider the
following example, for which the rules still work:
(define (f x) x)
(begin
(set! f 10)
f)
= (define f 10)
(begin
(void)
f)
Here f
is a state variable. The set!expression changes the definition
so f
stands for a number. The next step in an evaluation
substitutes 10
for the occurrence of f
.
Under ordinary circumstances, an assignment would replace a function definition with a different function definition. Take a look at this program:
(define (f x) x)
(define g f)
(+ (begin (set! f (lambda (x) 22))
5) (g 1))
The purpose of the underlined set!expression is to modify the definition of
f
so that it becomes a function that always produces 22
.
But g
stands for f
initially. Since f
is a the
name of a function, we can think of (define g f)
as a value
definition. The problem is that our current rules change the definition of
f
and, by implication, the definition of g
, because it
stands for f
:
= (define f (lambda (x) 22)) (define g f) (+(begin (void) 5)
(g 1)) = (define f (lambda (x) 22)) (define g f) (+ 5(g 1)
) = (define f (lambda (x) 22)) (define g f) (+ 5 22)
Scheme, however, does not behave this way. A set!expression can modify only one
definition at a time. Here it modifies two: f
's, which is
intended, and g
's, which happens through the indirection from
g
to f
. In short, our rules do not explain the behavior
of all programs with set!expressions; we need better rules if we wish to
understand Scheme fully.

The problem concerns the definitions of functions, which suggests that we take a second look at the representation of functions and function definitions. So far, we used the names of functions as values. As we have just seen, this choice may cause trouble in case the state variable is a function. The solution is to use a concrete representation of functions. Fortunately, we already have one in Scheme: lambdaexpressions. Furthermore, we rewrite function definitions so that they turn into variable definitions with a lambdaexpression on the righthand side:
(define (f x) x) = (define f (lambda (x) x))
Even recursive definitions are evaluated in this manner:
(define (g x) (cond [(zero? x) 1] [else (g (sub1 x))])) = (define g (lambda (x) (cond [(zero? x) 1] [else (g (sub1 x))])))
All other rules, including the rule for replacing variables with their values, remain the same.
Figure 112 specifies the set of values,^{73} as a subset of the set of expressions, and the set of value definitions, as a subset of the definitions. Using these definitions and the modified rules, we can take a second look at at the above example:
(define (f x) x)
(define g f) (+ (begin (set! f (lambda (x) 22)) 5) (g 1)) = (define f (lambda (x) x)) (define gf
) (+ (begin (set! f (lambda (x) 22)) 5) (g 1)) = (define f (lambda (x) x)) (define g (lambda (x) x)) (+ (begin(set! f (lambda (x) 22))
5) (g 1)) = (define f (lambda (x) 22)) (define g (lambda (x) x)) (+(begin (void) 5)
(g 1)) = (define f (lambda (x) 22)) (define g (lambda (x) x)) (+ 5(g 1)
) = (define f (lambda (x) 22)) (define g (lambda (x) x)) (+ 5 1)
The key difference is that the definition of g
directly associates
the variable with a function representation, not just a name for a
function.
The following program shows the effects of set!expressions on functions with an extreme example:
(define (f x) (cond [(zero? x) 'done] [else (f (sub1 x))])) (define g f) (begin (set! f (lambda (x) 'ouch)) (symbol=? (g 1) 'ouch))
The function f
is recursive on natural numbers and always produces
'done
. Initially, g
is defined to be f
. The
final beginexpression first modifies f
and then uses g
.
At first, we must rewrite the function definitions according to our modified rules:
= (define f (lambda (x) (cond [(zero? x) 'done] [else (f (sub1 x))]))) (define gf
) (begin (set! f (lambda (x) 'ouch)) (symbol=? (g 1) 'ouch)) = (define f (lambda (x) (cond [(zero? x) 'done] [else (f (sub1 x))]))) (define g (lambda (x) (cond [(zero? x) 'done] [else (f (sub1 x))]))) (begin(set! f (lambda (x) 'ouch))
(set! f (lambda (x) 'ouch)) (symbol=? (g 1) 'ouch))
Rewriting the definition of f
is straightforward. The major change
concerns the definition of g
. Instead of f
it now
contains a copy of the value for which f
currently stands. This
value contains a reference to f
, but that is not unusual.
Next, the set!expression modifies the definition of f
:
...
= (define f
(lambda (x)
'ouch))
(define g
(lambda (x)
(cond
[(zero? x) 'done]
[else (f (sub1 x))])))
(begin
(void)
(symbol=? (g 1)
'ouch))
No other definition, however, is affected.
In particular, the definition of g
remains the same, though the
f
inside of g
's value now refers to a new value. But we
have seen this phenomenon before. The next two steps follow the basic rules
of intermezzo 1:
... = (define f (lambda (x) 'ouch)) (define g (lambda (x) (cond [(zero? x) 'done] [else (f (sub1 x))]))) (begin (void) (symbol=? (f 0) 'ouch)) = (define f (lambda (x) 'ouch)) (define g (lambda (x) (cond [(zero? x) 'done] [else (f (sub1 x))]))) (begin (void) (symbol=? 'ouch 'ouch))
That is, the application of g
eventually applies f
to
0
, which yields 'ouch
. Hence the final result is
true
.
Exercise 38.3.4.
Validate that the following program evaluates to true
:
(define (makebox x) (local ((define contents x) (define (new y) (set! contents y)) (define (peek) contents)) (list new peek))) (define B (makebox 55)) (define C B) (and (begin ((first B) 33) true) (= (second C) 33) (begin (set! B (makebox 44)) (= (second C) 33)))
Underline for each step the subexpression that must be evaluated next. Show only those steps that involve a localexpression or a set!expression. Solution
While we decided to rewrite function definitions so that their righthand side are always lambdaexpressions, we stuck with a function application rule that assumes function definitions in the style of Beginning Student Scheme. More concretely, if the definition context contains a definition such as
(define f (lambda (x y) (+ x y)))
and the expression is
(* (f 1 2) 5)
then the next step in the evaluation is
(* (+ 1 2) 5)
For other occasions, however, we just replace variables with the values in the respective definitions. If we followed that rule, we would rewrite
(* (f 1 2) 5)
to
(* ((lambda (x y) (+ x y)) 1 2) 5)
At first glance, this exploration route ends here, because there are no laws for this application.
We can reconcile the two ideas with a new law, suggested by the last expression:
((lambda (x1 ... xn) exp) v1 ... vn) = exp with all x1 ... xn replaced by v1 ... vn
The law serves as a replacement of the law of application from algebra in the study of the foundations of computing. By convention, this law is called the ß_{v} (pronounced ``beta value'') axiom.
Beta and the Lambda Calculus: The orginal ß axiom was formulated by Alonzo Church in the late 1920s as follows:
((lambda (x) exp) exp1) = exp with x replaced by exp1
It does not restrict the argument in a function application to be a value. The interest of Church and other logicians^{74} was to explore the principles of computation, what computation could achieve, and what it couldn't. They confirmed that the axiom and a small sublanguage of Scheme, namely,

The language and the ß axiom became known as the lambda (pronounced: ``lambda'') calculus. Gerald Sussman and Guy L. Steele Jr. later based Scheme on the lambda calculus. In the mid1970s, Gordon Plotkin suggested the ß_{v} axiom as a better method for understanding function applications in programming languages such as Scheme.
The extension of our language with functions as values introduces not only new powers for the programmer but also new possibilities for errors. Recall that there are three kinds of errors: syntax errors, runtime (or semantics) errors, and logical errors. Advanced Student Scheme turns a class of syntactic errors of Beginning Student Scheme into runtime errors. It also introduces a new form of logical error.
Consider the following program:
;;howmanyinlist : (listof X) > N
;; to count how many itemsalist
contains (define (howmanyinlist alist) (cond [empty? (alist)] [else (+ (howmanyinlist (rest alist)) 1)]))
In Beginning Student Scheme or Intermediate Student Scheme,
DrScheme would have signaled a syntax error because alist
is the
parameter to a function but is also used as a function. Because functions
are values in Advanced Student Scheme, DrScheme must now accept
this function definition as syntactially correct. When the function is
applied to empty
or any other list value, however, DrScheme soon
applies empty
to no arguments, which is a runtime error. After
all, lists are not functions. DrScheme signals immediately with an error
message any attempt to apply a nonfunction and stops the evaluation.
The second form of error is logical. That is, a program that suffers from this form of error doesn't produce a syntax or a runtime error message. Instead, it produces wrong answers. Take a look at the following two definitions:
(define flip1 (local ((define state 1)) (lambda () (begin (set! state ( 1 state)) state))))  (define flip2 (lambda () (local ((define state 1)) (begin (set! state ( 1 state)) state)))) 
local
definition whose body evaluates to a function. The other defines a function
whose body contains a localexpression. According to our rules, the definition on
the left rewrites to
(define state1 1) (define flip1 (lambda () (begin (set! state1 ( 1 state1)) state1)))  (define flip2 (lambda () (local ((define state 1)) (begin (set! state ( 1 state)) state)))) 
The one on the right already associates a name with a function.
Let us now see how the two functions have radically different behaviors. To do so, we evaluate the expressions
(and (= (flip1) 0) (= (flip1) 1) (= (flip1) 0))  (and (= (flip2) 0) (= (flip2) 1) (= (flip2) 0)) 
Here are the first four steps of the evaluation for the expression on the lefthand side:
(define state1 1) (and (= (flip1) 0) (= (flip1) 1) (= (flip1) 0)) = (define state1 1) (and (= (begin (set! state1 ( 1 state1)) state1) 0) (= (flip1) 1) (= (flip1) 0)) = (define state1 1) (and (= (begin (set! state1 0) state1) 0) (= (flip1) 1) (= (flip1) 0)) = (define state1 0) (and (= (begin (void) state1) 0) (= (flip1) 1) (= (flip1) 0)) = (define state1 0) (and (= 0 0) (= (flip1) 1) (= (flip1) 0))
The relevant definition context is the definition of state1
, which
we see changing from 1
to 0
during the third step. From
this point, it is not difficult to validate that the expression produces
true
and that state1
ends up being 0
.
Compare this with the first three steps in the evaluation of the righthand expression:
(and (= (flip2) 0) (= (flip2) 1) (= (flip2) 0)) = (and (= (local ((define state 1)) (begin (set! state ( 1 state)) state)) 0) (= (flip2) 1) (= (flip2) 0)) = (define state1 1) (and (= (begin (set! state1 ( 1 state1)) state1) 0) (= (flip2) 1) (= (flip2) 0)) = (define state1 0) (and (= 0 0) (= (flip2) 1) (= (flip2) 0))
The only definition that matters here is the one for flip2
.
Superficially, the two evaluations are alike. But a closer look shows
that the second one differs from the first in crucial way. It creates the
definition for state1
while the first evaluation started with such
a definition.
Here is the continuation of the second evaluation:
... = (define state1 0) (and true (= (local ((define state 1)) (begin (set! state ( 1 state)) state)) 1) (= (flip2) 0)) = (define state1 0) (define state2 1) (and true (= (begin (set! state2 ( 1 state2)) state2) 1) (= (flip2) 0)) = (define state1 0) (define state2 0) (and true (= (begin (void) state2) 1) (= (flip2) 0)) = (define state1 0) (define state2 0) (and true (= 0 1) (= (flip2) 0))
It shows that flip2
creates a new definition every time it is
applied and that it always produces 0
. Contrary to its name, it
does not flip the value of state
upon every application. As a
result, the evaluation ends now with two new toplevel definitions and the
value false
.
The general moral is that a function defined in a localexpression is different from a function whose body contains a localexpression. The first ensures that some definitions are accessible only to a function. The definition exists once and only once for this function. In contrast, the second creates a new (toplevel) definition for every evaluation of the function body. In the next part of the book, we exploit both ideas to create new kinds of programs.
^{71} The grammar misses andexpression and orexpression, and a few other shortcuts.
^{72} We also evaluate the righthand side of definitions if they are not values, but we can safely ignore this minor issue here.
^{73} It lacks a specification of structural values, but they play no role in this discussion.
^{74} Logic is to computing what mathematics is to physics.