# sicp-ex-2.6

The first tough question.

If zero is given as:

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

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

one is the result of (add-1 zero)

``` (lambda (f) (lambda (x) (f ((zero f) x))))
```

zero is a function of one arg, that returns a function of one arg that returns the argument (identity function), so ((zero f) x) is just x. So, one reduces to:

``` (lambda (f) (lambda (x) (f x)))
```

two is the result of (add-1 one)

``` (lambda (f) (lambda (x) (f ((one f) x))))
```

substituting, and changing the lambda args for sanity:

```  => (lambda (f) (lambda (x) (f (((lambda (a) (lambda (b) (a b))) f) x))))
=> (lambda (f) (lambda (x) (f ((lambda (b) (f b)) x))))
=> (lambda (f) (lambda (x) (f (f x))))
```

So, one and two are:

``` (define one (lambda (f) (lambda (x) (f x))))
(define two (lambda (f) (lambda (x) (f (f x)))))
```

Applying add-1 again for kicks gives

```   (define three (lambda (f) (lambda (x) (f (f (f x))))))
```

So, the function f (or whatever) gets applied again and again to the innermost x.

To define add generally, the result will just be the function applied n times, where n is the (numerical) sum. add needs to take 2 args, a and b, both of which are 2-level nested lambdas (as above). So, the method signature is:

``` (define (add a b) ...)
```

and add needs to return a 2-level nested lambda, as a and b will be:

``` (define (add a b)
(lambda (f)
(lambda (x)
...)))
```

Essentially, we need to apply a's multiple calls to its f (its outer lambda arg) to b's multiple calls to its f and its x. Poor explanation. We need the function calls to be like this:

``` (fa (fa (fa (fa ... (fa xa))))...)
```

and xa will be the call to b:

``` xa = (fb (fb (fb ... (fb x))) ...)
```

We pass f and x to b like this:

``` ((b f) x)
```

so, we have

``` (fa (fa (fa (fa ... (fa ((b f) x))))))
```

but we need the function used by a in its outer lambda function to be the same as that used by b, or nothing will make any sense - using different functions would be like mixing octal and decimal numbers in a math problem. So, we pass f as the first lambda arg to a:

``` (a f)
```

and then a's inner lambda - a's x - will be ((b f) x)

So, the whole thing is:

``` (define (add a b)
(lambda (f)
(lambda (x)
((a f) ((b f) x)))))
```

Thanks to Ken Dyck for the hint.

Note: this explanation is brutal. If you are more articulate than I, let 'er rip.

jz

author of the ex 2.6 solution ^^^

If you wonder how to use these functions here are few examples..

```1 ]=> ((one square) 2)

;Value: 4

1 ]=> ((two square) 2)

;Value: 16

1 ]=> (((add two one) square) 2)

;Value: 256

1 ]=>

```

jsdalton

I found it helpful when experimenting to have a way to convert between integers and church numerals (e.g. to set up problems and also to confirm a solution). I used the following:

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

(lambda (f) (lambda (x) (f ((n f) x)))))

(define (int-to-church n)
(define (iter a result)
(if (> a n)
zero
(add-1 (iter (+ a 1) result))
))
(iter 1 zero))

(define (church-to-int cn)
((cn (lambda (n) (+ n 1))) 0))
```

anonymous

Hey jsdalton, thank you for the idea of procedures to convert between integers and church numerals. However, your int-to-church procedure doesn't need to define a helper procedure. The int-to-church procedure can be more succinctly written as:

``` ;; Recursive process
(define (int->church n)
(if (= n 0)
zero

;; Iterative process
(define (int->church n)
(define (iter i result)
(if (= i n)
result
(iter (+ i 1) (add-1 result))))
(iter 0 zero))
```

anonymous

I think I have a much simpler and easier to understand solution, but I'm not convinced it's entirely correct

```
```

Basically, you want to add-1 a times to b so you call a with add-1 and then call the resulting function with b to get a new function

Note: you should notice that this question says "not in terms of repeated application of add-1"

alexh

Here's yet another way of looking at it. A Church numeral is a second-order function: the numeral n is the function that turns f into "f composed with itself n times". Therefore we can define:

``` (define one (lambda (f) f))
(define two (lambda (f) (compose f f)))
```

where compose is the function from ex1.42:

``` (define (compose f g) (lambda (x) (f (g x))))
```

My short-cut for the "int->church" procedure is:

``` (define (print-church n)
(display ((n inc) 0)) (newline))
```

Then we can do:

``` (define (church-add m n) (lambda (f) (compose (m f) (n f))))
```

Another interesting thing: multiplying Church numerals is actually easier than adding them!

``` (define (church-mult m n) (compose m n))
(print-church (church-mult two three))
```

seok

An easier explanation to understand:

```
(define zero
(lambda (f) (lambda (x) x)))
(define one
(lambda (f) (lambda (x) (f x))))
(define two
(lambda (f) (lambda (x) (f (f x)))))

#|
It can be easily proved that (n f) is (lambda (x) (f (f .. (f x) .. ))) where f is repeated n times, by induction.

((add n m) f) = ((n+m) f)
= (lambda (x) (f^(n+m) x))
= (lambda (x) ((lambda (x) (f^n x)) (f^m x)))
= (lambda (x) ((lambda (x) (f^n x)) ((lambda (x) (f^m x)) x)))
= (lambda (x) ((n f) ((m f) x)))
|#

(lambda (f) (lambda (x) ((n f) ((m f) x)))))

```

yc

Maybe a duplicate, but still...

``` (define zero
(lambda (f) (lambda (x) x)))
(define one
(lambda (f) (lambda (x) (f x))))
(define two
(lambda (f) (lambda (x) (f (f x)))))

;; with the above, we can get
(define n
(lambda (f) (lambda (x) (f (f (f (f ... (f x))))))))
;;                          ------n times-----

(lambda (f)
(lambda (x)
(f ((n f) x)))))

;; consider `((n f) x)' in `add-1'
((n f) x)
= (((lambda (f)
(lambda (x)
(f (f (f (f ... (f x)))))))
f) x)
= ((lambda (x)
(f (f (f (f ... (f x))))))
x)
= (f (f (f (f ... (f x)))))

;; that is, f is applied n-times to x.
;; ((n f) x) with an additional f
(f ((n f) x))

;; now, assume the result of applying f n-times
;; to x is n-result
(define n-result ((n f) x))

;; if we want to apply f another m-times to n-result
;; we would write
((m f) n-result)

;; which is
((m f) ((n f) x))

;; put the result back into `add-1', we get