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.

Trackbacks for this post

  1. Numerical Integration (With Precision) | Jayway Team Blog - Sharing Experience

Leave a Reply