3.8 Evaluation rules

Here we summarize the grammar rules and evaluation rules. Since each grammar rule has an associated evaluation rule, we can determine the meaning of any grammatical Scheme fragment by combining the evaluation rules corresponding to the grammar rules followed to derive that fragment.

Program ::$\Rightarrow$ $\epsilon $ | ProgramElement Program
ProgramElement ::$\Rightarrow$ Expression | Definition

A program is a sequence of expressions and definitions.

Definition ::$\Rightarrow$ (define Name Expression)

A definition evaluates the expression, and associates the value of the expression with the name.

Definition ::$\Rightarrow$ (define (Name Parameters) Expression)

Abbreviation for

(define Name (lambda Parameters) Expression)

Expression ::$\Rightarrow $ PrimitiveExpression $\mid $ NameExpression
$\mid $ ApplicationExpression
$\mid $ ProcedureExpression $\mid $ IfExpression

The value of the expression is the value of the replacement expression.

PrimitiveExpression ::$\Rightarrow$ Number $\mid $ true $\mid $ false $\mid $ primitive procedure

Evaluation Rule 1: Primitives. A primitive expression evaluates to its pre-defined value.

NameExpression ::$\Rightarrow$ Name

Evaluation Rule 2: Names. A name evaluates to the value associated with that name.

ApplicationExpression ::$\Rightarrow$ (Expression MoreExpressions)

Evaluation Rule 3: Application. To evaluate an application expression:

  1. Evaluate all the subexpressions;
  2. Then, apply the value of the first subexpression to the values of the remaining subexpressions.
MoreExpressions ::$\Rightarrow$ $\epsilon $ $\mid $ Expression MoreExpressions
ProcedureExpression ::$\Rightarrow $ (lambda (Parameters) Expression)
Parameters ::$\Rightarrow$ $\epsilon $ $\mid $ Name Parameters

Evaluation Rule 4: Lambda. Lambda expressions evaluate to a procedure that takes the given parameters and has the expression as its body.

IfExpression ::$\Rightarrow$ (if Expression$_{Predicate}$

Evaluation Rule 5: If. To evaluate an if expression, (a) evaluate the predicate expression; then, (b) if the value of the predicate expression is a false value then the value of the if expression is the value of the alternate expression; otherwise, the value of the if expression is the value of the consequent expression.

The evaluation rule for an application (Rule 3b) uses apply to perform the application. Apply is defined by the two application rules:

  1. Application Rule 1: Primitives. :   To apply a primitive procedure, just do it.

  2. Application Rule 2: Constructed Procedures. :   To apply a constructed procedure, evaluate the body of the procedure with each parameter name bound to the corresponding input expression value.

Application Rule 2 uses the evaluation rules to evaluate the expression. Thus, the evaluation rules are defined using the application rules, which are defined using the evaluation rules! This appears to be a circular definition, but as with the grammar examples, it has a base case. Some expressions evaluate without using the application rules (e.g., primitive expressions, name expressions), and some applications can be performed without using the evaluation rules (when the procedure to apply is a primitive). Hence, the process of evaluating an expression will sometimes finish and when it does we end with the value of the expression.1

  1. This does not guarantee that evaluation always finishes, however! The next chapter includes some examples where evaluation never finishes.