SICP Problem 2.6

This is a short fun exercise I also went through while reading SICP. The problem gives a definition for zero and a function to compute the next integer (add 1):

(define zero (lambda (f) (lambda (x) x)))

(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))

The problem asks you to write the function that adds two numbers without using add-1 iteratively.

Let’s first look at the definitions to figure out what they do:

Zero

Zero is represented as a function, and this function, when evaluated on any parameter returns the identity function. We could write zero as \(zero(f)(x) = x\).

Add-1

To add 1 to a number, say \(n\), we wrap \(n\) in function \(f\). So \(add1(n)(f)(x) = f(n(f)(x))\). For zero we had \(zero(f)(x) = x\), one would be \(one(f)(x) = f(zero(f)(x)) = f(x)\), two then is \(two(f)(x) = f(one(f)(x)) = f(f(x))\).

We can easily see the pattern, \(k\) is applying \(k\) times the function \(f\) to \(x\).

Add

We can now write the function add to sum two numbers. Since adding \(n_1\) and \(n_2\) is returning a function that applies \(n_1 + n_2\) times the function \(f\) to \(x\) , we can think of it as applying \(n_1\) to \(n_2\). The code looks as follows:

(define (add n1 n2)
  (lambda (f) (lambda (x) ((n1 f) ((n2 f) x)))))

Verifying

Before we can check this, we need a way to evaluate the numbers. For this, notice that it is enough to evaluate our number setting \(x=0\) and \(f(x) = x + 1\):

(define (eval n)
  ((n (lambda (x) (+ 1 x))) 0))

We can check a few numbers:

(eval zero)
(eval (add-1 zero))
(eval (add-1 (add-1 zero)))
(eval (add-1 (add-1 (add-1 zero))))

returns:

0
1
2
3

Let’s write a function to build numbers using add-1:

(define (build n)
  (cond
    [(= 0 n) zero]
    [else (add-1 (build (- n 1)))]))

We first will check that this works for a reasonable set of numbers:

(define (errors n)
  (for/list 
    ([i (in-range 0 n)] 
     #:when (not (eq? (eval (build i)) i)))
    i))

When evaluated (up to 30,000 at least) this returns the empty list, which means, it did not find any errors.

Now we evaluate whether our add function works:

(define (add-errors n)
  (for/list 
    ([i (in-range 0 n)]
     [j (in-range 0 n)]
     #:when (not (eq? (eval (add (build j) (build i))) (+ i j))))
    (list i j)))

And when running this up to 1,000 it works as expected, producing an empty list.