Tagged Architectures, a question

[David Vinayak Wallace <GUMBY@mc.lcs.mit.edu>]

    Date: Thu, 15 Oct 87 11:10:28 PDT
    From: Bil Lewis <lewis at rocky.stanford.edu>

    There are machines that specifically tag all data words with type
    information...
    When they encountered X+Y, the data was loaded into the registers,
    the instruction + was called, and the hardware took care of
    deciding if it should call the FP add, the integer add, etc.

The 3600 does this also.

    Some of the special purpose personal machines also have hardware
    tags: the D-machines, the Lispms, etc.(?)

Neither the D-machine nor the lispms (by which I mean the cadr) is
tagged, as far as I can remember.  But see below.  The D-machines were
(are) all general-purpose microcoded machines (decendents of the Alto).
					       
					       On the Lispms, however,
    it is the POINTERS that are tagged with the type of the object
    pointed to, not the actual data word.
    Taking the Symbolics I machine as an example (32 bit pointers with
    8 more bits for tag + GC)...

    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)?

Lispm here means the later Symbolics machines (36xx and I-machine).
There's a little ambiguity in your language.  Small floats and fixes
are represented "immediately" -- that is, the tag bits say "use the
address field as the data itself."  So in those cases you just do a
hardware add of the data portion of the word.  Normally you wouldn't
have a pointer to these types.

In the case of a bignum, the data has to be boxed, and a piece of
microcode or macrocode used to operate on the pieces of the bignum.

    In other words, is the data itself ever tagged on these machines?
    If not, are the tag bits even used?  If so, what are they used
    for?

So this question is kind of funny.  In the case of immediate data the
full word is used, as we've seen.  But since, in the case of most
pointers, the contents will be pointers or immediates too, pretty much
all the tag and data bits are significant.

    And while we're at it, am I correct in calling the GC bits ``tag
    bits''?  CDR-coding bits are also tag bits?

Well, they're all tags.  I should have said "Type tag" above.  You
could call the cdr-code bits the "cdr tag" I suppose.  Would
substituting the word "label" for "tag" be less ambiguous?

Now, maclisp and many of its decendents used a system called BIBOP
(for Big Bag of Pages).  That is, a given page may hold only one kind
of datum.  So you can use the page number of an address (pointer) as
an index into a table to determine type.  Think of this as a tagging
scheme in which the tags and the pointers are kept in different parts
of memory!

If you're interested in the origins of this you might also want to
look at capability machines, which is where a lot of this technology
originated.