[Python-ideas] Revisiting Immutable Mappings

[Jonathan Fine]

Summary: Long post. Because of LSP, neither dict nor frozendict are a
subclass of the other.

Chris Barker wrote:
> If we REALLY had a time machine, then dict would subclass frozendict,
> and we’d be all set.

Prediction is difficult, particularly when it involves the future. - Neils Bohr.

And be careful about what you wish for.  Perhaps in Python 4 we can
fix this problem.

Chris Angelico <rosuav at gmail.com> wrote:
> Thanks to virtual subclassing, we can still do this. The question is, should we?

> Intuition tells me that a frozen dictionary is a form of dictionary
> that adds restrictions, not that a dictionary is a frozen dictionary
> that you left out to thaw.

It's not quite so simple. Sometimes, less is more.
https://www.phrases.org.uk/meanings/226400.html

Suppose every instance of class A has useful property P, and B is a
subclass of A. If the Liskov substitution principle (LSP) holds, then
every instance of B also has useful property P.

Notice that I said USEFUL property P. The negation Q of property P is
also a property. Often, Q is NOT USEFUL. But what if both P and its
negation Q are BOTH USEFUL?

Well, if there should be some strange useful property P, whose
negation is also useful then (drum roll) Liskov substitution says that
neither class is a subclass of the other. (I guess that's one of the
applications of LSP.)

Here's an example of such a property. A tuple of integers is
immutable, and so has a hash and can be used as a dictionary key.
Being immutable is a useful property. A list of integers is mutable,
and so can be used to record changing state. Being mutable is a useful
property.

Aside: Last month I prepared the show part of the show-and-tell for this.

https://github.com/jfine2358/python-show-and-tell/issues/1
How do we explain this to a novice

>>> dct = dict()
>>> point = [0, 1]
>>> dct[point] = 'red'
Traceback (most recent call last):
TypeError: unhashable type: 'list'

Conclusion: If we have LSP, then dict is not a subclass of frozendict,
and frozendict is not a subclass of dict. Neither is a subclass of the
other.

One way to fix this in Python 4 would be to create a common ancestor,
which has only the shared methods of dict and frozendict. Or do
something similar with abstract base classes.

Remark: The issues here might be related to mypy typing, which I've
not used. From what I've read, it seems to rely on LSP.

I've nothing to say at present about the hardest problem here, which
is naming things. We have list and tuple. But dict and what name for
frozen, and what name for common ancestor.
https://martinfowler.com/bliki/TwoHardThings.html

-- 
Jonathan