Guido van Rossum - Tail Recursion

http://neopythonic.blogspot.com/2009/04/tail-recursion.html

by tzury • 17 years ago

5 6 17 years ago

neopythonic.blogspot.com

jcl• 17 years ago

Looks like Guido pulled the article? It's not coming up for me, and there's only one (non-tail-recursion) article in the archives for April.

arvid• 17 years ago

the url changed http://neopythonic.blogspot.com/2009/04/tail-recursion-elimi...

tome• 17 years ago

I guess it meant this one:

http://neopythonic.blogspot.com/2009/04/tail-recursion-elimi...

jules2• 17 years ago

Why do you need to make a distinction between self recursive calls and other calls? And why a distinction between method calls and function calls? In Scheme all calls in tail position are tail calls, is there a special Python reason why that's not possible?

I don't think that stack traces are such a big deal. Stack traces only change if some function f calls another function g and immediately returns. The information that f wants to do nothing isn't very useful.

You are already making a trade-off between execution speed/memory cost and debug information. You don't record every function call even though that would be very useful for debugging. The current situation is an arbitrary trade-off, an a bad one in my opinion.

brushbox• 17 years ago

I'm not sure I understand your argument about stack traces and functions doing nothing. With TCE (tail-call elimination) the problem with stack traces are thus:

* with self-recursive functions it is no longer possible to see how many times the function has called itself (since the stack trace is collapsed to a single entry for the function rather than a proper trace of each call). This is a non-issue in my opinion - unless you have a language that also lets you know what your function call parameters were for each stack frame (if not then you are left with 'manually' working out where the recursion went wrong). As for debugging - it makes no difference since every self-recursive call made has no further effect on the computation.

* with ordinary tail-calls the issue could be a whole lot more noticeable as it means that given an error the stack trace will no longer contain any information on how you got from A (where you started making a series of tail-calls) to B. This one bears more thought (and I'd be interested in how Scheme implementations deal with this).

You further say "You don't record every function call even though that would be very useful for debugging" and I don't agree. Every debugger I've used records every function call on the stack (effectively the path to the current node in the call graph). If you meant that it doesn't record every function called in the history of the execution of the application - I agree that is useful and can easily be handled with a good logging infrastructure (and I'm sure that at least a few good debuggers would support such a log feature too). In fact, such a logging approach would possibly be an adequate solution to the tail-call problem. However that solution would need some extra "assistance" in order to be a valid approach in a "pure" functional language.

jules2• 17 years ago

> it makes no difference since every self-recursive call made has no further effect on the computation.

Yes, that's what I was trying to say. It's the same for non-self-recursive calls.

> If you meant that it doesn't record every function called in the history of the execution of the application

Yes I do mean that. Here's an example: http://www.lambdacs.com/debugger/

This records not only function calls but literally everything.

Guido van Rossum - Tail Recursion

Related Stories