Tagged Architectures, a question

["Daniel L. Weinreb" <DLW@alderaan.scrc.symbolics.com>]

Some of the Burroughs machines had tags of a sort, but I am pretty sure
they did not use them for representing datatypes of basic data items,
the way Lisp machines do.  You ought to either research this, or not
bother to mention it at all.  I am pretty sure the Cray and CDC machines
do not have tags of any sort.

In some architectures, interpretation of tags is done by microcode
rather than real hardware.  This includes the MIT CONS/CADR architecture
(the Symbolics LM-2 is the same architecture).  The Symbolics 36xx
series has actual hardware to interpret tags (of course the microcode
and higher-level software look at and set tags, too).

In both the CADR and 36xx architecture, there are tags in the pointers,
but there is also sometimes further data stored in memory that
determines the type of an object.  For example, a rational number and a
complex number both have the same tag in the pointer; you have to
dereference the pointer to further disciminate the type.

      Now I understand that when I call (CAR FOO), the hardware does a
    data type check (in parallel) of the pointer for FOO.  What happens,
    however, when I call (+ X Y), when X and/or Y are either bignums or
    large FP numbers?  Do I do the checking on the tag bits for the pointers
    in X & Y?  If so, then when I do the indirection to the actual data
    words, am I adding two 32 bits quantities whose tag bits are ignored, or
    am I adding two 40 bit quantities (mod GC)? 

It happens in several steps.  First, the tag-checking hardware looks at
the tags of both operands and notes that this is a "hard" case (two
bignums), and traps out to microcode for handling such cases.  From this
point on, the tag-checking hardware is no longer involved, and further
examinations of tags are done by microcode or macrocode (compiled Lisp).
The pointers are then dereferenced to figure out exactly which kind of
number we're talking about.  I don't exactly understand your last
sentence, but you never add 40 bit quantities: the adder is really a
32-bit adder.  In the case of bignums, the bits that represent the number
are stored in the low 32 bits of a block of 40-bit words in memory.

Have you read Dave Moon's article on the 36xx architecture, in IEEE
Computer last summer?  It might help make more of this clear.