peps: Add the PEP 416: Add a frozendict builtin type

http://hg.python.org/peps/rev/369cd3f69cd2 changeset: 4100:369cd3f69cd2 user: Victor Stinner <vstinner@wyplay.com> date: Wed Feb 29 18:58:50 2012 +0100 summary: Add the PEP 416: Add a frozendict builtin type files: pep-0400.txt | 2 +- pep-0410.txt | 2 +- pep-0416.txt | 112 +++++++++++++++++++++++++++++++++++++++ 3 files changed, 114 insertions(+), 2 deletions(-) diff --git a/pep-0400.txt b/pep-0400.txt --- a/pep-0400.txt +++ b/pep-0400.txt @@ -2,7 +2,7 @@ Title: Deprecate codecs.StreamReader and codecs.StreamWriter Version: $Revision$ Last-Modified: $Date$ -Author: Victor Stinner <victor.stinner@haypocalc.com> +Author: Victor Stinner <victor.stinner@gmail.com> Status: Draft Type: Standards Track Content-Type: text/x-rst diff --git a/pep-0410.txt b/pep-0410.txt --- a/pep-0410.txt +++ b/pep-0410.txt @@ -2,7 +2,7 @@ Title: Use decimal.Decimal type for timestamps Version: $Revision$ Last-Modified: $Date$ -Author: Victor Stinner <victor.stinner@haypocalc.com> +Author: Victor Stinner <victor.stinner@gmail.com> Status: Rejected Type: Standards Track Content-Type: text/x-rst diff --git a/pep-0416.txt b/pep-0416.txt new file mode 100644 --- /dev/null +++ b/pep-0416.txt @@ -0,0 +1,112 @@ +PEP: 416 +Title: Add a frozendict builtin type +Version: $Revision$ +Last-Modified: $Date$ +Author: Victor Stinner <victor.stinner@gmail.com> +Status: Draft +Type: Standards Track +Content-Type: text/x-rst +Created: 29-February-2012 +Python-Version: 3.3 + + +Abstract +======== + +Add a new frozendict builtin type. + + +Rationale +========= + +A frozendict mapping cannot be changed, but its values can be mutable (not +hashable). A frozendict is hashable and so immutable if all values are hashable +(immutable). + +Use cases of frozendict: + + * hashable frozendict can be used as a key of a mapping or as a member of set + * frozendict helps optimization because the mapping is constant + * frozendict avoids the need of a lock when the frozendict is shared + by multiple threads or processes, especially hashable frozendict + + +Constraints +=========== + + * frozendict has to implement the Mapping abstract base class + * frozendict keys and values can be unorderable + * a frozendict is hashable if all keys and values are hashable + * frozendict hash does not depend on the items creation order + + +Implementation +============== + + * Add a PyFrozenDictObject structure based on PyDictObject with an extra + "Py_hash_t hash;" field + * frozendict.__hash__() is implemented using hash(frozenset(self.items())) and + caches the result in its private hash attribute + * Register frozendict has a collections.abc.Mapping + * frozendict can be used with PyDict_GetItem(), but PyDict_SetItem() and + PyDict_DelItem() raise a TypeError + + +Recipe: immutable dict +====================== + +An immutable mapping can be implemented using frozendict:: + + import itertools + + class immutabledict(frozendict): + def __new__(cls, *args, **kw): + # ensure that all values are immutable + for key, value in itertools.chain(args, kw.items()): + if not isinstance(value, (int, float, complex, str, bytes)): + hash(value) + # frozendict ensures that all keys are immutable + return frozendict.__new__(cls, *args, **kw) + + def __repr__(self): + return 'immutabledict' + frozendict.__repr__(self)[10:] + + +Objections +========== + +*namedtuple may fit the requiements of a frozendict.* + +A namedtuple is not a mapping, it does not implement the Mapping abstract base +class. + +*frozendict can be implemented in Python using descriptors" and "frozendict +just need to be practically constant.* + +If frozendict is used to harden Python (security purpose), it must be +implemented in C. A type implemented in C is also faster. + +*The PEP 351 was rejected.* + +The PEP 351 tries to freeze an object and so may convert a mutable object to an +immutable object (using a different type). frozendict doesn't convert anything: +hash(frozendict) raises a TypeError if a value is not hashable. Freezing an +object is not the purpose of this PEP. + + +Links +===== + + * PEP 412: Key-Sharing Dictionary + (`issue #13903 <http://bugs.python.org/issue13903>`_) + * PEP 351: The freeze protocol + * `The case for immutable dictionaries; and the central misunderstanding of PEP 351 <http://www.cs.toronto.edu/~tijmen/programming/immutableDictionaries.html>`_ + * `Frozen dictionaries (Python recipe 414283) <http://code.activestate.com/recipes/414283-frozen-dictionaries/>`_ + by Oren Tirosh + + +Copyright +========= + +This document has been placed in the public domain. + -- Repository URL: http://hg.python.org/peps
participants (1)
-
victor.stinner