[Python-Dev] PEP 416: Add a frozendict builtin type (original) (raw)

Victor Stinner victor.stinner at haypocalc.com
Wed Feb 29 19:21:37 CET 2012

Previous message: [Python-Dev] Backporting PEP 414
Next message: [Python-Dev] PEP 416: Add a frozendict builtin type
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

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: RevisionRevisionRevision Last-Modified: DateDateDate 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.

Copyright

This document has been placed in the public domain.

Previous message: [Python-Dev] Backporting PEP 414
Next message: [Python-Dev] PEP 416: Add a frozendict builtin type
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

More information about the Python-Dev mailing list