[M3devel] REFANY-keyed tables?

[JC Chu]

> Another way of seeing it is that if st(x) = st(y) then x and y are pointing to the same object.


Well the language definition does state that st(x) = st(y) implies x = y (and the opposite implication is obvious).


>>> 5. But then y still has the old value: st(y) = s.


>> With a correctly implemented GC (which we have), step 5 can't happen.


> If x and y point to the same object and you don't assign to them, they keep pointing to the same object.


Hmm...  I’ll glad this is the case, but I don’t see how it follows from the language definition alone.  I mean the GC itself changes things on its own, without my having to assign to anything.  If some poor GC did let step 5 happen and we have x # y and st(x) # st(y), it is still consistent with x = y iff st(x) = st(y).  So this nice property is implementation-specific after all...  Or did I miss anything from the language definition?

— JC Chu


----------------------------------------
> To: jcchu at acm.org
> CC: mika at async.caltech.edu; m3devel at elegosoft.com
> To: rodney_bates at lcwb.coop
> Subject: Re: [M3devel] REFANY-keyed tables?
> Date: Sun, 2 Mar 2014 12:17:41 -0800
> From: mika at async.caltech.edu
>
>
> Right, right.
>
> Another way of seeing it is that if st(x) = st(y) then x and y are
> pointing to the same object. The language specification does talk about
> memory, albeit abstractly.
>
> If x and y point to the same object and you don't assign to them, they
> keep pointing to the same object. That is the language semantics,
> and yes, by The Green Book I mean Systems Programming with Modula-3.
>
> And yeah whatever the implementation does has to respect the language
> semantics. If the GC wants to change the bit representation of x then it
> has to change the bit representation of y in a way such that your program
> will always see x = y. Note that it is NOT literally required that the
> bit representation of x always equals the bit representation of y. But
> I do believe the GC accomplishes x = y by ensuring that their bit
> representations are always equal in any state where they may be checked
> by your program.
>
> Another way of looking at this is to consider references in the language
> as products of NEW. Every reference to a particular evaluation of NEW
> always points to the same thing. If NEW has only been evaluated once
> in your program, there can only be two REFANYs: NIL and the result of
> that NEW. Those are the language semantics. And of course the implementation
> has to go to some effort to ensure this property holds even as it fiddles
> with the bit representations of the two REFANYs. (NIL's bit representation
> is *probably* constant, but it doesn't have to be...)
>
> Mika
>
> "Rodney M. Bates" writes:
>>
>>
>>On 03/02/2014 09:00 AM, JC Chu wrote:
>>>> You can't apply ^ to REFANY.
>>>
>>> That was a mistake on my part. Let me rephrase my worry as follows, where st(r) denotes the storage location pointed to by the reference r.
>>>
>>> 1. x, y: REF T, where T has an equivalence relation T.Equal.
>>> 2. Initially, x = y # NIL and st(x) = st(y) = s.
>>> 3. Then the GC creates a copy s' of s.
>>> 4. Then the GC updates x so that st(x) = s'.
>>> 5. But then y still has the old value: st(y) = s.
>>
>>With a correctly implemented GC (which we have), step 5 can't happen. The GC
>>will prevent any use of y by a running mutator thread until it (the GC) has
>>updated y as well as x, so x = y again. My questions to Tony were about how the
>>M3 GC accomplishes this, and it does.
>>
>>The motivatation for not giving REFANY a succeeding Hash is that, after
>>the updates, x = y # <the value x and y had before the move>. This would
>>make a hash table fail, even if x = y works as defined. Mika is right,
>>as long as you stay in the safe subset of the language. You simply can't
>>write a hash function on a REFANY at all.
>>
>>Somebody could, however, declare the module with the Hash function UNSAFE,
>>LOOPHOLE the REFANY value to a Word.T (or something else, if the sizes were
>>not the same), and return that or something derived from it.
>>
>>It is never feasible in any language to define everything that can happen,
>>when type-unsafe techniques are used. That inevitably gets into implementation
>>details, which we often make assumptions about rather cavalierly. Part of
>>the wisdom of Modula-3 is that it clearly defines what the safe subset is,
>>then equally clearly defines the semantics of that,, without getting into
>>implementation.
>>
>>I was careless about glossing over the safe/unsafe distinction.
>>
>>>
>>> At step 5, we have x # y, st(x) # st(y), and T.Equal(x^, y^). If x is stored in a container for REFANY, then a membership check for x using y will fail,
>> because it can only be based on Refany.Equal. (If T.Equal is used then we won’t have this problem.)
>>>
>>>> REFANY behaves the way the Green Book says it does.
>>>
>>> You mean Systems Programming with Modula-3?
>>>
>>> — JC Chu
>>>
>>> -----Original Message-----
>>> From: mika at async.caltech.edu [mailto:mika at async.caltech.edu]
>>> Sent: Sunday, March 2, 2014 21:03
>>> To: JC Chu; rodney_bates at lcwb.coop
>>> Cc: m3devel at elegosoft.com
>>> Subject: Re: [M3devel] REFANY-keyed tables?
>>>
>>>
>>> I just want to make an observation...
>>>
>>> REFANY behaves the way the Green Book says it does. There's not a word in there about concurrent garbage collectors or bit-pattern representations of RE
>>FANY.
>>>
>>> If a, b : REFANY and a = b then a and b point to the same object.
>>>
>>> You can't apply ^ to REFANY. The only thing you can do to a value beyond = is narrow it to another type. That's why there's no Hash for REFANY.
>>> (Not because the garbage collector is implemented one way or another.)
>>>
>>> Of course you can put REFANY in a list. You can make as many copies in as many places as you want and = will continue working.
>>>
>>> The rest is implementation...
>>>
>>> I'm not saying there isn't a lot of implementation, or that the implementation doesn't have to get clever about some things, but you really don't need to
>> think about the implementation to know what you can and can't do with REFANY. It's all in the Green Book.
>>>
>>> I definitely would not suggest messing with the garbage collector because you want to get something working with REFANY in a pure Modula-3 program.
>>> It defeats the purpose of REFANY.
>>>
>>> If you MUST hash a whole bunch of objects that have being REFANY as their only thing in common I'd suggest using TYPECODE and registering hash procedures
>> for each type you're interested in. This is a simple enough thing that Modula-3's runtime "introspection" facilities more than suffice. (Those facilitie
>>s are more limited than Java's, for mostly good reasons.)
>>>
>>> Mika
>>>