Add a frozendict builtin type

classic Classic list List threaded Threaded
76 messages Options
1234
Reply | Threaded
Open this post in threaded view
|

Add a frozendict builtin type

Victor STINNER
Rationale
=========

A frozendict type is a common request from users and there are various
implementations. There are two main Python implementations:

 * "blacklist": frozendict inheriting from dict and overriding methods
to raise an exception when trying to modify the frozendict
 * "whitelist": frozendict not inheriting from dict and only implement
some dict methods, or implement all dict methods but raise exceptions
when trying to modify the frozendict

The blacklist implementation has a major issue: it is still possible
to call write methods of the dict class (e.g. dict.set(my_frozendict,
key, value)).

The whitelist implementation has an issue: frozendict and dict are not
"compatible", dict is not a subclass of frozendict (and frozendict is
not a subclass of dict).

I propose to add a new frozendict builtin type and make dict type
inherits from it. frozendict would not have methods to modify its
content and values must be immutable.


Constraints
===========

 * frozendict values must be immutable, as dict keys
 * frozendict can be used with the C API of the dict object (e.g.
PyDict_GetItem) but write methods (e.g. PyDict_SetItem) would fail
with a TypeError ("expect dict, got frozendict")
 * frozendict.__hash__() has to be determinist
 * frozendict has not the following methods: clear, __delitem__, pop,
popitem, setdefault, __setitem__ and update. As tuple/frozenset has
less methods than list/set.
 * issubclass(dict, frozendict) is True, whereas
issubclass(frozendict, dict) is False


Implementation
==============

 * Add an hash field to the PyDictObject structure
 * Make dict inherits from frozendict
 * frozendict values are checked for immutability property by calling
their __hash__ method, with a fast-path for known immutable types
(int, float, bytes, str, tuple, frozenset)
 * frozendict.__hash__ computes hash(frozenset(self.items())) and
caches the result is its private hash attribute

Attached patch is a work-in-progress implementation.


TODO
====

 * Add a frozendict abstract base class to collections?
 * frozendict may not overallocate dictionary buckets?

--

Examples of frozendict implementations:

http://bob.pythonmac.org/archives/2005/03/04/frozendict/
http://code.activestate.com/recipes/498072-implementing-an-immutable-dictionary/
http://code.activestate.com/recipes/414283-frozen-dictionaries/
http://corebio.googlecode.com/svn/trunk/apidocs/corebio.utils.frozendict-class.html
http://code.google.com/p/lingospot/source/browse/trunk/frozendict/frozendict.py
http://cmssdt.cern.ch/SDT/doxygen/CMSSW_4_4_2/doc/html/d6/d2f/classfrozendict_1_1frozendict.html

See also the recent discussion on python-list:

http://mail.python.org/pipermail/python-list/2012-February/1287658.html

--

See also the PEP 351.

Victor

_______________________________________________
Python-Dev mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/lists%2B1324100855712-1801473%40n6.nabble.com

frozendict.patch (32K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Add a frozendict builtin type

Xavier Morel-4

On 2012-02-27, at 19:53 , Victor Stinner wrote:

> Rationale
> =========
>
> A frozendict type is a common request from users and there are various
> implementations. There are two main Python implementations:
>
> * "blacklist": frozendict inheriting from dict and overriding methods
> to raise an exception when trying to modify the frozendict
> * "whitelist": frozendict not inheriting from dict and only implement
> some dict methods, or implement all dict methods but raise exceptions
> when trying to modify the frozendict
>
> The blacklist implementation has a major issue: it is still possible
> to call write methods of the dict class (e.g. dict.set(my_frozendict,
> key, value)).
>
> The whitelist implementation has an issue: frozendict and dict are not
> "compatible", dict is not a subclass of frozendict (and frozendict is
> not a subclass of dict).

This may be an issue at the C level (I'm not sure), but since this would
be a Python 3-only collection, "user" code (in Python) should/would
generally be using abstract base classes, so type-checking would not
be an issue (as in Python code performing `isinstance(a, dict)` checks
naturally failing on `frozendict`)

Plus `frozenset` does not inherit from `set`, it's a whitelist
reimplementation and I've never known anybody to care. So there's
that precedent. And of course there's no inheritance relationship
between lists and tuples.

> * frozendict has not the following methods: clear, __delitem__, pop,
> popitem, setdefault, __setitem__ and update. As tuple/frozenset has
> less methods than list/set.

It'd probably be simpler to define that frozendict is a Mapping (where
dict is a MutableMapping). And that's clearer.

> * Make dict inherits from frozendict

Isn't that the other way around from the statement above? Not that I'd
have an issue with it, it's much cleaner, but there's little gained by
doing so since `isinstance(a, dict)` will still fail if `a` is a
frozendict.

> * Add a frozendict abstract base class to collections?

Why? There's no `dict` ABC, and there are already a Mapping and a
MutableMapping ABC which fit the bill no?
_______________________________________________
Python-Dev mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/lists%2B1324100855712-1801473%40n6.nabble.com
Reply | Threaded
Open this post in threaded view
|

Re: Add a frozendict builtin type

Victor Stinner-3
> This may be an issue at the C level (I'm not sure), but since this would
> be a Python 3-only collection, "user" code (in Python) should/would
> generally be using abstract base classes, so type-checking would not
> be an issue (as in Python code performing `isinstance(a, dict)` checks
> naturally failing on `frozendict`)
>
> Plus `frozenset` does not inherit from `set`, it's a whitelist
> reimplementation and I've never known anybody to care. So there's
> that precedent. And of course there's no inheritance relationship
> between lists and tuples.

At a second thought, I realized that it does not really matter.
frozendict and dict can be "unrelated" (no inherance relation).

Victor
_______________________________________________
Python-Dev mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/lists%2B1324100855712-1801473%40n6.nabble.com
Reply | Threaded
Open this post in threaded view
|

Add a frozendict builtin type

Jim Jewett
In reply to this post by Victor STINNER


In http://mail.python.org/pipermail/python-dev/2012-February/116955.html
Victor Stinner proposed:

> The blacklist implementation has a major issue: it is still possible
> to call write methods of the dict class (e.g. dict.set(my_frozendict,
> key, value)).

It is also possible to use ctypes and violate even more invariants.
For most purposes, this falls under "consenting adults".

> The whitelist implementation has an issue: frozendict and dict are not
> "compatible", dict is not a subclass of frozendict (and frozendict is
> not a subclass of dict).

And because of Liskov substitutability, they shouldn't be; they should
be sibling children of a basedict that doesn't have the the mutating
methods, but also doesn't *promise* not to mutate.

>  * frozendict values must be immutable, as dict keys

Why?  That may be useful, but an immutable dict whose values
might mutate is also useful; by forcing that choice, it starts
to feel too specialized for a builtin.

> * Add an hash field to the PyDictObject structure

That is another indication that it should really be a sibling class;
most of the uses I have had for immutable dicts still didn't need
hashing.  It might be a worth adding anyhow, but only to immutable
dicts -- not to every instance dict or keywords parameter.

>  * frozendict.__hash__ computes hash(frozenset(self.items())) and
> caches the result is its private hash attribute

Why?  hash(frozenset(selk.keys())) would still meet the hash contract,
but it would be approximately twice as fast, and I can think of only
one case where it wouldn't work just as well.  (That case is wanting
to store a dict of alternative configuration dicts (with no defaulting
of values), but ALSO wanting to use the configurations themselves
(as opposed to their names) as the dict keys.)

-jJ

--

If there are still threading problems with my replies, please
email me with details, so that I can try to resolve them.  -jJ

_______________________________________________
Python-Dev mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/lists%2B1324100855712-1801473%40n6.nabble.com
Reply | Threaded
Open this post in threaded view
|

Re: Add a frozendict builtin type

Victor Stinner-3
>> The blacklist implementation has a major issue: it is still possible
>> to call write methods of the dict class (e.g. dict.set(my_frozendict,
>> key, value)).
>
> It is also possible to use ctypes and violate even more invariants.
> For most purposes, this falls under "consenting adults".

My primary usage of frozendict would be pysandbox, a security module.
Attackers are not consenting adults :-)

Read-only dict would also help optimization, in the CPython peephole
or the PyPy JIT.

In pysandbox, I'm trying to replace __builtins_ and (maybe also
type.__dict__) by a frozendict. These objects rely on PyDict API and
so expect a type "compatible" with dict. But PyDict_GetItem() and
PyDict_SetItem() may use a test like isinstance(obj, (dict,
frozendict)), especially if the C strucure is "compatible". But
pysandbox should not drive the design of frozendict :-)

>> The whitelist implementation has an issue: frozendict and dict are not
>> "compatible", dict is not a subclass of frozendict (and frozendict is
>> not a subclass of dict).
>
> And because of Liskov substitutability, they shouldn't be; they should
> be sibling children of a basedict that doesn't have the the mutating
> methods, but also doesn't *promise* not to mutate.

As I wrote, I realized that it doesn't matter if dict doesn't inherit
from frozendict.

>>  * frozendict values must be immutable, as dict keys
>
> Why?  That may be useful, but an immutable dict whose values
> might mutate is also useful; by forcing that choice, it starts
> to feel too specialized for a builtin.

If values are mutables, the frozendict cannot be called "immutable".
tuple and frozenset can only contain immutables values.

All implementations of frozendict that I found expect frozendict to be hashable.

>>  * frozendict.__hash__ computes hash(frozenset(self.items())) and
>> caches the result is its private hash attribute
>
> Why?  hash(frozenset(selk.keys())) would still meet the hash contract,
> but it would be approximately twice as fast, and I can think of only
> one case where it wouldn't work just as well.

Yes, it would faster but the hash is usually the hash of the whole
object content. E.g. the hash of a tuple is not the hash of items with
odd index, whereas such hash function would also meet the "hash
contract".

All implementations of frozendict that I found all use items, and not
only values or only keys.

Victor
_______________________________________________
Python-Dev mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/lists%2B1324100855712-1801473%40n6.nabble.com
Reply | Threaded
Open this post in threaded view
|

Re: Add a frozendict builtin type

Tres Seaver
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 02/27/2012 06:34 PM, Victor Stinner wrote:

> tuple and frozenset can only contain immutables values.

Tuples can contain mutables::

 $ python
 Python 2.6.5 (r265:79063, Apr 16 2010, 13:09:56)
 [GCC 4.4.3] on linux2
 Type "help", "copyright", "credits" or "license" for more information.
 >>> ({},)
 ({},)
 $ python3
 Python 3.2 (r32:88445, Mar 10 2011, 10:08:58)
 [GCC 4.4.3] on linux2
 Type "help", "copyright", "credits" or "license" for more information.
 >>> ({},)
 ({},)


Tres.
- --
===================================================================
Tres Seaver          +1 540-429-0999          [hidden email]
Palladion Software   "Excellence by Design"    http://palladion.com
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.10 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iEYEARECAAYFAk9MFOAACgkQ+gerLs4ltQ5mjQCgi1U7CloZUy0u0+c0mlLlIuko
+IIAoLqKGcAb6ZAEY5wpkwvtgRa6S+LV
=7Mh5
-----END PGP SIGNATURE-----

_______________________________________________
Python-Dev mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/lists%2B1324100855712-1801473%40n6.nabble.com
Reply | Threaded
Open this post in threaded view
|

Re: Add a frozendict builtin type

Nick Coghlan
In reply to this post by Victor Stinner-3
On Tue, Feb 28, 2012 at 9:34 AM, Victor Stinner
<[hidden email]> wrote:

>>> The blacklist implementation has a major issue: it is still possible
>>> to call write methods of the dict class (e.g. dict.set(my_frozendict,
>>> key, value)).
>>
>> It is also possible to use ctypes and violate even more invariants.
>> For most purposes, this falls under "consenting adults".
>
> My primary usage of frozendict would be pysandbox, a security module.
> Attackers are not consenting adults :-)
>
> Read-only dict would also help optimization, in the CPython peephole
> or the PyPy JIT.

I'm pretty sure the PyPy jit can already pick up and optimise cases
where a dict goes "read-only" (i.e. stops being modified).

I think you need to elaborate on your use cases further, and explain
what *additional* changes would be needed, such as allowing frozendict
instances as __dict__ attributes in order to create truly immutable
objects in pure Python code.

In fact, that may be a better way to pitch the entire PEP. In current
Python, you *can't* create a truly immutable object without dropping
down to a C extension:

>>> from decimal import Decimal
>>> x = Decimal(1)
>>> x
Decimal('1')
>>> hash(x)
1
>>> x._exp = 10
>>> x
Decimal('1E+10')
>>> hash(x)
10000000000

Contrast that with the behaviour of a float instance:

>>> 1.0.imag = 1
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: attribute 'imag' of 'float' objects is not writable

Yes, it's arguably covered by the "consenting adults" rule, but
really, Decimal instances should be just as immutable as int and float
instances. The only reason they aren't is that it's hard enough to set
it up in Python code that the Decimal implementation settles for "near
enough is good enough" and just uses __slots__ to prevent addition of
new attributes, but doesn't introduce the overhead of custom
__setattr__ and __delattr__ implementations to actively *prevent*
modifications.

We don't even need a new container type, we really just need an easy
way to tell the __setattr__ and __delattr__ descriptors for
"__slots__" that the instance initialisation is complete and further
modifications should be disallowed.

For example, if Decimal.__new__ could call "self.__lock_slots__()" at
the end to set a flag on the instance object, then the slot
descriptors could read that new flag and trigger an error:

>>> x._exp = 10
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: attribute '_exp' of 'Decimal' objects is not writable

To be clear, all of this is currently *possible* if you use custom
descriptors (such as a property() implementation where setattr and
delattr look for such a flag) or override __setattr__/__delattr__.
However, for a micro-optimised type like Decimal, that's a hard choice
to be asked to make (and the current implementation came down on the
side of speed over enforcing correctness). Given that using __slots__
in the first place is, in and of itself, a micro-optimisation, I
suspect Decimal is far from the only "immutable" type implemented in
pure Python that finds itself having to make that trade-off. (An extra
boolean check in C is a *good* trade-off of speed for correctness.
Python level descriptor implementations or attribute access overrides,
on the other hand... not so much).

Cheers,
Nick.

--
Nick Coghlan   |   [hidden email]   |   Brisbane, Australia
_______________________________________________
Python-Dev mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/lists%2B1324100855712-1801473%40n6.nabble.com
Reply | Threaded
Open this post in threaded view
|

Re: Add a frozendict builtin type

Alex Gaynor
Nick Coghlan <ncoghlan <at> gmail.com> writes:

> I'm pretty sure the PyPy jit can already pick up and optimise cases
> where a dict goes "read-only" (i.e. stops being modified).

No, it doesn't. We handle cases like a type's dict, or a module's dict,
by having them use a different internal implementation (while, of course,
still being dicts at the Python level). We do *not* handle the case of
trying to figure out whether a Python object is immutable in any way.

Alex

_______________________________________________
Python-Dev mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/lists%2B1324100855712-1801473%40n6.nabble.com
Reply | Threaded
Open this post in threaded view
|

Re: Add a frozendict builtin type

Dirkjan Ochtman
In reply to this post by Victor STINNER
On Mon, Feb 27, 2012 at 19:53, Victor Stinner
<[hidden email]> wrote:
> A frozendict type is a common request from users and there are various
> implementations. There are two main Python implementations:

Perhaps this should also detail why namedtuple is not a viable alternative.

Cheers,

Dirkjan
_______________________________________________
Python-Dev mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/lists%2B1324100855712-1801473%40n6.nabble.com
Reply | Threaded
Open this post in threaded view
|

Re: Add a frozendict builtin type

Mark Shannon-3
In reply to this post by Victor Stinner-3
Victor Stinner wrote:

>>> The blacklist implementation has a major issue: it is still possible
>>> to call write methods of the dict class (e.g. dict.set(my_frozendict,
>>> key, value)).
>> It is also possible to use ctypes and violate even more invariants.
>> For most purposes, this falls under "consenting adults".
>
> My primary usage of frozendict would be pysandbox, a security module.
> Attackers are not consenting adults :-)
>
> Read-only dict would also help optimization, in the CPython peephole
> or the PyPy JIT.

Not w.r.t. PyPy. It wouldn't do any harm though.

One use of frozendict that you haven't mentioned so far
is communication between concurrent processes/tasks.
These need to be able to copy objects without changing reference
semantics, which demands immutability.

Cheers,
Mark.
_______________________________________________
Python-Dev mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/lists%2B1324100855712-1801473%40n6.nabble.com
Reply | Threaded
Open this post in threaded view
|

Re: Add a frozendict builtin type

Victor STINNER
In reply to this post by Dirkjan Ochtman
> A frozendict type is a common request from users and there are various
>> implementations. There are two main Python implementations:
>
> Perhaps this should also detail why namedtuple is not a viable alternative.

It doesn't have the same API. Example: frozendict[key] vs
namedtuple.attr (namedtuple.key). namedtuple has no .keys() or
.items() method.

Victor
_______________________________________________
Python-Dev mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/lists%2B1324100855712-1801473%40n6.nabble.com
Reply | Threaded
Open this post in threaded view
|

Re: Add a frozendict builtin type

Victor STINNER
In reply to this post by Nick Coghlan
> I think you need to elaborate on your use cases further, ...

A frozendict can be used as a member of a set or as a key in a dictionary.

For example, frozendict is indirectly needed when you want to use an
object as a key of a dict, whereas one attribute of this object is a
dict. Use a frozendict instead of a dict for this attribute answers to
this problem.

frozendict helps also in threading and multiprocessing.

--

> ... and explain
> what *additional* changes would be needed, such as allowing frozendict
> instances as __dict__ attributes in order to create truly immutable
> objects in pure Python code.
> In current Python, you *can't* create a truly immutable object without dropping
> down to a C extension:

Using frozendict in for type dictionary might be a use case, but
please don't focus on this example. There is currently a discussion on
python-ideas about this specific use case. I first proposed to use
frozendict in type.__new__, but then I proposed something completly
different: add a flag to a set to deny any modification of the type.
The flag may be set using "__final__ = True" in the class body for
example.

Victor
_______________________________________________
Python-Dev mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/lists%2B1324100855712-1801473%40n6.nabble.com
Reply | Threaded
Open this post in threaded view
|

Re: Add a frozendict builtin type

Antoine Pitrou
On Tue, 28 Feb 2012 12:45:54 +0100
Victor Stinner <[hidden email]> wrote:
> > I think you need to elaborate on your use cases further, ...
>
> A frozendict can be used as a member of a set or as a key in a dictionary.
>
> For example, frozendict is indirectly needed when you want to use an
> object as a key of a dict, whereas one attribute of this object is a
> dict.

It isn't. You just have to define __hash__ correctly.

> frozendict helps also in threading and multiprocessing.

How so?

Regards

Antoine.


_______________________________________________
Python-Dev mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/lists%2B1324100855712-1801473%40n6.nabble.com
Reply | Threaded
Open this post in threaded view
|

Re: Add a frozendict builtin type

Mark Shannon-3
Antoine Pitrou wrote:

> On Tue, 28 Feb 2012 12:45:54 +0100
> Victor Stinner <[hidden email]> wrote:
>>> I think you need to elaborate on your use cases further, ...
>> A frozendict can be used as a member of a set or as a key in a dictionary.
>>
>> For example, frozendict is indirectly needed when you want to use an
>> object as a key of a dict, whereas one attribute of this object is a
>> dict.
>
> It isn't. You just have to define __hash__ correctly.
>
>> frozendict helps also in threading and multiprocessing.
>
> How so?

Inter process/task communication requires copying. Inter/intra thread
communication uses reference semantics. To ensure these are the same,
the objects used in communication must be immutable.

Cheers,
Mark.
_______________________________________________
Python-Dev mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/lists%2B1324100855712-1801473%40n6.nabble.com
Reply | Threaded
Open this post in threaded view
|

Re: Add a frozendict builtin type

Antoine Pitrou
On Tue, 28 Feb 2012 12:07:32 +0000
Mark Shannon <[hidden email]> wrote:

> Antoine Pitrou wrote:
> > On Tue, 28 Feb 2012 12:45:54 +0100
> > Victor Stinner <[hidden email]> wrote:
> >>> I think you need to elaborate on your use cases further, ...
> >> A frozendict can be used as a member of a set or as a key in a dictionary.
> >>
> >> For example, frozendict is indirectly needed when you want to use an
> >> object as a key of a dict, whereas one attribute of this object is a
> >> dict.
> >
> > It isn't. You just have to define __hash__ correctly.
> >
> >> frozendict helps also in threading and multiprocessing.
> >
> > How so?
>
> Inter process/task communication requires copying. Inter/intra thread
> communication uses reference semantics. To ensure these are the same,
> the objects used in communication must be immutable.

You just need them to be practically constant. No need for an immutable
type in the first place.

Regards

Antoine.
_______________________________________________
Python-Dev mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/lists%2B1324100855712-1801473%40n6.nabble.com
Reply | Threaded
Open this post in threaded view
|

Re: Add a frozendict builtin type

Paul Moore
In reply to this post by Mark Shannon-3
On 28 February 2012 12:07, Mark Shannon <[hidden email]> wrote:
>>> frozendict helps also in threading and multiprocessing.
>>
>> How so?
>
> Inter process/task communication requires copying. Inter/intra thread
> communication uses reference semantics. To ensure these are the same,
> the objects used in communication must be immutable.

Does that imply that in a frozendict, the *values* as well as the
*keys* must be immutable?

Isn't that a pretty strong limitation (and hence, does it not make
frozendicts a lot less useful than they might otherwise be)?
_______________________________________________
Python-Dev mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/lists%2B1324100855712-1801473%40n6.nabble.com
Reply | Threaded
Open this post in threaded view
|

Re: Add a frozendict builtin type

Victor STINNER
In reply to this post by Victor STINNER
Updated patch and more justifications.

New patch:
 - dict doesn't inherit from frozendict anymore
 - frozendict is a subclass of collections.abc.Mutable
 - more tests

>  * frozendict.__hash__ computes hash(frozenset(self.items())) and
> caches the result is its private hash attribute

hash(frozenset(self.items())) is preferred over
hash(sorted(self.items())) because keys and values may be unorderable.
frozenset() is faster than sorted(): O(n) vs O(n*log(n)).

frozendict hash doesn't care of the item order creation:

>>> a=frozendict.fromkeys('ai')
>>> a
frozendict({'a': None, 'i': None})
>>> b=frozendict.fromkeys('ia')
>>> b
frozendict({'i': None, 'a': None})
>>> hash(a) == hash(b)
True
>>> a == b
True
>>> tuple(a.items()) == tuple(b.items())
False

frozendict supports unorderable keys and values:

>>> hash(frozendict({b'abc': 1, 'abc': 2}))
935669091
>>> hash(frozendict({1: b'abc', 2: 'abc'}))
1319859033

>  * Add a frozendict abstract base class to collections?

I realized that Mapping already exists and so the following patch is enough:

+Mapping.register(frozendict)

> See also the PEP 351.

I read the PEP and the email explaining why it was rejected.

Just to be clear: the PEP 351 tries to freeze an object, try to
convert a mutable or immutable object to an immutable object. Whereas
my frozendict proposition doesn't convert anything: it just raises a
TypeError if you use a mutable key or value.

For example, frozendict({'list': ['a', 'b', 'c']}) doesn't create
frozendict({'list': ('a', 'b', 'c')}) but raises a TypeError.

Victor

_______________________________________________
Python-Dev mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/lists%2B1324100855712-1801473%40n6.nabble.com

frozendict-2.patch (38K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Add a frozendict builtin type

Victor STINNER
In reply to this post by Antoine Pitrou
>> A frozendict can be used as a member of a set or as a key in a dictionary.
>>
>> For example, frozendict is indirectly needed when you want to use an
>> object as a key of a dict, whereas one attribute of this object is a
>> dict.
>
> It isn't. You just have to define __hash__ correctly.

Define __hash__ on a mutable object can be surprising.

Or do you mean that you deny somehow the modification of the dict
attribute, and convert the dict to a immutable object before hashing
it?

>> frozendict helps also in threading and multiprocessing.
>
> How so?

For example, you don't need a lock to read the frozendict content,
because you cannot modify the content.

Victor
_______________________________________________
Python-Dev mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/lists%2B1324100855712-1801473%40n6.nabble.com
Reply | Threaded
Open this post in threaded view
|

Re: Add a frozendict builtin type

Antoine Pitrou
In reply to this post by Victor STINNER
On Tue, 28 Feb 2012 13:14:15 +0100
Victor Stinner <[hidden email]> wrote:
>
> > See also the PEP 351.
>
> I read the PEP and the email explaining why it was rejected.

I think you should write a separate PEP and explain the use cases
clearly.

cheers

Antoine.


_______________________________________________
Python-Dev mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/lists%2B1324100855712-1801473%40n6.nabble.com
Reply | Threaded
Open this post in threaded view
|

Re: Add a frozendict builtin type

Mark Shannon-3
In reply to this post by Victor STINNER
Hi,

I don't know if an implementation of the frozendict actually exists,
but if anyone is planning on writing one then can I suggest that they
take a look at my new dict implementation:
http://bugs.python.org/issue13903
https://bitbucket.org/markshannon/cpython_new_dict/

Making dicts immutable (at the C level) is quite easy with my new
implementation.

Cheers,
Mark.
_______________________________________________
Python-Dev mailing list
[hidden email]
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe: http://mail.python.org/mailman/options/python-dev/lists%2B1324100855712-1801473%40n6.nabble.com
1234