Saturday, November 6, 2010

Recursive Lambda Functions

This one I had presented at my talk at FISL in 2010: One interestign feature in some functional languages - not all - that is seemingly unavaliable from Python is the ability of anonimous functions to call themselves, using recursion.

You can do that in Python if you assign a name to an anonymous function -- but DUH -- it won't be anomous anymore.

So, it is possible to do:

fact = lambda n: n * fact(n - 1) if n > 1 else 1
fact(5)


But not without depending on the name "fact", external to the function. The porblem to call an anonymous function is to get a reference to itself. Well...for the called code, there is a way to get a reference, not to the calling function, but to the calling code object. The code object is an attribute (f_code) to execution frames in Python. And while one can't execute code_objects directly, given a code object, it is possible to build a function around it -- and this function will work the same as the calling function, and can be called.

To create a function, one just have to call the DFunctionType -- I import it from types, but it one could as well just do "FunctionType = type(lambda: None)" - (It is how it is defined inside the types.py file in the stdlib anyway). The documentation on FuntionType should be enough for anyone: it accepts a code_object and a globals dictionay as mandatory parameters.

So, here we are, for the Python recursive Lambda:

from inspect import currentframe
from types import FunctionType

lambda_cache = {}

def myself (*args, **kw):
    caller_frame = currentframe(1)
    code = caller_frame.f_code
    if not code in lambda_cache:
        lambda_cache[code] = FunctionType(code, caller_frame.f_globals)
    return lambda_cache[code](*args, **kw)

if __name__ == "__main__":
    print "Factorial of 5", (lambda n: n * myself(n - 1) if n > 1 else 1)(5)


(just note that it won't preserve default parameters for the lambda function - I found no way of getting a reference to those)

3 comments:

  1. this is one of the best python articles I have ever read!! thanks for settinging an argument with a co-worker about if python can do anonymous recursion :)

    ReplyDelete
  2. Its result:
    NameError: global name 'fact' is not defined

    ReplyDelete
    Replies
    1. The first example is not actually designed to work - the second example does recursion using the "myself" call.

      Delete