Not the Territory (was: Announcing E 0.8.4: The Birthday Release)

[Tyler Close]

Back by reluctant acceptance ;)

> Persistence:
>
> Same story, except that both FlexMaps and ConstMaps get serialized to disk
> using the pair of arrays encoding.  A ReadOnlyMap simply encodes which
> FlexMap it is guarding.  Again, no hash information is written out, and all
> keys are rehashed on revival.

One of the neat things about my object database is that, except for the
constructor statement, in-memory hashtables and disk-based dynamic hashtables
are indistinguishable to the programmer. I need permanent hash codes to make
this possible. If E must always read in the entire hashtable and rehash, then it
will never have this feature. This means E will not be able to seamlessly work
with large quantities of data. This is a shame for a persistent programming
language.

> [?] Hashtable lookup should go no deeper than what's immutable.
> I think we're agreed that it's broken if our hashtables depend, for their
> hashcode and equality comparison, on data that can change.  This doesn't
> create a requirement for transitive immutability, just for hashtable
> key-traversal logic that's bounded to at most the immutable part of the key.

That's too fancy pants in my opinion. The programmer should think of the key as
being immutable.

> [-] Not at all.
> There's a long history of symbolic languages with relocating garbage
> collectors and EQ-based hash tables.  AFAIK, they have settled on two
> techniques for handling the problem:
>
> 1) Have the EQ-hashtable implementation be in bed with the garbage
> collector, and silently re-hash when relocating the keys.  (Macintosh Common
> Lisp)
>
> 2) Assign a unique hashcode other than memory address, which must stay
> attached to the object.

I still hold that their is no practical use for mutable keys, so both of these
techniques feel like ugly, unnecessary hacks to me. Aren't enough things already
in bed with the garbage collector?

> >If you restricted hashing to transitively immutable objects, then
> you wouldn't
> >have to make this guarantee. It would also relieve you of the need to hide
> hash
> >codes.
>
> [+] That's correct, but not adequate.
> What about u1 & u2?  Who has which one determines who has what authority.
> If we aren't preserving == and != relationships across space & time to
> otherwise featureless objects, then we aren't representing "Who has what
> authority?" across space & time.

As far as I could grok, your two Unsealers example only demonstrated that at any
given point in time == on two object references must function correctly. It did
not create the requirement for the left hand side and the right hand side to
permanently maintain their current value. Only your hashtable creates this
requirement (or the need to fake it by giving special treatment to hashtables).

I *really* don't understand why transitively immutable keys are not adequate.

Demanding transitively immutable keys would also encourage the E programmer to
write transitively immutable classes. This could make the E runtime fertile
ground for yet other optimizations.

> >It was because of this that I was thinking you could merge the overloaded []
> >into one concept under the , syntax and use [] for tree-based maps.
>
> [?] I sense the direction, but I can't see the details.
> Sounds like a good proposal to flesh out.  I look forward to understanding
> this.  It sounds promising.

Anything in a list such as:
a, b, c
is an E 0.8.4 hashtable. No need for normal tuples/lists. Any list contained
within [] gets sorted and becomes a tree-based map.

Note that you could delay actually allocating the hashtable until the list
becomes large enough to warrant it and an element search is attempted.

Doing things this way would effectively guarantee that E programs never do
unreasonably long O(n) searches.

Tyler