PEP 814: Add frozendict built-in type

PEPs
62

I don’t know what formally unpredictable means, but I would prefer the O(n) taking place when constructing a frozendict, since that is both more predictable and much easier to both teach and understand.

5 Likes
63

It means we don’t guarantee that it will be have any particular performance characteristic, and we don’t guarantee what circumstances it may have any particular characteristic, even if it’s reasonably easy to predict or observe what it may be. (Contrasted to getting an item, which is guaranteed to be O(1), and so we can’t make changes that would impact that.)

And I’m sure some people would prefer it the way you propose, while others would prefer it to be the other way around. It’s on us to balance the competing scenarios and make a decision, which is why we take these discussions seriously and try not to just jump into something that seems obvious.

4 Likes
64

Just a general question. This is supposed to be an addition to builtins, so why not add the builtins tag?

5 Likes
65

I didn’t know this tag. I just added it :slight_smile:

3 Likes
66

I propose to defer the idea of adding a method to convert a mutable dict to an immutable frozendict: see draft PEP change. It can be added later, but it doesn’t have to be added right now. I prefer to reduce the scope of the PEP.

14 Likes
67

By the way, there is no way in Python to convert a list to a tuple with O(1) complexity. Same issue to convert a set to a frozenset. Only bytearray recently got a new specific take_bytes() method just for that. If someone wants a method to convert a dict to a frozendict, maybe an unified method is needed (see PEP 351 – The freeze protocol :slight_smile: ).

7 Likes
68

I’m curious how frozendict compares to types.MappingProxyType. I use it quite often, though I don’t do much comparing and hashing with it so it very well could be significantly different in terms of behavior.

69

Let me quote PEP 814:

types.MappingProxyType was added in 2012 (Python 3.3). This type is not hashable and it’s not possible to inherit from it. It’s also easy to retrieve the original dictionary which can be mutated, for example using gc.get_referents().

I also suppose that frozendict can also be a little bit faster than types.MappingProxyType, since types.MappingProxyType is a proxy to a dict.

Obiously, you can continue using types.MappingProxyType, even if frozendict is added, if it fits your needs :slight_smile:

4 Likes
70

Thank you for this PEP!

I was wondering if frozendict would be allowed in places where a dict instance is required, such as redefining obj.__dict__ which currently raises an error if the object is not (directly or indirectly) a dict.

>>> class A:
...     pass
...     
>>> obj = A()
>>> obj.__dict__ = frozendict()
Traceback (most recent call last):
  File "<python-input-7>", line 1, in <module>
    obj.__dict__ = frozendict()
    ^^^^^^^^^^^^
TypeError: __dict__ must be set to a dictionary, not a 'frozendict'

I was also thinking about type.__prepare__ but this one is a bit trickiest because it needs a mutable dictionnary.

>>> class F(frozendict):
...     def __setitem__(self, key, value):
...         pass
...         
>>> class M(type):
...     @classmethod
...     def __prepare__(cls, name, bases):
...         return F()
...         
>>> class A(metaclass=M):
...     pass
...     
Traceback (most recent call last):
  File "<python-input-12>", line 1, in <module>
    class A(metaclass=M):
        pass
TypeError: type.__new__() argument 3 must be dict, not F
1 Like
71

I’d be very happy to have a few core functions of the stdlib take any mapping, not only dict. Other examples, where such mappings could be provided are the localns and globalns arguments for eval and exec.

3 Likes
72

It’s implemented in the reference implementation for exec() :slight_smile:

>>> ns=frozendict(x=1, __builtins__=__builtins__); exec('print(x)', ns, ns)
1
>>> ns=frozendict(x=1, __builtins__=__builtins__); exec('x=2', ns, ns)
Traceback (most recent call last):
  ...
TypeError: 'frozendict' object does not support item assignment

I had a hack in the reference implementation to define a type.__dict__ as frozendict if __frozendict__ = True was defined. I had another hack for module namespace (module.__dict__ as frozendict). But I removed these hacks. I prefer to discuss such feature later, once the PEP will be accepted (if it’s accepted!).

7 Likes
73

Something @vstinner and I have been thinking about is memory compaction and lookup performance.
But we plan to dig into the details once the feature itself has landed.

7 Likes
74

The clean (from end user viewpoint) to add O(1) conversation from dict to frozendict is to update dict.clear:

def clear(self,/,*,to_frozen:bool = False)-> None | frozendict:
     """Remove all items from the dict. If to_frozen is True, return frozendict with existing contents."""
75

I’d find that interface completely bewildering. clear will either clear the dictionary or convert it to a different type of dictionary?

11 Likes
76

No. It clears the dictionary always.

It just returns the O(1) created frozendict if the new boolean is True.

77

Sure, but from an novice perspective this is a method that has two distinct use-cases, and they’re not even particularly related. I think that’d be very confusing.

10 Likes
78

Agreed. Why not just add a .freeze_and_clear() method or something?

1 Like
79

I think it’s just the name that’s off. Perhaps a name like move would work.

d.move() returns a frozendict and leaves a valid, but empty dict in d.

80

I think it would be good to land something as closely resembling set <-> frozenset / list <-> tuple as possible.

Then, with specific use cases and proof of performance gains in real life scenarios, can debate over optimisations (both seamless and requiring extensions).

Unless of course there are discrepancies in how set <-> frozenset / list <-> tuple ineracts and specification of the PEP regarding dict <-> frozendict.
In this case, I think, it is worth looking into it early.

At least Initially and at least to me personally it would be great just to get frozendict without any surprises.

And I think current spec is very close to that sweet spot for initial landing.

4 Likes
81

Looks like a nice addition.

  1. You define the interface as implementing collections.abc.Mapping then in a completely different section you define the interface relative to dict. It would be useful to define the interface in a single place (perhaps using Mapping as the base and using the style in abc). This would make the interface explicit and easier to digest. Thinking in terms of structural typing instead of nominal sub typing is useful as well. This could minimize the natural “subclass of dict” type questions that might arise.
  2. I get why you’re adding |= but I wish this wasn’t in there
  3. To avoid giving up on type safeness, it it possible for the typing spec to raise an type error for cases like x: frozendict[str, list[int]](a=[1,2]); hash(x)
  4. I understand the motivation to constrain the scope, but if possible, it would be useful to get the typed abstraction (typing.TypedFrozenDict or however this will work ) defined in this PEP. There’s enough people in Python that are using type hints and annotations that the typing aspect shouldn’t be thought of as second class citizen.
1 Like