## The Substitution Model: A Tool For Understanding Recursion

Section 1.3 in Structure and Interpretation of Computer Programs is about Formulating Abstractions with Higher-Order Procedures. As an example, the authors use three simple sums:

• a sum of an integer range
• a sum of the cubes of an integer range
• a sum of a series that converges to π/8

The purpose is to highlight what is common between them and what differs. The differences boil down to:

1. calculating the current term
2. calculating the next value

The authors show that all three functions can be expressed as calls to a higher-order function. Here is the `sum` function in Clojure:

```(defn sum [term a next b]
(if (> a b)
0
(+ (term a)
(sum term (next a) next b))))
```

The function takes four parameters: `[term a next b]`. `term` is the function for calculating the current term, `a` is the start of the range to perform the sum on, `next` is the function for calculating the next value in the sequence, and `b` is the end of the range. The `sum` function first calculates the current term by applying `term` to `a`, then adds that to the result of calling itself again, but this time not with `a`, but the next value in the sequence: `(next a)`. It keeps doing that until `a` is greater than `b`, then the upper bound is reached and the function is done. It doesn’t call itself any more, but instead returns zero.

# sum-integers

Using `sum` to calculate a sum of integers is easy. Each number in the sequence will itself be the actual term. We use the `identity` function as `term`, since it returns its input unchanged. The `inc` function increments its argument by one, so that is ideal for `next`. Here is the implementation:

```(defn sum-integers [a b]
(sum identity a inc b))
```

I’ll test the function in my REPL (`user>` is the prompt):

```user> (sum-integers 1 10)
55
```

# sum-cubes

The second example is summing up the cubes of an integer range. We define the `cube` function:

```(defn cube [x] (* x x x))
```

The implementation of `sum-cubes` is very similar to `sum-integers`. We simply replace `identity` with `cube`, so the current term will be the cube of the integer, rather than just the integer:

```(defn sum-cubes [a b]
(sum cube a inc b))
```
```user> (sum-cubes 1 10)
3025
```

# pi-sum

The third example is a series that happens to converge to π/8: In order to be able to apply the generic `sum` tool to this problem, we need to write two helper functions: one function for calculating the current term: `pi-term`, and one function for calculating the next value in the sequence: `pi-next`. We can see, by looking at the series above, that each term is `1/(x*(x+2))`, and that the next term has an `x` that is 4 greater than the previous term:

```(defn- pi-term [x] (/ 1 (* x (+ x 2))))
(defn- pi-next [x] (+ x 4))
```

Note that I didn’t use `defn` to define the functions, I used `defn-`. That is a Clojure feature for making the helper functions private, so we don’t clutter up the namespace with internal stuff. Now we have what we need to call `sum`.

```(defn pi-sum [a b]
(sum pi-term a pi-next b))
```

We’ll test this function with the range 1 to 10, multiplying with 8 so we’ll get π (remember that the series converges to π/8):

```user> (* 8 (pi-sum 1 10))
10312/3465
```

Here we can see that the output is Clojure’s built-in type Ratio. Division of integers that can’t be reduced to an integer yields a ratio, rather than a floating point or truncated value. This can be really useful, but when the numbers get large, it can be hard to see what the ratio represents:

```user> (* 8 (pi-sum 1 100))
3400605476464206445954873476681150352328/1089380862964257455695840764614254743075
```

Any numeric operation on a Ratio involving Doubles, will yield a Double. That means we can skip the Ratio and go directly to Double by using 1.0 as the starting point:

```user> (* 8 (pi-sum 1. 1000))
3.139592655589783
```

# The Substitution Model

If it’s not immediately obvious to you how `sum` works, you can always use the Substitution Model. Evaluate the body of the procedure with each formal parameter replaced by the corresponding argument. Let’s evaluate the call `(sum-integers 1 3)`:

Retrieve the body of `sum-integers`:

```(sum identity a inc b)
```

Replace the formal parameters `a` and `b` by the arguments `1` and `3`:

```(sum identity 1 inc 3)
```

The problem is reduced to evaluating a call to `sum` with four arguments. So let’s retrieve the body of `sum`:

```(if (> a b)
0
(+ (term a)
(sum term (next a) next b)))
```

Now we replace `sum`‘s formal parameters `[term a next b]` with our arguments `identity`, `1`, `inc`, and `3`:

```(if (> 1 3)
0
(+ (identity 1)
(sum identity (inc 1) inc 3)))
```

1 is not greater than 3, so it reduces to:

```(+ (identity 1)
(sum identity (inc 1) inc 3))
```

`(identity 1)` evaluates to `1`, and `(inc 1)` evaluates to `2`, so it reduces to:

```(+ 1
(sum identity 2 inc 3))
```

We’ll evaluate the call to `sum` again, directly replacing this time:

```(+ 1
(if (> 2 3)
0
(+ (identity 2)
(sum identity (inc 2) inc 3))))
```

2 is not greater than 3, so this reduces to:

```(+ 1
(+ 2
(sum identity 3 inc 3)))
```

We retrieve the body of `sum` again, replacing parameters with arguments:

```(+ 1
(+ 2
(if (> 3 3)
0
(+ (identity 3)
(sum identity (inc 3) inc 3))))
```

3 is not greater than 3, so this reduces to:

```(+ 1
(+ 2
(+ 3
(sum identity 4 inc 3))))
```

We retrieve the body of `sum` for the last time:

```(+ 1
(+ 2
(+ 3
(if (> 4 3)
0
(+ (identity 4)
(sum identity (inc 4) inc 3))))
```

4 is greater than 3, so this reduces to:

```(+ 1
(+ 2
(+ 3
0)))
```

which evaluates to 6.

The Substitution Model is a useful technique when you’re new to functional programming, or when you just need to know in detail what is really going on in a function.

1. Pingback: