Is there a way to refer to the current function in python?

Question

I want a function to refer to itself. e.g. to be recursive.

So I do something like that:

def fib(n):
    return n if n <= 1 else fib(n-1)+fib(n-2)

This is fine most of the time, but fib does not, actually, refer to itself; it refers to the the binding of fib in the enclosing block. So if for some reason fib is reassigned, it will break:

>>> foo = fib
>>> fib = foo(10)
>>> x = foo(8)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 2, in fib
TypeError: 'int' object is not callable

How can I prevent this from happening (from inside fib), if at all possible? As far as I know, the name of fib does not exist before the function-definition is fully executed; Are there any workarounds?

I don't have a real use case where it may actually happen; I am asking out of sheer curiosity.

Answer 1

I'd make a decorator for this

from functools import wraps

def selfcaller(func):
    @wraps(func)
    def wrapper(*args, **kwargs):
        return func(wrapper, *args, **kwargs)
    return wrapper

And use it like

@selfcaller
def fib(self, n):
    return n if n <= 1 else self(n-1)+self(n-2)

---

This is actually a readable way to define a Fixed Point Combinator (or Y Combinator):

fix = lambda g: (lambda f: g(lambda arg: f(f)(arg))) (lambda f: g(lambda arg: f(f)(arg)))

usage:

fib = fix(lambda self: lambda n: n if n <= 1 else self(n-1)+self(n-2))

or:

@fix
def fib(self):
    return lambda n: n if n <= 1 else self(n-1)+self(n-2)

The binding here happens in the formal parameter, so the problem does not arise.

Answer 2

There's no way to do what you're trying to do. You're right that fib does not exist before the function definition is executed (or, worse, it exists but refers to something completely different…), which means there is no workaround from inside fib that can possibly work.*

However, if you're willing to drop that requirement, there are workarounds that do work. For example:

def _fibmaker():
    def fib(n):
        return n if n <= 1 else fib(n-1)+fib(n-2)
    return fib
fib = _fibmaker()
del _fibmaker

Now fib is referring to the binding in the closure from the local environment of a call to _fibmaker. Of course even that can be replaced if you really want to, but it's not easy (the fib.__closure__ attribute is not writable; it's a tuple, so you can't replace any of its cells; each cell's cell_contents is a readonly attribute, …), and there's no way you're going to do it by accident.

There are other ways to do this (e.g., use a special placeholder inside fib, and a decorator that replaces the placeholder with the decorated function), and they're all about equally unobvious and ugly, which may seem to violate TOOWTDI. But in this case, the "it" is something you probably don't want to do, so it doesn't really matter.

---

Here's one way you can write a general, pure-python decorator for a function that uses self instead of its own name, without needing an extra self parameter to the function:

def selfcaller(func):
    env = {}
    newfunc = types.FunctionType(func.__code__, globals=env)
    env['self'] = newfunc
    return newfunc

@selfcaller
def fib(n):
    return n if n <= 1 else self(n-1)+self(n-2)

Of course this won't work on a function that has any free variables that are bound from globals, but you can fix that with a bit of introspection. And, while we're at it, we can also remove the need to use self inside the function's definition:

def selfcaller(func):
    env = dict(func.__globals__)
    newfunc = types.FunctionType(func.__code__, globals=env)
    env[func.__code__.co_name] = newfunc
    return newfunc

This is Python 3.x-specific; some of the attribute names are different in 2.x, but otherwise it's the same.

This still isn't 100% fully general. For example, if you want to be able to use it on methods so they can still call themselves even if the class or object redefines their name, you need slightly different tricks. And there are some pathological cases that might require building a new CodeType out of func.__code__.co_code. But the basic idea is the same.

---

* As far as Python is concerned, until the name is bound, it doesn't exist… but obviously, under the covers, the interpreter has to know the name of the function you're defining. And at least some interpreters offer non-portable ways to get at that information.

For example, in CPython 3.x, you can very easily get the name of the function currently being defined—it's just sys._getframe().f_code.co_name.

Of course this won't directly do you any good, because nothing (or the wrong thing) is bound to that name. But notice that f_code in there. That's the current frame's code object. Of course you can't call a code object directly, but you can do so indirectly, either by generating a new function out of it, or by using bytecodehacks.

For example:

def fib2(n):
    f = sys._getframe()
    fib2 = types.FunctionType(f.f_code, globals=globals())
    return n if n<=1 else fib2(n-1)+fib2(n-2)

Again, this won't handle every pathological case… but the only way I can think of to do so is to actually keep a circular reference to the frame, or at least its globals (e.g., by passing globals=f.f_globals), which seems like a very bad idea.

See Frame Hacks for more clever things you can do.

---

Finally, if you're willing to step out of Python entirely, you can create an import hook that preprocesses or compiles your code from a Python custom-extended with, say, defrec into pure Python and/or bytecode.

And if you're thinking "But that sounds like it would be a lot nicer as a macro than as a preprocessor hack, if only Python had macros"… then you'll probably prefer to use a preprocessor hack that gives Python macros, like MacroPy, and then write your extensions as macros.

Answer 3

Like abamert said "..there is no way around the problem from inside ..".

Here's my approach:

def fib(n):
    def fib(n):
        return n if n <= 1 else fib(n-1)+fib(n-2)
    return fib(n)

Answer 4

Someone asked me for a macro based solution for this, so here it is:

# macropy/my_macro.py
from macropy.core.macros import *

macros = Macros()

@macros.decorator()
def recursive(tree, **kw):
    tree.decorator_list = []

    wrapper = FunctionDef(
        name=tree.name,
        args=tree.args,
        body=[],
        decorator_list=tree.decorator_list
    )

    return_call = Return(
        Call(
            func = Name(id=tree.name),
            args = tree.args.args,
            keywords = [],
            starargs = tree.args.vararg,
            kwargs = tree.args.kwarg
        )
    )

    return_call = parse_stmt(unparse_ast(return_call))[0]

    wrapper.body = [tree, return_call]

    return wrapper

This can be used as follows:

>>> import macropy.core.console
0=[]=====> MacroPy Enabled <=====[]=0
>>> from macropy.my_macro import macros, recursive
>>> @recursive
... def fib(n):
...     return n if n <= 1 else fib(n-1)+fib(n-2)
...
>>> foo = fib
>>> fib = foo(10)
>>> x = foo(8)
>>> x
21

It basically does exactly the wrapping that hus787 gave:

• Create a new statement which does return fib(...), which uses the argument list of the original function as the ...
• Create a new def, with the same name, same args, same decorator_list as the old one
• Place the old function, together followed by the return statement, in the body of the new functiondef
• Strip the original function of its decorators (I assume you'd want to decorate the wrapper instead)

The parse_stmt(unparse_ast(return_call))[0] rubbish is a quick hack to get stuff to work (you actually can't just copy the argument AST from the param list of the function and use them in a Call AST) but that's just detail.

To show that it's actually doing that, you can add a print unparse_ast statement to see what the transformed function looks like:

@macros.decorator()
def recursive(tree, **kw):
    ...
    print unparse_ast(wrapper)
    return wrapper

which, when run as above, prints

def fib(n):

    def fib(n):
        return (n if (n <= 1) else (fib((n - 1)) + fib((n - 2))))
    return fib(n)

Looks like exactly what you want! It should work for any function, with multiple args, kwargs, defaults, etc., but I'm too lazy to test. Working with the AST is a bit verbose, and MacroPy is still super-experimental, but i think it's pretty neat.