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.

This Post Has One Comment

Leave a Reply

Close Menu