AA key conversion woes

[H. S. Teoh]

On Wed, Apr 18, 2012 at 12:37:21AM -0400, Jerry wrote:
> Sean Kelly <sean at invisibleduck.org> writes:
[...]
> > I'm inclined to say that if a reference type is used as a key to an
> > AA, the user either has to promise not to change (assumeUnique) it
> > or explicitly .idup it himself on insertion.
> 
> +1.  If AA's insist on immutable object keys, I worry that that will
> force more folks to roll their own hashtables when working with large
> tables where the cost of duping all those keys actually matters.
> 
> Also, I have found it useful on a number of occasions to key a hashtable
> with an object where the hash function is only computed on part of the
> object and the rest is mutable.
[...]

Thanks for pointing out this case. It's definitely a valid (and arguably
important) case, so the built-in AA implementation shouldn't insist on
immutable keys. (Though I should add that you'll need to implement a
compatible opEquals with your custom hash function for this to work
correctly, since the AA lookup code *does* do key comparisons, not just
hash value comparisons.)

So really, what AA's really want with its keys is that their *hash
value* and opEquals value (in the abstract sense) be immutable. Whether
the key is actually immutable is, in some sense, unimportant if the hash
value remains constant, and opEquals still compares equally with its
previous state.

However, going to the other extreme (completely trust the user to make
.toHash and .opEquals consistent and "immutable", and allow keys with
any kind of qualifiers) also causes other kinds of problems, most
notably with implicit conversions for key literals and AA method
const-correctness. So what about this instead:

- Any type that the user can define, that allows custom toHash and
  opEquals methods, are allowed to have any qualifiers (AFAIK, this is
  basically any struct and class?);

- Built-in value types are allowed any qualifiers (in this case it
  doesn't matter because unqualified and immutable are interconvertible
  via assignment);

- Built-in reference types (pointers, refs, arrays) must be either
  tail-immutable, or the tail must be a struct or class (i.e., the user
  is allowed to use arrays of unqualified objects with custom toHash and
  opEquals as AA keys).

This should allow the "nice" properties we can get from having the type
system enforce key immutability, for simple key types, and still allow
users to do complex stuff (define their own toHash/opEquals that ignore
parts of the object) when they need to.

If it were possible, I'd prefer to have the language enforce toHash and
opEquals immutability, but I don't think that is possible (since it can
potentially involve solving the halting problem). So this is the best
compromise I can think of right now.

What do people think of this new idea?

(Or should I just let users use assumeUnique and leave it at that?)


T

-- 
Questions are the beginning of intelligence, but the fear of God is the
beginning of wisdom.