[Subversion] / BytecodeAssembler / README.txt  

Diff of /BytecodeAssembler/README.txt

Parent Directory | Revision Log

version 2205, Tue Jul 4 22:21:25 2006 UTC version 2208, Wed Jul 5 02:56:05 2006 UTC
Line 16 
Line 16 
   
 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:
   
Line 291 
Line 301 
                  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
 -----------------  -----------------
Line 335 
Line 357 
 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
 ----------------------  ----------------------
Line 535 
Line 585 
     >>> 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::
   
Line 550 
Line 600 
     >>> 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::
   
Line 576 
Line 626 
 ``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::
   
Line 587 
Line 637 
 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
Line 646 
Line 696 
 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,
Line 660 
Line 720 
     ...             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)) )
Line 678 
Line 756 
                  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
Line 719 
Line 812 
   
     >>> 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:
Line 730 
Line 823 
     ...         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]) )
Line 754 
Line 848 
   
 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:
Line 764 
Line 858 
     ...     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.
   
   
Line 1033 
Line 1130 
   
     >>> 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::
   
Line 1065 
Line 1163 
   
     >>> 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::
   
Line 1742 
Line 1841 
                   3 RETURN_VALUE                    3 RETURN_VALUE
   
   
   
 Demo: "Computed Goto"/"Switch Statement"  Demo: "Computed Goto"/"Switch Statement"
 ========================================  ========================================
   
Line 1760 
Line 1858 
   
     >>> 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()
Line 1789 
Line 1887 
     ...             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


Generate output suitable for use with a patch program
Legend:
Removed from v.2205  
changed lines
  Added in v.2208

cvs-admin@eby-sarna.com

Powered by ViewCVS 1.0-dev

ViewCVS and CVS Help