by Ulrik Sandberg - Dynamic languages

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:

- calculating the current term
- 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:

1 2 3 4 5 |
(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.

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:

1 2 |
(defn sum-integers [a b] (sum identity a inc b)) |

I’ll test the function in my REPL (`user>`

is the prompt):

1 2 |
user> (sum-integers 1 10) 55 |

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

function:

1 |
(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:

1 2 |
(defn sum-cubes [a b] (sum cube a inc b)) |

1 2 |
user> (sum-cubes 1 10) 3025 |

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:

1 2 |
(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`

.

1 2 |
(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):

1 2 |
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:

1 2 |
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:

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

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`

:

1 |
(sum identity a inc b) |

Replace the formal parameters `a`

and `b`

by the arguments `1`

and `3`

:

1 |
(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`

:

1 2 3 4 |
(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`

:

1 2 3 4 5 |
] (if (> 1 3) 0 (+ (identity 1) (sum identity (inc 1) inc 3))) |

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

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

`(identity 1)`

evaluates to `1`

, and `(inc 1)`

evaluates to `2`

, so it reduces to:

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

We’ll evaluate the call to `sum`

again, directly replacing this time:

1 2 3 4 5 6 |
] (+ 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 3 4 |
] (+ 1 (+ 2 (sum identity 3 inc 3))) |

We retrieve the body of `sum`

again, replacing parameters with arguments:

1 2 3 4 5 6 7 |
] (+ 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 4 5 |
] (+ 1 (+ 2 (+ 3 (sum identity 4 inc 3)))) |

We retrieve the body of `sum`

for the last time:

1 2 3 4 5 6 7 8 |
] (+ 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 4 |
(+ 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.

[...] a previous blog entry, I explained the higher-order function sum and how to use the Substitution Model to follow the [...]