SICP Exercise 2.5 - How if it needs a modification?

Question

I'm currently reading the SICP, and working on Exercise 2.5 :

Exercise 2.5. 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^a*3^b. Give the corresponding definitions of the procedures cons, car, and cdr.

And I found a code : (Referring to https://codology.net/post/sicp-solution-exercise-2-5/)

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

(define (my-car x)
  (define (car-iter x count)
    (if (= 0 (remainder x 2))
         (car-iter (/ x 2) (+ 1 count))
          count))
    (car-iter x 0))

(define (my-cdr x)
  (define (cdr-iter x count)
(if (= 0 (remainder x 3))
  (cdr-iter (/ x 3) (+ 1 count))
   count))
(cdr-iter x 0))

My question is : How if the requirement of "Nonnegative integers" needs to be changed to "Accept both negative and nonnegative integers" ?

Ex :

> (define x (my-cons 2 -5))
> (my-car x)
2
> (my-cdr x)
-5

How to modify the code? I can't figure it out.

Thank you. May you have a great day.

Answer 1

As amalloy said in a comment this is really a maths problem. This encoding works because of the fundamental theorem of arithmetic, which is that any natural number (positive integer or zero) has a unique prime factorisation.

So you could encode the sign of the integers using one or more additional prime factors (you only need one, in fact, as you can for instance write the thing as 2^a3^b5^s where s is an integer in [0,3] which encodes the signs of both elements).

An alternative way is simply to use the existing representation but to map the integers to the naturals. This is nice because it's a practical demonstration that there are no more integers than naturals. Such a map might be:

• if i >= 0 then 2i.
• otherswise -2i - 1.

It's easy to see that this is 1-1, and also that 0 maps to 0 (which makes 0 a nice value for nil).

Here are these maps, written (sorry) in typed Racket as I'm trying to work out if I can use it.

(define (Z->N (i : Integer)) : Natural
  ;; map an integer to a natural
  (if (>= i 0)
      (* i 2)
      (- (* (- i) 2) 1)))

(define (N->Z (n : Natural)) : Integer
  ;; map the naturals into the integers
  (let-values ([(q r) (quotient/remainder n 2)])
    (if (zero? r)
        q
        (- (- q) 1))))

Now there is another problem with the implementation you have: it will happily handle numbers which are not of the form 2^a3^b, for instance anything which has other prime factors. The way to deal with that is to check that numbers are of that form when extracting the powers: in practice this means checking the number is of the form 2^a*3^b*1.

So the code below does this, as well as encoding integers as above. This again is in typed Racket (sorry, again), and it also makes use of multiple values and probably some other things which only exist in Racket.

(define (defactor (n : Natural) (p : Natural)) : (Values Natural Natural)
  ;; Given n and a factor p, return m where p does not divide m,
  ;; and j, the number of factors of p removed (so n = m*p^j)
  (let df-loop ([m : Natural n]
                [j : Natural 0])
    (let-values ([(q r) (quotient/remainder m p)])
      (if (zero? r)
          (df-loop q (+ j 1))
          (values m j)))))
  
(define (kar&kdr (k : Natural)) : (Values Integer Integer)
  ;; Given something which should be a kons, return its kar & kdr.
  ;; If it is not a kons signal an error
  (let*-values ([(k2 encoded-kar) (defactor k 2)]
                [(k23 encoded-kdr) (defactor k2 3)])
    (unless (= k23 1)
      (error 'kar&kdr "not a cons"))
    (values (N->Z encoded-kar) (N->Z encoded-kdr))))

(define (kons (the-kar : Integer) (the-kdr : Integer)) : Natural
  (* (expt 2 (Z->N the-kar))
     (expt 3 (Z->N the-kdr))))

(define (kar (the-kons : Natural)) : Integer
  (let-values ([(the-kar the-kdr) (kar&kdr the-kons)])
    the-kar))

(define (kdr (the-kons : Natural)) : Integer
  (let-values ([(the-kar the-kdr) (kar&kdr the-kons)])
    the-kdr))

And now

> (define d (kons 123 -456))
> d
- : Integer [more precisely: Nonnegative-Integer]
51385665200410193914365219310409629004573395973849642473134969706165383608831740620563388986738635202925909198851954060195023302783671526117732269828652603388431987979605951272414330987611274752111186624164906143978901704325355283206259678088536996807776750955110998323447711166379786727609752016045005681785186498933895920793982869940159108073471074955985333560653268614500306816876936016985137986665262182684386364851688838680773491949813254691225004097103180392486216812280763694296818736638062547181764608
> (kar d)
- : Integer
123
> (kdr d)
- : Integer
-456
> (kdr (+ d 1))
kar&kdr: not a cons [,bt for context]