Re: [cap-talk] __equalizer and such E operations

(CCing e-lang because this message contains discussion of E  
implementation; please do not reply to both lists.)

On Feb 12, 2008, at 23:15, Jonathan S. Shapiro wrote:
> On Tue, 2008-02-12 at 22:25 -0500, Kevin Reid wrote:
>> If the 'same' value has been computed multiple times (or passed over
>> a network), then it cannot have the same creation identity;
>> therefore, a structural comparison operation is useful. (Interning is
>> not feasible because of promises.)
>
> I am not entirely convinced that interning is infeasible. Is there  
> some
> reason that a promise cannot spontaneously resolve itself before being
> forced?

Forced? Promises in E are not lazy references. They resolve precisely  
when the holder of their resolver facet directs it.

Here's an example of the interning problem:

def a := [1, 2]

def [promise, resolver] := Ref.promise()

def b := [1, promise]

# At this point, a and b must obviously be separate instances;
# the equalizer will respond "indeterminate" if asked.

resolver.resolve(2)

# The equalizer should now respond that a equals b.

At this point, I see no means to combine a and b short of

  - keeping back-references from a promise to every non-selfless  
object containing a selfless object referring to it, so that the  
former may be retargeted to the interned instances of the newly  
settled[1] structure, or

  - having a garbage collector which replaces uninterned objects with  
interned ones when possible, and instructing it to perform a full  
sweep upon every promise resolution, or

  - having the comparison operator rewrite uninterned instances into  
forwarding pointers to interned instances, recursively, before  
comparing pointers -- which would require the ability to turn any  
(potentially Selfless) object into a forwarding pointer.

Of these methods, the third would result in a interning+comparison  
operation as complex as E's current equalizer, and the first two  
would be quite expensive, while still not enabling pointer comparison  
to mimic the "unknown" (as distinct from false) answers of the  
equalizer:

? def [p, r] := Ref.promise()
 > def a := [1, 1]
 > def b := [1, p]
 > __equalizer.optSame(a, b)
# value: null

? __equalizer.optSame([1, p], b)
# value: true

? __equalizer.optSame([2, p], b)
# value: false

optSame returns null if it cannot give a true or false answer yet.


(That said, it is entirely reasonable for an E implementation to  
combine multiple copies of the same structure *if it comes to know of  
them*, and I have an experimental version which does -- it is merely  
impractical (I believe) to maintain total knowledge.)


[1] A structure is said to be unsettled if it contains promises;  
settled if it does not.

-- 
Kevin Reid                            <http://homepage.mac.com/kpreid/>