Self Reference in Python

The J language has a verb called “Self Reference” which is $: allowing a recursive call to the “longest verb that contains it” (see J dictionary).

Here is a way for implementing a similar feature in Python. I made it work on several versions of Python (versions 2 and 3 with CPython as well as with Pypy).

import sys
class _self_reference():
    def __call__(self, *args):
        f = lambda *a: None
        f.__code__ = sys._getframe(1).f_code
        return f(*args)
    def __getitem__(self,n):
        def func(*args):
            f = lambda *a: None
            f.__code__ = sys._getframe(n+1).f_code
            return f(*args)
        return func
self = _self_reference()

Of course the self variable can be renamed like this or even simply _.

The self function now calls the function called previously with new arguments. Now, the factorial function is:

fac = lambda n: 1 if n <= 1 else n*self(n-1)

Of course, some care has to be taken concerning the numbers of call levels that a single function may add to the execution stack. If needed, the syntax self[1](...) may be used to get to refer to the the function called one more level below, and of course any positive integer will work.

The following example is rather useless but it shows how to jump to the second level by complicating the previous definition of the factorial:

fac2 = lambda n: 1 if n <= 1 else n*((lambda k: self[1](k-1))(n))

Continuation passing style in Python

Here are some thoughts concerning the continuation passing style in Python. Of course, being able to take any function as an argument for another function, the language already allows to use such a style of programming when needed; but this artcle focus on some elegant ways of calling a function from the innermost part of an expression without burdening the call stack of the interpreter. Like in a previous article, tail-call optimization is the purpose of this study.

First part: the main idea

First, let’s create a function diplaying together its argument and the current size of the stack; it will be used below in order to check where exactly a call to a continuation is made:

import traceback

def disp(x):
    print((len(traceback.extract_stack()),x))

Now, let’s figure out some function performing some kind of computation, adding many calls to the execution stack, and finally calling a continuation. A recursive function will suit these needs:

def test(k,n):
    return test(k,n-1) if n>0 else k(42)

While useless, this function is easy to understand: it calls itself many times with a decreasing counter then calls the function k with an argument being 42.

Now, lets’s see what happens:

>>> test(disp, 100)
(103, 42)

(The exact left value may change with the interpreter but it should be a little more than 100.)

An elegant way of getting rid of these useless calls waiting to return is to embed the initial call to the test function in some wrapper like:

C = lambda f: lambda c, *a: f(lambda x: lambda : c(x), *a)()

Let’s check:

>>> C(test)(disp, 100)
(4, 42)

The idea is to trap the argument intended to be given to the disp function in a closure, to return and empty the execution stack, and then to call the continuation.

The previous syntax allows a single return value which is the continuation; thus the following function can’t work properly:

def test2(k,n,b):
    return test2(k,n-1,not b) if n>0 else k(42) if b else None

Below is a working example and a faulty one:

>>> C(test2)(disp, 100, True)
(4, 42)
>>> C(test2)(disp, 100, False)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 1, in <lambda>
TypeError: 'NoneType' object is not callable

Some workaround can be found with:

C2 = ( lambda f: lambda c, *a:
       (lambda g: g() if callable(g) else g)
       (f(lambda x: lambda : c(x), *a) ) )

But the following part of the article will focus on the initial case where the single allowed return value is the call to the continuation.

Second part: variants of the previous solution

The above solution requires the user to put the continuation argument k as the first one of the function while many programmers usually put it after all other arguments. This order can be implemented but is less elegant than the previous one:

C3 = lambda f: lambda *a: f(*(list(a[:-1]) + [lambda x: lambda : a[-1](x)]) )()

I personally like another way for the very same idea (I also use the Y combinator for implementing the recursion in order to only rely here on lambda calculus):

Y = lambda f: (lambda x: x(x))(lambda y: f(lambda *args: y(y)(*args)))
test = lambda k: lambda n: Y(lambda f: lambda i: f(i-1) if i>0 else k(42))(n)
C = lambda f: lambda c: lambda a: f(lambda x: lambda : c(x))(a)()

which has to be used as:

>>> C(test)(disp)(100)

This style is itself a good transition to a more general solution allowing several continuations to be used (according to a case which is decided at the top of the stack but with an evaluation occuring once the stack will become empty):

C = lambda f: lambda *c: lambda *a: f(*map(lambda k: lambda x: lambda : k(x), c))(*a)()

which can still be used as:

>>> C(test)(disp)(100)

but which can also be used as:

def disp1(x):
    print(("ok",len(traceback.extract_stack()),x))
def disp2(x):
    print(("err",len(traceback.extract_stack()),x))

test = ( lambda k1, k2: lambda n:
           Y(lambda f: lambda i,j: f(i-1,not j) if i>0
                else k1(42) if j else k2(42))(n,False) )

where two different continuations are now used. The new wrapper can be used as:

C(test)(disp1,disp2)(15)

Third part: two more refinements

Two more improvements will now be added to the wrapper:

• allowing the continuation to take any number of arguments (usual continuation passing style requires the continuation to take one argument but it won’t hurt here to allow more);
• removing one level more in the execution stack by initially returning a tuple conataining the function and its arguments rather than a function.

The wrapper becomes (in Python 2):

C = lambda f: lambda *c: lambda *a: apply(*f(*map(lambda k: lambda *x: (k,x), c))(*a))

and in Python 3 (where apply doesn’t exist any more):

def C(f):
    def D(*c):
        def E(*a):
            func, args = f(*map(lambda k: lambda *x: (k,x), c))(*a)
            return func(*args)
        return E
    return D

Now the continuation will be added to the stack only one level above the wrapper itself with no intermediate call.

The final word

I finally wrote a little module containing various implementations of a general wrapper for handling both tail-elimination: in tail-recursion and in continuation-passing style; it is located at https://github.com/baruchel/tco

Infinite power in Python

A nice feature in the J programming language is the infinite power operator, which gives the ability to raise a function to the infinite power. The idea is to repeatedly apply a function to its previous result until some convergence is reached or until some system is stabilized. Such a feature allows to “hide” many while loops.

Here is a link to the page of the J for C programmers book explaining more about this way of coding: Loopless Code IV.

Implementing such a feature in Python is rather easy:

class __infinitepower__():
    def __init__(self):
        pass
    def __rpow__(self,f):
        def func(a):
            while True:
                b = f(a)
                if b == a:
                    return b
                a = b
        return func
infinitepower = __infinitepower__()
infinitepower.__rxor__ = infinitepower.__rpow__

This piece of code creates the infinitepower variable which can be used for raising any function to the infinite power. This object may be affected to a new variable with a shorter name for convenience purposes (rename it to oo, Inf, or any other name).

>>> oo=infinitepower
>>> from math import sqrt, cos
>>> (cos**oo)(.5)
0.7390851332151607
>>> (sqrt^oo)(.5)
0.9999999999999999

Of course, the operator for “power” is ** in Python, but it isn’t much more coding to also allow the variable to be used with ^ (while it could be held as a very bad idea from a pythonic point of view).

Optimizing tail-recursion in Python

It has often been claimed that tail-recursion doesn’t suit the pythonic way of coding and that one shouldn’t care about how to embed it in a loop. I don’t want to argue with this point of view; sometimes however I like trying or implementing new ideas as tail-recursive functions rather than with loops for various reasons (focusing on the idea rather than on the process, having twenty short functions on my screen in the same time rather than only three “pythonic” functions, working in an interactive session rather than editing my code, etc.).

Optimizing tail-recursion in Python is in fact quite easy. While it is said to be impossible or very tricky, I think it can be achieved with elegant, short and general solutions; I even think that most of these solutions don’t use Python features otherwise than they should. Clean lambda expressions working along with very standard loops lead to quick, efficient and fully usable tools for implementing tail-recursion optimization.

As a personal convenience, I wrote a small module implementing such an optimization by two different ways. I would like to discuss here about my two main functions.

The clean way: modifying the Y combinator

The Y combinator is well known; it allows to use lambda functions in a recursive manner, but it doesn’t allow by itself to embed recursive calls in a loop. Lambda calculus alone can’t do such a thing. A slight change in the Y combinator however can protect the recursive call to be actually evaluated. Evaluation can thus be delayed.

Here is the famous expression for the Y combinator:

lambda f: (lambda x: x(x))(lambda y: f(lambda *args: y(y)(*args)))

With a very slight change, I could get:

lambda f: (lambda x: x(x))(lambda y: f(lambda *args: lambda: y(y)(*args)))

Instead of calling itself, the function f now returns a function performing the very same call, but since it returns it, the evaluation can be done later from outside.

My code is:

def B(func):
    b = (lambda f: (lambda x: x(x))(lambda y:
          f(lambda *args: lambda: y(y)(*args))))(func)
    def wrapper(*args):
        out = b(*args)
        while callable(out):
            out = out()
        return out
    return wrapper

The function can be used in the following way; here are two examples with tail-recursive versions of factorial and Fibonacci:

>>> from recursion import *
>>> fac = B( lambda f: lambda n, a: a if not n else f(n-1,a*n) )
>>> fac(5,1)
120
>>> fibo = B( lambda f: lambda n,p,q: p if not n else f(n-1,q,p+q) )
>>> fibo(10,0,1)
55

Obviously recursion depth isn’t an issue any longer:

>>> B( lambda f: lambda n: 42 if not n else f(n-1) )(50000)
42

This is of course the single real purpose of the function.

Only one thing can’t be done with this optimization: it can’t be used with a tail-recursive function evaluating to another function (this comes from the fact that callable returned objects are all handled as further recursive calls with no distinction). Since I usually don’t need such a feature, I am very happy with the code above. However, in order to provide a more general module, I thought a little more in order to find some workaround for this issue (see next section).

Concerning the speed of this process (which isn’t the real issue however), it happens to be quite good; tail-recursive functions are even evaluated much quicker than with the following code using simpler expressions:

def B0(func):
    def wrapper(*args):
        out = func(lambda *x: lambda: x)(*args)
        while callable(out):
            out = func(lambda *x: lambda: x)(*out())
        return out
    return wrapper

I think that evaluating one expression, even complicated, is much quicker than evaluating several simple expressions, which is the case in this second version. I didn’t keep this new function in my module, and I see no circumstances where it could be used rather than the “official” one.

Continuation passing style with exceptions

Here is a more general function; it is able to handle all tail-recursive functions, including those returning other functions. Recursive calls are recognized from other return values by the use of exceptions. This solutions is slower than the previous one; a quicker code could probably be written by using some special values as “flags” being detected in the main loop, but I don’t like the idea of using special values or internal keywords. There is some funny interpretation of using exceptions: if Python doesn’t like tail-recursive calls, an exception should be raised when a tail-recursive call does occur, and the pythonic way will be to catch the exception in order to find some clean solution, which is actually what happens here…

class _RecursiveCall(Exception):
    def __init__(self, *args):
        self.args = args
def _recursiveCallback(*args):
    raise _RecursiveCall(*args)
def B2(func):
    def wrapper(*args):
        while True:
            try:
                return func(_recursiveCallback)(*args)
            except _RecursiveCall as e:
                args = e.args
    return wrapper

Now all functions can be used. In the following example, f(n) is evaluated to the identity function for any positive value of n:

>>> f = B2( lambda f: lambda n: (lambda x: x) if not n else f(n-1) )
>>> f(5)(42)
42

Of course it could be argued that exceptions are not intended to be used for intentionnaly redirecting the interpreter (as a kind of goto statement or probably rather a kind of continuation passing style), which I have to admit. But, again, I find funny the idea of using try with a single line being a return statement: we try to return something (normal behaviour) but we can’t do it because of a recursive call occuring (exception).