SICP - Solution: Exercise 2.6

January 8, 2019

Exercise 2.6 #

In case representing pairs as procedures wasn’t mind-boggling enough, consider that, in a language that can manipulate procedures, we can get by without numbers (at least insofar as nonnegative integers are concerned) by implementing 0 and the operation of adding 1 as

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

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

This representation is known as Church numeral’s, after its inventor, Alonzo Church, the logician who invented the λ-calculus.

Define one and two directly (not in terms of zero and add-1). (Hint: Use substitution to evaluate (add-1 zero)). Give a direct definition of the addition procedure + (not in terms of repeated application of add-1).

Solution #

(add-1 zero)

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

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

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

From this we can define:

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

(add-1 one)

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

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

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

From this we can define:

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

The addition will be defined as:

(define (add  m n)
  (lambda (f) (lambda (x) ((m f) ((n f) x)))))

To check the result, we can define f as add1 and x as 0:

(define one   (add-1 zero))
(define two   (add-1  one))
(define three (add-1  two))

(print ((zero add1) 0)) (newline)
(print (((add-1 zero) add1) 0)) (newline)
(print (((add-1 (add-1 zero)) add1) 0)) (newline)
(print (((add-1 (add-1 zero)) add1) 0)) (newline)
(print (((add three two) add1) 0)) (newline)