|
|
Changes since version 0.1: |
Changes since version 0.1: |
|
|
|
* Constant handling has been fixed so that it doesn't confuse equal values of |
|
differing types (e.g. ``1.0`` and ``True``), or equal unhashable objects |
|
(e.g. two empty lists). |
|
|
|
* Removed ``nil`, ``ast_curry()`` and ``folding_curry()``, replacing them with |
|
the ``nodetype()`` decorator and ``fold_args()``; please see the docs for |
|
more details. |
|
|
* Added stack tracking across jumps, globally verifying stack level prediction |
* Added stack tracking across jumps, globally verifying stack level prediction |
consistency and rejecting dead code. |
consistency and automatically rejecting attempts to generate dead code. It |
|
should now be virtually impossible to accidentally generate bytecode that can |
|
crash the interpreter. (If you find a way, let me know!) |
|
|
Changes since version 0.0.1: |
Changes since version 0.0.1: |
|
|
21 LOAD_CONST 0 (None) |
21 LOAD_CONST 0 (None) |
24 LOAD_CONST 8 (<code object <lambda> at ...>) |
24 LOAD_CONST 8 (<code object <lambda> at ...>) |
|
|
|
Note that although some values of different types may compare equal to each |
|
other, ``Code`` objects will not substitute a value of a different type than |
|
the one you requested:: |
|
|
|
>>> c = Code() |
|
>>> c(1, True, 1.0, 1L) # equal, but different types |
|
>>> dis(c.code()) |
|
0 0 LOAD_CONST 1 (1) |
|
3 LOAD_CONST 2 (True) |
|
6 LOAD_CONST 3 (1.0) |
|
9 LOAD_CONST 4 (1L) |
|
|
|
|
Simple Containers |
Simple Containers |
----------------- |
----------------- |
a constant, rather than generating code to recreate the tuple using a series of |
a constant, rather than generating code to recreate the tuple using a series of |
``LOAD_CONST`` operations followed by a ``BUILD_TUPLE``. |
``LOAD_CONST`` operations followed by a ``BUILD_TUPLE``. |
|
|
|
If the value wrapped in a ``Const`` is not hashable, it is compared by identity |
|
rather than value. This prevents equal mutable values from being reused by |
|
accident, e.g. if you plan to mutate the "constant" values later:: |
|
|
|
>>> c = Code() |
|
>>> c(Const([]), Const([])) # equal, but not the same object! |
|
>>> dis(c.code()) |
|
0 0 LOAD_CONST 1 ([]) |
|
3 LOAD_CONST 2 ([]) |
|
|
|
Thus, although ``Const`` objects hash and compare based on equality for |
|
hashable types:: |
|
|
|
>>> hash(Const(3)) == hash(3) |
|
True |
|
>>> Const(3)==Const(3) |
|
True |
|
|
|
They hash and compare based on object identity for non-hashable types:: |
|
|
|
>>> c = Const([]) |
|
>>> hash(c) == hash(id(c.value)) |
|
True |
|
>>> c == Const(c.value) # compares equal if same object |
|
True |
|
>>> c == Const([]) # but is not equal to a merely equal object |
|
False |
|
|
|
|
Local and Global Names |
Local and Global Names |
---------------------- |
---------------------- |
>>> const_value(Local('x')) |
>>> const_value(Local('x')) |
Traceback (most recent call last): |
Traceback (most recent call last): |
... |
... |
NotAConstant: <bound method str.Local of 'x'> |
NotAConstant: Local('x',) |
|
|
Tuples of constants are recursively replaced by constant tuples:: |
Tuples of constants are recursively replaced by constant tuples:: |
|
|
>>> const_value( (1,Global('y')) ) |
>>> const_value( (1,Global('y')) ) |
Traceback (most recent call last): |
Traceback (most recent call last): |
... |
... |
NotAConstant: <bound method str.Global of 'y'> |
NotAConstant: Global('y',) |
|
|
As do any types not previously described here:: |
As do any types not previously described here:: |
|
|
``Const`` node instead of a ``Call`` node:: |
``Const`` node instead of a ``Call`` node:: |
|
|
>>> Call( Const(type), [1] ) |
>>> Call( Const(type), [1] ) |
<bound method type.Const of <type 'int'>> |
Const(<type 'int'>) |
|
|
Thus, you can also take the ``const_value()`` of such calls:: |
Thus, you can also take the ``const_value()`` of such calls:: |
|
|
passed in to another ``Call``:: |
passed in to another ``Call``:: |
|
|
>>> Call(Const(type), [Call( Const(dict), [], [('x',27)] )]) |
>>> Call(Const(type), [Call( Const(dict), [], [('x',27)] )]) |
<bound method type.Const of <type 'dict'>> |
Const(<type 'dict'>) |
|
|
Notice that this folding takes place eagerly, during AST construction. If you |
Notice that this folding takes place eagerly, during AST construction. If you |
want to implement delayed folding after constant propagation or variable |
want to implement delayed folding after constant propagation or variable |
As you can see, the ``Code.DUP_TOP()`` is called on the code instance, causing |
As you can see, the ``Code.DUP_TOP()`` is called on the code instance, causing |
a ``DUP_TOP`` opcode to be output. This is sometimes a handy trick for |
a ``DUP_TOP`` opcode to be output. This is sometimes a handy trick for |
accessing values that are already on the stack. More commonly, however, you'll |
accessing values that are already on the stack. More commonly, however, you'll |
want to implement more sophisticated callables, perhaps something like:: |
want to implement more sophisticated callables. |
|
|
|
To make it easy to create diverse target types, a ``nodetype()`` decorator is |
|
provided:: |
|
|
|
>>> from peak.util.assembler import nodetype |
|
|
>>> from peak.util.assembler import ast_curry |
It allows you to create code generation target types using functions. Your |
|
function should take one or more arguments, with a ``code=None`` optional |
|
argument in the last position. It should check whether ``code is None`` when |
|
called, and if so, return a tuple of the preceding arguments. If ``code`` |
|
is not ``None``, then it should do whatever code generating tasks are required. |
|
For example:: |
|
|
>>> def TryFinally(block1, block2, code=None): |
>>> def TryFinally(block1, block2, code=None): |
... if code is None: |
... if code is None: |
... return ast_curry(TryFinally, block1, block2) |
... return block1, block2 |
... code( |
... code( |
... Code.SETUP_FINALLY, |
... Code.SETUP_FINALLY, |
... block1, |
... block1, |
... block2, |
... block2, |
... Code.END_FINALLY |
... Code.END_FINALLY |
... ) |
... ) |
|
>>> TryFinally = nodetype()(TryFinally) |
|
|
|
Note: although the nodetype() generator can be used above the function |
|
definition in either Python 2.3 or 2.4, it cannot be done in a doctest under |
|
Python 2.3, so this document doesn't attempt to demonstrate that. Under |
|
2.4, you would do something like this:: |
|
|
|
@nodetype() |
|
def TryFinally(...): |
|
|
|
and code that needs to also work under 2.3 should do something like this:: |
|
|
|
nodetype() |
|
def TryFinally(...): |
|
|
|
But to keep the examples here working with doctest, we'll be doing our |
|
``nodetype()`` calls after the end of the function definitions, e.g.:: |
|
|
>>> def ExprStmt(value, code=None): |
>>> def ExprStmt(value, code=None): |
... if code is None: |
... if code is None: |
... return ast_curry(ExprStmt, value) |
... return value, |
... code( value, Code.POP_TOP ) |
... code( value, Code.POP_TOP ) |
|
>>> ExprStmt = nodetype()(ExprStmt) |
|
|
>>> c = Code() |
>>> c = Code() |
>>> c( TryFinally(ExprStmt(1), ExprStmt(2)) ) |
>>> c( TryFinally(ExprStmt(1), ExprStmt(2)) ) |
14 POP_TOP |
14 POP_TOP |
15 END_FINALLY |
15 END_FINALLY |
|
|
|
The ``nodetype()`` decorator is virtually identical to the ``struct()`` |
|
decorator in the DecoratorTools package, except that it does not support |
|
``*args``, does not create a field for the ``code`` argument, and generates a |
|
``__call__()`` method that reinvokes the wrapped function to do the actual |
|
code generation. |
|
|
|
Among the benefits of this decorator are: |
|
|
|
* It gives your node types a great debugging format:: |
|
|
|
>>> tf = TryFinally(ExprStmt(1), ExprStmt(2)) |
|
>>> tf |
|
TryFinally(ExprStmt(1,), ExprStmt(2,)) |
|
|
The ``ast_curry()`` utility function returns an ``instancemethod`` chain that |
* It makes named fields accessible:: |
binds the given arguments to the given function, creating a hashable and |
|
comparable data structure -- a trivial sort of "AST node". Just follow the |
|
code pattern above, using a ``code=None`` final argument, and returning a |
|
curried version of the function if ``code is None``. Otherwise, your function |
|
should simply do whatever is needed to "generate" the arguments. |
|
|
|
(This is exactly the same pattern that ``peak.util.assembler`` uses internally |
|
to implement ``Const``, ``Call``, ``Local``, and other wrapper functions.) |
|
|
|
The ``ast_curry()`` utility function isn't quite perfect; due to a quirk of the |
|
``instancemethod`` type, it can't save arguments whose value is ``None``: if |
|
you pass a ``None`` argument to ``ast_curry()``, it will be replaced with a |
|
special ``nil`` object that tests as false, and generates a ``None`` constant |
|
when code is generated for it. If your function accepts any arguments that |
|
might have a value of ``None``, you must correctly handle the cases where you |
|
receive a value of ``nil`` (found in ``peak.util.assembler``) instead of |
|
``None``. |
|
|
|
However, if you can use ``ast_curry()`` to generate your AST nodes, you will |
|
have objects that are hashable and comparable by default, as long as none of |
|
your child nodes are unhashable or incomparable. This can be useful for |
|
algorithms that require comparing AST subtrees, such as common subexpression |
|
elimination. |
|
|
|
|
>>> tf.block1 |
|
ExprStmt(1,) |
|
|
|
>>> tf.block2 |
|
ExprStmt(2,) |
|
|
|
* Hashing and comparison work as expected (handy for algorithms that require |
|
comparing or caching AST subtrees, such as common subexpression elimination):: |
|
|
|
>>> ExprStmt(1) == ExprStmt(1) |
|
True |
|
>>> ExprStmt(1) == ExprStmt(2) |
|
False |
|
|
|
|
|
Please see the `struct decorator documentation`_ for info on how to customize |
|
node types further. |
|
|
|
.. _struct decorator documentation: http://peak.telecommunity.com/DevCenter/DecoratorTools#the-struct-decorator |
|
|
|
Note: hashing only works if all the values you return in your argument tuple |
|
are hashable, so you should try to convert them if possible. For example, if |
|
an argument accepts any sequence, you should probably convert it to a tuple |
|
before returning it. Most of the examples in this document, and the node types |
|
supplied by ``peak.util.assembler`` itself do this. |
|
|
|
|
Constant Folding in Custom Targets |
Constant Folding in Custom Targets |
|
|
>>> def And(values, code=None): |
>>> def And(values, code=None): |
... if code is None: |
... if code is None: |
... return ast_curry(And, tuple(values)) |
... return tuple(values), |
... end = Label() |
... end = Label() |
... for value in values[:-1]: |
... for value in values[:-1]: |
... try: |
... try: |
... else: # and false constants end the chain right away |
... else: # and false constants end the chain right away |
... return code(value, end) |
... return code(value, end) |
... code(values[-1], end) |
... code(values[-1], end) |
|
>>> And = nodetype()(And) |
|
|
>>> c = Code() |
>>> c = Code() |
>>> c.return_( And([1, 2]) ) |
>>> c.return_( And([1, 2]) ) |
|
|
The above example only folds constants at code generation time, however. You |
The above example only folds constants at code generation time, however. You |
can also do constant folding at AST construction time, using the |
can also do constant folding at AST construction time, using the |
``folding_curry()`` function. For example:: |
``fold_args()`` function. For example:: |
|
|
>>> from peak.util.assembler import folding_curry |
>>> from peak.util.assembler import fold_args |
|
|
>>> def Getattr(ob, name, code=None): |
>>> def Getattr(ob, name, code=None): |
... try: |
... try: |
... except NotAConstant: |
... except NotAConstant: |
... return Call(Const(getattr), [ob, name]) |
... return Call(Const(getattr), [ob, name]) |
... if code is None: |
... if code is None: |
... return folding_curry(Getattr, ob, name) |
... return fold_args(Getattr, ob, name) |
... code(ob) |
... code(ob) |
... code.LOAD_ATTR(name) |
... code.LOAD_ATTR(name) |
|
>>> Getattr = nodetype()(Getattr) |
|
|
>>> const_value(Getattr(1, '__class__')) |
>>> const_value(Getattr(1, '__class__')) |
<type 'int'> |
<type 'int'> |
|
|
The ``folding_curry()`` function is essentially the same as ``ast_curry()``, |
The ``fold_args()`` function tries to evaluate the node immediately, if all of |
unless all of the arguments it's given are recognized as constants. In that |
its arguments are constants, by creating a temporary ``Code`` object, and |
case, ``folding_curry()`` will create a temporary ``Code`` object, and run the |
running the supplied function against it, then doing an ``eval()`` on the |
curried function against it, doing an ``eval()`` on the generated code and |
generated code and wrapping the result in a ``Const``. However, if any of the |
wrapping the result in a ``Const``. |
arguments are non-constant, the original arguments (less the function) are |
|
returned. This causes a normal node instance to be created instead of a |
|
``Const``. |
|
|
This isn't a very *fast* way of doing partial evaluation, but it makes it |
This isn't a very *fast* way of doing partial evaluation, but it makes it |
really easy to define new code generation targets without writing custom |
really easy to define new code generation targets without writing custom |
constant-folding code for each one. Just use ``folding_curry()`` instead of |
constant-folding code for each one. Just ``return fold_args(ThisType, *args)`` |
``ast_curry()`` if you want your node constructor to be able to do eager |
instead of ``return args``, if you want your node constructor to be able to do |
evaluation. If you need to, you can check your parameters in order to decide |
eager evaluation. If you need to, you can check your parameters in order to |
whether to call ``ast_curry()`` or ``folding_curry()``; this is in fact how |
decide whether to call ``fold_args()`` or not; this is in fact how ``Call`` |
``Call`` implements its ``fold`` argument and the suppression of folding when |
implements its ``fold`` argument and the suppression of folding when |
the call has no arguments. |
the call has no arguments. |
|
|
|
|
|
|
>>> def If(cond, then, else_=Pass, code=None): |
>>> def If(cond, then, else_=Pass, code=None): |
... if code is None: |
... if code is None: |
... return ast_curry(If,cond,then,else_) |
... return cond, then, else_ |
... else_clause = Label() |
... else_clause = Label() |
... end_if = Label() |
... end_if = Label() |
... code(cond, else_clause.JUMP_IF_FALSE, Code.POP_TOP, then) |
... code(cond, else_clause.JUMP_IF_FALSE, Code.POP_TOP, then) |
... code(end_if.JUMP_FORWARD, else_clause, Code.POP_TOP, else_) |
... code(end_if.JUMP_FORWARD, else_clause, Code.POP_TOP, else_) |
... code(end_if) |
... code(end_if) |
|
>>> If = nodetype()(If) |
|
|
It works okay if there's no dead code:: |
It works okay if there's no dead code:: |
|
|
|
|
>>> def If(cond, then, else_=Pass, code=None): |
>>> def If(cond, then, else_=Pass, code=None): |
... if code is None: |
... if code is None: |
... return ast_curry(If,cond,then,else_) |
... return cond, then, else_ |
... else_clause = Label() |
... else_clause = Label() |
... end_if = Label() |
... end_if = Label() |
... code(cond, else_clause.JUMP_IF_FALSE, Code.POP_TOP, then) |
... code(cond, else_clause.JUMP_IF_FALSE, Code.POP_TOP, then) |
... if code.stack_size is not None: |
... if code.stack_size is not None: |
... end_if.JUMP_FORWARD(code) |
... end_if.JUMP_FORWARD(code) |
... code(else_clause, Code.POP_TOP, else_, end_if) |
... code(else_clause, Code.POP_TOP, else_, end_if) |
|
>>> If = nodetype()(If) |
|
|
As you can see, the dead code is now eliminated:: |
As you can see, the dead code is now eliminated:: |
|
|
3 RETURN_VALUE |
3 RETURN_VALUE |
|
|
|
|
|
|
Demo: "Computed Goto"/"Switch Statement" |
Demo: "Computed Goto"/"Switch Statement" |
======================================== |
======================================== |
|
|
|
|
>>> def Switch(expr, cases, default=Pass, code=None): |
>>> def Switch(expr, cases, default=Pass, code=None): |
... if code is None: |
... if code is None: |
... return ast_curry(Switch, expr, tuple(cases), default) |
... return expr, tuple(cases), default |
... |
... |
... d = {} |
... d = {} |
... else_block = Label() |
... else_block = Label() |
... Code.POP_BLOCK, |
... Code.POP_BLOCK, |
... end_switch |
... end_switch |
... ) |
... ) |
|
>>> Switch = nodetype()(Switch) |
|
|
>>> c = Code() |
>>> c = Code() |
>>> c.co_argcount=1 |
>>> c.co_argcount=1 |