Re: loss of abstraction Alan Watson 24 Aug 2005 23:44 UTC

> How about numbers, booleans, chars and the empty list?

Lets consider a concrete example of an implementation that uses tagged
pointers. Each pointer has tag bits and value bits. Tagged pointers are
used for null (the empty list), #t, #f, fixnums, and characters.
Eveything else is boxed. The implementation has boxed bignums.

I might arrange to generate uninterned nulls, booleans, integers, or
characters as follows:

(1) I would use three tag values for null, #t, and #f. Interned objects
have the value bits equal to zero. Uninterned objects have the value
bits not equal to zero.

(2) I would use one tag value for fixnums and encode the sign and
magnitude in the the value bits. Interned integers would be represented
by tagged fixnums or boxed bignums according to their value. Uninterned
integers would always be represented by boxed bignums.

(3) I would use one tag value for characters and encode the code point
in the value bits. I would box uninterned chararacters.

The impact on complexity and performance of (1) is minor. At worse,
comparison of the value of a pointer becomes comparision of the tab bits
of a pointer. The impact of (2) is also minor, as boxed bignums are
already present. The impact of (3) is non-trivial but isolated: the
fundamental operations on a char are testing its type and converting it
to an integer, and the code for these changes from:

   (define (char? object)
     (= (get-tag-bits object) CHAR-TAG-VALUE))
   (define (char->integer char)
     (get-value-bits char)

to:

   (define (char? object)
     (or (= (get-tag-bits object) CHAR-TAG-VALUE))
	(= (get-box-tag-bits object) BOXED-CHAR-TAG-VALUE)))
   (define (char->integer char)
     (if (= (get-tag-bits object) CHAR-TAG-VALUE)
       (get-value-bits char)
       (get-boxed-char-value-bits char)))

Any code size expansion or some loss of efficiency will likely be small.

Is this clear?

Regards,

Alan
--
Dr Alan Watson
Centro de Radioastronomía y Astrofísica
Universidad Astronómico Nacional de México