recursive decorator

Discussion in 'Python' started by Ethan Furman, Sep 2, 2009.

  1. Ethan Furman

    Ethan Furman Guest

    Greetings, List!

    The recent thread about a recursive function in a class definition led
    me back to a post about bindfunc from Arnaud, and from there I found
    Michele Simionato's decorator module (many thanks! :), and from there I
    began to wonder...

    from decorator import decorator

    @decorator
    def recursive1(func, *args, **kwargs):
    return func(func, *args, **kwargs)

    @recursive1
    def factorial1(recurse, n):
    if n < 2:
    return 1
    return n * recurse(n-1)

    factorial(4)
    TypeError: factorial1() takes exactly 2 arguments (1 given)

    Now it's *entirely* possible that I am missing something easy here, but
    at any rate I was thinking about the above error, about how one of the
    design goals behind the decorator module was to enable introspection to
    give accurate information about usage, etc, and how if the signature was
    *exactly* preserved then we have this pesky and seemingly out of place
    variable, not mention we can't 'just use it' in the code.

    So I set out to create a signature-modifying decorator that would lose
    that first parameter from the wrapper, while keeping the rest of the
    signature intact. This is what I was able to come up with:

    def recursive(func):
    """
    recursive is a signature modifying decorator.
    Specifially, it removes the first argument, so
    that calls to the decorated function act as
    if it does not exist.
    """
    argspec = inspect.getargspec(func)
    first_arg = argspec[0][0]
    newargspec = (argspec[0][1:], ) + argspec[1:]
    fi = decorator.FunctionMaker(func)
    old_sig = inspect.formatargspec( \
    formatvalue=lambda val: "", *argspec)[1:-1]
    new_sig = inspect.formatargspec( \
    formatvalue=lambda val: "", *newargspec)[1:-1]
    new_def = '%s(%s)' % (fi.name, new_sig)
    body = 'return func(%s)' % old_sig
    def wrapper(*newargspec):
    return func(wrapper, *newargspec)
    evaldict = {'func':func, first_arg:wrapper}
    return fi.create(new_def, body, evaldict, \
    doc=fi.doc, module=fi.module)


    I cannot remember whose sig it is at the moment (maybe Aahz'?), but it
    says something about debugging being twice as hard as coding, so if you
    code as cleverly as you can you are, by definition, not smart enough to
    debug it! And considering the amount of trial-and-error that went into
    this (along with some thought and reasoning about scopes !-), I am
    hoping to get some code review.

    And if there's an easier way to do this, I wouldn't mind knowing about
    that, too!

    Many thanks.

    ~Ethan~
    Ethan Furman, Sep 2, 2009
    #1
    1. Advertising

  2. On Sep 3, 12:19 am, Ethan Furman <> wrote:
    > Greetings, List!
    >
    > The recent thread about a recursive function in a class definition led
    > me back to a post about bindfunc from Arnaud, and from there I found
    > Michele Simionato's decorator module (many thanks! :), and from there I
    > began to wonder...
    >
    > from decorator import decorator
    >
    > @decorator
    > def recursive1(func, *args, **kwargs):
    >      return func(func, *args, **kwargs)
    >
    > @recursive1
    > def factorial1(recurse, n):
    >      if n < 2:
    >          return 1
    >      return n * recurse(n-1)
    >
    > factorial(4)
    > TypeError: factorial1() takes exactly 2 arguments (1 given)


    What are you trying to do here? I miss why you don't use the usual
    definition of factorial.
    If you have a real life use case which is giving you trouble please
    share. I do not see
    why you want to pass a function to itself (?)

    M. Simionato
    Michele Simionato, Sep 3, 2009
    #2
    1. Advertising

  3. Ethan Furman

    Ethan Furman Guest

    Michele Simionato wrote:
    > On Sep 3, 12:19 am, Ethan Furman <> wrote:
    >
    >>Greetings, List!
    >>
    >>The recent thread about a recursive function in a class definition led
    >>me back to a post about bindfunc from Arnaud, and from there I found
    >>Michele Simionato's decorator module (many thanks! :), and from there I
    >>began to wonder...
    >>
    >>from decorator import decorator
    >>
    >>@decorator
    >>def recursive1(func, *args, **kwargs):
    >> return func(func, *args, **kwargs)
    >>
    >>@recursive1
    >>def factorial1(recurse, n):
    >> if n < 2:
    >> return 1
    >> return n * recurse(n-1)
    >>
    >>factorial(4)
    >>TypeError: factorial1() takes exactly 2 arguments (1 given)

    >
    >
    > What are you trying to do here? I miss why you don't use the usual
    > definition of factorial.
    > If you have a real life use case which is giving you trouble please
    > share. I do not see
    > why you want to pass a function to itself (?)
    >
    > M. Simionato


    Factorial is an example only.

    The original thread by Bearophile:
    http://mail.python.org/pipermail/python-list/2009-May/711848.html

    A similar thread from kj (where scopes is the actual problem):
    http://mail.python.org/pipermail/python-list/2009-August/725174.html

    Basic summary: the recursive decorator (the one you snipped, not the
    one showing above), is a replacement for the bindfunc decorator, and
    preserves the signature of the decorated function, minus the
    self-referring first parameter. It solves kj's problem (although there
    are arguably better ways to do so), and I think helps with Bearophiles
    as well. As a bonus, the tracebacks are more accurate if the function
    is called incorrectly. Consider:

    In [1]: def recursive(func):
    ...: def wrapper(*args, **kwargs):
    ...: return func(wrapper, *args, **kwargs)
    ...: return wrapper
    ...:

    In [2]: @recursive
    ...: def factorial(recurse, n):
    ...: if n < 2:
    ...: return 1
    ...: else:
    ...: return n * recurse(n-1)
    ...:

    In [3]: factorial(1, 2) # in incorrect call
    --------------------------------------------------------------------
    TypeError Traceback (most recent call last)

    C:\pythonlib\<ipython console> in <module>()

    C:\pythonlib\<ipython console> in wrapper(*args, **kwargs)

    TypeError: factorial() takes exactly 2 arguments (3 given)
    ^^^^^^^^^^^^^^^^^^^^^
    mildly confusing /

    ----------------------------------------
    versus the error with the new decorator:
    ----------------------------------------

    In [2]: factorial(4, 5) # another incorrect call
    --------------------------------------------------------------------
    TypeError Traceback (most recent call last)

    C:\pythonlib\<ipython console> in <module>()

    TypeError: factorial() takes exactly 1 argument (2 given)
    ^^^^^^^^^^^^^^^^^^^^

    This latter error matches how factorial actually should be called, both
    in normal code using it, and in the function itself, calling itself.

    So that's the why and wherefore. Any comments on the new decorator
    itself? Here it is again:

    def recursive(func):
    """
    recursive is a signature modifying decorator.
    Specifially, it removes the first argument, so
    that calls to the decorated function act as if
    it does not exist.
    """
    argspec = inspect.getargspec(func)
    first_arg = argspec[0][0]
    newargspec = (argspec[0][1:], ) + argspec[1:]
    fi = decorator.FunctionMaker(func)
    old_sig = inspect.formatargspec( \
    formatvalue=lambda val: "", *argspec)[1:-1]
    new_sig = inspect.formatargspec( \
    formatvalue=lambda val: "", *newargspec)[1:-1]
    new_def = '%s(%s)' % (fi.name, new_sig)
    body = 'return func(%s)' % old_sig
    def wrapper(*newargspec):
    return func(wrapper, *newargspec)
    evaldict = {'func':func, first_arg:wrapper}
    return fi.create(new_def, body, evaldict, \
    doc=fi.doc, module=fi.module)

    ~Ethan~
    Ethan Furman, Sep 3, 2009
    #3
  4. On Sep 3, 6:41 pm, Ethan Furman <> wrote:
    >
    > The original thread by Bearophile:
    >    http://mail.python.org/pipermail/python-list/2009-May/711848.html


    I have read the thread. What Bearophile wants can be implemented with
    a bytecode hack, no
    need for the decorator module. Let me call 'recur' the self-function,
    like in Clojure.
    You can define a decorator that makes "self-conscious" a recursive
    function as follows:

    # requires byteplay by Noam Raphael
    # see http://byteplay.googlecode.com/svn/trunk/byteplay.py
    from byteplay import Code, LOAD_GLOBAL, STORE_FAST, LOAD_FAST

    def enable_recur(f):
    print f.func_code.co_names
    if 'recur' not in f.func_code.co_names:
    return f # do nothing on non-recursive functions
    c = Code.from_code(f.func_code)
    c.code[1:1] = [(LOAD_GLOBAL, f.__name__), (STORE_FAST, 'recur')]
    for i, (opcode, value) in enumerate(c.code[2:]):
    if opcode == LOAD_GLOBAL and value == 'recur':
    c.code[i+2] = (LOAD_FAST, 'recur')
    f.func_code = c.to_code()
    return f

    ## example of use

    @enable_recur
    def f(x):
    if x == 1:
    return 1
    else:
    return x*recur(x-1)

    print f(4) # =>24


    Please accept this without explanation since it would take me a lot of
    time
    to explain how it works. Just accept that bytecode hacks are
    incredible
    (and nonportable too) ;-)

    Michele Simionato
    Michele Simionato, Sep 4, 2009
    #4
  5. Ethan Furman

    Ethan Furman Guest

    Michele Simionato wrote:
    > On Sep 3, 6:41 pm, Ethan Furman <> wrote:
    >
    >>The original thread by Bearophile:
    >> http://mail.python.org/pipermail/python-list/2009-May/711848.html

    >
    >
    > I have read the thread. What Bearophile wants can be implemented with
    > a bytecode hack, no
    > need for the decorator module. Let me call 'recur' the self-function,
    > like in Clojure.
    > You can define a decorator that makes "self-conscious" a recursive
    > function as follows:
    >
    > # requires byteplay by Noam Raphael
    > # see http://byteplay.googlecode.com/svn/trunk/byteplay.py
    > from byteplay import Code, LOAD_GLOBAL, STORE_FAST, LOAD_FAST
    >
    > def enable_recur(f):
    > print f.func_code.co_names
    > if 'recur' not in f.func_code.co_names:
    > return f # do nothing on non-recursive functions
    > c = Code.from_code(f.func_code)
    > c.code[1:1] = [(LOAD_GLOBAL, f.__name__), (STORE_FAST, 'recur')]
    > for i, (opcode, value) in enumerate(c.code[2:]):
    > if opcode == LOAD_GLOBAL and value == 'recur':
    > c.code[i+2] = (LOAD_FAST, 'recur')
    > f.func_code = c.to_code()
    > return f
    >
    > ## example of use
    >
    > @enable_recur
    > def f(x):
    > if x == 1:
    > return 1
    > else:
    > return x*recur(x-1)
    >
    > print f(4) # =>24
    >
    >
    > Please accept this without explanation since it would take me a lot of
    > time
    > to explain how it works. Just accept that bytecode hacks are
    > incredible
    > (and nonportable too) ;-)
    >
    > Michele Simionato


    No worries -- not sure I would understand the explanation at this point,
    anyway!

    Just to verify, using the decorator module is portable, yes?

    ~Ethan~
    Ethan Furman, Sep 4, 2009
    #5
  6. On Sep 4, 7:03 pm, Ethan Furman <> wrote:

    > Just to verify, using the decorator module is portable, yes?


    Yes, it is portable. BTW, here is what you want to do (requires
    decorator-3.1.2):

    from decorator import FunctionMaker

    def bindfunc(f):
    name = f.__name__
    signature = ', '.join(FunctionMaker(f).args[1:]) # skip first arg
    return FunctionMaker.create(
    '%s(%s)' % (name, signature),
    'return _func_(%s, %s)' % (name, signature),
    dict(_func_=f), defaults=f.func_defaults,
    doc=f.__doc__, module=f.__module__)

    @bindfunc
    def fac(self, n):
    return 1 if n <= 1 else n * self(n - 1)

    print fac(5)
    help(fac)
    Michele Simionato, Sep 5, 2009
    #6
  7. Ethan Furman

    sturlamolden Guest

    On 4 Sep, 14:50, Michele Simionato <>
    wrote:

    > # requires byteplay by Noam Raphael
    > # seehttp://byteplay.googlecode.com/svn/trunk/byteplay.py
    > from byteplay import Code, LOAD_GLOBAL, STORE_FAST, LOAD_FAST


    Incrediby cool :)
    sturlamolden, Sep 5, 2009
    #7

  8. > def enable_recur(f):
    >     print f.func_code.co_names
    >     if 'recur' not in f.func_code.co_names:
    >         return f # do nothing on non-recursive functions
    >     c = Code.from_code(f.func_code)
    >     c.code[1:1] = [(LOAD_GLOBAL, f.__name__), (STORE_FAST, 'recur')]
    >     for i, (opcode, value) in enumerate(c.code[2:]):
    >         if opcode == LOAD_GLOBAL and value == 'recur':
    >             c.code[i+2] = (LOAD_FAST, 'recur')
    >     f.func_code = c.to_code()
    >     return f
    >

    There is a useless line 'print f.func_code.co_names' here, a left over
    of my tests, sorry.
    Michele Simionato, Sep 5, 2009
    #8
  9. Ethan Furman

    Ethan Furman Guest

    Michele Simionato wrote:
    [snip]
    > Yes, it is portable. BTW, here is what you want to do (requires
    > decorator-3.1.2):
    >
    > from decorator import FunctionMaker
    >
    > def bindfunc(f):
    > name = f.__name__
    > signature = ', '.join(FunctionMaker(f).args[1:]) # skip first arg
    > return FunctionMaker.create(
    > '%s(%s)' % (name, signature),
    > 'return _func_(%s, %s)' % (name, signature),
    > dict(_func_=f), defaults=f.func_defaults,
    > doc=f.__doc__, module=f.__module__)


    I figured there must be an easy way using your module. Here is what I
    came up with *not* using the module -- this whole thing was definitely a
    mind-stretching exercise. Many thanks for your decorator routines -- no
    way could I have gotten this far without them to guide me!

    def bind_func(func):
    name = func.__name__
    argspec = inspect.getargspec(func)
    self = argspec[0][0]
    newargspec = (argspec[0][1:], ) + argspec[1:]
    signature = inspect.formatargspec( \
    formatvalue=lambda val: "", *newargspec)[1:-1]
    new_func = 'def _wrapper_(%(signature)s):\n' \
    ' return %(self)s(_wrapper_, %(signature)s)' % \
    {'signature':signature, 'self':'old_func'}
    evaldict = {'old_func':func}
    exec new_func in evaldict
    wrapped = evaldict['_wrapper_']
    wrapped.__name__ = name
    wrapped.__doc__ = func.__doc__
    wrapped.__module__ = func.__module__
    wrapped.__dict__ = func.__dict__
    wrapped.func_defaults = func.func_defaults
    return wrapped

    ~Ethan~
    Ethan Furman, Sep 9, 2009
    #9
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Jean Lutrin
    Replies:
    8
    Views:
    634
    Chris Uppal
    Nov 18, 2004
  2. Jeffrey Froman

    Decorator Syntax For Recursive Properties

    Jeffrey Froman, Apr 17, 2005, in forum: Python
    Replies:
    2
    Views:
    308
    Jeffrey Froman
    Apr 17, 2005
  3. glomde
    Replies:
    5
    Views:
    515
    glomde
    Mar 29, 2007
  4. n00m
    Replies:
    12
    Views:
    1,104
  5. vamsi
    Replies:
    21
    Views:
    2,052
    Keith Thompson
    Mar 9, 2009
Loading...

Share This Page