[Python-Dev] Proper tail recursion (original) (raw)

Christian Tismer tismer at stackless.com
Fri Jul 16 02:09:04 CEST 2004

Christopher T King wrote:

On Thu, 15 Jul 2004, Bob Ippolito wrote:

On Jul 15, 2004, at 11:10 AM, Christopher T King wrote:

But in this case what is tail-call optimization going to do for you? You still require a stack at least the size of the height of your tree because of traverse(t.left) since that can not be tail-call optimized away, with the proposed algorithm. In Andrew's example, he noted that it would only help for list-like structures (i.e. those with mostly right nodes). I think Guido is in the right here, if you want to work around the recursion limit, use Stackless.. It should already be able to go just about as deep as you want.

Right.

You're right -- even if Stackless doesn't do tail call optimization, implementation should be trivial. But there's no guarantee when or even if Stackless will be merged with CPython, and until that happens, Stackless isn't an option for many (most?) people.

Wrong.

Stackless will always be there, one or two weeks later but will be there.

There is a guarantee: It will never be part of CPython. Proof: Just follow the postings in python-dev over the last five years, and how Guido handled these. If the proposals seemed to have a tiny chance, it was finally shut down by some "And however you argue, I don't want it" like statement. "If you need it, use it, that's where Stackless is for". In a sense, I like this Groucho Marx approach of "whatever it is, I'm against it". It is just not coherent with all the feature-creaping-ins of the past years, this is not consistent.

Some way I can accept this. But the whole story is partially like cheating. First, I was dissed because of Guido disliking continuations. OK! Next, I was dissed because of rewriting lots of the core is not feasible. OK! Btw., I have almost solved this by some automation which could apply sensible patches to almost every extension module. But who cares. Afterwards, I was dissed because compatibility to Jython was made into a problem. OK! Nice that I could turn a not-so-beloved kid into a really loved one.

After all (as said many times, already), I don't care, and I continue with Stackless. Also by supporting more supportive languages like Prothon (although I still don't understand why prototypes are better than classes).

Anyway, removing recursive-descend evaluation from Python would mean to remove Guido from Python, which is certainly not an option. At least I won't try this for his life-time, and it is also by no means my wish. I prefer to stick within my role as the dark side of Python. :-)

If I only could understand him, that would really help.

ciao -- chris

p.s.: since yesterday, Psyco belongs to the "well supported special modules for Stackless". Psyco is the only module that I know of that heavily depends on frame layout. You have to recompile it, but then it works really fine. I hope not to impose resentments on Psyco by that :)

Christian Tismer :^) <mailto:tismer at stackless.com> Mission Impossible 5oftware : Have a break! Take a ride on Python's Johannes-Niemeyer-Weg 9a : Starship http://starship.python.net/ 14109 Berlin : PGP key -> http://wwwkeys.pgp.net/ work +49 30 89 09 53 34 home +49 30 802 86 56 mobile +49 173 24 18 776 PGP 0x57F3BF04 9064 F4E1 D754 C2FF 1619 305B C09C 5A3B 57F3 BF04 whom do you want to sponsor today? http://www.stackless.com/

More information about the Python-Dev mailing list