Functional Problem Solving (CSC 151 2014F) : Readings
Primary: [Front Door] [Schedule] - [Academic Honesty] [Disabilities] [Email] - [FAQ] [Teaching & Learning] [Grading] [Rubric] - [Calendar]
Current: [Assignment] [EBoard] [Lab] [Outline] [Reading]
Sections: [Assignments] [EBoards] [Examples] [Handouts] [Labs] [Outlines] [Readings]
Reference: [Setup] [VM] [Errors] - [Functions A-Z] [Functions By Topic] - [Racket] [Scheme Report (R5RS)] [R6RS] [TSPL4]
Related Courses: [Davis (2013F)] [Rebelsky (2014S)] [Weinman (2014F)]
Misc: [Submit Questions] - [SamR] [Glimmer Labs] [CS@Grinnell] [Grinnell] - [Issue Tracker (Course)]
Summary: We consider the algorithm and structures that the Scheme interpreter users to evaluate Scheme expressions.
To many Scheme programmers, the Scheme environment is a bit of a “black box”: You type an expression, the Scheme interpreter chugs along for a few milliseconds (or perhaps longer) and then spits out an answer. It is certainly possible to use Scheme without knowing anything more about the Scheme interpreter. However, we have found that students use Scheme much better when they know a little bit about the way in which Scheme interprets expressions. As importantly, when things go wrong, knowing a bit about the interpreter can help you resolve problems.
Clearly, it's not appropriate to cover every aspect of the Scheme interpreter this early in your experience of Scheme. Hence, we will start with a simple description of the Scheme interpreter and, when you learn new parts of Scheme, we'll add more information about the interpreter.
Right now, you know how to enter four kinds of expressions in Scheme:
2.4
and
"hello"
.
homework1
, with a value, such as 91
,
using the define
keyword.
homework1
just described,
or built-in to Scheme, such as pi
.
We will consider how Scheme evaluates each in turn.
When the Scheme interpreter evaluates expressions, it relies on
a data structure to keep track of information. In particular,
a dictionary associates names with values.
The Scheme interpreter uses the dictionary to look up each name that it
encounters.
The Scheme interpreter updates the dictionary when it encounters a
define
expression.
The evaluation strategy for simple expressions is fairly straightforward: The Scheme interpreter simply converts the human-readable expression to some internal representation. If the simple expression is all that's been typed, it then converts that internal representation back to human-readable form and prints it out.
How does the Scheme interpreter know that it has a simple value to evaluate? If the interpreter sees a digit (0-9) or a minus-sign, it knows that the value is a number, and reads the remaining parts of the number. If the interpreter sees a quotation mark ("), it knows that it has a string and reads everything else until the ending quotation mark. Since those are the only kinds of simple values we know about right now, those are the only ones we discuss here.
Evaluating procedure calls is clearly a bit more difficult. In general, the Scheme interpreter can't apply a procedure to some arguments until it has evaluated the arguments. Hence, it evaluates all the arguments (using the same algorithm) and then applies the procedure.
For example, to evaluate (+ (* 2 3) (* 4 5))
, the interpreter
must first evaluate (* 2 3)
and (* 4 5)
. The
results of those evaluations are 6 and 20, which it can then add, giving
26. If the addition was the outermost operation, it can then print the
result. If the addition expression is part of a larger expression, such as
(* 0.25 (+ (* 2 3) (* 4 5)))
, it uses the
26 in evaluating the enclosing expression.
How does the interpreter know that it has a compound expression to evaluate?
It sees an open parenthesis. Unless the first thing after the open
parenthesis is the keyword define
(or one of a few
other special keywords
you'll learn about later), it assumes that the first thing after the
open parenthesis is a procedure, the remaining things are the arguments
to that procedure.
Definitions are a special case of compound expressions in which
the procedure is define
. To evaluate a definition,
the interpreter must evaluate the associated expression. Once it is
done evaluating that expression, it puts the name and the value of
the expression into the dictionary. For example, given
(define x (+ 2 3))
, the interpreter evaluates
(+ 2 3)
, giving 5, and then puts the entry
(x . 5) in the dictionary. (We'll represent dictionary entries with
an open parenthesis, the name, a period, the value, and a close
parenthesis.)
As the definition of the dictionary suggests, the evaluation strategy for names is pretty straightforward: The Scheme interpreter simply looks them up in the dictionary.
(+ 22 3)
.
define
, so the whole
expression is a procedure call. The procedure will we apply
is +
, the addition procedure.
+
) to the two arguments,
(that is, 22 and 3). The result is 25.
Now, let's suppose we had a somewhat more complex expression, such as
(* pi (
. As you might note, that expression computes the area of a circle given its diameter.
expt
(/ diameter
2) 2))
define
, so the whole
expression is a procedure call. The procedure we will apply
is *
.
pi
.
pi
in the definitions table. If we are
lucky, it's been predefined.
Let's see ... it's defined as 3.14159...
.
define
(and it probably shouldn't
be a definition in the middle of an expression), so the
subexpression is a procedure call. The procedure we will apply is
expt
.
expt
.
define
, so the whole
subexpression is a procedure call. The procedure we will apply
is /
(division).
diameter
.
diameter
in the table. Hmmm ...
it's not a predefined value (which is probably good, since
it is likely that programs will want to use only one diameter).
But we haven't defined it either. Boom!
It is clearly impossible to continue evaluating the expression,
so we stop.
Well, it seems we should have defined diameter
first.
Let's do so. (define diameter 10)
define
. It's
a definition. The name we will be defining is diameter
.
(diameter . 10)
to the dictionary.
Okay, let's go back and explore the previous expression,
(* pi (
.
expt
(/ diameter
2) 2))
define
, so the whole
expression is a procedure call. The procedure we will apply
is *
.
pi
.
pi
in the definitions table. If we are
lucky, it's been predefined. Let's see ... it's defined
as 3.14159...
.
define
, so the whole subexpression
is a procedure call. The procedure we will apply is
expt
.
expt
.
define
, so the whole
expression is a procedure call. The procedure we will apply
is /
(division).
diameter
.
diameter
in the table. Since
we just put (diameter . 10)
into the dictionary,
we can be fairly confident that we'll find that entry,
and can therefore use the value 10.
/
procedure..
expt
. Do any remain?
expt
only has two parameters.)
pi
,
which we found was 3.14159, and an expression, which we just
found was 25.
Here's a simplified version of the algorithm that the Scheme interpreter seems to follow.
Look at the next non-space character
If the next non-space character is an open parenthesis
Look at the next thing.
If the next thing is the keyword define
Read the next thing (a name to define)
Read the next thing (an expression)
Evaluate the expression, giving a value
Add a (name . value) entry to the dictionary
Otherwise the next thing must be a function
Read and evaluate each argument
Apply the function to the evaluated arguments
Otherwise, see if the next non-space character is a digit (or + or -)
Read all the parts of a number
The number is the result
Otherwise, see if the next non-space character is a letter
Read everything up to the next space (or close paren).
Look up the thing just read in the dictionary.
If it's not there, crash and burn
Otherwise, the result is the value found in the dictionary
Of course, things are not quite as simple as the discussion above suggests (and it's not even clear that the discussion above suggests things are simple). For example, there are a host of kinds of Scheme expressions that we have not yet explored. We will consider those in future discussions of Scheme's evaluation strategies.
However, we've left off one thing that's relevant to the Scheme you
already know. As you may have seen, Scheme lets you write definitions for
functions, such as (define multiply *)
. What does that
do to our evaluation strategy? Primarily, it means that we have to
check if the thing we see after an open parenthesis is a defined name
and, if so, get its definition from the dictionary.
In fact, Scheme looks up the procedure, even if you're using one
of the standard procedures. Hence, if you use +
or
sqrt
, it still looks it up in the table, where it finds
the internal representation of the corresponding procedure. You can
tell that Scheme looks up these standard procedures by redefining them.
For example, (define + -)
will make your program behave
very strangely thereafter.
a. What does Scheme do to evaluate a simple value, such as a number?
b. What does Scheme do evaluate a name, such as pi
?
c. What two steps does Scheme need to do to evaluate a procedure call, such as (quotient 7 2)
?
d. What two steps does Scheme need to do to evaluate a definition, such as (define today "Tuesday")
?
What are the roughly seven steps Scheme will take to evaluate the following expression?
(define average (/ (+ 7 8 9) 3))