[Python-Dev] PEP 416: Add a frozendict builtin type
Victor Stinner
victor.stinner at haypocalc.com
Wed Feb 29 19:21:37 CET 2012
As requested, I create a PEP and a related issue:
http://www.python.org/dev/peps/pep-0416/
http://bugs.python.org/issue14162
The PEP 416 is different from my previous propositions: frozendict
values can be mutable and dict doesn't inherit from frozendict
anymore. But it is still possible to use the PyDict C API on
frozendict (which is more an implementation detail).
TODO:
- write the documentation
- decide if new functions should be added to the C API, maybe a new
PyFrozenDict_New() function? (but would it take a mapping or a list of
tuple?)
--
PEP: 416
Title: Add a frozendict builtin type
Version: $Revision$
Last-Modified: $Date$
Author: Victor Stinner <victor.stinner at 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.
More information about the Python-Dev
mailing list