Some misconceptions about (Scheme's) tail recursion

[xytroxon]

"Simplicity, for the sake of simplicity, is the hallmark of simple mindedness... Or of a Scheme programmer... But, I repeat myself..."

 -- xytroxon's 1st ASC (Asymptotic Space Complexity) corollary.



Schemers often decry the lack of TCO (Tail Call Optimization) in newLISP... Here is a great blog building on the author of Python shunning TCO in his language design... The blog looks at the history of TCO, and then addresses some of the finer points of Scheme's TCO programming "heresy"...



Abstract Heresies Blog:

http://funcall.blogspot.com/2009/04/you-knew-id-say-something.html">//http://funcall.blogspot.com/2009/04/you-knew-id-say-something.html



http://www.reddit.com/r/programming/comments/8fj0p/some_misconceptions_on_tail_recursion/">Link to reddit discussion

To summarize, this point of view about tail recursion is based on these ideas:



    * It's purpose is to avoid writing looping constructs, which are somehow considered 'bad' by 'purists'. These weirdos 'think' in loops, then transform the code to be 'recursive with tail calls' when they write it, and then expect the compiler transform it back. This is academic mental gymnastics with no practical purpose.



    * People who like tail recursion are purposefully burdening their code in the name of 'mathematical' or 'theoretical' purity, but they expect the language implementor to bear the weight.



    * Any code that depends on tail recursion can easily be rewritten to use a looping construct instead. Such a rewrite is a trivial local transformation.



    * Inter-procedural tail recursion may have some performance benefit, but such benefit is very small at best, and the tradeoff is the loss of valuable debugging information.

At the conclusion of this "blog in progress", the author exposes the problem with TCO's Bubble Sort like "asymptotic space complexity" that "acts upon the entire program"...



Of course! Why didn't I think of that! ;)



-- xytroxon

[Kazimir Majorinc]

> 1) Does the Interpretor do any kind of tail call optimisation?



No, not at all.



As far as I can see, this is not easy to implement in an efficient way. The interpreter would have to detect tail recursion at runtime, which takes much more than time than simply executing the call/return. Each function must inspect itself, just to find those (extremely few) cases of tail recursion.



Above that, it would violate some basic principles of picoLisp. Trying to be clever behind the scenes, doing things the programmer did not explicitly specify, losing simplicity and what-you-see-is-what-you-get.

[xytroxon]

I don't really want to trash Schemers too much (somebody has to keep the LISPers honest ;o), but their attacks on Python have generated a few cutting, if not humorous, counter observations...



Here are some quotes from a blog on the "Final Word" on TCO not being for Python by Python's creator Guido van Rossum:



http://neopythonic.blogspot.com/2009/04/final-words-on-tail-calls.html">Click here for original article at: neopythonic.blogspot.com

The most interesting use case brought up for TCO is the implementation of algorithms involving state machines. The proponents of TCO claim that the only alternative to TCO is a loop with lots of state, which they consider ugly. Now, apart from the observation that since TCO essentially is a GOTO, you write spaghetti code using TCO just as easily, Ian Bicking gave a solution that is as simple as it is elegant.

And;

And here it ends. One other thing I learned is that some in the academic world scornfully refer to Python as "the Basic of the future". Personally, I rather see that as a badge of honor, and it gives me an opportunity to plug a book of interviews with language designers to which I contributed, side by side with the creators of Basic, C++, Perl, Java, and other academically scorned languages -- as well as those of ML and Haskell, I hasten to add. (Apparently the creators of Scheme were too busy arguing whether to say "tail call optimization" or "proper tail recursion." :-)

Ouch!



-- xytroxon