- Due
- Friday, 8 February 2019
- Summary
- We consider the algorithms and structures that Scheme and Racket interpreters use as they evaluates Scheme expressions.
- Prerequisites
- Racket basics. Procedures.
- Disclaimer
- This reading is
*long*. You can feel free to skim a bit. There is a TL;DR section toward the end.

We use the terms “interpreter” and “evaluator” for the programs that read and execute Scheme and Racket programs. To many Scheme and Racket programmers, the interpreter is a bit of a “black box”. That is, you type an expression, the interpreter chugs along for a few milliseconds (or, in some cases, much longer), and then produces an answer.

It is certainly possible to use Racket without knowing anything about how DrRacket and other interpreters evaluate expressions. However, knowing a bit about the interpreter helps you understand why DrRacket does what it does. And, when things go wrong, knowing a bit about the interpreter can help you resolve problems.

It is neither possible nor appropriate to cover every aspect of the Racket interpreter this early in your study of DrRacket. You don’t know all of the Racket language and you don’t know all of the computational and algorithmic techniques that are central to the interpreter. Nonetheless, you know enough to get a simplified, high-level overview of the interpreter. And, as we suggested, having that overview will prove of benefit.

At this point, you’ve encountered approximately six different kinds of expressions in Racket.

*Simple values*: The basic building blocks of more complex expressions, values like 2.4 and “hello”.*Procedure calls*: Expressions that involve applying some procedure, such as`+`

, to some values, such as`2.4`

and`5`

. Procedure calls are surrounded by parentheses, which is how the Racket interpreter knows that they are procedure calls.*Simple definitions*: Definitions, which use the keyword`define`

, associate an identifier, such as`homework1`

, with a corresponding value, such as`90`

or`"A-"`

.*Procedure definitions*: As you’ve recently scene, one form of procedure definitions uses both the keyword`define`

and the keyword`lambda`

.*Identifiers*: Identifiers are the words that we have given meaning to with`define`

. Parameters are the words that represent inputs to a procedure. We usually consider parameters a form of identifier.*Lists*: You’ve generally seen lists as output, such as from the`string-split`

operation. Since you will not study lists in depth until later in the semester, this reading will provide only a bit about lists.

As you might expect, the Racket interpreter uses a slightly different process to evaluate each kind of expression. We will consider each in turn, exploring examples and related issues along the way.

You may recall that computer science is the study of algorithms *and*
data structures. That is, we describe not only processes, but ways of
organizing information. The Racket interpreter uses a variety of data
structures.

One important structure is a *dictionary* it uses to look up each
identifier it encounters. The interpreter must update the dictionary
when it encounters a definition or a procedure call. We will represent
the dictionary as a table. For example, we would use something like the
following table to represent the definition `(define`

`homework1`

`90)`

.

```
IDENTIFIER VALUE TYPE
homework1 90 exact integer
```

Evaluation is traditionally at least a two-step process. First, the interpreter “parses” the textual input, turning it into an internal representation of the input. Next, the interpreter evaluates that internal representation. Let’s consider a few expressions.

- The parser inteprets the expression “
`2`

” as the exact integer*value*`2`

. - The parser interprets the expression “
`x`

” as the*identifier*`x`

. The parser does not check whether or not`x`

has been defined. - The parser interprets the expression “
`'x`

” as the*symbol*`x`

. Names and symbols look quite similar. However, Racket treats them differently. - The parser interprets the expression “
`(define x 5)`

” as a*compound expression*with three elements. Element 0 is the*keyword*`define`

. Element 1 is the identifier`x`

. Element 2 is the exact integer value`5`

. (You’ll note we number starting at zero. For reasons you may have discovered already and which we’ll return to later in this semester, computer scientists tend to count elements starting with the value zero rather than the value one.) - The parser interprets the expression “
`1/3`

” as the exact rational`1/3`

. - The parser interprets the expression “
`"Hello"`

” as the string value`"Hello"`

. - The parser interprets the expression “
`*`

” as the identifier`*`

. You’ll note that we’ve said that`*`

is a identifier, rather than either a keyword or the multiplication procedure. Racket has a somewhat limited set of keywords, and, as you may have noted, expressions that involve keywords behave somewhat differently. You can’t, for example, redefine a keyword. You can, however, redefine a identifier (including`*`

). Different parsers may have different approaches to parsing keywords. Some may identify keywords early, as we have done. Others may wait until evaluation to determine whether a identifier is a keyword. - The parser interprets the expression “
`(* 7 x 11)`

” as a compound expression with four elements. Element 0 is the identifier`*`

. Element 1 is the exact integer value`7`

. Element 2 is the identifier`x`

. Element 3 is the exact integer value`11`

. - The parser interprets the expression “
`'(8 "aitch" h)`

” as a*list*with three elements. Element 0 is the exact integer value`8`

. Element 1 is the string value`"aitch"`

. Element 2 is the symbol`h`

. That last part may be a bit surprising. Why is it the symbol`h`

rather than the identifier`h`

? Because the outer tick mark signifies that any words that follow represent symbols. - The parser interprets the expression “
`(* x (+ 8 1/2 x))`

” as a compound expression with three elements. Element 0 is the identifier`*`

. Element 1 is the identifier`x`

. Element 2 is another compound expression, one of four elements. Element 0 is the identifier`+`

. Element 1 is the exact integer value`8`

. Element 2 is the exact rational value`1/2`

. Element 3 is the identifier`x`

.

You may note that there is some potential confusion in that last
compound expression, since we have two element 0’s, two element
1’s, and two element 2’s. Hence, we often display parsed expressions
using a format in which indentation helps indicate which expression
each value belongs to. For example, we might represent
`(define y (* 2 (+ x 1/2) x))`

as follows.

```
compound-expression/3:
0: keyword:define
1: id:y
2: compound-expression/4:
0: id:*
1: value:2 (exact integer)
2: compound-expression/3:
0: id:+
1: id:x
2: value:1/2 (exact rational)
3: id: x
```

Most experienced Racket and Scheme programmers subconsciously translate the code they type into this kind of representation. That is, they know what things they’ve entered are compound expressions, keywords, identifiers, and values. They also often keep track of the type of each value and it’s place in nesting of compound expressions.

Note that Racket has its own internal representation of most of the
basic types of values. Conceptually, every computer ends up
representing most values as a sequence of 0’s and 1’s and has a set of
rules for how those sequences are interpreted. You need not
understand that internal representation to know that `5`

is the
exact integer 5, that `1.2`

is the inexact real 1.2, or that `3/5`

is the exact rational number 3/5.

So, how does the parser translate the text of a Racket expression into an internal structure? The algorithm is, or should be, relatively straightforward.

```
To read the next expression
---------------------------
Skip over any whitespace (space, tab, newline, etc.) and comments.
Look at the next character.
If the next character is an open parenthesis, we have a compound expression
Skip over the open parenthesis
Read each subexpression, one by one, until you reach the end
Skip over the close parenthesis
Combine the portions into a compound expression
Otherwise, if the next character is a tick mark
Look at the following character
If it is an open parenthesis
Follow the instructions for reading a compound expression,
except that you treat all non-numeric words as symbols,
rather than identifiers or keywords. Return that compound
expression as a list value.
Otherwise,
Read the next word
If it takes the form of a number,
Treat it like a number
Otherwise,
Treat it as a symbol
Otherwise, if the next character is a double-quotation mark, "
Read until you find the matching double-quotation mark
Combine all the characters you've read into a string value.
Otherwise (that is, for any other character)
Read the next word
If the word is one of the keywords (define, lambda, etc.)
Convert the word to a keyword
Otherwise, if the word has the form of an exact integer
Convert the word to an exact integer, using the appropriate
internal representation for integers
Otherwise, if the word has the form of a rational number
Convert the word to a rational number
Otherwise, if the word has the form of an inexact real number
Convert the word to an inexact number
Otherwise
Convert the word to an identifier
```

Of course, some aspects of these instructions are a bit vague. What is “the form of an exact integer” or “the form of a rational number”? Here are some approximate definitions.

- An
*exact integer*is a sequence of digits with an optional leading`+`

or`-`

. So`11`

is an exact integer, as are`-11`

and`+11`

. However,`++11`

is not an exact integer because it has more than one leading`+`

,`11.0`

is not an exact integer because it has a decimal point,`11x`

is not an exact integer because it has a non-digit character, and so on and so forth. What is`11x`

? It’s not an exact rational, an inexact real, or a complex number, so it must be an identifier. (We would not recommend that you use it as an identifier, even though you can.) - An
*exact rational*is a sequence of digits with an optional leading`+`

or`-`

, a slash, and another sequence of digits. Hence,`7/11`

,`+7/11`

, and`-7/11`

are all exact rational numbers. However,`7.0/11`

is not because it contains a decimal point and`7/+11`

is not because because it contains a`+`

in a position other than the front. What are these two words? They are both identifiers. - An
*inexact real number*is a sequence of digits with an optional leading`+`

or`-`

as well as a decimal point or an exponential portion or both. An exponential portion is the letter e, an optional`+`

or`-`

, and a sequence of digits. For example,`11.7`

,`+11.7`

`-11.7`

,`11e7`

,`11e-7`

and`-11e+7`

are all inexact numbers.`11.`

is also an inexact number. For the time being, we will not distinguish inexact real numbers from inexact integers. - A
*complex number*is a number (one of the three kinds we’ve just listed), a`+`

or`-`

, an unsigned number, and the letter`i`

. If both numbers are exact, the complex number is also exact. If either number is inexact, the complex number is inexact.`7+11i`

is an exact complex number, as are`-7+11i`

,`-7-11i`

, and`7-11i`

. However,`7+-11`

is not a complex number.

But what about the “word” that we are supposed to read? Racket and
Scheme are fairly generous about the words and identifiers they permit.
In most situations, a word is a sequence of standard characters that
does not include whitespace, parentheses, square brackets, curly braces,
a tick mark, a backtick, a semicolon, an octothorpe (hash, pound
sign), or a double quotation mark. So, as strange as it may seem,
`3+-4`

is a valid identifier, as are `x/3`

, `x++`

, `+---+`

, and many
other things it would be hard to conceive of.

```
> (define 3++ 11)
> 3++
11
> (define 3/-4 -2)
> 3/-4
-2
> (define +----+ *)
> (+----+ 3++ 3/-4)
-22
```

Note that just because things are possible does not mean that they are a
good idea. Defining `3/-4`

as `2`

is likely to confuse the reader.
Racket gives you great power. Use it wisely.

Let’s consider a simple parsing example. The vertical bar, `|`

shows
where we are in the input.

```
**remaining input** **action** **notes**
|(define x (+ 3 y)) Skip whitespace None
|(define x (+ 3 y)) Look at next char next:(
|(define x (+ 3 y)) If open paren Yes
(|define x (+ 3 y)) Read subexp In compound
(|define x (+ 3 y)) Skip whitespace None; In compound
(|define x (+ 3 y)) Look at next char next:d; In compound
(|define x (+ 3 y)) If open paren No; In compound
(|define x (+ 3 y)) If tick mark No; In compound
(|define x (+ 3 y)) If double quote No; In compound
(|define x (+ 3 y)) Otherwise ... In compound
(|define x (+ 3 y)) Read the next word In compound
(define| x (+ 3 y)) word:define; In compound
(define| x (+ 3 y)) If keyword Yes; word:define; In compound
(define| x (+ 3 y)) Convert to keyword In compound [0:keyword:define]
(define| x (+ 3 y)) Read subexp In compound [0:keyword:define]
(define| x (+ 3 y)) Skip whitespace Yes; In compound [0:keyword:define]
(define |x (+ 3 y)) Look at next char char:x; In compound [0:keyword:define]
(define |x (+ 3 y)) If open paren No; In compound [0:keyword:define]
(define |x (+ 3 y)) If tick mark No; In compound [0:keyword:define]
(define |x (+ 3 y)) If double quote No; In compound [0:keyword:define]
(define |x (+ 3 y)) Otherwise ... No; In compound [0:keyword:define]
(define |x (+ 3 y)) Read the next word In compound [0:keyword:define]
(define x| (+ 3 y)) word:x; In compound [0:keyword:define]
(define x| (+ 3 y)) If keyword No; In compound [0:keyword:define]
(define x| (+ 3 y)) If exact int No; In compound [0:keyword:define]
(define x| (+ 3 y)) If rational No; In compound [0:keyword:define]
(define x| (+ 3 y)) If inexact No; In compound [0:keyword:define]
(define x| (+ 3 y)) If complex No; In compound [0:keyword:define]
(define x| (+ 3 y)) Otherwise ... In compound [0:keyword:define]
(define x| (+ 3 y)) Convert to id In compound [0:k:d,1:id:x]
(define x| (+ 3 y)) Read subexp In compound [0:k:d,1:id:x]"
(define x (+ 3 y)|) _magic_ In compound [0:k:d,1:id:x,2:compound[...]]
(define x (+ 3 y)|) Until you reach the end Yes; In compound [0:k:d,1:id:x,2:compound[...]]
(define x (+ 3 y)|) Skip over In compound [0:k:d,1:id:x,2:compound[...]]
(define x (+ 3 y))| Skip over In compound [0:k:d,1:id:x,2:compound[...]]
(define x (+ 3 y))| Combine the portions In compound [0:k:d,1:id:x,2:compound[...]]
```

After all those steps, including the elided parsing of `(+ 3 y)`

, we end
up with the following.

```
compound-expression/3
0: keyword:define
1: id:x
2: compound-expression/3
0: id:+
1: value:3 (exact integer)
2: id:y
```

*Note*: This parsing algorithm may seem a bit complex. And it is.
However, the real parsing algorithm is even more complex. For
example, the parameter list and body in a `lambda`

expression are
parsed in a different way than other parenthesized expressions.
We’ll leave those complexities as an issue for future consideration.

Now that we’ve parsed the expression (or, more accurately, now that
the interpreter has parsed the expression), it’s time to evaluate
the expression. As you may recall, in the notes above, we considered
six different kinds of expressions: simple values, procedure calls,
simple definitions, procedure definitions with `lambda`

, identifiers,
and lists. Now that we know how the interpreter parses each
expression into an internal representation, we can consider how to
evaluate the different kinds of expressions.

Note that we’ve only used three structures to represent expressions:
compound expressions, identifiers, and values. Procedure calls, simple
definitions, and procedure definitions all get represented as compound
expressions. Simple values and lists both get represented as values.
However, we can distinguish definitions from calls by checking whether
element 0 is the keyword `define`

or not. And we can distinguish simple
values and lists by checking their type. (However, we need not do so at
the moment.)

Let’s consider how to evaluate each kind of structure.

- To evaluate an
*identifier*, look the identifier up in the dictionary. For example, if our identifier is`x`

and the dictionary associates the exact integer`11`

with`x`

, we return the exact integer`11`

. If the dictionary does not associate any value with`x`

, issue an error. - To evaluate a
*value*, use the value the parser constructed. For example, if the original text contained`7/11`

, the parser identified and stored that as the exact rational number`7/11`

, so we return that. - To evaluate a
*compound expression that starts with*, evaluate element 2 of the compound expression and then put the combination of element 1 and that result into the dictionary. For example, given the structure that corresponds to`define`

`(define x 11)`

, we would update the dictionary to associate`x`

with the exact integer`11`

. - To evaluate a
*compound expression that represents a procedure call*, evaluate all the elements of the expression and then apply the procedure. For example, to evaluate the structure corresponding to`(+ 1 2)`

, the interpreter first evaluates the`+`

, the`1`

, and the`2`

. It can evaluate them in any order; on some machines, it may even evaluates them simultaneously. The`+`

is an identifier, so it looks it up in the dictionary and discovers that it’s the built-in mulitplication operation. The`1`

is an exact integer. The`2`

is also an exact integer. So the interpreter passes`1`

and`2`

to the built-in multiplication operation.

Are those all the kinds of expressions? Not quite. We haven’t really
explained how to evaluate a `lambda`

expression. That’s a complex
enough issue that we’ll leave it for a bit later.

Let’s consider what the interpreter might do upon encountering the following series of expressions. (More precisely, we will consider what the interpreter will do given the parsed versions of those expressions.)

```
(define multiply *)
(define divide /)
(define diameter 17)
(define radius (divide diameter 2))
(multiply pi (expt radius 2))
```

What does the dictionary look like before we’ve run any code? The basic
dictionary associates most of the built-in identifiers with their
associated values. For example, it associates `*`

with the built-in
multiplication procedure and `pi`

with a reasonable approximation
thereof.

```
> *
#<procedure:*>
> pi
3.141592653589793
```

We begin with `(define multiply *)`

, which the parser has likely
represented as follows.

```
compound-expession/3:
0: keyword:define
1: id:multiply
2: id:*
```

That’s a definition, which we can tell because it’s a compound
expression whose element 0 is the keyword `define`

. So we evaluate
element 2, the identifier `*`

. We evaluate identifiers by looking them
up in the table. The basic dictionary maps `*`

to the built-in
multiplication operation that it shows to us as `#<procedure:*>`

. Next,
we update the dictionary to associate that value with `multiply`

.

```
IDENTIFIER VALUE TYPE
multiply #<procedure:*> procedure
```

Note that there is a difference between the identifier `*`

and the
procedure value represented by `#<procedure:*>`

. The first is just an
identifier. The latter is a procedure provided to us by the Scheme or
Racket interpreter. For convenience, we can refer to it as `*`

.
However, it is possible to change meanings, as the following example
suggests.

```
> *
#<procedure:*>
> (define * -)
> *
#<procedure:->
> (* 2 7)
-5
```

Of course, no one in their right mind would use such a definition, except to frustrate others. We include it only to remind you of the difference between the identifier and the underlying procedure.

Returning to our sequence of expressions, our next expression to
evaluate is `(define divide /)`

. That’s similar enough to the first
definition that we won’t go through the details. Our dictionary now
contains the following.

```
IDENTIFIER VALUE TYPE
multiply #<procedure:*> procedure
divide #<procedure:/> procedure
```

The next expression, `(define diameter 17)`

is similar. However, in
this case, `17`

is a value rather than a name, so the interpreter need
not look it up in the dictionary before associating it with `diameter`

.

```
IDENTIFIER VALUE TYPE
multiply #<procedure:*> procedure
divide #<procedure:/> procedure
diameter 17 exact integer
```

Now we’re on to a somewhat more complex expression,
`(define radius (divide diameter 2))`

. Once again, we have a
definition. So the interpreter must evaluate element two of the
compound expression, `(divide diameter 2)`

. Since `divide`

is not
a keyword, it knows that we have a procedure call. The steps for
procedure calls are to evaluate each of the parts.

The interpereter looks up `divide`

in the dictionary. That gives
`#<procedure:/>`

. It looks up `diameter`

in the dictionary. That
gives `17`

. `2`

is an integer, so it need not look it up.

We are now left with `(#<procedure:/> 17 2)`

. The interpreter then
runs the built-in code for the division procedure, using inputs of
`17`

and `2`

. It gives a result of `8 1/2`

, or something simlar.

Where were we? Ah, we were in the middle of the definition of
`radius`

. The interpreter has now evaluated element 2 of the
compound statement, and it’s ready to update the dictionary.

```
IDENTIFIER VALUE TYPE
multiply #<procedure:*> procedure
divide #<procedure:/> procedure
diameter 17 exact integer
radius 8 1/2 exact rational
```

We’re now down to the last expression to evaluate,
`(multiply pi (expt radius 2))`

. Let’s see. That’s
a compound expression which the parsers has likely reprsented
something like the following.

```
compound-expession/3:
0: id:multiply
1: id:pi
2: compound-expression/3:
0: id:expt
1: id:radius
2: value:2 (exact integer)
```

That’s a compound expression that does not involve a keyword.
What does the interpreter do? It evaluates each part.
`multiply`

is an identifier, which it looks up in the dictionary
and finds `#<procedure:*>`

. `pi`

is also an identifier which
has the value `3.1415....`

.
The third
part of the compound expresssion is another compound expression.
So, the evaluator checks if it involves a keyword (it doesn’t).

Once again, it evaluates each part of the procedure in turn.
`expt`

is an identifier, naming the built-in procedure
`#<procedure:expt>`

. `radius`

is an identifier which
the dictionary indicates has the value `8 1/2`

(or `17/2`

). The `2`

is a constant. The evaluator is left with
`(#<procedure:expt> 17/2 2)`

. So the evaluator runs the built-in procedure
using those two inputs. That procedure returns `72 1/4`

(or `289/4`

).

Now the interpreter can evaluate the outer expression, which has
boiled down to `(#<procedure:*> 3.141592653589793 289/4)`

It
can then feed those two values to the built-in multiplication
procedure, yielding something like `226.98006922186255`

.

It seems like a lot of work, doesn’t it? But that’s okay; digital computers are good at doing a lot of repetitious work that uses a relatively straightforward algorithm.

We’ve seen how Racket evaluates simple expressions, compound expressions,
and definitions. But what happens when we define our own procedures
using `lambda`

? That’s a bit more complicated. We need to consider
two separate issues: What the Racket interpreter does when it
encounters a lambda expression and what the interpreter does when
it encounters a procedure call in which the procedure is a lambda
expression.

Let’s consider a relatively simple example, a procedure that adds two to its input.

```
(define add2
(lambda (x)
(+ 2 x)))
```

The parser is likely to change that to something like the following.

```
compound-expression/3:
0: keyword:define
1: id:add2
2: compound-expression/3:
0: keyword:lambda
1: compound-expression/1:
0: id:x
2: compound-expression/3:
0: id:+
1: value:2 (exact integer)
2: id:x
```

By now, you know that to evaluate a compound expression that begins
with the keyword `define`

, we evaluate element 2 of the compound
expression and then update the dictionary. But how does the
interpreter evaluate a lambda expession? It turns out that it
doesn’t do it now; the evaluation doesn’t happen until later.
Rather, the interpreter stores the whole lambda expression in
the dictionary. (Although it stores it in the internal form,
we’ll represent it in the form we write.) Before doing so, it
checks to make sure that the expression “makes sense”; for example,
that it only uses names that it knows.

```
IDENTIFIER VALUE TYPE
add2 (lambda (x) (+ 2 x)) lambda expression
```

Now let’s consider what happens when we write `(add2 5)`

. As
you have likely guessed, the parser first converts that to an
internal representation.

```
compound-expression/2:
0: id:add2
1: val:5 (exact integer)
```

The interpreter has a compound expression that does not involve a keyword. So it evaluates each part of the compound expression and then applies the procedure it expects to find in position 0.

Let’s see. `add2`

is an identifier, so the interpreter looks it
up in the dictionary. It finds the lambda expression
`(lambda (x) (+ 2 x))`

. It looks a `5`

and finds a constant value.
It is now left with something a bit strange.

```
((lambda (x) (+ 2 x)) 5)
```

The interpeter then plunges ahead. The value in the procedure position is not a built-in procedure, but rather a lambda expression. So it uses the algorithm for applying lambda expressions. What is that algorithm? It goes something like the following.

```
To apply a lambda expression
----------------------------
Inputs:
* A lambda expression of the form (lambda (param1 param2 ...) body)
* Arguments arg1 arg2 ...
Verify that the number of arguments equals the number of parameters
For each pair of parameter and corresponding argument
Add the parameter and the argument to the dictionary
Evaluate the body
Remove the things we've added to the dictionary
Return the value of the body
```

What does that all mean? Let’s look.

Our lambda expession has the form `(lambda (x) (+ 2 x))`

. There’s
one parameter, `x`

. The body is `(+ 2 x)`

. It would make sense
to call this on, say, the value 5. It would not make sense to
call it with no arguments. It would not make sense to call it with
two or more arguments. So our first step is to check the number
of arguments. We have only one argument. All is good.

What next? We put the parameter/argument pair in the dictionary. Our dictionary now looks like the following (we’ve put in a line to separate the variables for the procedure from those we’ve defined globally).

```
IDENTIFIER VALUE TYPE
add2 (lambda (x) (+ 2 x)) lambda expression
---
x 5 exact integer
```

Next, the interpreter evaluates the body, `(+ 2 x)`

. By
this time, you should know the drill. It’s a compound expression
with no keyword. So it looks up the `+`

, yielding
`#<procedure:+>`

and the `x`

, yielding 5. It now has
to evaluate `(#<procedure:+> 2 5)`

. It passes the `2`

and `5`

to the built-in addition procedure, yielding 7.

But it’s not done yet! That `x`

has been put in the dictionary.
After the lambda expression is done, it should not be there any
more. So *poof*, it gets removed.

```
IDENTIFIER VALUE TYPE
add2 (lambda (x) (+ 2 x)) lambda expression
```

And we’re now done with the evaluation.

What happens when we use the same identifier in different contexts?
For example, suppose we write `(define x 11)`

and then call `(add2 3)`

?
It turns out that Racket is relatively smart. We’ll start with the
dictionary before the call.

```
IDENTIFIER VALUE TYPE
add2 (lambda (x) (+ 2 x)) lambda expression
x 11 exact integer
```

As before, when we call `add2`

, we extract the lambda expression,
giving us `((lambda (x) (+ 2 x)) 3)`

. The algorithm for evaluating
lambdas puts `x`

and `3`

in the dictionary as follows

```
IDENTIFIER VALUE TYPE
add2 (lambda (x) (+ 2 x)) lambda expression
x 11 exact integer
---
x 3 exact integer
```

Note that there are *two* things named `x`

in the dictionary. Which
one does the Racket interpreter use? For now, we should assume it
uses the one most recently added. So when it looks up `x`

, it finds
the value `3`

. As before, it adds 2, this time yielding 5. We’ve
finished the lambda, so we clear out the dictionary.

```
IDENTIFIER VALUE TYPE
add2 (lambda (x) (+ 2 x)) lambda expression
x 11 exact integer
```

Let’s check to see if things worked the way we expected.

```
> (define add2 (lambda (x) (+ 2 x)))
> (define x 11)
> add2
#<procedure:add2>
> x
11
> (add2 3)
5
> x
11
```

Yup. They did.

You may have noted that there was one expression we wrote that seemed
a bit strange, `((lambda (x) (+ 2 x)) 5)`

. Is that just an
intermediate internal representation for the computer? No. It
turns out that Racket lets you write a lambda expression wherever
you need a procedure.

```
> (lambda (x) (+ 2 x))
#<procedure>
> ((lambda (x) (+ 2 x)) 5)
7
> ((lambda (x) (+ 2 x)))
Error! #<procedure>: arity mismatch;
Error! the expected number of arguments does not match the given number
Error! expected: 1
Error! given: 0
> ((lambda (x) (+ 2 x)) 5 7)
Error! . #<procedure>: arity mismatch;
Error! the expected number of arguments does not match the given number
Error! expected: 1
Error! given: 2
Error! arguments...:
> ((lambda (x y) (+ (* x y) (/ x y))) 1 3)
3 1/3
```

Will you ever want to write lambda expressions without naming them? It
turns out that there are certain circumstances in which that is quite
useful. We call such uses *anonymous procedures*, since they lack names.

The Racket interpreter goes through two major steps when evaluating
expressions. First, it *parses* the text you type to convert it to
an internal representation. In doing so, it identifies the type of
most values. Second, it *evaluates* that internal representation
according to a somewhat straightforward (but long) set of rules.

In addition to the internal representation, the interpreter relies on a “dictionary” that associates identifiers with values. Those values can be numbers, strings, lists, built-in procedures, and even lambda expressions.

To apply a procedure defined by a lambda expression, we add parameter/argument pairs to the dictionary, evaluate the body, and then clean up the dictionary.

In the discussion of applying lambda expressions to values, we suggested that the Scheme interpreter updates the dictionary and then evaluates the body of the expression. In point of fact, the actual semantics of variables are a bit more complicated and, in some cases, depend on where they appear in the program code rather than where they are used in a running program. Hence, the claim that the interpreter simply updates the dictionary is a simplification, albeit a useful one. For most of the code you write in this class (and elsewhere), the simplification is acceptable. However, there are some cases in which the simplification breaks down. We’ll mention them when they occur.

For those who like esoteric terminology, the model we’ve given you is
*dynamically scoped*, with the meaning of each variable determined by
its context at the time the program is evaluated. However, the Scheme
language is actually *statically scoped*, with the meaning of each
variable determined. For those of you who don’t like esoteric
terminology, ignore the preceding two sentences. (We thought about
telling you to ignore the whole paragraph, but that means you would have
to ignore the instruction telling you to ignore the paragraph, which
could lead to some confusion.)

Give the internal representation of the following expression.

```
(define a (* (+ p q r s) 3))
```

What are the roughly eight steps that the Scheme evaluator will do as it evaluates the following expression.

```
(define exp (/ (+ 7 8 9) count))
```

This section draws upon How Scheme evaluates expressions (take 1) and How Scheme evaluates expressions (take 2) from Grinnell College’s CSC 151. Samuel A. Rebelsky wrote the original version. A variety of other folks (particularly Janet Davis and Jerod Weinman) made substantial updates.