[Python-Dev] Proper tail recursion

Michael Walter michael.walter at gmail.com
Thu Jul 15 15:34:53 CEST 2004


Herro,

On Thu, 15 Jul 2004 05:32:05 -0700, Michael Chermside <mcherm at mcherm.com> wrote:
> Drat!
> 
> I mis-clicked the "Send" button before finishing my previous email.
> 
> Here's the entire thing:
> 
> Christopher King writes:
> > To tell the truth, I don't really have any immediate use for this
> > functionality, either, but since it turned out to be so
> > easy to implement,
> > I ask, "why not?" ;)
> 
> Martin replies:
> > The traditional answer to that question is "because Jython cannot
> > support it".
> 
> No... that answer applies to *language features*, but not *implementation
> details*. The recursion limit (the value of it anyhow) is an
> implementation detail.
> 
> Think of it this way: if Iron Python, Jython, or PyPy were to implement
> a clever trick that made loops run 10x faster, that would be swell,
> even if the same trick couldn't be done in CPython. If CPython can find
> a way to run recursion far more efficiently, then that's swell too. Of
> course, the actual results from running the program must not differ,
> but that doesn't seem too difficult to achieve.
Well, tail call elimination (or "proper tail recursion", being a
subset of it?) is not only an implementation detail as it opens up
Python to a functional/recursion-oriented programming style (as you
also argue further down).

So either you would keep your patch purely as an implementation detail
(i.e. "Python has proper tail recursion!" in the "news" would be a
no-no), or it has to be possible for all Python implementations to
implement "proper" tail recursion (at least in my understanding).

Anyway there was no agreement yet that Jython couldn't support that
_feature_, too, IIRC - I would certainly be happy to have it in
Python.

> Guido writes:
> > I'm not interested in adding this to the official Python release.
> >
> > One reason is that if an exception happens in such a tail-recursive
> > call, the stack trace will be confusing.
Hmm. Maybe we could have some kind of indicator that tail recursion
occured (or even a recursion count -- of course this will only work
for tail recursion, not for general tail call elimination)?

> Guido continues:
> > Another reason is that I don't think it's a good idea to try to
> > encourage a Scheme-ish "solve everything with recursion" programming
> > style in Python.
> 
> I wouldn't say that tail recursion *encouraged* a functional style,
> rather I would say that refusing to accept a working version of
> tail recursion actively *discourages* the use of that style.
How about: Tail recursion "enables" recursion-oriented (functional) style? :)

Cheers,
Michael


More information about the Python-Dev mailing list