Explanation of TraversalKey, and a change proposal (was Re: Labeled promises?)

On Nov 30, 2005, at 10:34, Mark Miller wrote:

>> Would it break anything in the E model to attach labels to promises?
>
> The only issue I see is how it might effect the sameness semantics of
> TraversalKeys. If there's no issue there, then I think this is a  
> good idea.
> It may be a good idea anyway, but it'd take more examination.

I believe this shouldn't be a problem, since under all circumstances  
in which the visible label might change, the TraversalKey-identity  
will also have changed. Is there some other problem you're thinking of?

> A placeholder for an explanation of TraversalKeys is at
> http://www.erights.org/javadoc/org/erights/e/elib/tables/ 
> TraversalKey.html .
> Kevin, could you post an explanation? Thanks.

Um. I don't actually understand TraversalKey that well. What I know I  
probably found from some existing documentation and reading the E-on- 
Java implementation, which I copied for E-on-CL.

Intent:

A TraversalKey is always Settled. Therefore, it can be used as an  
'identity of' some value which has not yet become settled, so that  
cyclic, unsettled data structures may be traversed with a map or set  
used to track what portions have been seen before.

(This is used in TextWriter and serialization, for example.)

Semantics:

A TraversalKey K can be generated from some other reference O. This  
key is the same as some other TraversalKey L of O, if and only if no  
promise of which O is composed has been resolved (whether or not it  
was resolved to another promise) between the times K and L were  
generated.

Implementation:

A TraversalKey is composed of the target reference, a hash code, and  
a "fringe" set.

The hash code is the sameness hash of the target; promises are  
included as their primitive identity hash. The fringe is the set of  
all promises contained in (the Selfless portion of) the target.

Two TraversalKeys are the same if their hash codes are equal, their  
targets are sameYet *and* their fringes contain the same elements.

The last restriction ensures that two TraversalKeys whose targets  
would not have been sameYet when the TraversalKeys were created will  
never be considered the same, which would break sameness consistency.

Analogy:

A TraversalKey is essentially 'the sameness' of a reference *at a  
particular time*. Thus it does not vary with time, unlike the  
original possibly-unsettled reference, and so a TraversalKey is  
always settled.

If __equalizer.sameYet did not exist, it could be emulated with  
__equalizer.sameEver(makeTraversalKey(a), makeTraversalKey(b)).

MarkM: What would you think of having makeTraversalKey be a method of  
Equalizer, instead of a separate import? TraversalKey's semantics are  
fundamentally connected to the Equalizer, so this seems to me to fit  
well.

Advantages:
   * Fewer independent paths via which sameness definitions are  
provided to the E environment; this might help with refraction.
   * More discoverable; it can be found from help(__equalizer).
   * In E-on-CL, this would eliminate one importable-primitive  
declaration.
   * If Equalizer and TraversalKey were implemented in E, it would  
make sense to define them together since they share 'private' unsafe  
operations.

--

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