# SICP 1b Procedures & Processes: Substitution Model

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.