sicp-ex-2.6

The first tough question.

If zero is given as:

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

And add-1 is:

 (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. Crappy 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 friggin brutal. If you are more articulate than I, let 'er rip.

<< Previous exercise (2.5) | Index | Next exercise (2.7) >>

shyam

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 ]=>