spec: is dict[k] an error if k is unhashable?

[alandonovan]

The Go implementation of Starlark, following Python2 and 3, rejects a dictionary operation in which the key is unhashable:

$ starlark -c '{}.get([])'
Traceback (most recent call last):
  cmdline:1:7: in <toplevel>
  <builtin>: in get
Error: get: unhashable type: list

$ python2 -c '{}.get([])'
Traceback (most recent call last):
  File "<string>", line 1, in <module>
TypeError: unhashable type: 'list'

$ python3 -c '{}.get([])'
Traceback (most recent call last):
  File "<string>", line 1, in <module>
TypeError: unhashable type: 'list'

By contrast, the Java implementation permits a lookup with any value, including unhashable ones. The lookup fails, though it is not necessarily an error, so execution may continue:

$ blaze-bin/third_party/bazel/src/main/java/com/google/devtools/starlark/Starlark  
>> {}.get([])
None

(This behavior occurs even when the dict is non-empty, so it can't be explained as the implementation taking a shortcut for empty dicts.)

Clearly, the Java implementation is in fact hashing the key, so the error message ("unhashable type") issued by an update operation such as {}.update([([], 1)]) seems not to tell the whole story.

I think the spec should state that all dict operations attempt to hash the key (even when unnecessary, such as {}.get(k)) and fail if the key is unhashable.

[laurentlb]

See bazelbuild/bazel#8730

[josharian]

See also google/starlark-go#113 and google/starlark-go#165

[alandonovan]

More weirdness: are functions hashable or not?

% starlark
Welcome to Starlark (go.starlark.net)
>>> {len: 1}
{<built-in function len>: 1}
>>> len in {}
False
>>> {}.get(len, False)
False

% python2
Python 2.7.17rc1 (default, Oct 10 2019, 10:26:01) 
>>> {len: 1}
{<built-in function len>: 1}
>>> len in {}
False
>>> {}.get(len, False)
False


% python3.8
Python 3.8.1 (default, Dec 31 2019, 14:30:41) 
[GCC 8.3.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> {len: 1}
{<built-in function len>: 1}
>>> len in {}
False
>>> {}.get(len, False)
False

% blaze-bin/third_party/bazel/src/main/java/com/google/devtools/starlark/Starlark
>> {len: 1}
unhashable type: 'function'
>> len in {}
unhashable type: 'function'
>> {}.get(len, False)
unhashable type: 'function'

[brandjon]

Consistency with set semantics (see also discussion in #290) also requires that we fail on unhashable values. So let's do it.

(This also suggests that a future type checker should reject attempts to access or update a dict key with unhashable type.)

Created #296 for the function question.