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.