[E-Lang] '==' (was: Immutable map operations)

[Mark S. Miller]

At 02:30 PM Friday 3/23/01, Dean Tribble wrote:
>>I have been dreading the impending discussion of "==" on collections.
>
>I thought that was resolved some time ago, where there's a default '==' behavior, and one can supply one.  Were there remaining open issues?

I think you mean that the equivalence-class comparison operator used by a 
collection can be supplied.  Yes, I believe that's what was decided, and 
implemented in Hydro but not in E's current collections.  But I don't think 
that's what Tyler is referring to.

In E, one cannot supply an '==' behavior.  The integrity of '==' is 
guaranteed by the TCB.  In E, the left hand side can supply an '<=>' behavior.

In E, objects are either selfless or selfish.  All PassByCopy object are 
selfless (don't have a creation identity).  All PassByProxy objects, the 
default for objects defined in E, are selfish (do have a creation identity.) 
All selfless objects are immutable.  Selfish object may be mutable or not.  
Two selfless objects are == when they are indistinguishable.  Two selfish 
objects are == when they are in the same object -- the result of the same 
act of object creation.  Therefore, two objects that are == are 
indistinguishable.

Of course, one doesn't compare objects, one compares references to objects.  
Since SturdyRefs are an active controversy, I'll leave them alone for now.  
Two live references are == when they are both resolved, and are known to 
designate objects that are == by the above rules.  However, this doesn't 
necessarily mean that two live references that are == are indistinguishable. 
One may have resolved to a remote object and then become broken.  The other 
may still be unbroken, or be broken with a different problem.  Two 
references may be tested for computational/semantic equivalence by:

    a == b || E optProblem(a) == E optProblem(b)

To put it another way, '==' is equivalence up to brokenness.

Since the SturdyRef controversy will probably also cause us to revisit 
reference breakage rules, the above statements may also be brought into 
question.

A true or false answer from '==' must be stable.  Once "a == b" gives an 
answer for references "a" and "b", it must always give that same answer for 
those two references.  When references are sufficiently resolved locally (in 
this Vat) to know that "a == b" will never be true by the above rules, then 
false should be returned.  When references are insufficiently resolved to 
determine if "a" may ever be == to "b", then '==' must throw an exception.

The above paragraph is a constraint on a specification.  I some later time I 
need to write out the specification that meets this constraint.


In any case, ConstList and ConstMap are both PassByCopy, transparent, 
selfless, and immutable.  I assume the proposal is for the Hydro collections 
to be as well.  Therefore, two Hydro collections would be == not by creation 
but by equivalence.


        Cheers,
        --MarkM