[M3devel] small objects

[Mika Nystrom]

So following my previous email, I suggest the following, which
doesn't change the language definition at all:

INTERFACE TaggedInteger;
IMPORT Word;

TYPE T <: REFANY;
     V = [ TaggedMin .. TaggedMax ];

CONST TaggedMin = -Word.Shift(1,BITSIZE(REFANY)-2); 
      TaggedMax =  Word.Shift(1,BITSIZE(REFANY)-2) - 1;

PROCECURE Extract(t : T) : V;

PROCEDURE New(v : V) : T;

(* ...the usual generic support routines... *)

END TaggedInteger.

The compiler, runtime, and the implementation of this interface
would be responsible for hiding the values in REFANYs, doing the
correct thing for NARROW, ISTYPE, TYPECASE, TYPECODE, # and =...

What functionality is missing?  I think the compiler/runtime changes
are pretty much the same no matter which of the proposals you go
with...

     Mika

"Rodney M. Bates" writes:
>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.
>>