High Performance Linux

Thursday, January 5, 2012

Tail Recursion in Perl and Python (or why do we prefer Perl to Python)

Few years ago I was making several Python projects. I moved from Perl to Python because of its clearer syntax and it was just interesting for me to know why so much people (like Google and Yandex) moved to Python.

However I back to Perl after two years with Python. Python is good mature language with great modules and scalable preemptive multi-threading support (unlike Ruby which uses cooperative multi-threading for 1.8 and global interpreter lock (GIL) for current 1.9 version). But programming in Python becomes quite tedious if you wish to do some unusual things.

Lets consider following simple example of recursive factorial calculation:

sub tail_factorial
{
        my ($total, $n) = @_;

        return $total unless $n;
        return tail_factorial($total * $n, $n - 1);
}

In Python this code looks like (also quite short and straightforward):

def tail_factorial(total, n):
        if not n:
                return total
        return tail_factorial(total * n, n - 1)

Perl5 does not have tail recursion optimization (unlike Perl6). The same story with Python3.However there is simple solution for Perl (example is borrowed from Pure Perl tail call optimization, changed lines are in italic):

sub tail_factorial2
{
        my ($total, $n) = @_;

        return $total unless $n;

        @_ = ($n * $total, $n - 1);
        goto &tail_factorial2;

}

However I was wondered that there is no clear solution for Python. There is decorators implementations (see Tail Call Optimization Decorator (Python recipe) or Tail recursion decorator revisited), but all of them uses additional functions and internal loops. Other solutions are Tail Recursion in Python using Pysistence and Tail recursion in Python also uses internal cycles and helping functions.

Guido has stated about such solutions in his blog as "it's simply unpythonic". This is bit unnatural example and really there is no big deal to rewrite the function to use a loop (we live with the practice in kernel programming for a long time). However actually there are plenty of such limitations with Python (one more good example is that you can not call Python program as a single line, so you can not buili it into shell scripts and use it as extended sed/awk for advanced grep'ing). Thus I prefer to work with powerful and flexible tool rather than with limited and poor. This is why we use Perl in our daily work.

No comments:

Post a Comment