Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #55319 > unrolled thread

Re: Tail recursion to while iteration in 2 easy steps

Back to article view | Back to comp.lang.python

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: Tail recursion to while iteration in 2 easy steps random832@fastmail.us - 2013-10-02 08:31 -0400
    Re: Tail recursion to while iteration in 2 easy steps Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-10-02 13:32 +0000
      Re: Tail recursion to while iteration in 2 easy steps random832@fastmail.us - 2013-10-02 10:04 -0400
        Re: Tail recursion to while iteration in 2 easy steps Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-10-02 19:13 +0000

#55319 — Re: Tail recursion to while iteration in 2 easy steps

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.

[toc] | [next] | [standalone]

#55334

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

[toc] | [prev] | [next] | [standalone]

#55344

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.

[toc] | [prev] | [next] | [standalone]

#55376

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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web