[PEAK] Compiling lvalues, iterators, and comprehensions

[Phillip J. Eby]

At 12:59 PM 7/28/2008 -0400, Phillip J. Eby wrote:
>So, the next thing to implement should be to just add For(), 
>LocalAssign(), and UnpackSequence() node types to BytecodeAssembler 
>(with doc & tests, of course), and release a new version.

Not quite so simple, as it turns out.  I've implemented all of that 
in my working copy, but there are a few additional bits needed to 
make the whole thing work properly.

List comprehensions need setup code and body code that's dependent on 
the Python version, as Python 2.3 uses the list-in-progress' 
.append() method, while 2.4 and up use a LIST_APPEND opcode.  So 
we'll also need a ListComp('tempname', body) nodetype to wrap the 
For() loops, and a LCAppend('tempname', value) nodetype to wrap the 
output values.

For generator expressions, there's a similar version-dependency 
hiccup: in Python 2.5 and up, the YIELD_VALUE opcode leaves a value 
on the stack: either None, or a value sent in by the generator's 
send() method.  So a POP_TOP has to be added in 2.5 and up, to get 
rid of this value.  So, a YieldStmt() node type that handles this 
needs to be added as well.

To create a list comprehension, one would simply use something like:

     ListComp('_[1]', For(..., ..., LCAppend('_[1]', ...)))

Of course, there might be nested For()'s, and there could be If()'s 
in there as well.

For a generator expression's function body, it's a bit simpler:

     For(..., ..., YieldStmt(...))

Our top-level queries will likely be done this way.  However, inline 
generator expressions need to create a nested function definition in 
code, which can be tricky because it may need to be a closure.  That 
is, if any part of the generator expression refers to local variables 
in the enclosing function, those variables need to be defined as cell 
or free variables in the enclosing function as well - which could 
invalidate already-generated code.

Python's compiler addresses this by pre-scanning code to figure out 
what variables are needed in nested scopes, and thus knows in advance 
whether to to use the FAST or DEREF version of an opcode.  PEAK-Rules 
and BytecodeAssembler, however, do not have this ability, which means 
that a dynamic mechanism for retroactively setting up nested scopes 
is required.

One way to do this would be for Code objects to track their local 
assignments (STORE_FAST targets), and have the ability to replace 
existing FAST opcodes with DEREF opcodes.  These pieces could then be 
assembled into a higher-level method like 
"innerCode.nest_in(outerCode)", which would take any undefined locals 
in "innerCode" and make them free variables there, then make sure 
they're cell or free variables in "outerCode".
That might be a bit tricky, in that whatever's generating the code 
has to already know whether something's a local or a global, but in 
PEAK-Rules and the query comprehension system we can statically know 
that.  (Because all locals bindings are via 'for' loops and argument 
definitions, all of which always happen before any possible use of 
those bindings -- at least, "before" in the sense of the sequence 
code is generated in.)

Thus, building a generator expression would amount to creating a 
fresh code object and compiling the For(..., ..., YieldStmt(...)) 
stuff there, then nesting the code block in the current code block 
and creating a code constant from it, building a function object from 
that, and then invoking the function object.

This probably means we'll want a Closure(name, body, defaults) node 
type, where body is the code to be placed in a new function, and 
defaults is an optional sequence of default values to bind to the new 
function object (and name is the new code object's co_name; 
"<genexpr>" in the case of a generator expression).  That would make 
a generator expression basically equal a Call() of the Closure() of a 
For() loop.

Really, Closure() might as well be called Function(), since it can 
know from its enclosing code flags whether closure is even possible, 
and it can know by the presence of free/cell vars on the resulting 
code constant, whether it actually needs to be a closure.  In other 
words, it will generate either a MAKE_FUNCTION or MAKE_CLOSURE, 
depending on the enclosing code flags and whether any cell/free vars 
are present.

All this is going to be a bit messy to test, particularly the part 
where we need to be able to rewrite FAST->DEREF.  However, it won't 
actually be that difficult to implement; probably I'll just make Code 
objects iterable, yielding a position, opcode, and argument.  The 
rewrite feature would then just patch the appropriate bytecodes at 
the specified positions.

Rather than a .nest_in() method, it might make more sense to give 
Code objects a .nested() method that creates a new Code object linked 
to the outer code object, and then have the .code() method do any 
FAST->DEREF fixups (and mark the outer code object's cell variables).

The place where this *doesn't* work, is if you have multiple nested 
generator expressions or other functions in the outer code object, 
each referring to different locals in the outer code, *and* there are 
free variables in the outer code.  In these cases, the outer code 
object will have to be rewritten in-place to relocate any referenced 
free variables, making room for the added cell variables.  So, code 
objects will need an .addcells(varnames) method, that can be called 
by their nested code objects' .code() methods to ensure that the 
named variables are either cell or free variables, and doing an 
in-place fixup of DEREF opcode offsets, as well as doing the FAST->DEREF fixup.

All this should be pretty straightforward to code, but may be awkward 
to test.  Nonetheless, at this point I've added these features to my 
plans for the BytecodeAssembler 0.4 release.