[M3devel] small objects

[Rodney M. Bates]

Tagged types and object type hierarchies:

At first, I was imagining that you could create
an object subtype of a TAGGED type:

(* An untagged hierarchy: *)
TYPE O1 = OBJECT F1: INTEGER END;
TYPE O2 = O1 OBJECT F2: CHAR END;
TYPE O3 = O2 OBJECT F3: BOOLEAN END:

(* Tag each one directly: *)
TYPE TO1 = TAGGED O1;
TYPE TO2 = TAGGED O2;
TYPE TO3 = TAGGED O3;

(* A tagged hierarchy: *)
TYPE TO2S = TO1 OBJECT F2: CHAR END;
TYPE TO3S = TO2S OBJECT F3: BOOLEAN END;

Is TO2S = TO2 and TO3S = TO3?

Is O2 <: TO2S and O3 <: TO3S?

Therein lies tar.  The type equality and subtype relations are getting
awfully elaborate for a language that advertises relative simplicity.

Then I thought about two parallel hierarchies, one tagged and one not,
as Tony's second proposal.  But that leaves it awfully inconvenient
to have both a tagged and untagged counterpart that are otherwise the
same, and you need the untagged counterpart to do ISTYPE/NARROW/TYPECASE/:=
to get the "definitely-a-heap-reference" value out of a tagged type.

If I read it right, Tony's first proposal does not allow to subclass an
already tagged type  (i.e., no "tagged hierarchy" as above).  Is that
what you meant, Tony?  If so, I think this is enough, and avoids the
complicated type equality and subtype relations.

A separate issue:

On the INTEGER side of this, I think we need a builtin type that is an
implementation-defined subrange of INTEGER, that can hold just the
integer values a tagged type can hold.  Maybe "TAG"?  (Actually, this
name is a poor choice, since it's not the tag itself, but it's the best
I can think right now, so I will use it in discussion). 

If we really want to constrain the implementation to always use exactly
the low bit as the tag, then CARDINAL would do for this.  A new builtin
type would leave open other tagging representations with other ranges of
representable integers, as well as the low-bit tag with signed integers.

Then we could also allow ISTYPE(x, TAG), etc. to get the "definitely-an-
integer" value out.

This gives fully type-safe support for small objects, which I really
prefer, if not too complicated. 

  

Tony Hosking wrote:
> I like the notion of having a TAGGED INTEGER type that is a hybrid 
> ordinal/reference.
>
> Subtyping rules for references would now be as follows:
>
> NULL <: REF T <: REFANY
> TAGGED INTEGER <: REF T <: REFANY
>
> ROOT <: REFANY
> NULL <: T OBJECT ... END <: T
> TAGGED INTEGER <: T OBJECT ... END <: T (but only for T <: REFANY, not 
> T <: ADDRESS)
>
> Thus, TAGGED INTEGER is a funny sort of hybrid ordinal/reference 
> type.  Values of TAGGED INTEGER are non-pointer values similar to the 
> value NIL.  We can then do ISTYPE(x, TAGGED INTEGER), and NARROW(x, 
> TAGGED INTEGER), and TYPECODE(TAGGED INTEGER), similarly to ISTYPE(x, 
> NULL), NARROW(x, NULL), and TYPECODE(NULL).
>
> Because TAGGED INTEGER is an ordinal we can extract the integer value 
> it holds using ORD(x).
> Similarly, we can construct a TAGGED INTEGER using VAL(x, TAGGED 
> INTEGER).
>
> ***The only problem with this scheme is how to efficiently perform 
> run-time tests for dereferencing NULL, and TAGGED INTEGER?***
>
> So, here is a slightly less elegant alternative that is probably 
> straightforward to implement.  Introduce a separate TAGGED hierarchy.
>
> NULL <: REF T <: REFANY
> NULL <: UNTRACED REF T <: ADDRESS
> TAGGED INTEGER <: TAGGED REF T <: TAGGED REFANY
>
> Note that NULL is not a subtype of TAGGED REF T or TAGGED REFANY.
>
> ROOT <: REFANY
> TAGGED ROOT <: TAGGED REFANY
> NULL <: T OBJECT END <: T where T <: REFANY or T <: ADDRESS
> TAGGED INTEGER <: T OBJECT ... END <: T where T <: TAGGED REFANY
>
> Note that NULL is not a subtype of T OBJECT ... END where T <: TAGGED 
> REFANY.
>
> This way, tagged references only need a run-time test for the tag on 
> dereference (we can throw an "attempt to dereference TAGGED INTEGER" 
> at run time, just like we throw "attempt to dereference NIL" for 
> untagged references).  This check can be a straightforward test of the 
> low bit tag.  Of course, the weird thing here is now that we don't 
> have a single NULL value for TAGGED references --- we have multiple 
> null values VAL(x, TAGGED INTEGER).  Instead of asking "x == NIL" we 
> must ask "ISTYPE(x, TAGGED INTEGER)".
>
> Of course, because TAGGED INTEGER is an ordinal, we can also perform 
> the usual ordinal operations like INC(x), DEC(x), wherever x is typed 
> TAGGED INTEGER.
>