Background#

The goal of this package is to present an alternative representation of Python that is more amenable to analysis and optimization. The eventual goal is to lift Python’s bytecode into an SSA form and then transforming that SSA CFG into a dataflow graph, and this package is the first step along that path.

It mirrors in some way the work in the C / LLVM space to automatically parallize and optimize that code.

One way we can understand this problem is visually, as the number of differnt forms Python takes:

  1. In the CPython implementation, Python goes from:

    1. Source code

    2. to an AST

    3. to bytecode

  2. We then want to take that lowest level, bytecode, and build back up to a higher level representation that is more amenable to optimization and analysis, describing the semantics of Python:

    1. This package implements a minimal data semantics of the bytecode level, that is more tightly specified than how the bytecode is represented in memory. This gives us a higher level representation

    2. On top of that, we can transform the stack based representation into SSA CFG created from the bytecode. This effectively erases the stack details, leaving you with SSA. This translation is meant to be an abstract analog of CPython’s bytecode interpreter. So that instead of interpreting the bytecode eagerly, it builds up a CFG first that has the same semantics as interpreting it.

    3. Finally, we can lift that A dataflow graph, showing data dependencies, from this SSA. At this level, program optimization becomes much simpler and straightforward.

We test out abstraction level 1-3 by also building ways to go backwards, and taking Python bytecode as an input and making sure all the transformations are isomorphic. This type of testing can help us be confident that the different representations are semantically faithful to the original bytecode source, and so the original Python behavior.

To use this library to somehow optimize or analyze Python code then, you would walk down the first three Python levels, then walk down our three levels we provide here, perform any optimizations or translations, and walk back up however many levels you like to get the form you are looking for.

The underlying theory behind this library is that at the dataflow graph level, we can more closely represent the programs denotional semantics, aka the underlying conceptual meaning of the program. This is the level closer to our own human understanding of what the program “does”. So if we can move the program faithfully up to this level, then we can reason about it in terms which are closer to how we think.

For example, as a human we can reason about adding taking the sum of two arrays, and say that “the result at index i is the addition of the first array at index i at the second array at index i. So if we add two arrays and then immediately index, we know that we don’t have to recompute the full array, but simply the sum of the two corresponding values.” Encoding this sort of logic at the level of Python bytecode simply does not make sense. The bytecode has no idea about some abstract value of an array, or more fundamentally even of a value that is defined mathematically like this. However, at the dataflow level, it becomes feasible to reason about values in this matheamtical sense, instead of in a memory/imperative sense. So at least we have some hope of being express this sort of meaning, and have the computer use it to optimize our program.

After doing this optimization, we can move it back down to whatever level we like to actually execute. We might chose to go back to Python source, or we might instead chose to compile to some alternative implementaiton before executing, such as high level language like SQL or a lower level langauge like LLVM.