Monday, October 25, 2010

SICP 2.5: Representing Pairs as a Product

From SICP section 2.1.3 What Is Meant by Data?

Exercise 2.5 asks us to show that we can represent pairs of non-negative integers using only numbers and arithmetic operations if we represent the pair a and b as the integer that is the product 2a3b. We're to give the corresponding definitions of the procedures cons, car, and cdr.

This exercise reminds me of the old adage that just because you can do something doesn't mean that you should. The implementations of cons, car, and cdr that follow are severely limited in that they can only join pairs of integers, not pairs of any type of data as we've seen before.

Regardless, here is what is meant by representing non-negative integers as the product 2a3b. Note that because 2 and 3 are both prime, and due to the fundamental theorem of arithmetic, any integer values that we insert for a and b will result in a unique value for the product 2a3b. Because the product is unique, we're able to get back the original values of a and b by just storing the product and remembering the rule we used to generate it.

The definition of cons is straightforward from the requirements using the built-in Scheme expt procedure.
(define (cons a b)
(* (expt 2 a)
(expt 3 b)))

But once we've combined two integers in this way, how do we separate them again? For example, if we evaluate (cons 5 6) we get a result of 23328. The corresponding implementation of car needs to take the value 23328 and tell us what that the original value of a was 5. We can do that by counting the number of times 23328 is evenly divisible by 2. Since 2 and 3 have no factors in common, once you divide all the 2s out of 23328 you'll be left with a power of 3. Since we're going to be doing the same thing for cdr, we'll define a general procedure that can be reused.

There's no easy way to find out how many times one number evenly divides another other than simply trying to divide by the number in a loop and testing for a remainder. If there was a quick formula that we could apply to get the answer in one step then prime factorization would be much easier than it is. We'll have to use an iterator to do this in as few steps as possible.
; count the number of times n is evenly divisible by d
(define (num-divs n d)
(define (iter x result)
(if (= 0 (remainder x d))
(iter (/ x d) (+ 1 result))
result))
(iter n 0))

I tested this with the example values above to make sure it gives the correct results.
> (num-divs 23328 2)
5
> (num-divs 23328 3)
6

Now we can define both car and cdr in terms of num-divs.
(define (car x)
(num-divs x 2))

(define (cdr x)
(num-divs x 3))

Finally, we can use the axiom of pairs (from Lecture 2B) to show that our new definitions for cons, car, and cdr work together as they should.
> (car (cons 4 7))
4
> (cdr (cons 4 7))
7


Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

2 comments:

chekkal said...

here is my solution:

(define (cons a b) (* (expt 2 a) (expt 3 b)))

(define (logb b n) (floor (/ (log n) (log b))))

(define (car x) (logb 2 (/ x (gcd x (expt 3 (logb 3 x))))))

(define (cdr x) (logb 3 (/ x (gcd x (expt 2(logb 2 x))))))

adityaathalye said...

I used logarithms and iteration to achieve the same end. Except that, pure iteration--the way Bill has done it--is the best way to represent a and b as integers. Logarithms force floating point computation that is good enough for engineering definitions, but fails to satisfy the exacting requirements of mathematical purity.

https://github.com/lambdadi/sicp/blob/master/ex2-05-arithmetic-cons.scm