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).
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).
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.
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.
Exceptions to the general evaluation rule are called special forms.
definecreates a binding from a symbol to a value in the environment. The value may be a procedure object (e.g., as created by
(define x 3)does not apply
defineto two arguments, one of which is the value of the symbol
xand the other of which is 3, since the purpose of the
defineis precisely to associate
xwith a value. (That is,
(define x 3)is not a combination.)
cond. Once a true predicate is found, subsequent predicates (and their corresponding consequents) are not evaluated.
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.