# SICP 1b

Procedures & Processes: Substitution Model

## Table of Contents

The simplest model to understand how procedures work is the *substitution
model*.

So far we have seen different kinds of expressions: numbers, symbols, λ-expressions, definitions, conditionals and combinations. Ignore λ-expressions, definitions and conditionals for now, as they have special forms.

## 1 Substitution rule

To evaluate an application: Evaluate the operator to get the procedure. Evaluate the operands to get the arguments. Apply the procedure to the arguments. Copy the body of the procedure, substituting the arguments supplied for the formal parameters of the procedure. Evaluate the resulting new body.

Below is a trace of the substitution rule in action.

Sum of squares:

(define (sos x y) (+ (sq x) (sq y))) (define (sq x) (* x x))

Trace of sum of squares:

(sos 3 4) (+ (sq 3) (sq 4)) (+ (sq 3) (* 4 4)) (+ (sq 3) 16) (+ (* 3 3) 16) (+ 9 16) 25

For now take `+`

and `*`

to be primitive, as we need to ignore
details. The key to understanding complicated things is knowing what not to
look at, what not to compute, what not to think about.

## 2 Conditionals

An `if`

statement comprises a *predicate*, *consequent* and *alternative*.
Learn the names of what we're handling. Once you have the name of a spirit, you
have power over it.

(if <predicate> <consequent> <alternative>)

Evaluation of an `if`

expression:

To evaluate an if expression: Evaluate the predicate expression. If it yields true, evaluate the consequent expression. Otherwise, evaluate the alternative expression.

## 3 Peano arithmetic

Below are two possible ways of implementing addition of positive integers.

(define (+ x y) (if (= x 0) x (+ (-1+ x) (1+ y)))) (define (+ x y) (if (= x 0) x (1+ (+ (-1+ x) y))))

What do their traces look like?

(+ 3 4) (+ 2 5) (+ 1 6) (+ 0 7) 7 (+ 3 4) (1+ (+ 2 4)) (1+ (1+ (+ 1 4))) (1+ (1+ (1+ (+ 0 4)))) (1+ (1+ (1+ 4))) (1+ (1+ 5)) (1+ 6) 7

The first is an *iteration*, because:
$$time\; =\; O(x),\; space\; =\; O(1)$$

The second is a *linear recursion*, because:
$$time\; =\; O(x),\; space\; =\; O(x)$$

Evidently, the first is better.

## 4 Round and round

Another example of a recursive procedure, is the procedure to draw a circle.

(define (circle x y) (plot x y) (circle (- x (* y dt)) (+ y (* x dt))))

## 5 Fornicating rabbits

Below is a rudimentary procedure for calculating the nth Fibonacci number (i.e. the number of rabbits in the nth generation).

(define (fib n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2))))))

The trace produces the below tree.

fib4 / \ / \ fib3 fib2 / \ / \ / \ / \ fib2 fib1 fib1 fib0 / \ | | | / \ 1 1 0 fib1 fib0 | | 1 0

$$time\; =\; O(fib(n)),\; space\; =\; O(n)$$

There are better algorithms for calculating the nth Fibonacci number.
In the above example, `fib2`

is calculated twice (one of the calculations is
redundant). By visualising algorithms, it is easier to determine where
improvements can be made.

## 6 Tower of Hanoi

Construct recursive procedures by wishful thinking. You have to believe!

(define (move n from to spare) (cond ((= n 0) "Done") (else (move (-1+ n) from spare to) (print-move from to) (move (-1+ n) spare to from))))

Note to self: avoiding JavaScript whilst writing maths equations is tough. Implementing trees in LaTeX is even tougher.