recursive decorator

[Ethan Furman]

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~

 

[Michele Simionato]

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

 

[Ethan Furman]

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~

 

[Michele Simionato]

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

 

[Ethan Furman]

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~

 

[Michele Simionato]

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)

 

[sturlamolden]

# 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

 

[Michele Simionato]

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.

 

[Ethan Furman]

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~