{+ 3 4}
returns (list ’+ 3 4), and to
{+ {- 3 4} 7}
returns (list ’+ (list ’- 3 4) 7).
The read primitive is a crown jewel of Lisp and Scheme. It reduces what are conventionally two quite
elaborate phases, called tokenizing (or scanning) and parsing, into three different phases: tokenizing, reading
and parsing. Furthermore, it provides a single primitive that does the first and second, so all that’s left to do
is the third. read returns a value known as an s-expression.
The parser needs to identify what kind of program it’s examining, and convert it to the appropriate
abstract syntax. To do this, it needs a clear specification of the concrete syntax of the language. We’ll
use Backus-Naur Form (BNF), named for two early programming language pioneers. A BNF description of
rudimentary arithmetic looks like this:
<AE> ::= <num>
| {+ <AE> <AE>}
| {- <AE> <AE>}
The <AE> in the BNF is called a non-terminal, which means we can rewrite it as one of the things on the
right-hand side. Read ::= as “can be rewritten as”. Each | presents one more choice, called a produc-
tion. Everything in a production that isn’t enclosed in <· · ·> is literal syntax. (To keep the description
simple, we assume that there’s a corresponding definition for <num>, but leave its precise definition to your
imagination.) The <AE>s in the productions are references back to the <AE> non-terminal.
Notice the strong similarity between the BNF and the abstract syntax representation. In one stroke, the
BNF captures both the concrete syntax (the brackets, the operators representing addition and subtraction)
and a default abstract syntax. Indeed, the only thing that the actual abstract syntax data definition contains
that’s not in the BNF is names for the fields. Because BNF tells the story of concrete and abstract syntax so
succintly, it has been used in definitions of languages ever since Algol 60, where it first saw use.
8
CHAPTER 1. MODELING LANGUAGES
Assuming all programs fed to the parser are syntactically valid, the result of reading must be either a
number, or a list whose first value is a symbol (specifically, either ’+ or ’-) and whose second and third
values are sub-expressions that need further parsing. Thus, the entire parser looks like this:2
;; parse : sexp −→ AE
;; to convert s-expressions into AEs
(define (parse sexp)
(cond
[(number? sexp) (num sexp)]
[(list? sexp)
(case (first sexp)
[(+) (add (parse (second sexp))
(parse (third sexp)))]
[(-) (sub (parse (second sexp))
(parse (third sexp)))])]))
Here’s the parser at work. The first line after each invocation of (parse (read)) is what the user types;
the second line after it is the result of parsing. This is followed by the next prompt.
Language: PLAI - Advanced Student.
> (parse (read))
3
(num 3)
> (parse (read))
{+ 3 4}
(add (num 3) (num 4))
> (parse (read))
{+ {- 3 4} 7}
(add (sub (num 3) (num 4)) (num 7))
This, however, raises a practical problem: we must type programs in concrete syntax manually every
time we want to test our programs, or we must pre-convert the concrete syntax to abstract syntax. The
problem arises because read demands manual input each time it runs. We might be tempted to use an
intermediary such as a file, but fortunately, Scheme provides a handy notation that lets us avoid this problem
entirely: we can use the quote notation to simulate read. That is, we can write
Language: PLAI - Advanced Student.
> (parse ’3)
(num 3)
> (parse ’{+ 3 4})
(add (num 3) (num 4))
2This is a parser for the whole language, but it is not a complete parser, because it performs very little error reporting: if a user
provides the program {+ 1 2 3}, which is not syntactically legal according to our BNF specification, the parser silently ignores
the 3 instead of signaling an error. You must write more robust parsers than this one.
1.4. PRIMUS INTER PARSERS
9
> (parse ’{+ {- 3 4} 7})
(add (sub (num 3) (num 4)) (num 7))
This is the last parser we will write in this book. From now on, you will be responsible for creating
a parser from the concrete syntax to the abstract syntax. Extending the parser we have seen is generally
straightforward because of the nature of syntax we use, which means it would be worthwhile to understand
the syntax better.
1.4
Primus Inter Parsers
Most languages do not use this form of parenthesized syntax. Writing parsers for languages that don’t is
much more complex; to learn more about that, study a typical text from a compilers course. Before we drop
the matter of syntax entirely, however, let’s discuss our choice—parenthetical syntax—in a little more depth.
I said above that read is a crown jewel of Lisp and Scheme. In fact, I think it’s actually one of the great
ideas of computer science. It serves as the cog that helps decompose a fundamentally difficult process—
generalized parsing of the input stream—into two very simple processes: reading the input stream into an
intermediate representation, and parsing that intermediate representation. Writing a reader is relatively sim-
ple: when you see a opening bracket, read recursively until you hit a closing bracket, and return everything
you saw as a list. That’s it. Writing a parser using this list representation, as we’ve seen above, is also a
snap.
I call these kinds of syntaxes bicameral,3 which is a term usually used to describe legislatures such as
that of the USA. No issue becomes law without passing muster in both houses. The lower house establishes
a preliminary bar for entry, but allows some rabble to pass through knowing that the wisdom of the upper
house will prevent excesses. In turn, the upper house can focus on a smaller and more important set of
problems. In a bicameral syntax, the reader is, in American terms, the House of Representatives: it rejects
the input
{+ 1 2)
(mismatched delimiters) but permits both of
{+ 1 2}
{+ 1 2 3}
the first of which is legal, the second of which isn’t in our arithmetic language. It’s the parser’s (Senate’s)
job to eliminate the latter, more refined form of invalid input.
Exercise 1.4.1 Based on this discussion, examine XML. What do the terms well-formed and valid mean,
and how do they differ? How do these requirements relate to bicameral syntaxes such as that of Scheme?
3Two houses.
10
CHAPTER 1. MODELING LANGUAGES
Part II
Rudimentary Interpreters
11
Chapter 2
Interpreting Arithmetic
Having established a handle on parsing, which addresses syntax, we now begin to study semantics. We will
study a language with only numbers, addition and subtraction, and further assume both these operations are
binary. This is indeed a very rudimentary exercise, but that’s the point. By picking something you know
well, we can focus on the mechanics. Once you have a feel for the mechanics, we can use the same methods
to explore languages you have never seen before.
The interpreter has the following contract and purpose:
;; calc : AE −→ number
;; consumes an AE and computes the corresponding number
which leads to these test cases:
(test (calc (parse ’3)) 3)
(test (calc (parse ’{+ 3 4})) 7)
(test (calc (parse ’{+ {- 3 4} 7})) 6)
(notice that the tests must be consistent with the contract and purpose statement!) and this template:
(define (calc an-ae)
(type-case AE an-ae
[num (n) · · ·]
[add (l r) · · · (calc l) · · · (calc r) · · ·]
[sub (l r) · · · (calc l) · · · (calc r) · · ·]))
In this instance, we can convert the template into a function easily enough:
(define (calc an-ae)
(type-case AE an-ae
[num (n) n]
[add (l r) (+ (calc l) (calc r))]
[sub (l r) (- (calc l) (calc r))]))
Running the test suite helps validate our interpreter.
13
14
CHAPTER 2. INTERPRETING ARITHMETIC
What we have seen is actually quite remarkable, though its full power may not yet be apparent. We have
shown that a programming language with just the ability to represent structured data can represent one of
the most interesting forms of data, namely programs themselves. That is, we have just written a program
that consumes programs; perhaps we can even write programs that generate programs. The former is the
foundation for an interpreter semantics, while the latter is the foundation for a compiler. This same idea—
but with a much more primitive language, namely arithmetic, and a much poorer collection of data, namely
just numbers—is at the heart of the proof of Gödel’s Theorem.
Chapter 3
Substitution
Even in a simple arithmetic language, we sometimes encounter repeated expressions. For instance, the
Newtonian formula for the gravitational force between two objects has a squared term in the denominator.
We’d like to avoid redundant expressions: they are annoying to repeat, we might make a mistake while
repeating them, and evaluating them wastes computational cycles.
The normal way to avoid redundancy is to introduce an identifier.1 As its name suggests, an identifier
names, or identifies, (the value of) an expression. We can then use its name in place of the larger compu-
tation. Identifiers may sound exotic, but you’re used to them in every programming language you’ve used
so far: they’re called variables. We choose not to call them that because the term “variable” is semantically
charged: it implies that the value associated with the identifier can change (vary). Since our language ini-
tially won’t offer any way of changing the associated value, we use the more conservative term “identifier”.
For now, they are therefore just names for computed constants.
Let’s first write a few sample programs that use identifiers, inventing notation as we go along:
{with {x {+ 5 5}} {+ x x}}
We will want this to evaluate to 20. Here’s a more elaborate example:
{with {x {+ 5 5}}
{with {y {- x 3}}
{+ y y}}}
[+ operation]
= {with {x 10} {with {y {- x 3}} {+ y y}}}
[substitution]
= {with {x 10} {with {y {- 10 3}} {+ y y}}}
[descent]
= {with {y {- 10 3}} {+ y y}}
[- operation]
= {with {y 7} {+ y y}}
[substitution]
= {with {y 7} {+ 7 7}}
[descent]
= {+ 7 7}
[+ operation]
= 14
1As the authors of Concrete Mathematics say: “Name and conquer”.
15
16
CHAPTER 3. SUBSTITUTION
En passant, notice that the act of reducing an expression to a value requires more than just substitution;
indeed, it is an interleaving of substitution and calcuation steps. Furthermore, when we have completed
substition we “descend” into the inner expression to continue calculating.
Now let’s define the language more formally. To honor the addition of identifiers, we’ll give our language
a new name: WAE, short for “with with arithmetic expressions”. Its BNF is:
<WAE> ::= <num>
| {+ <WAE> <WAE>}
| {- <WAE> <WAE>}
| {with {<id> <WAE>} <WAE>}
| <id>
Notice that we’ve had to add two rules to the BNF: one for associating values with identifiers and another for
actually using the identifiers. The nonterminal <id> stands for some suitable syntax for identifiers (usually
a sequence of alphanumeric characters).
To write programs that process WAE terms, we need a data definition to represent those terms. Most
of WAE carries over unchanged from AE, but we must pick some concrete representation for identifiers.
Fortunately, Scheme has a primitive type called the symbol, which serves this role admirably.2 Therefore,
the data definition is
(define-type WAE
[num (n number?)]
[add (lhs WAE?) (rhs WAE?)]
[sub (lhs WAE?) (rhs WAE?)]
[with (name symbol?) (named-expr WAE?) (body WAE?)]
[id (name symbol?)])
We’ll call the expression in the named-expr field the named expression, since with lets the name in the id
field stand in place of that expression.
3.1
Defining Substitution
Without fanfare, we used substitution to explain how with functions. We were able to do this because
substitution is not unique to with: we’ve studied it for years in algebra courses, because that’s what happens
when we pass arguments to functions. For instance, let f (x, y) = x3 + y3. Then
f (12, 1) = 123 + 13 = 1728 + 1 = 1729
f (10, 9) = 103 + 93 = 1000 + 729 = 1729 3
Nevertheless, it’s a good idea to pin down this operation precisely.
2In many languages, a string is a suitable representation for an identifier. Scheme does have strings, but symbols have the
salutary property that they can be compared for equality in constant time.
3What’s the next smallest such number?
3.1. DEFINING SUBSTITUTION
17
Let’s make sure we understand what we’re trying to define. We want a crisp description of the process
of substitution, namely what happens when we replace an identifier (such as x or x) with a value (such as 12
or 5) in an expression (such as x3 + y3 or {+ x x}).
Recall from the sequence of reductions above that substitution is a part of, but not the same as, cal-
culating an answer for an expression that has identifiers. Looking back at the sequence of steps in the
evaluation example above, some of them invoke substitution while the rest are calcuation as defined for AE.
For now, we’re first going to pin down substitution. Once we’ve done that, we’ll revisit the related question
of calculation. But it’ll take us a few tries to get substitution right!
Definition 1 (Substitution) To substitute identifier i in e with expression v, replace all identifiers in e that
have the name i with the expression v.
Beginning with the program
{with {x 5} {+ x x}}
we will use substitution to replace the identifier x with the expression it is bound to, 5. The definition of
substitution above certainly does the trick: after substitution, we get
{with {x 5} {+ 5 5}}
as we would want. Likewise, it correctly substitutes when there are no instances of the identifier:
{with {x 5} {+ 10 4}}
to
{with {x 5} {+ 10 4}}
(since there are no instances of x in the expression, no substitutions occur). Now consider:
{with {x 5} {+ x {with {x 3} 10}}}
The rules reduce this to
{with {x 5} {+ 5 {with {5 3} 10}}}
Huh? Our substitution rule converted a perfectly reasonable program (whose value is 15) into one that isn’t
even syntactically legal, i.e., it would be rejected by a parser, because the program contains 5 where the BNF
tells us to expect an identifier. We definitely don’t want substitution to have such an effect! It’s obvious that
the substitution algorithm is too na¨ıve. To state the problem with the algorithm precisely, though, we need
to introduce a little terminology.
Definition 2 (Binding Instance) A binding instance of an identifier is the instance of the identifier that
gives it its value. In WAE, the <id> position of a with is the only binding instance.
18
CHAPTER 3. SUBSTITUTION
Definition 3 (Scope) The scope of a binding instance is the region of program text in which instances of the
identifier refer to the value bound by the binding instance.
Definition 4 (Bound Instance) An identifier is bound if it is contained within the scope of a binding in-
stance of its name.
Definition 5 (Free Instance) An identifier not contained in the scope of any binding instance of its name is
said to be free.
With this terminology in hand, we can now state the problem with the first definition of substitution
more precisely: it failed to distinguish between bound instances (which should be substituted) and binding
instances (which should not). This leads to a refined notion of substitution.
Definition 6 (Substitution, take 2) To substitute identifier i in e with expression v, replace all identifiers in
e which are not binding instances that have the name i with the expression v.
A quick check reveals that this doesn’t affect the outcome of the examples that the previous definition
substituted correctly. In addition, this definition of substitution reduces
{with {x 5} {+ x {with {x 3} 10}}}
to
{with {x 5} {+ 5 {with {x 3} 10}}}
Let’s consider a closely related expression:
{with {x 5} {+ x {with {x 3} x}}}
Hopefully we can agree that the value of this program is 8 (the left x in the addition evaluates to 5, the right
x is given the value 3 by the inner with, so the sum is 8). The refined substitution algorithm, however,
converts this expression into
{with {x 5} {+ 5 {with {x 3} 5}}}
which, when evaluated, yields 10.
What went wrong here? Our substitution algorithm respected binding instances, but not their scope.
In the sample expression, the with introduces a new scope for the inner x. The scope of the outer x
is shadowed or masked by the inner binding. Because substitution doesn’t recognize this possibility, it
incorrectly substitutes the inner x.
Definition 7 (Substitution, take 3) To substitute identifier i in e with expression v, replace all non-binding
identifiers in e having the name i with the expression v, unless the identifier is in a scope different from that
introduced by i.
3.1. DEFINING SUBSTITUTION
19
While this rule avoids the faulty substitution we’ve discussed earlier, it has the following effect: after
substitution, the expression
{with {x 5} {+ x {with {y 3} x}}}
whose value should be that of {+ 5 5}, or 10, becomes
{with {x 5} {+ 5 {with {y 3} x}}}
The inner expression should result in an error, because x has no value. Once again, substitution has changed
a correct program into an incorrect one!
Let’s understand what went wrong. Why didn’t we substitute the inner x? Substitution halts at the with
because, by definition, every with introduces a new scope, which we said should delimit substitution. But
this with contains an instance of x, which we very much want substituted! So which is it—substitute
within nested scopes or not? Actually, the two examples above should reveal that our latest definition for
substitution, which may have seemed sensible at first blush, is too draconian: it rules out substitution within
any nested scopes.
Definition 8 (Substitution, take 4) To substitute identifier i in e with expression v, replace all non-binding
identifiers in e having the name i with the expression v, except within nested scopes of i.
Finally, we have a version of substitution that works. A different, more succint way of phrasing this
definition is
Definition 9 (Substitution, take 5) To substitute identifier i in e with expression v, replace all free instances
of i in e with v.
Recall that we’re still defining substitution, not evaluation. Substitution is just an algorithm defined over
expressions, independent of any use in an evaluator. It’s the calculator’s job to invoke substitution as many
times as necessary to reduce a program down to an answer. That is, substitution simply converts
{with {x 5} {+ x {with {y 3} x}}}
into
{with {x 5} {+ 5 {with {y 3} 5}}}
Reducing this to an actual value is the task of the rest of the calculator.
Phew! Just to be sure we understand this, let’s express it in the form of a function.
;; subst : WAE symbol WAE → WAE
;; substitutes second argument with third argument in first argument,
;; as per the rules of substitution; the resulting expression contains
;; no free instances of the second argument
(define (subst expr sub-id val)
(type-case WAE expr
20
CHAPTER 3. SUBSTITUTION
[num (n) expr]
[add (l r) (add (subst l sub-id val)
(subst r sub-id val))]
[sub (l r) (sub (subst l sub-id val)
(subst r sub-id val))]
[with (bound-id named-expr bound-body)
(if (symbol=? bound-id sub-id)
expr
(with bound-id
named-expr
(subst bound-body sub-id val)))]
[id (v) (if (symbol=? v sub-id) val expr)]))
3.2
Calculating with with
We’ve finally defined substitution, but we still haven’t specified how we’ll use it to reduce expressions to
answers. To do this, we must modify our calculator. Specifically, we must add rules for our two new source
language syntactic constructs: with and identifiers.
• To evaluate with expressions, we calculate the named expression, then substitute its value in the
body.
• How about identifiers? Well, any identifier that is in the scope of a with is replaced with a value when
the calculator encounters that identifier’s binding instance. Consequently, the purpose statement of
subst said there would be no free instances of the identifier given as an argument left in the result. In
other words, subst replaces identifiers with values before the calculator ever “sees” them. As a result,
any as-yet-unsubstituted identifier must be free in the whole program. The calculator can’t assign a
value to a free identifier, so it halts with an error.
;; calc : WAE → number
;; evaluates WAE expressions by reducing them to numbers
(define (calc expr)
(type-case WAE expr
[num (n) n]
[add (l r) (+ (calc l) (calc r))]
[sub (l r) (- (calc l) (calc r))]
[with (bound-id named-expr bound-body)
(calc (subst bound-body
bound-id
(num (calc named-expr))))]
[id (v) (error ’calc ”free identifier”)]))
3.3. THE SCOPE OF WITH EXPRESSIONS
21
Observe that the step we earlier labeled “descend” is handled by the recursive invocation of calc. One
subtlety: In the rule for with, the value returned by calc is a number, but subst is expecting a WAE
expression. Therefore, we wrap the result in (num · · ·) so that substitution will work correctly.
Here are numerous test cases. Each one should pass:
(test (calc (parse ’5)) 5)
(test (calc (parse ’{+ 5 5})) 10)
(test (calc (parse ’{with {x {+ 5 5}} {+ x x}})) 20)
(test (calc (parse ’{with {x 5} {+ x x}})) 10)
(test (calc (parse ’{with {x {+ 5 5}} {with {y {- x 3}} {+ y y}}})) 14)
(test (calc (parse ’{with {x 5} {with {y {- x 3}} {+ y y}}})) 4)
(test (calc (parse ’{with {x 5} {+ x {with {x 3} 10}}})) 15)
(test (calc (parse ’{with {x 5} {+ x {with {x 3} x}}})) 8)
(test (calc (parse ’{with {x 5} {+ x {with {y 3} x}}})) 10)
(test (calc (parse ’{with {x 5} {with {y x} y}})) 5)
(test (calc (parse ’{with {x 5} {with {x x} x}})) 5)
3.3
The Scope of with Expressions
Just when we thought we were done, we find that several of the test cases above (can you determine which
ones?) generate a free-identifier error. What gives?
Consider the program
{with {x 5}
{with {y x}
y}}
Common sense would dictate that its value is 5. So why does the calculator halt with an error on this test
case?
As defined, subst fails to correctly substitute in this program, because we did not account for the named
sub-expressions in with expressions. To fix this problem, we simply need to make subst treat the named
expressions as ordinary expressions, ripe for substitution. To wit:
(define (subst expr sub-id val)
(type-case WAE expr
[num (n) expr]
[add (l r) (add (subst l sub-id val)
(subst r sub-id val))]
[sub (l r) (sub (subst l sub-id val)
(subst r sub-id val))]
[with (bound-id named-expr bound-body)
(if (symbol=? bound-id sub-id)
expr
(with bound-id
22
CHAPTER 3. SUBSTITUTION
(subst named-expr sub-id val)
(subst bound-body sub-id val)))]
[id (v) (if (symbol=? v sub-id) val expr)]))