[Python-Dev] PEP 550 v3 (original) (raw)

Yury Selivanov yselivanov.ml at gmail.com
Mon Aug 21 20:31:37 EDT 2017

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() # LC41 = LC4.copy() # LC41[a] = c # EC.push(LC41) # EC = [LC1, LC2, LC3, LC41({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 nestedgen(): # EC = [outerLC, gen1LC, nestedgenLC] yield # EC = [outerLC, gen1LC, nestedgenLC] yield def gen1(): # EC = [outerLC, gen1LC] n = nestedgen() yield # EC = [outerLC, gen1LC] next(n) # EC = [outerLC, gen1LC] yield next(n) # EC = [outerLC, gen1LC] def gen2(): # EC = [outerLC, gen2LC] yield # EC = [outerLC, gen2LC] 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

More information about the Python-Dev mailing list