frozendict: an experiment

[Marco Sulla]

On Thu, 16 Jul 2020 at 06:11, Inada Naoki <songofacandy at gmail.com> wrote:
> On Thu, Jul 16, 2020 at 2:32 AM Marco Sulla
> <Marco.Sulla.Python at gmail.com> wrote:
> > Yes, but, instead of creating a view, you can create and cache the
> > pointer of a "real" object, that implements the dict view API.
> > For example, keys for a frozendict could be an "ordered" frozenset.
> > This "oset" could be a frozendict
> I am not sure about what are you saying.
> Does it really solve the usage of dict views?
> How about my example? (`assert d.keys() == {"spam", "egg"}`)

Well, if the frozendict "views" will implement the full API of the
dict views, your assert and all the existing code will continue to
work.
The difference will be that views *could* be faster.

> > On Wed, 15 Jul 2020 at 08:07, Inada Naoki <songofacandy at gmail.com> wrote:
> Oh, ! am talking about dict views.  I meant there is no difference
> between "how dict view is useful for dict" and "how dict view is
> useful for frozendict".
>
> But I am still not sure about the optimizations and functional
> programming you are talking about.
> Please elaborate more, please?

About frozendict optimization

an immutable dict could be optimized in different ways in Python:
1. as I said, views can be replaced with "real", cached objects. This
will speed up subsequent calls to keys() etc.
2. as tuples and strings, small frozendicts can be interned in a
cache. The same cache can be used to return a cached frozendict
instead of recreate it, as tuples.
3. many python internals uses a mapping proxy to a dict, to avoid its
modification. A frozendict can be used instead.
4. dicts can use a split table or a combined table. This is useful for
maintaining insertion order upon deletion and insertion.
   This is not required for frozendicts, since once created they can't
be modified. frozendicts can be all split or all combined dicts.
   So in theory frozendicts could be created with the max useful size,
without resizing them, add the keys and values and then remove the
unused.
   This could speed up creation.

About functional programming

Well, pure functional programming requires no side effects:
https://en.wikipedia.org/wiki/Functional_programming
Object mutability is a side effect. Pure functional programming uses
only immutable objects.
In Python, pure functional programming is impossible, since even
functions are (partially) mutable objects. But Python has a lot of
functional programming features:
https://docs.python.org/3/howto/functional.html
Every builtin mutable data type has its immutable counterpart now,
dict apart. And types.MappingProxyType is not usable in real world,
since it's really slow.