https://mail.python.org/pipermail/python-dev/2006-February/0...
Kotlin _kinda_ does this as well, but if you have a reference to an immutable map in Kotlin, you are still free to mutate the values (and even keys!) as much as you like.
It explains a lot about the design of Python container classes, and the boundaries of polymorphism / duck typing with them, and mutation between them.
I don't always agree with the choices made in Python's container APIs...but I always want to understand them as well as possible.
Also worth noting that understanding changes over time. Remember when GvR and the rest of the core developers argued adamantly against ordered dictionaries? Haha! Good times! Thank goodness their first wave of understanding wasn't their last. Concurrency and parallelism in Python was a TINY issue in 2006, but at the forefront of Python evolution these days. And immutability has come a long way as a design theme, even for languages that fully embrace stateful change.
The new implementation has saved space, but there are opportunities to save more space (specifically after deleting keys) that they've now denied themselves by offering the ordering guarantee.
Things that were not useful in 2006 might be totally useful in 2026 ;P
Still, like you, I'm curious wether he has anything to say about it.
“What has been is what will be, and what has been done is what will be done; there is nothing new under the sun.”
He doesn't address the reason that most of us in 2025 immediately think of, which is that it's easier to reason about code if you know that certain values can't change after they're created.
What a change in culture over the last 20 years!
Not that it's entirely unwarranted, of course.
... Well, yes; it doesn't support the methods for mutation. Thinking of ImmutableFoo as a subclass of Foo is never going to work. And, indeed, `set` and `frozenset` don't have an inheritance relationship.
I normally find Hettinger very insightful so this one is disappointing. But nobody's perfect, and we change over time (and so do the underlying conditions). I've felt like frozendict was missing for a long time, though. And really I think the language would have been better with a more formal concept of immutability (e.g. linking it more explicitly to hashability; having explicit recognition of "cache" attributes, ...), even if it didn't go the immutable-by-default route.
Given how dynamic Python is, such a subclass relationship need not be evident at the C level. You can totally make one class whose implementation is independent of another class a subclass of the other, using PEP 3119. This gives implementations complete flexibility in how to implement the class while retaining the ontological subclass relationship.
Theoretically, could `set` be a subclass of `frozenset` (and `dict` of `frozendict`)? Do other languages take that approach?
> linking [immutability] more explicitly to hashability
AFAIK immutability and hashability are equivalent for the language's "core" types. Would it be possible to enforce that equivalence for user-defined types, given that mutability and the implementation of `__hash__` are entirely controlled by the programmer?
When you interpret Liskov substitution properly, it's very rare that anything Liskov-substitutes anything, making the entire property meaningless. So just do things based on what works best in the real world and aim for as much Liskov-substitution as is reasonable. Python is duck-typed anyway.
It's a decent guiding principle - Set and ImmutableSet are more substitutable than Set and Map, so Set deriving from ImmutableSet makes more sense than Set deriving from Map. It's just not something you can ever actually achieve.
Type the dict as a mapping when you want immutability:
x: Mapping[int, int] = {1: 1}
x[1] = 2 # Unsupported target for indexed assignment ("Mapping[int, int]").
y = {}
y[x] = 0 # Mypy thinks this is fine. Mapping is hashable, after all!
If you want real immutable data structures, not a cheap imitation, check out pyrsistent.
You think Python developers are going to roll their own HAMT on top of frozendicts? Or are they just gonna make copies? Personally, I'd just use pyrsistent which seems to get it right.
Look up persistent data structures [0]
The main trick is to store everything in a tree with a large branching factor.
The elements are on your leaves. When you want to make an edit you need to create only the nodes from the root to the actual leaf. Then you return the new root. Everything else you can share.
This is a log operation, normally implemented with branch 32.
It works with vectors as well as dicts. Creating a copy is constant, it's immutable can be shared freely (especially on GC'd languages).
Insert/Delete are O(log32(n)) instead of O(n) they'd be with a full copy.
[0] https://en.wikipedia.org/wiki/Persistent_data_structure#Pers...
You can do the same thing with binary trees and other structures. It's more fiddly, and there's definitely places where single-ownership allows mutability "under the hood" for real performance gains, but that's the basic idea.
Functional data structures essentially create a proxy on every write. This can be inefficient if you make writes in batches, and you only need immutability between batches.
from types import MappingProxyType
d = {}
d["a"] = 1
d["b"] = 2
print(d)
frozen = MappingProxyType(d)
print(frozen["a"])
# Error:
frozen["b"] = "new"
Only if you deny access to the underlying real dict.
Maybe I misunderstood, but it sounds to me like you're hoping for the following code to work:
def will_not_modify_arg(x: frozendict) -> Result:
...
foo = {"a": 1, "b": 2} # type of foo is dict
r = will_not_modify_arg(foo)
Edit: that is, if as the caller you want foo to be immutable, then you make it a frozendict
So could this also have been approached from the other side, as in making unordered NamedTuples with support for the Mapping API? The line between dictionaries and named tuples and structs (across various languages) has always seemed a bit blurry to me, so I'm trying to get a better picture of it all through this.
If you want to create a named tuple with arbitrary field names at runtime then you need to create a new named tuple type before you create the instance. That is possible, since Python is a very dynamic language, but it's not particularly efficient and, more importantly, just feels a bit wrong. And are you going to somehow cache the types and reuse them if the field names match? It's all a bit of a mess compared to just passing the entries to the frozendict type.
So I think the differences aren't great, but they are sufficient. A frozendict is not going to be indexable by an integer. Python already has an abstract type for this, for mostly the use of type checking I imagine: https://docs.python.org/3/glossary.html#term-mapping
Documentation for namedtuple: https://docs.python.org/3/library/collections.html#collectio...
But yeah I'd be in favour of something that looked a lot like a named tuple but with mutable values and supporting [name] access too. And of course some nice syntactic sugar rather like dicts and sets have with curly brackets today.
The entries of a tuple cannot be assigned to, but the values can be mutated. The same is true for a `frozendict` (according to the PEP they don't support `__setitem__`, but "values can be mutable").
I don't see anything wrong with your asking to understand
Edit: Of course, I get down voted as I predicted I would. Lol.
Since only the keys are const, the values not, frozendict is not thread-safe per se. There needs to be a small lock around the value getter and setter.
This proposal is important enough that I chimed in on the thread with a detailed example of how SQLAlchemy uses this pattern:
https://discuss.python.org/t/pep-814-add-frozendict-built-in...
Personally, I’ve been using a wrapper around `collections.namedtuple` as an underlying data structure to create frozen dictionaries when I’ve needed something like that for a project.
https://peps.python.org/pep-0416/
Also one in 2019 for a "frozenmap":
For example, I often write classes that do cacheable analysis that results in a dict (e.g. the class stores a list of tiles defined by points and users want a point-to-tiles mapping for convenience). It's worth caching those transformations, e.g. using @functools.cached_property, but this introduces a risk where any caller could ruin the returned cached value by editing it. Currently, I take the safety hit (cache a dict) instead of the performance hit (make a new copy for each caller). Caching a frozendict would be a better tradeoff.
`.freeze()` should probably just return a frozendict instead of in-place mutating the dict, and they should be separate types. Under the hood, you'll have to build the hashtable anyway to make the frozendict; as long as you're doing that work, you may as well build an object to contain the hashtable and just have that object be separate from the dict that birthed it.
The values referenced by both the original dict and the frozendict can be the same values; no need to clone them.
Another alternative mentioned was `move`, which would create a frozen version in constant time and clear the original dict.
If all it does is set a flag that prevents modifications, that's different.
Bringing up TypedDict is sort of interesting, because it seems like a frozen dictionary could have been implemented by PEP 705, if typing.ReadOnly was enforced at runtime, and not just a hint to a static type checker.
I expect this is not a very big ask and the various typecheckers will have versions of this soon after release.
IMHO TypedDict in Python are essentially broken/useless as is
What is needed is TS style structural matching, like a Protocol for dicts
n = 1000
a = {}
for i in range(n):
a[i] = str(i)
a = frozendict(a) # O(n) operation can be turned to O(1)
There are also potentially other optimizations that could be applied (not specific to dict/frozendict) to reduce the memory overhead on operations like "a = f(a)" for selected values of "f".
But actually, I suspect it can't do this optimization simply because the name `frozendict` could be shadowed.
It’s optimized for fast reads in exchange for expensive creation.
[0] https://flax.readthedocs.io/en/latest/api_reference/flax.cor...
If you have fixed keys, a frozen dataclass will do. If you don't, you can always start with a normal dict d, then store tuple(sorted(d.items())) to have immutability and efficient lookups (binary search), then throw away d.
People hardly ever use this tool. That suggests that there isn't much of a need for a frozendict.
Not really, C# has ConcurrentDictionary.
{{'foo': 'bar'}: 1, {3:4, 5:6}: 7}
...and there is no reasonable builtin way to get around this!
You may ask: "Why on earth would you ever want a dictionary with dictionaries for its keys?"
More generally, sometimes you have an array, and for whatever reason, it is convenient to use its members as keys. Sometimes, the array in question happens to be an array of dicts. Bang, suddenly it's impossible to use said array's elements as keys! I'm not sure what infuriates me more: said impossibility, or the python community's collective attitude that "that never happens or is needed, therefore no frozendict for you"
There is nothing at all bizarre or unexpected about this. Mutable objects should not be expected to be valid keys for a hash-based mapping — because the entire point of that data structure is to look things up by a hash value that doesn't change, but mutating an object in general changes what its hash should be.
Besides which, looking things up in such a dictionary is awkward.
> More generally, sometimes you have an array, and for whatever reason, it is convenient to use its members as keys.
We call them lists, unless you're talking about e.g. Numpy arrays with a `dtype` of `object` or something. I can't think of ever being in the situation you describe, but if the point is that your keys are drawn from the list contents, you could just use the list index as a key. Or just store key-value tuples. It would help if you could point at an actual project where you encountered the problem.
If you want to have hash map keys, you need to think about how to hash them and how to compare for equality, it's just that. There will be complications to that such as floats, which have a tricky notion of equality, or in Python mutable collections which don't want to be hashable.
So sets can be viewed as implicitly sorted, which is why the order of the elements cannot be used to differentiate two sets.
Being sorted internally to enforce the equivalence between sets with elements provided in different orders does not imply anything about the existence of an operation that would retrieve elements in a desired order or which would return subsets less or greater than a threshold. When such operations are desired, an order relation must be externally defined on the set.
So a possible definition of sets and multisets is as sorted arrays with or without unicity of elements, while sequences are unsorted arrays (which may also have the constraint of unique elements). However the standard set operations do not provide external access to the internal order, which is an order between arbitrary identifiers attached to the elements of the set, which have no meaning externally.
"PEP 351 – The freeze protocol" (2005, rejected) https://peps.python.org/pep-0351/ ; IIUC the freeze protocol proposed basically:
def freeze(obj)
return cache.setsefault(hash(obj),
obj.__freeze__())
I wasn't able to find a URL to this post (2021) from the python-ideas mailing list archives using a double quoted search term today; I had to use the python mailing list search engine? Did something break crawling of mailing lists? Old mailman HTML archives were very simple to crawl.. ENH: pypa: add a sitemap.xml for/of mailing list archives, forums; @pypa: ask for search engine indexing advice: "How do we make sure that the python mailing list archives will be search indexed?" (as they traditionally were)
How to find the .txt of mailing list archives posts these days?
From "[Python-ideas] Re: Introduce constant variables in Python" (2021) https://mail.python.org/archives/list/python-ideas@python.or... :
- pyrsistent: PMap, PVector
I'm out of time for this; (reformatting this for HN so that URLs will be auto-linkified but newlines won't be eliminated) here's the full email as .txt, the mailing list archive has a hyperlinkified version with newlines preserved. GH Markdown and CommonMark Markdown also preserve newlines and auto-linkify:
From: [@westurner]
Date: Thu, Jun 17, 2021, 10:43 AM
Subject: Re: [Python-ideas] Re: Introduce constant variables in Python
Cc: python-ideas <python-ideas@python.org>
On Mon, May 24, 2021 at 5:43 PM Chris Angelico <rosuav@gmail.com> wrote:
Requiring that a name not be rebound is well-defined and testable.
Requiring that an object not change is either trivial (in the case of,
say, an integer) or virtually impossible (in the case of most
objects).
What would be the advantage of such a declaration?
ChrisA
## Existing threads re: consts and applications thereof
So, `/? from:me pyrsistent` I found a few results:
- "[Python-Dev] Challenge: Please break this! (a.k.a restricted mode revisited)" 2016-04
https://mail.python.org/pipermail/python-dev/2016-April/143958.html
- ~Sandboxing python within python is nontrivial to impossible; consts might help a bit
- https://mail.python.org/pipermail/python-dev/2016-April/143958.html
- "Proposal to add const-ness type hints to PEP-484"
https://mail.python.org/archives/list/python-ideas@python.org/thread/OVPF5I6IOVF6GOJQRH5UGCCU3R7PQHUF/
- https://github.com/python/typing/issues/242
- "Final names and attributes" https://github.com/python/mypy/pull/5522
This is where `typing.Final` comes from.
- "[Python-ideas] "Immutable Builder" Pattern and Operator"
https://mail.python.org/pipermail/python-ideas/2017-January/044374.html
- [pyrsistent] and "fn.py [do] immutables:
https://github.com/kachayev/fn.py/blob/master/README.rst#persistent-data-structures "
- "[Python-ideas] Add recordlcass to collections module"
https://groups.google.com/g/python-ideas/c/9crHfcCBgYs/m/6_EEaWJAAgAJ
- ORMs (e.g. Django, SQLAlchemy) require "dirty state" checking to know which object attributes have changed and need an SQL statement to be executed to synchronize the state; this is relevant because when we're asking for mutable namedtuple we're often trying to do exactly this pattern.
- "[Python-ideas] Suggestions: dict.flow_update and dict.__add__"
https://www.google.com/search?q=%22%5BPython-ideas%5D+Suggestions%3A+dict.flow_update+and+dict.__add__%22
> dicttoolz has functions for working with these objects; including dicttoolz.merge (which returns a reference to the merged dicts but does not mutate the arguments passed).
>
> https://toolz.readthedocs.io/en/latest/api.html#dicttoolz
> https://toolz.readthedocs.io/en/latest/api.html#toolz.dicttoolz.merge
>
> pyrsistent has a PRecord class with invariants and type checking that precedes dataclasses. pyrsistent also has 'freeze' and 'thaw' functions for immutability. PRecord extends PMap, which implements __add__ as self.update(arg) (which does not mutate self)
https://github.com/tobgu/pyrsistent/blob/master/README.rst#precord
>
> https://github.com/tobgu/pyrsistent/blob/master/pyrsistent/_pmap.py
- "[Python-ideas] How to prevent shared memory from being corrupted ?"
https://www.google.com/search?q=%22How+to+prevent+shared+memory+from+being+corrupted+%3F%22
> PyArrow Plasma object ids, "sealing" makes an object immutable, pyristent
>
> https://arrow.apache.org/docs/python/plasma.html#object-ids
> https://arrow.apache.org/docs/python/plasma.html#creating-an-object-buffer
> > Objects are created in Plasma in two stages. First, they are created, which allocates a buffer for the object. At this point, the client can write to the buffer and construct the object within the allocated buffer. [...]
- [Python-ideas] Experimenting with dict performance, and an immutable dict
https://mail.python.org/archives/list/python-ideas@python.org/message/DNBGUJHDH4UTPSETMFFWMJHNXQXIWX4I/
> https://pyrsistent.readthedocs.io/en/latest/intro.html#pyrsistent :
>
>> Pyrsistent is a number of persistent collections (by some referred to as functional data structures). Persistent in the sense that they are immutable.
>>
>> All methods on a data structure that would normally mutate it instead return a new copy of the structure containing the requested updates. The original structure is left untouched.
>>
>> This will simplify the reasoning about what a program does since no hidden side effects ever can take place to these data structures. You can rest assured that the object you hold a reference to will remain the same throughout its lifetime and need not worry that somewhere five stack levels below you in the darkest corner of your application someone has decided to remove that element that you expected to be there.
>>
>> Pyrsistent is influenced by persistent data structures such as those found in the standard library of Clojure. The data structures are designed to share common elements through path copying. It aims at taking these concepts and make them as pythonic as possible so that they can be easily integrated into any python program without hassle.
> What would be the advantage of such a declaration?
Constants don't need to be locked or unlocked; which is advantageous for parallelism and reasoning about program correctness.
True consts (wherein everything referred to in that object is 'frozen' and immutable or at least only modifiable with e.g. copy-on-write)
wouldn't require locks,
which would be post-GIL advantageous.
You could do consts by never releasing a threading.Lock (or similar):
- https://docs.python.org/3/library/asyncio-sync.html#locks
- https://docs.python.org/3/library/threading.html#lock-objects
- This from
https://docs.python.org/2/library/sets.html?highlight=immutable#immutable-transforms re ImmutableSet/FrozenSet
is not present in the python 3 docs:
https://docs.python.org/3/library/stdtypes.html#set-types-set-frozenset
Though - even if Python enforced normal consts in the language - all of the other code objects would still be mutable, so you still have the impossibility of sandboxing python.
Functional and contracts coding styles rely upon invariance;
which can be accomplished with various third-party packages that enforce const-ness throughout what may be an object tree behind that reference that would otherwise need to be copy.deepcopy()'d.
## pyrsistent
Src: https://github.com/tobgu/pyrsistent
> - PVector, similar to a python list
> - PMap, similar to dict
> - PSet, similar to set
> - PRecord, a PMap on steroids with fixed fields, optional type and invariant checking and much more
> - PClass, a Python class fixed fields, optional type and invariant checking and much more
> - Checked collections, PVector, PMap and PSet with optional type and invariance checks and more
> - PBag, similar to collections.Counter
> - PList, a classic singly linked list
> - PDeque, similar to collections.deque
> - Immutable object type (immutable) built on the named tuple
> - freeze and thaw functions to convert between python standard collections and pyrsistent collections.
> - Flexible transformations of arbitrarily complex structures built from PMaps and PVectors.
## icontract
Src: https://github.com/Parquery/icontract
> icontract provides design-by-contract to Python3 with informative violation messages and inheritance.
>
> It also gives a base for a flourishing of a wider ecosystem:
>
> - A linter pyicontract-lint,
> - A sphinx plug-in sphinx-icontract,
> - A tool icontract-hypothesis for automated testing and ghostwriting test files which infers Hypothesis strategies based on the contracts,
together with IDE integrations such as icontract-hypothesis-vim, icontract-hypothesis-pycharm, and icontract-hypothesis-vscode,
> - Directly integrated into CrossHair, a tool for automatic verification of Python programs,
together with IDE integrations such as crosshair-pycharm and crosshair-vscode, and
> - An integration with FastAPI through fastapi-icontract to enforce contracts on your HTTP API and display them in OpenAPI 3 schema and Swagger UI.
https://en.wikipedia.org/wiki/Invariant_(mathematics)#Invari... [ https://en.wikipedia.org/wiki/Class_invariant ]
> What is the difference between "invariant" and "constant" and "final"?