One of our goals in this chapter is to isolate issues about thinking
procedurally. As a case in point, let us consider that, in evaluating
combinations, the interpreter is itself following a procedure.
an operator combination,
do the following:
of the combination.
Apply the function that is denoted by
the operator to the arguments that are the values of
Even this simple rule illustrates some important points about
processes in general. First, observe that the first step dictates
that in order to accomplish the evaluation process for a
combination we must first perform the evaluation process on each
element of the combination. Thus, the evaluation rule is
recursive in nature;
that is, it includes, as one of its steps, the need to invoke the rule
Notice how succinctly the idea of recursion can be used to express
what, in the case of a deeply nested combination, would otherwise be
viewed as a rather complicated process. For example, evaluating
(2 + 4 * 6) * (3 + 12);
requires that the evaluation rule be applied to four different
combinations. We can obtain a picture of this process by
the combination in the form of a
tree, as shown in
Each combination is represented by a
branches corresponding to the operator and the
operands of the combination stemming from it.
terminal nodes (that is, nodes with
no branches stemming from them) represent either operators or numbers.
Viewing evaluation in terms of the tree, we can imagine that the
values of the operands percolate upward, starting from the terminal
nodes and then combining at higher and higher levels. In general, we
shall see that recursion is a very powerful technique for dealing with
hierarchical, treelike objects. In fact, the percolate values
upward form of the evaluation rule is an example of a general kind
of process known as
Next, observe that the repeated application of the first step brings
us to the point where we need to evaluate, not combinations, but
primitive expressions such as
numerals or names.
We take care of the primitive cases by stipulating that
the values of numerals are the numbers that they name,
the values of
names are the objects associated
with those names in the environment.
The key point to
notice is the role of the
environment in determining the meaning of
in expressions. In an interactive language such as
it is meaningless to speak of the value of an expression such as
x + 1
without specifying any information about the environment
that would provide a meaning for the
As we shall see in chapter 3, the general notion of
the environment as providing a context in which evaluation takes place
will play an important role in our understanding of program execution.
Notice that the
evaluation rule given above does not handle
For instance, evaluating
const x = 3;
does not apply
an equality operator =
to two arguments, one
of which is the value of the
x and the other of which is
3, since the purpose of the
is precisely to associate
x with a value.
const x = 3;
The string const
in the constant declaration is rendered in bold letters to indicate
words that carry a particular meaning, and thus cannot be used as
interpreter to treat the respective statement in a special way.
Each such syntactic form has its own evaluation rule. The various
kinds of statements and expressions (each with its associated
evaluation rule) constitute the
syntax of the programming language.