I frequently find myself in a situation where I wish I could say "the execution order of these two lines just doesn't matter."
Proposed here are two freshly drafted PEP's advocating for the addition of nondeterminism as a spring board for future automatic parallelism. The first calls for core language changes, the second calls for a minor (and likely symbolic) change to list comprehension's semantics to better support future parallelism. PEP: XXX Title: Nondeterminism Version: $Revision$ Last-Modified: $Date$ Author: Adam DePrince <[EMAIL PROTECTED]> Status: Draft Python-Version: 3.0 Type: Standards Content-Type: text/plain Created: 24-Mar-2006 Post-History: Abstract Proposed herein is are two new control flow structures that allow the explicit specification of parallelism by defining the order of expression evaluation as non-deterministic, thus removing the requirement of sequential execution. Background A number of mechanisms have been proposed in Python that have the side effect of permitting the automatic discovery of parallelism. PEP 288 presents the notion of a generator, an object that inherently lends itself to concurrent operation and possibility automatic self organization of a pipeline. Stackless Python in PEP 219/220 presents a mechanism by which a large number micro threads could be efficiently supported, thus allowing for a realistic manifestation of a deep generator based software pipeline. Additionally, this PEP's sibling, XXX, proposes that the execution order of list comprehensions be made non-deterministic to permit future parallel implementations. DISCUSSION Two new control flow structures are proposed. While as of yet no name is proposed, for the sake of brevity we will refer to them as any and first. The any structure would call for the execution of all expressions within the any block in an non-determinate order. The user would warrant that no side effects exist between the expressions, and assigned to the variable the any block would be a list representing the return values of each of the expressions in the order they appear in the code (but not necessarily in the order of execution.) The first structure would execute all enclosed expressions concurrently, again, the order of execution being non-deterministic, other than the promise that all would be started. The return value of the first expression to finish would be assigned to the variable associated with the first block and the execution of the other operations terminated. SPECIFICATION The use of the word 'any' and 'first' is only a convenience. I do not yet propose a keyword for these structures. ... any retval: 1 2+3 my_function_that_returns_17() ... retval would be assigned [1, 5, 17] Only the order of evaluation is not deterministic. first retval: urllib.open( 'mirror1' ).read() urllib.open( 'mirror2' ).read() urllib.open( 'mirror3' ).read() .... retval would contain the data from the fastest mirror, the other threads would be disposed of. IMPLEMENTATION TBD - Incomplete REFERENCES TBD COPYRIGHT This document has been placed in the public domain. PEP: XXX Title: Nondeterministic List comprehensions Version: $Revision$ Last-Modified: $Date$ Author: Adam DePrince <[EMAIL PROTECTED]> Status: Draft Python-Version: 3.0 Type: Standards Content-Type: text/plain Created: 24-Mar-2006 Post-History: Abstract The semantics of the list comprehension offer the future benefit of multi-threading and parallel execution, assuming that the programmer treat the order of evaluation as non-deterministic and avoids the introduction of dependencies and side-effects. Background A number of mechanisms have been proposed in Python that have the side effect of permitting the automatic discovery of parallelism. PEP 288 presents the notion of a generator, an object that inherently lends itself to concurrent operation and possibility of automatic self organization of pipelined, and thus parallel, operation. Stackless Python in PEP 219/220 presents a mechanism by which a large number micro threads could be efficiently supported, thus allowing for a realistic manifestation of a deep generator based software pipeline. DISCUSSION Generators and generator comprehension are often regarded as superior to list comprehension due to the reduced footprint of in-flight data and the future potential of vertical parallelism via pipelining. List comprehensions, while having the drawback of requiring the presence of the entire working set in-flight, places no inherent restriction on the order of execution. This permits us to distribute the execution effort horizontally across multiple micro-threads, with a far higher potential for parallelism than generators at the expense of requiring the user warrant the absence of side effects of dependencies between each passing of the list comprehension loop. This minor semantic requirement that list comprehension possess no interdependencies or side effects permits us to operate on the list in an arbitrary order, including dispatching the execution across multiple threads. SPECIFICATION We change the semantics of a the list comprehension to explicitly state that the order of evaluation is non-deterministic, and that there should exist no dependencies or side effects. This leaves open the potential for future parallelization. PROBLEMS There are a currently a number of problems. Generators provide an intuitive and natural partitioning of the problem. The future partitioning of a list comprehension is a more capricious; generally, we choose a fixed number of threads to dovetail across, but little guidance can be gleaned from the use. The second drawback is the current state of python. With the global interpreter lock firmly in place, we have no compelling argument by which to parallelize our list comprehension, even if they were partitioned. Currently the creation of said micro-threads and the dovetailing of the workload would actually increase the execution time in the current 2.4 implementation of Python. Generators, even with the current lack of real parallelism to the resulting pipeline, benefit from the drastic reduction in the amount of in-flight data during their execution. The third problem is in the near term, this PEP calls for no implementation change, its only a request that users regard the execution order as non-deterministic. There is a reasonable change that this would be ignored. Lastly, there has been discussion of recasting list comprehension as generator comprehensions as an easy of normalizing the semantics of the iterator variable with respect to the callee's name-space. Such an effort would assign an explicit order of execution to the list comprehension. REFERENCES TBD COPYRIGHT This document has been placed in the public domain. -- http://mail.python.org/mailman/listinfo/python-list