SICP Solutions - Exercise 2.6

This was an interesting problem. Thought I’d share my solution here.

Scene

We are given the Church numeral representation of the number zero:

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

And a function that given a (positive) Church numeral, returns the next one:

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

Part 1

Question:

Define one and two directly (not in terms of zero and add- 1). (Hint: Use substitution to evaluate (add-1 zero)).

Answer:

Here are the steps for the substitution:

(add-1 zero)

1. Evaluate zero.

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

2. Apply the lambda argument to add-1.

; body of add-1
(lambda (f) (lambda (x) (f ((n f) x))))) ; substitute the 'n' here

; result
(lambda (f) (lambda (x) (f (((lambda (f) (lambda (x) x)) f) x))))

3. This looks like a combinaton with lot of lambdas; but look closely, and you’ll see that only one of those is supplied an argument. Apply it.

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

4. Apply lambda procedure to ‘x’.

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

5. No more arguments to apply. This is the body for our procedure that defines ‘one’:

(define one (lambda (f) (lambda (x) (f x))))

Similiarly, we can find ‘two’ by evaluating (add-1 one):

(define two (lambda (f) (lambda (x) (f (f x)))))

Part 2

Question:

Give a direct definition of the addition procedure + (not in terms of repeated application of add-1).

Answer:

I leave this exercise to the reader. You can check your answer here.