[M3devel] REFANY-keyed tables?

[mika at async.caltech.edu]

Here is the simple way of thinking about garbage collectors:

The only thing that your program might do differently if you turn off
the garbage collector is run out of memory sooner.  Nothing else about
its behavior should change---any change would point to a mistake
in the implementation of the garbage collector.  

    Mika

JC Chu writes:
>I see.  So it is expected for garbage collectors to ensure that, as Tony =
>put it, =E2=80=98every reference to a particular evaluation of NEW =
>always points to the same thing=E2=80=99.
>
>=E2=80=94 JC Chu
>
>-----Original Message-----
>From: Antony Hosking [mailto:hosking at purdue.edu]=20
>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) =3D st(y) then x and y are =
>pointing to the same object.
>>=20
>>=20
>> Well the language definition does state that st(x) =3D st(y) implies x =
>=3D y (and the opposite implication is obvious).
>>=20
>>=20
>>>>> 5. But then y still has the old value: st(y) =3D s.
>>=20
>>=20
>>>> With a correctly implemented GC (which we have), step 5 can't =
>happen.
>>=20
>>=20
>>> If x and y point to the same object and you don't assign to them, =
>they keep pointing to the same object.
>>=20
>>=20
>> Hmm...  I=E2=80=99ll glad this is the case, but I don=E2=80=99t 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 =3D y iff st(x) =3D st(y).  So this nice =
>property is implementation-specific after all...  Or did I miss anything =
>from the language definition?
>>=20
>> =E2=80=94 JC Chu
>>=20
>>=20
>> ----------------------------------------
>>> 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
>>>=20
>>>=20
>>> Right, right.
>>>=20
>>> Another way of seeing it is that if st(x) =3D st(y) then x and y are=20
>>> pointing to the same object. The language specification does talk=20
>>> about memory, albeit abstractly.
>>>=20
>>> If x and y point to the same object and you don't assign to them,=20
>>> they keep pointing to the same object. That is the language=20
>>> semantics, and yes, by The Green Book I mean Systems Programming with =
>Modula-3.
>>>=20
>>> 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=20
>>> program will always see x =3D y. Note that it is NOT literally =
>required=20
>>> that the bit representation of x always equals the bit representation =
>
>>> of y. But I do believe the GC accomplishes x =3D y by ensuring that=20
>>> their bit representations are always equal in any state where they=20
>>> may be checked by your program.
>>>=20
>>> Another way of looking at this is to consider references in the=20
>>> language as products of NEW. Every reference to a particular=20
>>> evaluation of NEW always points to the same thing. If NEW has only=20
>>> been evaluated once in your program, there can only be two REFANYs:=20
>>> 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=20
>>> 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...)
>>>=20
>>> Mika
>>>=20
>>> "Rodney M. Bates" writes:
>>>>=20
>>>>=20
>>>> On 03/02/2014 09:00 AM, JC Chu wrote:
>>>>>> You can't apply ^ to REFANY.
>>>>>=20
>>>>> 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.
>>>>>=20
>>>>> 1. x, y: REF T, where T has an equivalence relation T.Equal.
>>>>> 2. Initially, x =3D y # NIL and st(x) =3D st(y) =3D s.
>>>>> 3. Then the GC creates a copy s' of s.
>>>>> 4. Then the GC updates x so that st(x) =3D s'.
>>>>> 5. But then y still has the old value: st(y) =3D s.
>>>>=20
>>>> With a correctly implemented GC (which we have), step 5 can't=20
>>>> 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 =3D y again. My=20
>>>> questions to Tony were about how the
>>>> M3 GC accomplishes this, and it does.
>>>>=20
>>>> The motivatation for not giving REFANY a succeeding Hash is that,=20
>>>> after the updates, x =3D y # <the value x and y had before the =
>move>.=20
>>>> This would make a hash table fail, even if x =3D y works as defined. =
>
>>>> Mika is right, as long as you stay in the safe subset of the=20
>>>> language. You simply can't write a hash function on a REFANY at all.
>>>>=20
>>>> Somebody could, however, declare the module with the Hash function=20
>>>> 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.
>>>>=20
>>>> It is never feasible in any language to define everything that can=20
>>>> happen, when type-unsafe techniques are used. That inevitably gets=20
>>>> into implementation details, which we often make assumptions about=20
>>>> rather cavalierly. Part of the wisdom of Modula-3 is that it clearly =
>
>>>> defines what the safe subset is, then equally clearly defines the=20
>>>> semantics of that,, without getting into implementation.
>>>>=20
>>>> I was careless about glossing over the safe/unsafe distinction.
>>>>=20
>>>>>=20
>>>>> At step 5, we have x # y, st(x) # st(y), and T.Equal(x^, y^). If x=20
>>>>> is stored in a container for REFANY, then a membership check for x=20
>>>>> using y will fail,
>>>> because it can only be based on Refany.Equal. (If T.Equal is used=20
>>>> then we won=E2=80=99t have this problem.)
>>>>>=20
>>>>>> REFANY behaves the way the Green Book says it does.
>>>>>=20
>>>>> You mean Systems Programming with Modula-3?
>>>>>=20
>>>>> =E2=80=94 JC Chu
>>>>>=20
>>>>> -----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?
>>>>>=20
>>>>>=20
>>>>> I just want to make an observation...
>>>>>=20
>>>>> REFANY behaves the way the Green Book says it does. There's not a=20
>>>>> word in there about concurrent garbage collectors or bit-pattern=20
>>>>> representations of RE
>>>> FANY.
>>>>>=20
>>>>> If a, b : REFANY and a =3D b then a and b point to the same object.
>>>>>=20
>>>>> You can't apply ^ to REFANY. The only thing you can do to a value =
>beyond =3D 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=20
>>>>> another.)
>>>>>=20
>>>>> Of course you can put REFANY in a list. You can make as many copies =
>in as many places as you want and =3D will continue working.
>>>>>=20
>>>>> The rest is implementation...
>>>>>=20
>>>>> I'm not saying there isn't a lot of implementation, or that the=20
>>>>> implementation doesn't have to get clever about some things, but=20
>>>>> 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.
>>>>>=20
>>>>> 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.
>>>>>=20
>>>>> 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=20
>>>>> registering hash procedures
>>>> for each type you're interested in. This is a simple enough thing=20
>>>> that Modula-3's runtime "introspection" facilities more than=20
>>>> suffice. (Those facilitie s are more limited than Java's, for mostly =
>
>>>> good reasons.)
>>>>>=20
>>>>> Mika
>>>>>                        =20