[Python-Dev] PEP 550 v3

[Yury Selivanov]

On Mon, Aug 21, 2017 at 3:10 PM, Guido van Rossum <guido at python.org> wrote:
[..]
> Agreed. However now I am confused as to how the HAMT fits in. Yury says
> somewhere that the HAMT will be used for the EC and then cloning the EC is
> just returning a pointer to the same EC. But even if I interpret that as
> making a new EC containing a pointer to the same underlying HAMT, I don't
> see how that will preserve the semantics that different logical threads,
> running interleaved (like different generators being pumped alternatingly),
> will see updates to LCs that are lower on the stack of LCs in the EC. (I see
> this with the stack-of-dicts version, but not with the immutable HAMT
> inplementation.)

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.

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)

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).

[..]
>>
>> I'll also note that the first iteration of the PEP didn't really make
>> this distinction, and it caused a problem that Nathaniel pointed out:
>> generators would "snapshot" their entire dynamic context when first
>> created, and then never adjust it for external changes between
>> iterations. This meant that if you adjusted something like the decimal
>> context outside the generator after creating it, it would ignore those
>> changes - instead of having the problem of changes inside the
>> generator leaking out, we instead had the problem of changes outside
>> the generator *not* making their way in, even if you wanted them to.
>
>
> OK, this really needs to be made very clear early in the PEP. Maybe this
> final sentence provides the key requirement: changes outside the generator
> should make it into the generator when next() is invoked, unless the
> generator itself has made an override; but changes inside the generator
> should not leak out through next().

It's covered here with two examples:
https://www.python.org/dev/peps/pep-0550/#ec-semantics-for-generators

Yury