Stackless Python, Tail Recursion and Functional Programming

[Manuel M. Garcia]

On Sat, 11 Jan 2003 01:18:05 -0400, beno <zope at thewebsons.com> wrote:
(edit)
>Someone wrote me from this list advising me to drop my passion for 
>functional programming because Python doesn't optimize for it.

Wait a minute!  Don't "drop your passion" just yet!  I was the one
that told you that CPython does not optimize for tail-recursion.  But
"Tail-recursion" is not the whole of "functional programming".

These two are found together in the LISP world, but a language that
does not optimize for tail-recursion is not precluded from having
functional programming elements.

Tail-recursion is just a looping construct.  Instead of using
tail-recursion for looping, just use a "while" or "for" loop.

# ######################################### #

import operator

def factorial_forloop(n):
    x = 1L
    for i in xrange(1, n + 1):
        x *= long(i)
    return x

def factorial_tailloop(n):
    if n == 0: return 1L
    return long(n) * factorial_tailloop(n - 1)

def factorial_functional(n):
    return reduce(
        operator.mul,
        range(1, n + 1),
        1 )

def print_functions(*functions):
    def g(n):
        for f in functions:
            r = f(n)
            print '%s(%i) = %r' % (f.__name__, n, r)
    return g

p = print_functions(
    factorial_forloop,
    factorial_functional,
    factorial_tailloop )

p(0)
p(1)
p(2)
p(3)
p(4)
p(5)
p(20)
p(50)
p(1000)
    
# ######################################### #

On my machine, "factorial_forloop" handles 1000 just fine, and
"factorial_tailloop" blows up with a
"RuntimeError: maximum recursion depth exceeded"

If CPython optimized tail-recursion, we would expect
"factorial_forloop" and "factorial_tailloop" to have similar
performance.

But that doesn't mean you can't use recursive algorithms in Python.
Beyond fully optimized tail-recursion, Python handles general
recursion just as efficiently as any language.

Anyway, getting back to "functional programming"...

A loose definition of "functional programming" is:

    Typing in the description of a computation,
    and getting the answer
    without needing to specify any procedure to get that 
    answer.

More or less.

Some trickier stuff left out of the definition above:

    We can programmatically manipulate these descriptions of
    computations.

    As above, we can just describe these manipulations, we don't
    need to specify the procedure to do these manipulations.

    The output of our computations can be another description!
    To start the whole thing over again!

Python has some functional programming abilities:

"factorial_functional" shows one functional programming approach to
factorial.  I don't specify any loop, it is implied by "reduce".  This
one also runs just fine for 1000.

Some Python built-ins that are taken from the functional programming
world are: lambda, map, apply, reduce, filter.

Also list comprehensions:

    [ x * 10 for x in range(50) if (x % 3) == 1 ]

Instead of:

    list0 = []
    x = 0
    while x < 50:
        if (x % 3) == 1:
            list0.append(x * 10)
        x += 1

I learned functional programming in Mathematica.  The language that
seems to be on the forefront of functional programming is Haskell.  I
have no experience with Haskell.

I would assume there are "tricky" things you can do in Haskell that
you cannot do in Python without creating your own Python
implementation of Haskell.

If there is something cool in Haskell you wish you could do in Python,
the people in comp.lang.python will give you a way to do it, if it can
be done in Python.

Manuel