Engaging Computing Group | OPLfall09 / SchemeRulesOfEvaluation browse

Most of the below is copied verbatim from the SICP text, http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-10.html.

Elements of Programming

primitive expressions, which represent the simplest entities the language is concerned with (i.e., arithmetic operators; numbers),
means of combination, by which compound elements are built from simpler ones (i.e., compound expressions),
means of abstraction, by which compound elements can be named and manipulated as units (i.e., procedures).

Combinations

To evaluate a combination, do the following:

Evaluate the subexpressions of the combination.
Apply the procedure that is the value of the leftmost subexpression (the operator) to the arguments that are the values of the other subexpressions (the operands).

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 itself.

Primitives

We take care of the primitive cases by stipulating that

the values of numerals are the numbers that they name,
the values of built-in operators are the machine instruction sequences that carry out the corresponding operations, and
the values of other names are the objects associated with those names in the environment.

We may regard the second rule as a special case of the third one by stipulating that symbols such as + and * are also included in the global environment, and are associated with the sequences of machine instructions that are their “values.”

The Substitution Model for Procedure Application

We can assume that the mechanism for applying primitive procedures to arguments is built into the interpreter. For compound procedures, the application process is as follows:

To apply a compound procedure to arguments, evaluate the body of the procedure with each formal parameter replaced by the corresponding argument.

Special Forms

Exceptions to the general evaluation rule are called special forms.

define creates a binding from a symbol to a value in the environment. The value may be a procedure object (e.g., as created by lambda).

For instance, evaluating (define x 3) does not apply define to two arguments, one of which is the value of the symbol x and the other of which is 3, since the purpose of the define is precisely to associate x with a value. (That is, (define x 3) is not a combination.)

if and cond. Once a true predicate is found, subsequent predicates (and their corresponding consequents) are not evaluated.
and and or. Once a sub-expression is false (in the case of and) or true (in the case of or), subsequent sub-expressions are not evaluated.