[PEAK] Compiling lvalues, iterators, and comprehensions
Phillip J. Eby
pje at telecommunity.com
Tue Jul 29 13:02:19 EDT 2008
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.
More information about the PEAK
mailing list