Stackless Python, Tail Recursion and Functional Programming

[beno]

Thank you for your tutorial! I'll study it in detail and put it to practice.
beno

At 11:51 PM 1/11/2003 +0000, you wrote:
>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
>--
>http://mail.python.org/mailman/listinfo/python-list