Re: Tail recursion to while iteration in 2 easy steps

Discussion in 'Python' started by random832@fastmail.us, Oct 2, 2013.

  1. Guest

    On Tue, Oct 1, 2013, at 17:30, Terry Reedy wrote:
    > Part of the reason that Python does not do tail call optimization is
    > that turning tail recursion into while iteration is almost trivial, once
    > you know the secret of the two easy steps. Here it is.


    That should be a reason it _does_ do it - saying people should rewrite
    their functions with loops means declaring that Python is not really a
    multi-paradigm programming language but rather rejects functional
    programming styles in favor of imperative ones.
    , Oct 2, 2013
    #1
    1. Advertising

  2. On Wed, 02 Oct 2013 08:31:25 -0400, random832 wrote:

    > On Tue, Oct 1, 2013, at 17:30, Terry Reedy wrote:
    >> Part of the reason that Python does not do tail call optimization is
    >> that turning tail recursion into while iteration is almost trivial,
    >> once you know the secret of the two easy steps. Here it is.

    >
    > That should be a reason it _does_ do it - saying people should rewrite
    > their functions with loops means declaring that Python is not really a
    > multi-paradigm programming language but rather rejects functional
    > programming styles in favor of imperative ones.


    Python is not as aggressively functional as (say) Haskell, but it is
    surely an exaggeration to suggest that the failure to include tail call
    optimization means that Python "rejects" functional programming styles.
    You can still write you code in a functional style, it just won't be as
    heavily optimized.


    --
    Steven
    Steven D'Aprano, Oct 2, 2013
    #2
    1. Advertising

  3. Guest

    On Wed, Oct 2, 2013, at 9:32, Steven D'Aprano wrote:
    > Python is not as aggressively functional as (say) Haskell, but it is
    > surely an exaggeration to suggest that the failure to include tail call
    > optimization means that Python "rejects" functional programming styles.
    > You can still write you code in a functional style, it just won't be as
    > heavily optimized.


    IMO, tail call optimization is essential to writing in a functional
    style, since otherwise you end up with a stack overflow error on any
    input above a trivial size.
    , Oct 2, 2013
    #3
  4. On Wed, 02 Oct 2013 10:04:49 -0400, random832 wrote:

    > On Wed, Oct 2, 2013, at 9:32, Steven D'Aprano wrote:
    >> Python is not as aggressively functional as (say) Haskell, but it is
    >> surely an exaggeration to suggest that the failure to include tail call
    >> optimization means that Python "rejects" functional programming styles.
    >> You can still write you code in a functional style, it just won't be as
    >> heavily optimized.

    >
    > IMO, tail call optimization is essential to writing in a functional
    > style, since otherwise you end up with a stack overflow error on any
    > input above a trivial size.


    Hardly essential. Here's some functional code that doesn't rely on tail-
    call optimization for efficiency:

    result = map(some_function, some_iterator)

    In Python 3 that even uses lazy evaluation, for free.

    Or you can increase the amount of memory available in the stack. Another
    alternative would be for the compiler to convert your recursive code into
    iterative code. Well, that wouldn't work for Python.

    Not all functional code is recursive, and not all recursive functional
    code is tail-recursive. So while Python's lack of tail-call optimization
    is a failure of Best Practice functional *implementation*, it doesn't
    prevent you from writing in a functional *style*.

    Ultimately, Python does not pretend to be a pure-functional language. If
    you want Haskell, you know where to get it. Python steals a few good
    ideas from functional programming, like comprehensions and lazy-evaluated
    iterators, provides a few functional programming constructs like map,
    reduce, and filter, and gives you first-class functions as values. You
    can write code in a functional style in Python, but don't mistake that
    for Python being a functional language.

    --
    Steven
    Steven D'Aprano, Oct 2, 2013
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Terry Michaels

    Tail Call Optimization (Tail Recursion)

    Terry Michaels, Apr 18, 2011, in forum: Ruby
    Replies:
    16
    Views:
    309
    Robert Klemme
    Apr 20, 2011
  2. Terry Reedy
    Replies:
    66
    Views:
    372
    Charles Hixson
    Oct 9, 2013
  3. Terry Reedy
    Replies:
    1
    Views:
    130
    88888 Dihedral
    Oct 4, 2013
  4. Mark Janssen
    Replies:
    0
    Views:
    126
    Mark Janssen
    Oct 2, 2013
  5. Replies:
    1
    Views:
    96
    Steven D'Aprano
    Oct 4, 2013
Loading...

Share This Page