PEP 795: Add deep immutability to Python

PEPs
1

Hello, we have just created PEP 795 to add deep immutability to Python:

Abstract

This PEP proposes adding a mechanism for deep immutability to Python. The mechanism requires some changes to the core language, but user-facing functions are delivered in a module called immutable.

[…]

Deep immutability provides strong guarantees against unintended modifications, thereby improving correctness, security, and parallel execution safety.

[…]

Immutability in action:

from immutable import freeze, isfrozen

class Foo:
    pass

f = Foo()
g = Foo()
h = Foo()

f.f = g
g.f = h
h.f = g # cycles are OK!
del g # Remove local ref to g, so g's RC = 1
del h # Remove local reg to h, so h's RC = 1

g.x = "African Swallow" # OK
freeze(f) # Makes, f, g and h immutable
g.x = "European Swallow" # Throws an exception "g is immutable"
isfrozen(h) # returns True
h = None # Cycle detector will eventually find and collect the cycle

The whole pep can be found online:

We already had a pre-pep discussion here.

Let us know what you think!

– @mjp41 @stw @matajoh @xFrednet

11 Likes
2

What changes have been made based on feedback in the pre pep discussion? Skimming the document, I couldn’t find anything.

Especially worries about the fact that this mechanism can’t guarantee immutability (see my counterexample), the fact that it breaks very simple assumption (an instance of list can be appended to) and that trying to freeze arbitrary objects could result in your interpreter becoming unusable. I can’t find anything that considers these points.

15 Likes
3

These are questions that went ignored in the previous thread so I’ll restate here.

When I tested the reference implementation I found that I could not freeze a fractions.Fraction. Is that just a limitation of the reference implementation or is it expected that the final implementation would not be able to freeze a Fraction? I think the error message was something like “cannot freeze module object” which seems like a significant limitation. Also from testing it seems that a class that has @classmethod results in instances that cannot be frozen so there are perhaps several things that would make Fraction unfreezable.

Given f = fractions.Fraction(1, 2) is it expected that f would be freezable?

If the answer is “yes” then what is the full set of objects that would be frozen by freeze(f) and what are the implications of all of those things being frozen?

If the answer is “no” then what restrictions would the author of a class like Fraction need to follow if they wanted the instances to be freezable?

8 Likes
4

Was there any discussion of an immutable proxy alternative? I see it’s not mentioned in the rejected section.

The basic idea is to wrap an object graph with a new object that provides recursive, synchronised access to the graph and supports moving between contexts. On the inside, we can pull more tricks as internal implementation details than are possible with mutating semantics like these (e.g. it becomes valid to pickle/move/unpickle the graph behind a proxy object, or to simply share the memory, or to use a proxy-level lock rather than individual object level flags, or let each object define its own proxy type, or handle it differently for processes vs. threads. vs interpreters, etc.).

It seems unavoidable that programmers under this approach will have to deal with very infectious failures - passing any user-defined object into a library that uses freeze could result in my entire program being frozen and hence broken. Having to opt out of someone else’s optimization is a pretty terrible experience.

(Also, I suspect the module will probably be pushed to collections.immutable, based on current precedent. Not saying you should, just be aware of that possibility. The name is the least of my concerns right now :wink: )

12 Likes
5

First of all, impressive work everyone!

High-level, my two main complaints are:

  1. Instinctively, the uses of del and = None feel really foreign and “non-Pythonic”. Part of Python’s appeal to many is that you don’t have to think about garbage collection (either cyclic or with reference counting), and I feel like the current proposal hurts that idea. I’m not sure what the best way around this is yet.
  2. To freeze() an object, you have to inherently mutate it, which is a little odd in something that’s supposed to make something immutable. I think this leads to a lot of additional complexity, such as deep recursion that causes random things to become immutable. Thinking out loud, an alternative could be to allow objects to opt-in to themselves being immutable in __new__ or __init__ (think super().__new__(frozen=True)), so any state that needs to be frozen can be validated right then and there.

To make its instances freezable, a type that uses C extensions that adds new functionality implemented in C must register themselves using register_freezable(type) .

I would expect this to be a dunder __freezeable__ attribute, rather than some arbitrary function imported from a module. Better yet, this could be a type flag in C. Was this inspired by ABC’s register?

  1. Modify object mutation operations (PyObject_SetAttr, PyDict_SetItem, PyList_SetItem, etc.) to check the flag and raise an error when appropriate.

Hm, won’t this do bad things to performance? Seemingly, there would be an extra load and check for every attribute write, container store, etc. Extensions that want to support this will also have to put these everywhere. This will be even worse on FT, where that check will probably have to be atomic.

As a necessary requirement for the extension Sharing Immutable Data Across Subinterpreters, we will add support for atomic reference counting for immutable objects.

Atomic reference counting has been tried in previous GIL-removal attempts, and failed due to the performance hit. Is the plan to make all reference counting atomic, or only some magical cases?

Yeah, I think this is a much more robust approach, because the wrapped object doesn’t even have to be immutable, or follow strict Py_CHECKWRITE contracts. Immutability is nice sometimes, but you still generally want some shared data between threads. Several months ago, I threw together a POC for this exact idea with subinterpreters via an immortal object proxy. There are definitely some issues with it, but I think this PEP doing something similar would play better with the ecosystem (particularly because you wouldn’t need to modify every C type out there).

6 Likes
6

If you do copy.deepcopy(..) on an immutable object is the result also immutable?

Edit:

Similarly if you pickle and unpickle does it maintain immutability? (Even if there is a custom setstate, etc.). In particular I’m thinking about multiprocessing and if immutability would make it to other processes.

3 Likes
7

This just strikes me as too huge a change to Python semantics. The fact that arbitrary sections of the object graph could be made immutable from any given call to freeze seems like an unacceptable risk. The fact that you can just call freeze(obj) on something and thereby essentially turn it into something quite different (in terms of supported operations) is similarly disruptive (e.g., the example of freezing a list and then being unable to mutate it).

There also appear to be some gaps and inconsistencies in the PEP.

Consider the object graph o1 --> o2 --> o3 where o1 and o3 can be made immutable, but o2 cannot. What are the possible behaviours of freeze(o1)?

  1. Freeze fails partially. All subgraphs which could be made immutable entirely remain immutable. Remaining objects remain mutable. In our example, o3 remains immutable but o1 and o2 remain mutable.

The other numbered items are marked as “rejected”, so apparently this is the accepted one. This suggests that o3 would remain frozen as a side-effect of a failed attempt to freeze o1. But then later:

Following the outcomes of the design decisions discussed just above, the freeze(obj) function works as follows:
[…] If obj cannot be made immutable, the entire freeze operation is aborted without making any object immutable.

Now it says that the freeze will not make any objects immutable.

Then there is this:

Although we have not seen this during our later stages of testing, it is possible that freezing an object that references global state (e.g., sys.modules, built-ins) could inadvertently freeze critical parts of the interpreter.

This is not very comforting. :slight_smile: What kind of testing has been done? If I have this:

import sys

class Foo:
    def __init__(self):
        self.x = sys.modules

f = Foo()
freeze(f)

. . . what is the defined behavior? What if it is sys.path instead of sys.modules?

Mitigation: Avoiding accidental freezing is possible by inheriting from (or storing a pointer to) the NotFreezable class.

This mitigation doesn’t seem adequate, since if I have an object that references sys.modules, I don’t know if someone else might wind up trying to freeze my object indirectly via some chain of references.

In general I’m not convinced by the argument that freezing is opt-in so everything will be fine. There could be rarely-used code paths that mutate an object, which under this PEP could then unexpectedly fail due to distant code that freezes some other object that was indirectly linked in the object graph. The problem is compounded if it can affect critical global state (like sys.modules). We don’t want a situation where you install some library and everything appears fine for a long time and then later on you call some function in a seemingly innocuous way and suddenly your interpreter is ice-nined because the freeze made its way to sys.path or the like.

13 Likes
8

So, the first replies here echo the concerns I stated on the ideas thread, and which are not as of yet addressed.

TL;DR: the freezing of an instance’s class and all its hierarchy (superclasses, metaclasses) seens to be too over-reaching, and may not only cause severe problems as stated by @steve.dower , @ZeroIntensity and @BrenBarn posts (so far).

So, for Python since its inception up to know, if I create a class - I can come “later” and change it - by replacing a method, or changing an attribute. That may or not be “good practice”, but it is inherently allowed in Python.

And with this feature as currently stated, if between the two events, an instance of my class happens to be in a frozen graph, all of a suden an exception will be raised - in my code.

To keep it visual, let’s say we have these:

Project A: my project, project B: another 3rd party lib which makes use of freeze and Project C: a “final user” project consuming both A and C

Project C comes to add an instance of A.Klass() to a list - and pass that list to B.communicate() which freezes it, and therefore freezes A.Klass.

The remedy with the PEP as is is to mark A.Klass as “NotFreezable” - which could be feasible (more like a workaround) for new code - but what for already existing code?

What if the “not good programming practice” A.Klass mutation is restricted to a new subclass being created?

The PEP text supposedly addresses this, but doesn’t feel like complete:

Summary

Because this reference [to subclasses] does not get exposed to the programmer in any dangerous way, we permit immutable classes to be subclassed (by mutable classes).

What is “any dangerous way”? The fact is that type(A).__subclassess__() would allow one to retrieve a “non-frozen” subclass of a frozen class: there is no semantic difference if __subclasses__ were a direct attribute instead of being a callable.

If the protocol will resort to raise an error when super(None, type(self).__subclasses__()[0]).mutate_class() it could as well just raise the same error when calling self.mutate_class() -
Maybe assuming that classes are not freezable at all is a worth (and required) compromise on the non-strict immutability side.

Other than rejecting class freezing outright, I’d pursue the proxy idea: That is, instead of eagerly freezing everything in a subject graph, guard the attribute/item retrievals on a frozen object so that nested items are either lazily frozen, or retrieved as a “frozen proxy” (which seems suitable for classes) - in this scenario, a 'frozen proxy" for a class would have the same guards.

(the original object owner could be able to bypass that by having a reference to an item in an object graph prior to freezing, ang them mutating that branch after freezing the root object - but, I think for cases like this “consenting adults” apply)

1 Like
9

Have you considered my suggested consenting-adult approach of limiting the recursion to only the subordinates of an object being frozen to make the proposal a lot less prone to freezing unintended objects?

It’s hard for me to imagine how a proxy approach can work when a proxy object cannot possibly be of the same type as the actual object. It may be able to behave like the actual object, but it will fail if its exact type is checked on or if direct access to a slot of the actual object is needed.

Thanks for the POC. I haven’t spent time looking into the implementation, but can you quickly brief me at a high level on how for example a proxy dict can work with, say, PyDict_GetItem? Does PyDict_GetItem need to be modified such that it will obtain the actual object first if it finds that the object passed in is a proxy?

1 Like
10

What changes have been made based on feedback in the pre pep discussion? Skimming the document, I couldn’t find anything.

Ah, that’s a great question — we should probably have highlighted that in the post above. So a bunch of things changed in the PEP:

  1. We added a section on expected usage
  2. We added a section about hashing
  3. We added a section about typing
  4. We added a clarification that making objects immutable does not weaken type-based reasoning on a fundamental level (that’s part of 2. but I wanted to highlight that here — i.e. there is nothing in Python today that guarantees that a list can be appended to, this was also demonstrated by e.g. @nloic-simon in the old ideas thread)
  5. We added a section on naming and we also changed some names
  6. We moved some things around, e.g. moving copy-on-write to a deferred ideas section
  7. We fixed some bugs in the code examples that readers caught

For clarity: in terms of fundamental changes to the design, we did not make any changes (yet).

With respect to the accidental freezing of parts of the interpreter, I’ll get back to you in this channel. Thanks for reminding us!

1 Like
11

Hi Steve,

Now it may be that I am just hearing what I want to hear, but it seems to me like you are describing the region-based ownership model that we mention in the future extensions work (which is why it is not in the rejected section). We presented this during the Python language summit and the presentation we gave is here:

https://wrigstad.com/summit-presentation-final.pdf

The presentation might be hard to grok in isolation. We do have an entire paper about this stuff which you can read here:

https://dl.acm.org/doi/10.1145/3729313

The way I understand it, what we call a region is the proxy that you are describing. All the objects inside a region stay mutable, and the region controls who may access its contents. In our proposal — since we are focused on concurrency — a region can be operated on by only one thread at a time.

Regions and immutability go together because you cannot for example easily put type objects in regions — think strings and numbers… So some things you want to be able to share directly without a proxy, which is where deep immutability comes into play.

Please excuse me if I am projecting stuff onto what you wrote, but it seems to me to be a lot of mindshare going on here!

2 Likes
12

Here is some more information about the project, which might be a good introduction: Fearless Concurrency for Python | Project Verona

(Assuming this is close or related to the region based ownership mentioned above)

One thing we’re cautious about, is adding too much freedom to immutability, as features like allowing internal mutability of these objects might make it complicated to integrate with future work.

As part of the linked paper, we’ve developed a small toy language, which implements immutability alongside regions. When working with the toy language, we usually only needed to make types and literals immutable, since they should be the same across all proxy objects. But most other objects remained mutable.

1 Like
13

This work sounds super interesting and similar to what we want to do in future work following this PEP. Do you have any more documentation of how the POC works?

I’m also interested, in your implementation, is there any way to get a reference to the object behind the proxy? And if so, what happens if an interpreter holds on to the reference while data is requested from another interpreter?

14

Thanks for restating them — they were not intentionally ignored! We will reply in this thread!

15

Hi Peter — so the use of del and = None were used to illustrate a capability of the proposal to handle cycles. There is nothing in this proposal that forces a program to use these concepts or a programmer to think about garbage collection. The reason why we highlighted the support for cycles is not actually related to GC but more in line with your next point — when you force objects to be immutable on creation, then creating cycles is something that you cannot do. The intention was to show that the proposal was strong enough to support the creation of cycles.

Further down in the PEP we discuss adding support for collecting cyclic immutable garbage without using the Python cycle detector. Again, this is not something that a programmer needs to think about. It is actually rather the opposite: you don’t have to care whether your data contains a cycle or not — we can freeze them regardless and also GC them efficiently regardless.

I hope I was able to fully satisfy your first main complaint with the above.

With respect to your second main complaint, one option (which is discussed in the PEP under More Rejected Alternatives) is to make a copy of the frozen object. That both solves your conceptual problem of marking the object as immutable has to mutate the object to set a flag, and also avoids “random things” becoming immutable under-foot. Of course, the failure mode now is that your frozen object graph still contains the “random things” but nothing that you expected to stay mutable will have become mutated. It would be possible to permit freezing to work either in-place (as in the proposal) or by copy.

I will let @matajoh answer the question about the inspiration (etc.) of register_freezable(type).

We don’t expect the performance to be much negatively impacted by this PEP. Hopefully we can back this up soon once we have rebased our implementation of this PEP on Python 3.15.

Actually no. In free-threaded Python, we can piggyback on existing locks to ensure this check does not race badly with concurrent freezing.

Good question. Atomic reference counting will only be used on immutable objects, so mutable objects are unaffected. Furthermore, since the immutable objects are, well immutable, there are no extra costs for fortifying the run-time against races on field updates at the same time as we are doing reference count manipulations. So the situation is a lot simpler than when you cannot fall back on a GIL to exclude possibility of such situations.

In the free-threaded build, we can use the reference counting mechanism it provides for concurrency.

4 Likes
16

This is a super good question. We have always talked about copying as being the way to “un-freeze” something (rather than doing it in-place, like we have proposed freezing to be). We should update the PEP with a clear statement on this.

Same answer here. On a related note, deep immutable objects will become sharable by reference across subinterpreters (with the follow-up extension that we propose in the PEP).

1 Like
17

Here’s a cleaned up diff:

diff --git "a/pep-0795" "b/pep-0795.rst"
index 12b6ffe..26aa4ec 100644
--- "a/pep-0795.rst"
+++ "b/pep-0795.rst"
@@ -26,8 +26,6 @@ but user-facing functions are delivered in a module called
 
 2. The function ``isfrozen(obj)`` -- returns ``True`` if ``obj`` is immutable
 
-2.5. The function ``isfreezable(obj)`` -- returns ``True`` if all objects reachable from ``obj`` can be frozen
-
 3. The type ``NotFreezable`` which is an empty type which cannot be made immutable and can be used as a super class to classes whose instances should not be possible to freeze
 
 4. The type ``NotFreezableError`` which is raised on an attempt to mutate an immutable object
@@ -242,15 +240,6 @@ wishes to support immutability needs updating. The downside of the
 opt-in model is that a large part of all Python libraries cannot
 be (even nominally) made immutable (out-of-the-box).
 
-This PEP proposes to make support for immutability in C extensions
-and Python wrappers of classes which would otherwise not be freezable
-opt-in through a whitelisting mechanism implemented through the
-function ``register_freezable(type)`` in the ``immutable`` module.
-
-Note that it is possible to mix modules and types that support
-immutability with those that do not, as long as this does not
-breaks strictness.
-
 
 Strictness
 ----------
@@ -382,6 +371,49 @@ starting places are ``object.c`` `[1]`_ and ``dictobject.c`` `[2]`_.
 .. _[2]: https://github.com/mjp41/cpython/pull/51/files#diff-b08a47ddc5bc20b2e99ac2e5aa199ca24a56b994e7bc64e918513356088c20ae
 
 
+Expected Usage of Immutability
+------------------------------
+
+The main motivation for adding immutability in this PEP is to
+facilitate concurrent programming in Python. This is not something
+that Python's type system currently supports -- developers have to
+rely on other (i.e. not type-driven) methods to communicate around
+thread-safety and locking protocols. We expect that the same
+methodology works for immutable objects with the added benefit
+that mistakes lead to exceptions rather than incorrectness bugs or
+crashes. As the Python community adopts immutability, we expect to
+learn about the patterns that arise and this can inform e.g. how
+to develop tools, documentation, and types for facilitating
+programming with immutable objects in Python.
+
+We expect that libraries that for example want to provide intended
+constants may adopt immutability as a way to guard against someone
+say re-defining pi. Freezing a module's state can be made optional
+(opt-in or opt-out) so that the option of re-defining pi can be
+retained.
+
+If immutability is adopted widely, we would expect libraries to
+contain a section that detail what types etc. that it provides
+that can be made immutable or not. If Python's type system adds
+support for (say) distinguishing between must-be-mutable,
+must-be-immutability, and may-be-immutable, such annotations can
+be added to the documentation of a library's public API.
+
+If a library relies on user-provided data to be immutable, we
+expect the appropriate pattern is to check that the data is
+immutable and if not raising an exception rather than to make the
+data immutable inside the library code. This pushes the obligation
+to the user in a way that will not lead to surprises due to data
+becoming immutable under foot.
+
+We expect programmers to use immutability to facilitate safe
+communication between threads, and for safe sharing of data
+between threads. In both cases, we believe it is convenient to be
+able to freeze a data structure in-place and share it, and we
+expect programmers to have constructed these data structures with
+this use case in mind.
+
+
 Deep Freezing Semantics
 =======================
 
@@ -657,9 +689,6 @@ Implementation Details
    cycle detection, and marks objects appropriately, and backs
    out on failure, possibly partially freezing the object graph.
 
-2.5. Add the ``isfreezable(obj)`` function which checks that all
-   objects reachable from ``obj`` can be frozen.
-
 3. Add the ``register_freezable(type)`` function that is used to
    whitelist types implemented as C extensions, permitting their
    instances to be made immutable.
@@ -751,6 +780,14 @@ More Rejected Alternatives
        logic and/or temporal interactions which can be hard to
        test and reproduce.
 
+Another rejected idea was to provide a function ``isfreezable(obj)`` which
+returns ``True`` if all objects reachable from ``obj`` can be made
+immutable. This was rejected because free-threaded Python permits
+data-races during freezing. This means that the result of the check
+can be non-deterministic. A better way is to simply try to make
+an object immutable and catch the exception if the object could not
+be frozen.
+
 
 A Note on Modularisation
 ========================
@@ -801,6 +838,187 @@ mutable and access to shared immutable objects can race on accesses
 to weak references.
 
 
+Hashing
+=======
+
+Deep immutability opens up the possibility of any freezable object being
+hashable, due to the fixed state of the object graph making it possible to compute
+stable hash values over the graph as is the case with ``tuple`` and ``frozenset`` . However,
+there are several complications (listed below) which should be kept in mind for any future
+PEPs which build on this work at add hashability for frozen objects:
+
+
+Instance versus Type Hashability
+--------------------------------
+
+At the moment, the test for
+`hashability <https://docs.python.org/3/glossary.html#term-hashable>`__
+is based upon the presence (or absence) of a ``__hash__`` method and an
+``__eq__`` method. Places where ``PyObject_HashNotImplemented`` is currently
+used would need to be modified as appropriate to have a contextual logic
+which provides a default implementation that uses ``id()`` if the object
+instance has been frozen, and throws a type error if not.
+
+This causes issues with type checks, however. The check of
+``isinstance(x, Hashable)`` would need to become contextual, and
+``issubclass(type(x), Hashable)`` would become underdetermined for
+many types. Handling this in a way that is not surprising will require
+careful design considerations.
+
+
+Equality of Immutable Objects
+-----------------------------
+
+One consideration with the naive approach (*i.e.*, hash via ``id()``) is
+that it can result in confusing outcomes. For example, if there were
+to be two lists:
+
+.. code-block:: python
+
+  a = [1, 2, 3, 4]
+  b = [1, 2, 3, 4]
+  assert(hash(a) == hash(b))
+
+There would be a reasonable expectation that this assertion would be true,
+as it is for two identically defined tuples. However, without a careful
+implementation of ``__hash__`` and ``__eq__`` this would not be the case.
+Our opinion is that an approach like that used in ``tuplehash`` is
+recommended in order to avoid this behavior.
+
+
+Decorators of Immutable Functions
+=================================
+
+One natural issue that arises from deeply immutable functions is the
+state of various objects which are attached to them, such as decorators.
+In particular, the case of ``lru_cache`` is worth investigating. If the cache
+is made immutable, then freezing the function has essentially disabled the
+functionality of the decorator. This might be the correct and desirable
+functionality, from a thread safety perspective! In practice, we see three
+potential approaches:
+
+1. The cache is frozen in its state at the point when freeze is called.
+   Cache misses will result in an immutability exception.
+
+2. Access to the cache is protected by a lock to ensure thread safety
+
+3. There is one version of the cache per interpreter (*i.e.*, the cache is thread local)
+
+There are arguments in favor of each. Of them, (3) would
+require additional class to be added (*e.g.*, via the ``immutable`` module)
+which provides "interpreter local" dictionary variable that can be safely
+accessed by whichever interpreter is currently calling the immutable function.
+We have chosen (1) in order to provide clear feedback to the programmer that
+they likely do not want to freeze a function which has a (necessarily) mutable
+decorator or other object attached to it. It is likely not possible to make
+all decorators work via a general mechanism, but providing some tools to
+provide library authors with the means to provide a better experience for
+immutable decorators is in scope for a future PEP building on this work.
+
+
+Deferred Ideas
+==============
+
+Copy-on-Write
+-------------
+
+It *may* be possible to enforce immutability through copy-on-write.
+Such a system would not raise an exception on ``x.f = y`` when
+``x`` points to an immutable object, but rather copy the contents
+of ``x`` under the hood. Essentially, ``x.f = y`` turns into ``x =
+deep_copy(x); x.f = y``. While it is nice to avoid the error, this
+can also have surprising results (e.g. loss of identity of ``x``),
+is less predictable (suddenly the time needed to execute ``x.f = y``
+becomes proportional to the object graph rooted in ``x``) and may
+make code harder to reason about.
+
+
+Typing
+------
+
+Support for immutability in the type system is worth exploring in
+the future. Especially if Python adopts an ownership model that
+enables reasoning about aliasing, see `Data-Race Free Python`_
+below.
+
+Currently in Python, ``x: Foo`` does not give very strong
+guarantees about whether ``x.bar(42)`` will work or not, because
+of Python's strong reflection support that permits changing a
+class at run-time, or even changing the type of an object.
+Making objects immutable in-place exacerbates this situation as
+``x.bar(42)`` may now fail because ``x`` has been made immutable.
+However, in contrast to failures due to reflective changes of
+a class, a ``NotFreezableError`` will point to the place in the
+code where the object was frozen. This should facilitate debugging.
+
+In short: the possibility of making objects immutable in-place
+does not weaken type-based reasoning in Python on a fundamental
+level. However, if immutability becomes very frequently used, it
+may lead to the unsoundness which already exists in Python's current
+typing story surfacing more frequently. As alluded to in the
+future work on `Data-Race Free Python`_, this can be mitigated by
+using region-based ownership.
+
+There are several challenges when adding immutability to a type
+system for an object-oriented programming language. First, self
+typing becomes more important as some methods require that self is
+mutable, some require that self is immutable (e.g. to be
+thread-safe), and some methods can operate on either self type.
+The latter subtly needs to preserve the invariants of immutability
+but also cannot rely on immutability. We would need a way of
+expressing this in the type system. This could probably be done by
+annotating the self type in the three different ways above --
+mutable, immutable, and works either way.
+
+A possibility would be to express the immutable version of a type
+``T`` as the intersection type ``immutable & T`` and a type that
+must preserve immutability but may not rely on it as the union
+of the immutable intersection type with its mutable type
+``(immutable & T) | T``.
+
+Furthermore, deep immutability requires some form of "view-point
+adaption", which means that when ``x`` is immutable, ``x.f`` is
+also immutable, regardless of the declared type of ``f``.
+View-point adaptation is crucial for ensuring that immutable
+objects treat themselves correctly internally and is not part of
+standard type systems (but well-researched in academia).
+
+Making ``freeze`` a soft keyword as opposed to a function `has
+been proposed
+<https://discuss.python.org/t/adding-deep-immutability/92011/71>`_
+to facilitate flow typing. We believe this is an excellent
+proposal to consider for the future in conjunction with work on
+typing immutability.
+
+
+Naming
+======
+
+We propose to call deep immutability simply "immutability". This
+is simple, standard, and sufficiently distinguishable from other
+concepts like frozen modules.
+
+We also propose to call the act of making something immutable
+"freezing", and the function that does so ``freeze()``. This is
+the same as used in JavaScript and Ruby and is considerably
+snappier than ``make_immutable()`` which we suspect would be
+immediately shortened in the community lingo. The major concern
+with the freeze verb is that immutable objects risk being referred
+to as "frozen" which then comes close to frozen modules (bad link)
+and types like ``frozenset`` (good link).
+
+While naming is obviously important, the names we picked initially
+in this PEP are not important and can be replaced. A good short
+verb for the action seems reasonable. Because the term immutable
+is so standard, we should think twice about replacing it with
+something else.
+
+Qualifying immutability and freezing with an additional "deep" (as
+proposed `here
+<https://discuss.python.org/t/adding-deep-immutability/92011/6>`_)
+seems like adding extra hassle for unclear gains.
+
+
 Future Extensions
 =================
 
@@ -915,6 +1133,18 @@ is to make it impossible for Python programs to have data races.
 Support for deeply immutable data is the first important step
 towards this goal.
 
+The region-based ownership that we propose can be used to restrict
+freezing to only be permitted on regions which are isolated. If
+such a restriction is built into the system, then there will be a
+guarantee that freezing objects will not turn affect references
+elsewhere in the system (they cannot exist when the region is
+isolated). Such a design can also be used to track immutability
+better in a type system and would be able to deliver a guarantee
+that a reference of a mutable type never points to an immutable
+object, and conversely. These points will be unpacked and made
+more clear in the PEP for the ownership model.
+
+
 
 Reference Implementation
 ========================
@@ -924,7 +1154,6 @@ Reference Implementation
 There are some discrepancies between this PEP and the reference
 implementation, including:
 
-- The ``isfreezable(obj)`` function is not yet implemented.
 - The ``NotFreezable`` type is currently freezable (but inheriting
   from it stops instances of the inheriting class from being made immutable).
18

So, to begin, every pure Python class is freezable by default. An object graph which consists of only pure Python objects can be frozen. We have also made several types compatible with freezing and added them statically, such as list, dict, and other core types.

The purpose of register_freezable is to increase the scope of what can be frozen. The first category is C extension types. We have made some types from the standard library freezable, such as Decimal. To do so, in each case we have added the appropriate write barriers and then called register_freezable as part of that module’s initialisation. C extension authors who wish their types to be freezable can do the same, as otherwise C extension types with custom functionality are not freezable by default.

The second purpose of register_freezable is to allow programmers to explicitly declare an immutable wrapper type. In this scenario, they can write a Python class which wraps an otherwise unfreezable type (e.g., a C extension) and then provide logic in Python that makes that type threadsafe/freezable. They can then call register_freezable, at which point the freezability check will stop walking the type graph at that type. For this second use case, we’ve thought perhaps a decorator may be a better fit (as a bit of syntactic sugar) but wanted to get a sense of how the feature was received.

A really important side note on this topic is that the check we perform to ensure that a type is freezable is not just a simple check to see whether a type is a C extension type. Instead, we inspect the methods. If the dictionary is empty and all methods are inherited from freezable types (i.e., types which we know have write barriers added appopriately) then the type will “inherit” freezability. This is what allows ctypes to be frozen, for example.

1 Like
19

I’m not even thinking that robust. On the surface, by proxy I mean something like this:

class ReadOnlyDictProxy:
    def __init__(self, d): self.__d = d
    def __getitem__(self, k): return self.__d[k]
    def __setitem__(self, k, v): raise ImmutableError()
    ...

But the trick is that’s only the API surface, and the implementation can be all sorts of different inside, handling locking/ownership/copying/etc. The critical part is that the original owner of the dict is able to pass a proxy while still retaining ownership of the dict (and yes, if they mutate it then mutations may be seen eventually by others, depending on the kind of proxy you created for them). Implement an object.__proxy__ member and we can make all objects automatically (inefficiently) shareable, with the ability to override it for certain types.

If you wanted to apply it to regions, then you could say the original dict is permanently fixed in its region, but proxies are allowed to be passed and used across regions. (If you implement “region” with “subinterpreter” then much of it is already there.)

The main point is that it doesn’t require users to understand complex ownership or sharing semantics. They have an object, they keep the unchanged object, their other task can see the object but can’t change it, and from their POV it magically works without changing much, if any, of their existing code.[1]

And internally we have all sorts of freedom to implement efficient and safe methods for sharing, rather than putting that burden on every developer involved in a huge project. So we can use RW locks on types where they make sense, or make full copies, or migrate into shared memory, or defer reference counting entirely. If the original object goes away, we can choose whether the proxies keep it alive or start failing, because it’s behind the API.

Many of the specific ideas you’ve got here will be helpful, but the main thing I want is to keep them as private details as much as possible, rather than making it a part of the user interface of Python. We shouldn’t have to make the Python language and semantics more complex for this.

  1. Assuming we did indeed add object.__proxy__ and start using it. ↩︎

20

This feels to me like you’re missing the point. Yes, Python doesn’t guarantee that a list can be appended to, but there are very strong conventions that dictate that passing an object to a function that accepts a value of type list means that you are OK with that called function appending a value to the list. Furthermore, list is a subclass of MutableSequence, and while technically, a sequence which defined all mutating methods as raising an exception still fits the specification of MutableSequence, I don’t think anyone is going to accept that it’s reasonable to think it’s a valid example of a mutable sequence.

By having frozen lists still have a type of list, you are explicitly violating those social conventions. And by making the argument I quote above, you are saying that social conventions don’t matter, all that matters is “the letter of the language specification” - which as you correctly point out, guarantees almost nothing.

I don’t think this is a reasonable argument to make, and even if you disagree, it’s probably irrelevant, as what matters is the practical impact of the choice to consider a frozen list as still having the type list - and you can’t handwave that away. If the type system isn’t tracking mutability, are you saying that the user must do so? Because the success of static type checkers says very clearly to me that people don’t want to do that sort of manual tracking of constraints.

21 Likes