Re: A proposal to modify `None` so that it hashes to a constant

On 11/30/2022 8:48 PM, Rob Cliffe via Python-Dev wrote:
> Thank you for this very clear analysis, Oscar.
> It seems to me that this strengthens the OP's case.  I am curious as to 
> whether others agree.

I do.

> On 30/11/2022 13:35, Oscar Benjamin wrote:
>> On Tue, 29 Nov 2022 at 23:46, Steven D'Aprano <[email protected]> 
>> wrote:
>>> On Tue, Nov 29, 2022 at 08:51:09PM -0000, Yoni Lavi wrote:
>>>
>>>> It does make your argument invalid though, since it's based on this
>>>> assumption that I was asking for a requirement on iteration order
>>>> (e.g. like dict's iteration order = insertion order guarantee), which
>>>> is not the case.
>>> Yoni, I think this answer is disingenious.
>> I don't think it is disingenuous. There are just a lot of people
>> talking past each other and not quite understanding what each person
>> means because there is confusion about even the intended meaning of
>> terms like "deterministic". I will expand here with enough detail that
>> we should hopefully be able to avoid misunderstanding each other.
>>
>> There are probably other places where you could find mentions of this
>> in the docs but I just took a quick look in the Python 3.5 docs
>> (before hash randomisation) to find this mention of dictionary
>> iteration order:
>> https://docs.python.org/3.5/library/stdtypes.html#dictionary-view-objects
>>
>> What it says is
>> """
>> Keys and values are iterated over in an arbitrary order which is
>> non-random, varies across Python implementations, and depends on the
>> dictionary’s history of insertions and deletions.
>> """
>> The key point is the use of the term "non-random" which here is
>> intended to mean that although no particular ordering is guaranteed
>> you can expect to rerun the same program and get the same result
>> deterministically. A different version or implementation of Python
>> might give a different order but rerunning the same program twice
>> without changing anything should give the same result even if that
>> result depends in some way on the iteration order of some
>> dictionaries. I can't immediately find a similar statement about sets
>> but in practice the same behaviour applied to sets as well. Note
>> carefully that it is this *narrow* form of determinism that Yoni is
>> interested in.
>>
>> Of course there are some caveats to this and the obvious one is that
>> this statement does not apply if there are some objects that use
>> identity based hashing so this is not deterministic:
>>
>> class A:
>>      def __init__(self, data):
>>          self.data = data
>>      def __repr__(self):
>>          return 'A(%s)' % self.data
>>
>> a1 = A(1)
>> a2 = A(2)
>>
>> for a in {a1, a2}:
>>      print(a)
>>
>> Running this gives:
>>
>> $ python3.5 t.py
>> A(2)
>> A(1)
>> $ python3.5 t.py
>> A(1)
>> A(2)
>>
>> On the other hand if all of the hashes themselves are deterministic
>> then the program as a whole will be as well so this is deterministic:
>>
>> class A:
>>      def __init__(self, data):
>>          self.data = data
>>      def __repr__(self):
>>          return 'A(%s)' % self.data
>>      def __hash__(self):
>>          return hash(self.data)
>>      def __eq__(self):
>>          return self.data == other.data
>>
>> a1 = A(1)
>> a2 = A(2)
>>
>> for a in {a1, a2}:
>>      print(a)
>>
>> $ python3.5 t.py
>> A(1)
>> A(2)
>> $ python3.5 t.py
>> A(1)
>> A(2)
>>
>> So we have two classes of hashable objects:
>>
>> 1. Those with deterministic hash
>> 2. Those with non-deterministic hash
>>
>> A program that avoids depending on the iteration order of sets or
>> dicts containing objects with non-deterministic hash could be
>> deterministic. It is not the case that the program would depend on the
>> iteration order for its *correctness* but just that the behaviour of
>> the program is *reproducible* which is useful in various ways e.g.:
>>
>> - You could say to someone else "run this code with CPython 3.5 and
>> you should be able to reproduce exactly what I see when I run the
>> program". It is common practice e.g. in scientific programming to
>> record things like random seeds so that someone else can precisely
>> reproduce the results shown in a paper or some other work and this in
>> general requires that it is at least possible to make everything
>> deterministic.
>>
>> - When debugging it is useful to be able to reproduce an error
>> condition precisely. Debugging non-deterministic failures can be
>> extremely difficult. In the same way that you might want to reproduce
>> correctly functioning code it is also very useful to be able to
>> reproduce bugs.
>>
>> I can list more examples but really it shouldn't be necessary to
>> justify from first principles why determinism in programming is
>> usually a good thing. There can be reasons sometimes why determinism
>> is undesired or cannot or should not be guaranteed. It should not be
>> controversial though to say that all things being equal determinism is
>> usually a desirable feature and should be preferred by default. I
>> don't think that the 3.5 docs I quoted above used the words
>> "non-random" casually: it was an intended feature and people were
>> aware that breaking that behaviour would be problematic in many
>> situations.
>>
>> Of course in Python 3.6 this determinism was broken with the
>> introduction of hash randomisation for strings. It was considered that
>> for security purposes it would be better to have some internal
>> non-deterministic behaviour to guard against attackers. Specifically
>> the hashes of three types (str, bytes and datetime) were made
>> non-deterministic between subsequent CPython processes. The effect was
>> not only to change purely internal state though but also the
>> observable iteration order of dicts and sets which became
>> non-deterministic from one run of CPython to another. It was
>> anticipated at the time that this might be problematic in some
>> situations (it certainly was!) and so an environment variable
>> PYTHONHASHSEED was introduced in order to restore determinism for
>> cases that needed it.
>>
>> So now if you want to have reproducible behaviour with Python 3.6+ you
>> also need to fix PYTHONHASHSEED as well as avoiding the use of other
>> types of non-deterministically hashable objects in sets and dicts.
>> This is something that I have personally used mainly for the
>> reproducibility of rare bugs e.g. "to reproduce this you should run
>> the following Python code using commit abc123 under CPython 3.6 and
>> with PYTHONHASHSEED=1234".
>>
>> Subsequently in Python 3.7 dict iteration order was changed to make it
>> always deterministic by having it not depend on the hash values at
>> all, with the order depending on the order of insertions into the dict
>> instead. This introduced a *stronger* guarantee of determinism: now
>> the ordering could be expected to be reproducible even with different
>> versions and implementations of Python. For many this seemed to have
>> resolved the problems of undefined, implementation-defined etc
>> ordering. However this only applied to dicts and not sets and as of
>> Python 3.12 any issues about deterministic ordering still remain
>> wherever sets are used.
>>
>> The introduction of hash randomisation means that since Python 3.6
>> there are now three classes of hashable objects:
>>
>> 1. Objects with deterministic hash (int etc)
>> 2. Objects with non-deterministic hash that can be controlled with
>> PYTHONHASHSEED (bytes, str and datetime).
>> 3. Objects with non-deterministic hash that cannot be controlled
>> (id-based hashing).
>>
>> The question in this thread and others is which of these three classes
>> None should belong to. Although None is just one particular value it
>> is a very commonly used value and its non-deterministic hash can creep
>> through to affect the hash of larger data structures that use
>> recursive hash calls (e.g. a tuple of tuples of ... that somewhere
>> contains None). Also certain situations such as a type hint like
>> Optional[T] as referred to by the OP necessarily use None:
>>
>> $ python -c 'from typing import Optional; print(hash(Optional[int]))'
>> -7631587549837930667
>> $ python -c 'from typing import Optional; print(hash(Optional[int]))'
>> -6488475102642892491
>>
>> Somehow this affects frozen dataclasses but I haven't used those
>> myself so I won't demonstrate how to reproduce the problem with them.
>>
>> Here is a survey of types from builtins:
>>
>> NoneType bool bytearray bytes complex dict ellipsis enumerate filter
>> float frozenset int list map memoryview object range reversed set
>> slice str tuple type zip
>>
>> We can divide these into the three classes described above plus the
>> non-hashable types (I haven't checked this in the code, but just
>> experimenting with calling hash):
>>
>> 1. Deterministic hash:
>> bool, complex, float, frozenset, int, range, tuple
>>
>> 2. Hash depends on hash seed:
>> str, bytes
>>
>> 3. Hash depends on id:
>> NoneType, ellipsis, enumerate, filter, memoryview, object, reversed, zip
>>
>> 4. Non-hashable:
>> bytearray, dict, list, set, slice
>>
>> The question here is whether None belongs in class 3 or class 1. To me
>> it seems clear that there is no advantage in having None be in class 3
>> except perhaps to save a few simple lines of code:
>> https://github.com/python/cpython/pull/99541/files
>>
>> There is however a worthwhile advantage in having None be in class 1.
>> If None had a deterministic hash then tuples, frozensets etc
>> consisting of objects with None as well as other objects with
>> deterministic hash could all have deterministic hash. The behaviour of
>> iteration order for sets would then be deterministic in the *narrow*
>> sense that is referred to by the Python 3.5 docs above.
>>
>> Some have argued that the fact that some types have a seed dependent
>> hash implies that None should not have a deterministic hash but this
>> does not follow. It was known at the time that str and bytes were
>> moved from class 1 to class 2 that it would be problematic to do so
>> which is precisely why PYTHONHASHSEED was introduced. However
>> PYTHONHASHSEED does not help here because None is not even in class 2
>> but rather class 3.
>>
>> If I was going to label any claim made by anyone in these threads as
>> disingenuous then it would be the claim that None is somehow not
>> "special". Firstly many types have deterministic hash so it isn't
>> really that much of a special property. Secondly None is *clearly* a
>> special value that is used everywhere! When I open the CPython
>> interpreter there are already thousands of references to None before I
>> have even done anything:
>>
>>    >>> import sys
>>    >>> sys.getrefcount(None)
>>    4429
>>
>> The motivation for this and other threads is to bring determinism in
>> the *narrow* sense. Others (including me) have made references to
>> other kinds of determinism that have derailed the threads by
>> misunderstanding exactly what Yoni is referring to. The *stronger*
>> sense of determinism would be useful if possible but it is not the
>> intended topic of these threads.
>>
>> -- 
>> Oscar
>> _______________________________________________
>> Python-Dev mailing list -- [email protected]
>> To unsubscribe send an email to [email protected]
>> https://mail.python.org/mailman3/lists/python-dev.python.org/
>> Message archived at 
>> https://mail.python.org/archives/list/[email protected]/message/73KMUPBTS4MIOMPRT3PBQ36HREQFXUUN/
>> Code of Conduct: http://python.org/psf/codeofconduct/
> 
> _______________________________________________
> Python-Dev mailing list -- [email protected]
> To unsubscribe send an email to [email protected]
> https://mail.python.org/mailman3/lists/python-dev.python.org/
> Message archived at 
> https://mail.python.org/archives/list/[email protected]/message/KVY3SRLMEFTAY7CBJHYDXQ4HCHK6P2O4/
> Code of Conduct: http://python.org/psf/codeofconduct/

-- 
Terry Jan Reedy

_______________________________________________
Python-Dev mailing list -- [email protected]
To unsubscribe send an email to [email protected]
https://mail.python.org/mailman3/lists/python-dev.python.org/
Message archived at https://mail.python.org/archives/list/[email protected]/message/MNPGEGH3AQOB75OEEXQNZIARCBZYUSYA/
Code of Conduct: http://python.org/psf/codeofconduct/