# 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:

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:

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

## sum-cubes

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

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:

## 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:

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`.

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):

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:

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:

## 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`:

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

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

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

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

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

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

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

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

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

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

4 is greater than 3, so this reduces to:

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.