Substitution Model

These are my notes on the discussion from 1.1.3 - 1.1.5 of the text.

The substitution model of process evaluation, as described on page 9 of the text.

To evaluate a combination

1. Evaluate the subexpressions of the combination
2. 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).

Define does not follow the rules above. It is one of several special forms.

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

Given the procedures

(define (square x) (* x x))

(define (sum-of-squares x y)
  (+ (square x) (square y)))

(define (f n)
  (sum-of-squares (+ n 1) (* n 2)))

We would evaluate (f 5) by the following substitutions
(sum-of-squares (+ n 1) (* n 2)
(sum-of-squares (+ 5 1) (* 5 2)
(+ (square 6) (square 10))
(+ 36 100)
136


This substitution model above uses applicative-order evaluation. An alternative is normal-order evaluation. Normal order evaluation fully expands all arguments before applying procedures.

(f 5)
(sum-of-squares (+ 5 1) (* 5 2)
(+ (square (+ 5 1)) (square (* 5 2)))
(+ (* (+ 5 1) (+ 5 1)) (* (* 5 2) (* 5 2)))
(+ (* 6 6) (* 10 10))
(+ 36 100)
136

The interpreter actually uses applicative order evaluation, but the substitution model as described here does not accurately capture how the interpreter works.