[Python-Dev] PEP 550 v3

[Yury Selivanov]

On Mon, Aug 21, 2017 at 8:06 PM, Guido van Rossum <guido at python.org> wrote:
> On Mon, Aug 21, 2017 at 12:50 PM, Yury Selivanov <yselivanov.ml at gmail.com>
> wrote:
>>
>> Few important things (using the current PEP 550 terminology):
>>
>> * ExecutionContext is a *dynamic* stack of LogicalContexts.
>> * LCs do not reference other LCs.
>> * ContextKey.set() can only modify the *top* LC in the stack.
>>
>> If LC is a mutable mapping:
>>
>>      # EC = [LC1, LC2, LC3, LC4({a: b, foo: bar})]
>>
>>      a.set(c)
>>      #    LC4 = EC.top()
>>      #    LC4[a] = c
>>
>>      # EC = [LC1, LC2, LC3, LC4({a: c, foo: bar})]
>>
>> If LC are implemented with immutable mappings:
>>
>>      # EC = [LC1, LC2, LC3, LC4({a: b, foo: bar})]
>>
>>      a.set(c)
>>      #    LC4 = EC.pop()
>>      #    LC4_1 = LC4.copy()
>>      #    LC4_1[a] = c
>>      #    EC.push(LC4_1)
>>
>>      # EC = [LC1, LC2, LC3, LC4_1({a: c, foo: bar})]
>>
>> Any code that uses EC will not see any difference, because it can only
>> work with the top LC.
>
>
> OK, good. This makes more sense, especially if I read "the EC" as shorthand
> for the EC stored in the current thread's per-thread state.

That's exactly what I meant by "the EC".

> The immutable
> mapping (if used) is used for the LC, not for the EC, and in this case
> cloning an EC would simply make a shallow copy of its underlying list --
> whereas without the immutable mapping, cloning the EC would also require
> making shallow copies of each LC. And I guess the linked-list implementation
> (Approach #3 in the PEP) makes EC cloning an O(1) operation.

All correct.

>
> Note that there is a lot of hand-waving and shorthand in this explanation,
> but I think I finally follow the design. It is going to be a big task to
> write this up in a didactic way -- the current PEP needs a fair amount of
> help in that sense.

Elvis Pranskevichus (our current What's New editor and my colleague)
offered me to help with the PEP. He's now working on a partial rewrite.

I've been working on this PEP for about a month now and at this point
it makes it difficult for me to dump this knowledge in a nice and
readable way (in any language that I know, FWIW).

> (If you want to become a better writer, I've recently
> enjoyed reading Steven Pinker's The Sense of Style: The Thinking Person's
> Guide to Writing in the 21st Century. Amongst other fascinating topics, it
> explains why so often what we think is clearly written can cause so much
> confusion.)

Will definitely check it out, thank you!

>
>>
>> Back to generators. Generators have their own empty LCs when created
>> to store their *local* EC modifications.
>>
>> When a generator is *being* iterated, it pushes its LC to the EC. When
>> the iteration step is finished, it pops its LC from the EC.  If you
>> have nested generators, they will dynamically build a stack of their
>> LCs while they are iterated.
>>
>> Therefore, generators *naturally* control the stack of EC.  We can't
>> execute two generators simultaneously in one thread (we can only
>> iterate them one by one), so the top LC always belongs to the current
>> generator that is being iterated:
>>
>>     def nested_gen():
>>         # EC = [outer_LC, gen1_LC, nested_gen_LC]
>>         yield
>>         # EC = [outer_LC, gen1_LC, nested_gen_LC]
>>         yield
>>
>>     def gen1():
>>         # EC = [outer_LC, gen1_LC]
>>         n = nested_gen()
>>         yield
>>         # EC = [outer_LC, gen1_LC]
>>         next(n)
>>         # EC = [outer_LC, gen1_LC]
>>         yield
>>         next(n)
>>         # EC = [outer_LC, gen1_LC]
>>
>>     def gen2():
>>         # EC = [outer_LC, gen2_LC]
>>         yield
>>         # EC = [outer_LC, gen2_LC]
>>         yield
>>
>>     g1 = gen1()
>>     g2 = gen2()
>>
>>     next(g1)
>>     next(g2)
>>     next(g1)
>>     next(g2)
>
>
> This, combined with your later clarification:
>
>> In the current version of the PEP, generators are initialized with an
>> empty LogicalContext.  When they are being iterated (started or
>> resumed), their LogicalContext is pushed to the EC.  When the
>> iteration is stopped (or paused), they pop their LC from the EC.
>
> makes it clear how the proposal works for generators. There's an important
> piece that I hadn't figured out from Nick's generator example, because I had
> mistakenly assumed that something *would* be captured at generator create
> time. It's a reasonable mistake to make,

Yeah, it is very subtle.

>
>>
>> HAMT is a way to efficiently implement immutable mappings with O(log32
>> N) set operation, that's it.  If we implement immutable mappings using
>> regular dicts and copy, set() would be O(log N).
>
>
> This sounds like abuse of the O() notation. Mathematically O(log N) and
> O(log32 N) surely must be equivalent, since log32 N is just K*(log N) for
> some constant K (about 0.288539), and the constant disappears in the O(), as
> O(K*f(N)) and O(f(N)) are equivalent. Now, I'm happy to hear that a
> HAMT-based implementation is faster than a dict+copy-based implementation,
> but I don't think your use of O() makes sense here.

I made a typo there: when implementing an immutable mapping
with Python dicts, setting a key is an O(N) operation (not O(log N)):
we need to make a shallow copy of a dict and then add an item
to it. (the PEP doesn't have this typo)

With HAMT, set() is O(log32 N):
https://github.com/python/peps/blob/master/pep-0550-hamt_vs_dict.png

Yury