[M3devel] Resummary of tagged reference proposals

[Rodney M. Bates]

Tony Hosking wrote:
> On 20 Apr 2009, at 23:35, Rodney M. Bates wrote:
>
>> I am going to try to resummarize the various proposals, as their
>> description has now gotten rather scattered around in all the
>> discussion.
>> ---------------------------------------------------------------------
>> Mika's proposal (I'll call it the "minimalist" propsal):
>>
>> Mika, please correct me if I misrepresent what you are proposing.
>>
>> There are no language changes at all, only changes in implementation.
>> The implementation of the existing type REFANY, and no other type,
>> allows it to have values whose lsb is nonzero.  ISTYPE, NARROW,
>> TYPECASE, and narrowing assignments, when and only when applied to
>> REFANY, have their generated code fixed so it checks the lsb, and, if
>> it is nonzero, consider the runtime type check to have failed, in
>> whichever way such a failure is already handled.
>>
>> The only effect is to liberalize the rules unsafe code must follow to
>> avoid undermining the safety of safe code.  Only unsafe code can
>> create or detect these misaligned values.  Today, it must never return
>> them in a variable of any reference type, lest the four narrowing
>> operations unexpectedly crash.  In the proposal, unsafe code would be
>> able to return such values in variables of type REFANY, but not any
>> other type.
>
> I don't see why we can't have safe creation of the misaligned values 
> as per Mika's interface.

Well, somebody has to implement that interface, and that module will 
have to be UNSAFE.
You weren't thinking of implementing it in C were you? ;-)
>
>> Already, the only things safe code can do with values of REFANY are
>> copy them around (which would happily work on misaligned values) and
>> narrow them.  With the implementation of the narrowing operations
>> changed, misaligned values can never escape from REFANY variables.
>>
>> In safe code, there is no way to detect whether a value of type REFANY
>> is misaligned.  Doing it by elimination, trying to narrow to any
>> proper subtype of REFANY, is impractical, as there are an unbounded
>> number of REF types to eliminate.
>
> An alternative would be to loosen the language spec to allow 
> TYPECODE(REFANY) and use this typecode for tagged references.  Then 
> one can explicitly test for it without elimination of alternatives.
>
>> If there is more than one abstract data type that uses this mechanism,
>> client code can not be prevented from mixing up values from the
>> different abstractions. (Perhaps this could be fixed by a language
>> change allowing BRANDED REFANY?)
>
> Indeed.
>
>> ---------------------------------------------------------------------
>> My (Rodney's) "safe" proposal:
>>
>> There is a new type named TAGABLE.  It is a subrange of INTEGER, whose
>> bounds are implementation-defined.  These can be queried by the
>> existing FIRST and LAST functions.  Similar to CARDINAL, it has all
>> the properties of a subrange type but is not the same type as the
>> corresponding subrange.
>>
>> There is a new type constructor TAGGED.  If T is any traced or object
>> type, including branded and opaque types, then TAGGED T is a new type
>> whose value set is the union of the value sets of T and TAGABLE.
>> Moreover,
>>
>> TAGABLE <: TAGGED T
>> T <: TAGGED T.
>>
>> IF T # U, then TAGGED T and TAGGED U are not the same type and have no
>> subtype or assignability relation to each other.
>>
>> The semantics of ISTYPE, NARROW, TYPECASE, and assignability of a type
>> to a type are generalized so that their to-be-narrowed operand can
>> have a tagged type, and if it does, their to-be-narrowed-to type can
>> be TAGABLE.
>
> Hmm.  It seems there is a nasty loophole in your spec.
> Consider:
>
> TYPE T = BRANDED OBJECT END
> TYPE U = BRANDED OBJECT END
>
> These are unrelated types.
>
> Now, the rules let me take:
>
> t: TAGGED T
>
> and obtain:
>
> i: TAGABLE := NARROW(t, TAGABLE);
>
> But TAGABLE <: TAGGED U
>
> so I can do:
>
> u: TAGGED U := t;
>
> Is that your intention?
>
>>
>>
>> Comments:
>>
>> Making TAGGED T have no relation to TAGGED U avoids a lot of really
>> complicated type equality and subtype rules.  The former would be a
>> drastic departure from the current state of Modula-3.
>>
>> It is up to the implementation to decide the bit representation of
>> tagged types, including how values of TAGABLE will be distinguished
>> from reference values.  Though the language would not require it, most
>> likely a word the same size as a pointer will be used.  Using the lsb
>> as the tag bit is an efficient encoding, because in any currently
>> conceivable machine, it will be zero for all pointers to heap objects.
>> There is no reason pickles would have to use the same representation
>> as compiler-generated code.
>>
>> The implementation should define the bounds of TAGABLE to be whatever
>> it can fit in its representation, after removing the values that are
>> true pointers.  If the lsb is used as a tag, this will no doubt be a
>> 31-bit integer on a 32-bit machine and 63-bit integer on a 64-bit
>> machine.  The language wouldn't even specify whether it is signed,
>> although somehow unsigned seems nice to me.  If it is unsigned and the
>> suggested encodings are used, TAGABLE would have the same bounds as
>> CARDINAL, but it really should be a separate type, so as not to
>> overconstrain the implementation.
>>
>> If T is branded, then the effects of branding will propagate to TAGGED
>> T, thus allowing independent abstract data types to ensure each one's
>> values can't be mixed up with the other's.  This will statically
>> detect misuses by client code.  However, TAGGED T is not a branded
>> type.
>>
>> If T is an opaque type, then TAGGED T can be used to combine the space
>> efficiency of tagging with the ability of an opaque type to reveal
>> some but not all of its properties.  To use this, client code will
>> have to narrow a value first, since access to methods/fields could not
>> have a definable meaning for a value in TAGABLE.
>>
>> On the other hand, T could be an opaque subtype of REFANY, thus
>> revealing almost nothing about TAGGED T to clients.  This would give
>> tagged types the existing ability of ensuring statically, that the
>> code in a revealed context will never get TAGGED REFANY, thus avoiding
>> extra runtime type checks.
>
>