One of our goals in this chapter is to isolate issues about process
descriptions. As a case in point, let us consider that, in evaluating
operator combinations, the interpreter proceeds as follows.
To evaluate an operator combination, do the following:
Evaluate the operand expressions 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 an operator
we must first perform the evaluation process on each operand of the
operator 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 operator 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 operator 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.
Notice the role of the
environment in determining the meaning of
the names in expressions. In
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 constant declarations.
For instance, evaluating
const x = 3;
does not apply the =
operator to two arguments, one
of which is the value of the name
x and the other of which is
3, since the purpose of the constant declaration
is precisely to associate
x with a value.
(That is, the part x = 3
in the constant declaration
const x = 3;
is not an operator combination.)
The string const
in the constant declaration is rendered in bold letters to indicate that it
carry a particular meaning, and thus cannot be used as names.
A keyword or a combination of keywords instructs the
Each such syntactic form
has its own evaluation rule. The various kinds of statements (each
with its associated evaluation rule) constitute the
syntax of the