SICP Exercise 2.78: Using Primitive Types

The internal procedures in the scheme-number package are essentially nothing more than calls to the primitive procedures +, -, etc. It was not possible to use the primitives of the language directly because our type-tag system requires that each data object have a type attached to it. In fact, however, all Lisp implementations do have a type system, which they use internally. Primitive predicates such as symbol? and number? determine whether data objects have particular types. Modify the definitions of type-tag, contents, and attach-tag from section 2.4.2 so that our generic system takes advantage of Scheme's internal type system. That is to say, the system should work as before except that ordinary numbers should be represented simply as Scheme numbers rather than as pairs whose car is the symbol scheme-number.

To recap, here are the original implementations of the three procedures in question:

(define (attach-tag type-tag contents)
  (cons type-tag contents))
(define (type-tag datum)
  (if (pair? datum)
      (car datum)
      (error "Bad tagged datum -- TYPE-TAG" datum)))
(define (contents datum)
  (if (pair? datum)
      (cdr datum)
      (error "Bad tagged datum -- CONTENTS" datum)))

What we want to do is to modify these so that they treat any contents or datum that is a primitive number specially.

The changes to type-tag and contents are straightforward. We simply extend them both so that, in addition to checking whether datum is a pair and handling that as is currently done, they also check whether it's a number. If a number is encountered then, rather than raise an error as would currently happen, type-tag should return 'scheme-number while contents should return the datum directly.

attach-tag raises an interesting issue. Now the obvious solution is simply to modify it so that it tests whether the passed contents is a number or not. If it is then simply return the number; if it isn't then return a tagged pair (i.e. the current behaviour). However, this is not necessarily the correct behaviour.

Our system is supposed to be additive, supporting new number representations. What if I decide to add a new package for representing transfinite cardinal numbers, with the tag 'transfinite-cardinal, and the representation being a non-negative primitive Scheme integer such that 0 represents ℵ₀, 1 represents ℵ₁, and so on? If I make the obvious modification to attach-tag then attach-tag will ignore my type-tag, spot that the contents are a primitive Scheme number, return the untagged contents and break my transfinite cardinals package!

No, for attach-tag to work correctly, it really needs to check if type-tag is 'scheme-number rather than checking whether contents is a primitive Scheme number.

Given all that, here's how we can express this programmatically:

(define (attach-tag type-tag contents)
  (if (= type-tag 'scheme-number)
      contents
      (cons type-tag contents)))
(define (type-tag datum)
  (cond ((number? datum) 'scheme-number)
        ((pair? datum) (car datum))
        (else (error "Bad tagged datum -- TYPE-TAG" datum))))
(define (contents datum)
  (cond ((number? datum) datum)
        ((pair? datum) (cdr datum))
        (else (error "Bad tagged datum -- CONTENTS" datum))))

If we swap these in for our original three procedures then we can give it all a spin:

> (attach-tag 'scheme-number 5)
5
> (attach-tag 'transfinite-cardinal 2)
(mcons 'transfinite-cardinal 2)
> (type-tag 4)
'scheme-number
> (contents 3)
3
> (type-tag (attach-tag 'transfinite-cardinal 2))
'transfinite-cardinal
> (contents (make-rational 5 4))
(mcons 5 4)
> (add (make-scheme-number 5) (make-scheme-number 4))
9
> (add (make-rational 1 3) (make-rational 1 4))
(mcons 'rational (mcons 7 12))

All seems to be in order... If you're wondering about the mcons then you should read part (b) of my solution to exercise 2.73.