[M3devel] small objects

[Tony Hosking]

On 7 Apr 2009, at 10:42, Mika Nystrom wrote:

> You mean this proposal (you had two, I think)?

Yes, this is the proposal I converged on.  It really is only minimal  
change to the type system: introduction of a third hierarchy of   
TAGGED reference types.  I did something similar for orthogonal  
persistence a few years ago where it was useful to have a TRANSIENT  
reference hierarchy for things that should not persist.  [The  
semantics was that every run of a program would initialize TRANSIENT  
references to NIL rather than have them have the persistent value.   
This was slightly messier in that I also permitted TRANSIENT REFANY <:  
REFANY, which was a little odd.]

> --
>
> 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.
>
> ---
>
> I like it fine, I think... I'm just worried, generally, about
> changing the type system.  Hmmmm... you mean that the TAGGED
> things would just be a separate hierarchy?

The change is relatively minor in that it doesn't touch the original  
REFANY hierarchy.

> So you'd just add TAGGED in front of the REFs for this new hierarchy.
> But why no NULL?

No NULL because then we need a test for both NIL and values of type  
TAGGED INTEGER on every dereference.  You can easily declare:

TYPE Null = TAGGED INTEGER;
CONST Nil = VAL(0, TAGGED INTEGER);

The point is that TAGGED INTEGER now lets you have a range of non- 
pointer reference values, whereas NIL is the singleton non-reference  
value in type NULL.

> And you're comfortable with doing the conversions automatically?

No, I said that the conversions needed to be explicit

>
> So
>
>  tx : TAGGED INTEGER := 5;

tx: TAGGED INTEGER := VAL(5,TAGGED INTEGER);

>  x  : INTEGER := tx;

x: INTEGER := ORD(tx);

> would be OK?
>
> In that case it's just the m3tk that needs to be modified, and
> that's just busy work, I think.  If it works it's beautiful...

As I said, I am almost done with the compiler changes, and only need  
to push it into the run-time.  Things like m3tk and pickles will need  
to be smartened up as necessary.

>
>
>     Mika
>
>
>
> Tony Hosking writes:
>> I really don't like your proposal for the reasons you mention.  It
>> makes regular REF more expensive than it currently is.  What is it
>> about my relatively minor changes to the type system that you object
>> to?  I've just about finished changing the compiler front-end (in
>> relatively minor ways) to accomodate the proposal I made yesterday.
>> And it has the advantage of separating REF from TAGGED REF so we keep
>> the standard REF clean.
>>
>> On 7 Apr 2009, at 00:50, Mika Nystrom wrote:
>>
>>> Hi Rodney,
>>>
>>> I would like this capability too, but I am a bit wary of Tony's
>>> idea of changing the Modula-3 language---even in a "minor" way.
>>> I've been working for the last week or so on an application using
>>> the Modula-3 Toolkit, and I must say I have realized that the
>> Modula-3 type system has a lot more subtleties than I thought.  I
>>> would not want to make any real changes to it.  There's a paper
>>> called "The Modula-3 Type System" by Cardelli, Donahue, Kalsow, and
>>> Nelson that is worth studying in detail before making any changes
>>> whatsoever, I think.  Also remember that changes to the type system
>>> will affect m3tk and anything that depends on m3tk (which includes
>>> two or three stub generators in the main tree and who knows how
>>> many dependencies outside of it).
>>>
>>> I'm still not sure why we can't take the approach of Word.T .
>>> Make a RefanyOrInt.T that can safely be:
>>>
>>> 1. Tested whether it is a small integer or a REFANY
>>>
>>> 2. If a REFANY, be dereferenced as normal, *or* via
>>>  RefanyOrInt.ToRefany
>>>
>>> 3. If a small integer, can be extracted via RefanyOrInt.ToInt
>>>
>>> 4. Created either as a small integer or a REFANY
>>>
>>> Any other operations on it (including ISTYPE and TYPECASE, at least
>>> when the object is a small integer) would result in a checked  
>>> runtime
>>> error.
>>>
>>> Note that with the declaration "RefanyOrInt.T = REFANY", the current
>>> compiler will as far as I know not accept any operations on
>>> RefanyOrInt.T outside of ISTYPE, TYPECASE, and NARROW (explicit or
>>> implicit).
>>>
>>> I wouldn't be surprised if most of what I'm proposing already works
>>> (i.e., crashes with a checked runtime error as it should) with the
>>> current runtime.  Anything that slips through would need to be fixed
>>> up with a one-bit check of the LSB of the REFANY for the operations
>>> mentioned above.  Unfortunately this has to be done for operations  
>>> on
>>> every REFANY, not just the new type.
>>>
>>> I think that Modula-3 programmers are already aware that using
>>> REFANYs involves forcing the runtime to do extra type-checking work,
>>> so they already know not to use them if they are looking for maximum
>>> performance, so I don't think that burdening operations on REFANY
>>> with an extra one-bit check is too onerous.
>>>
>>> An advantage of my proposal is that the amount of code in the new
>>> proposed library is truly diminutive.  In fact, I think I posted
>>> pretty much that code to the list a few weeks ago.
>>>
>>> (If you missed it, it's
>>>
>>> http://www.async.caltech.edu/~mika/interp/
>>>
>>> )
>>>
>>>    Mika
>>>
>>>
>>> "Rodney M. Bates" writes:
>>>> I spent quite a bit of time playing with a more general system  
>>>> where
>>>> there is a set of "tagged" types, with (an implementation-defined
>>>> subrange of) INTEGER and a reference type both being a subtype of a
>>>> tagged type.  It might have been tolerable, if it weren't for the
>>>> interaction with object subtypes and opaque types, which quickly
>>>> gets deep into a deep linguistic tar pit.
>>>>
>>>> Tony's approach is much simpler and would serve what I see as the
>>>> need.  It does sacrifice any static checking of what reference type
>>>> is being tagged, and will also require an extra runtime ISTYPE/
>>>> TYPECASE.
>>>>
>>>> Would INTEGER and REFANY be assignable to TAGGED, or would there
>>>> also need to be an explicit conversion in that direction too, say
>>>> VAL(x, TAGGED)?  I think I favor the explicit conversion here.  It
>>>> is a bit inconsistent with the usual Modula-3 assignability
>>>> philosophy,
>>>> but not requiring the explicit conversion already gets your toes
>>>> into tar.
>>>>
>>>> We would have to have something more like ISTYPE, though, which  
>>>> will
>>>> tell which type the value belongs to without risking a runtime  
>>>> error,
>>>> which VAL would do.
>>>>
>>>> An intermediate approach might be to have a set of tagged types
>>>> constructed by, say, TAGGED T, where I is a reference type, but
>>>> with no subtype relations on them at all, thus still requiring
>>>> the explicit conversions and checks.
>>>>
>>>> I do want to say, I _really_ want this capability somehow.  I have
>>>> an ADT module whose internal data structure, for full generality,
>>>> needs to have two heap objects (the second because it has nonstatic
>>>> size) and 11 total words counting the orginal pointer, in the  
>>>> case of
>>>> values that would fit directly  into the "pointer" word.  Moreover,
>>>> these small cases are in the great majority.
>>>>
>>>> Besides the 11-to-one increase in actual occupied space, there
>>>> is extra time for allocation, periodic tracing, and collection,  
>>>> space
>>>> loss due to heap fragmentation, and time/space tradeoff loss due to
>>>> reduced locality of reference.  So sometimes, it would be a big
>>>> performance gain if we could do it.
>>>>
>>>>
>>>> Tony Hosking wrote:
>>>> It is a much more pervasive hack than I would be comfortable with
>>>>> since it touches on the compiler (for all the type operations) as
>>>>> well
>>>>> as the run-time system in ways that are pretty gross.  I would  
>>>>> much
>>>>> rather have a new TAGGED builtin.  ISTYPE would not work on it  
>>>>> since
>>>>> that only works on references.  The only thing you need is a way  
>>>>> to
>>>>> extract the value -- we could overload VAL(x, T) where x can be a
>>>>> TAGGED and T can be REFANY or INTEGER.
>>>>>
>>>>>