[M3devel] REFANY-keyed tables?

Tue Mar 4 01:03:33 CET 2014

I see.  So it is expected for garbage collectors to ensure that, as Tony put it, ‘every reference to a particular evaluation of NEW always points to the same thing’.

— JC Chu

-----Original Message-----
From: Antony Hosking [mailto:hosking at purdue.edu] 
Sent: Monday, March 3, 2014 22:58
To: JC Chu
Cc: mika at async.caltech.edu; Rodney M. Bates; ^M3DEVEL
Subject: Re: [M3devel] REFANY-keyed tables?

The GC maintains what is called a to-space invariant: all mutators are switched to the copy space before the collector starts moving objects.  The read barrier ensures that mutators can never see old space objects.  But as Mika notes, this is an implementation detail that ensures the language semantics in which reference equality just works as you would expect.  The same is true of Java or any garbage collected language.

Sent from my iPad

On Mar 3, 2014, at 8:25 AM, JC Chu <jcchu at acm.org> wrote:

>> 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
>>>>                         