SICP Exercise 2.7: Representing Intervals

Alyssa's program is incomplete because she has not specified the implementation of the interval abstraction. Here is a definition of the interval constructor:

(define (make-interval a b) (cons a b))

Define selectors upper-bound and lower-bound to complete the implementation.

A nice and straightforward exercise. We have two values held in a pair. The upper-bound will be the maximum of the two values; the lower-bound will be the minimum of the two. I've already noted that Scheme has a couple of predefined procedures, max and min that can make this determination for us, so the implementations are simply:

(define (upper-bound i) (max (car i) (cdr i)))
(define (lower-bound i) (min (car i) (cdr i)))

And a quick test:

> (define i1 (make-interval 5 10))
> (define i2 (make-interval 7 2))
> (lower-bound i1)
5
> (upper-bound i1)
10
> (lower-bound i2)
2
> (upper-bound i2)
7

SICP Exercise 2.6: A Little Churchin' Up

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 numerals, 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).

Let's take the hint and run with it...

  (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 ((lambda (x) x) x))))
= (lambda (f) (lambda (x) (f x)))

That give us a definition for one:

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

And we can do the same to figure out two:

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

So two is:

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

Looking at the pattern we can see that the Church numeral representation of the positive integer n is fⁿ(x) (i.e. (f ο f ο…ο f ο f)(x), with n occurrences of f). Also, to assist with the remainder of the exercise, we should note that:

• zero produces a single-parameter lambda expression that ignores its parameter and returns a single-parameter lambda expression that returns its parameter. So we can convert zero to its integer equivalent value using the expression ((zero f) 0), where f is any value.
• one produces a single-parameter, f, lambda expression that returns a new single-parameter lambda expression that returns the results of applying f to its parameter. So, assuming we pass 0 as the parameter to the second lambda expression as with zero, then we can convert one to its integer equivalent value using the expression ((one inc) 0), where inc is the increment procedure defined earlier.
• two produces a single-parameter, f, lambda expression that returns a new single-parameter lambda expression that returns the results of applying f to the results of applying f to its parameter. So similar to one, we can convert two to its integer equivalent value using the expression ((two inc) 0).

We can generalize this to saying that for any Church numeral, n, we can convert it to its integer equivalent value using the expression ((n inc) 0). Here's a procedure that encapsulates this logic which we can use to allow easy testing of our work with Church numerals:

(define (unchurch n)
  ((n inc) 0))

For example:

> (unchurch zero)
0
> (unchurch one)
1
> (unchurch two)
2

Now onto defining + for Church numerals. We know that we want this to produce a valid Church numeral. I.e. a single-parameter lambda expression whose parameter, f, is a procedure and that returns a single-parameter lambda expression. We also know that, given two Church numerals representing the nonnegative integers a and b, we want the evaluation of (((+ a b) f) x) to apply f repeatedly, starting with x as the initial input, for a total of a+b times. How can we do this? Well evaluating ((a f) x) will apply f a total of a times to whatever is passed to it as x, and ((b f) x) will apply f a total of b times to whatever is passed to it as x. So we can produce a composite function that evaluates ((b f) x) and then uses that as the value of x for evaluating ((a f) x) (or vice versa). Here's my definition

(define (+ a b)
  (lambda (f) (lambda (x) ((a f) ((b f) x)))))

And to check it works:

> (unchurch (+ one two))
3
> (unchurch (+ (+ one two) two))
5

Of course we can go much further with Church numerals - there's a whole raft of definitions for various computations. Just for fun I also defined * for Church numerals:

(define (* a b)
  (lambda (f) (lambda (x) ((a (b f)) x))))

And here it is in action:

> (unchurch (* (+ one two) two))
6
> (unchurch (* (+ two two) (+ one two)))
12
> (unchurch (* (* two two) (* one two)))
8

SICP Exercise 2.5: Prime Factor Pairs

Show that we can represent pairs of nonnegative integers using only numbers and arithmetic operations if we represent the pair a and b as the integer that is the product 2^a3^b. Give the corresponding definitions of the procedures cons, car, and cdr.

The reason we can use this method of representation comes down to the fact that the two numbers 2 and 3 are both prime numbers. As a result, the product 2^a3^b is a prime factorization of some number n. Now the fundamental theory of arithmetic states that each number >1 has a unique prime factorization. This implies that for any nonnegative integers a and b, 2^a3^b will produce a unique number. Alternatively, there are no two pairs of nonnegative integers, {a, b} and {c, d}, such that 2^a3^b=2^c3^d.

So if we represent the pair of nonnegative integers {a, b} as the integer value n=2^a3^b then this will be a unique representation of the pair. Provided we can then extract the a and b values out of n then this will be a viable representation.

So how can we do this?

Well, the simple way is to just count the number of times we can start from n and repeatedly divide by either 2 or 3, depending upon whether we're trying to find a or b, without leaving any remainder. Assuming we're happy with this approach we can define cons, car, and cdr as:

(define (cons a b)
  (if (and (>= a 0) (>= b 0))
      (* (expt 2 a) (expt 3 b))
      (error "a and b must be >= 0")))

(define (count-factors n f)
  (define (iter remaining result)
    (if (> (remainder remaining f) 0)
        result
        (iter (/ remaining f) (+ result 1))))
  (iter n 0))

(define (car p) (count-factors p 2))
(define (cdr p) (count-factors p 3))

Here's an example of it in practice:

> (define pair (cons 21 14))
> (car pair)
21
> (cdr pair)
14

Note that we don't have to use prime numbers in the representation here. Provided the numbers we use in the representation are coprime the representation will still work. For example, we could represent the pair of nonnegative integers {a, b} as the integer value n=20^a21^b. Neither 20 nor 21 are prime. However, 20 has the prime factorization 2×2×5, while 21 has the prime factorization 3×7. There are no common factors here, so all should still work. To test this, lets change the definitions of cons, car, and cdr to:

(define (cons a b)
  (if (and (>= a 0) (>= b 0))
      (* (expt 20 a) (expt 21 b))
      (error "a and b must be >= 0")))

(define (car p) (count-factors p 20))
(define (cdr p) (count-factors p 21))

...and give it a spin:

> (define pair (cons 12 10))
> (car pair)
12
> (cdr pair)
10