Some misconceptions about (Scheme's) tail recursion
Posted: Mon Apr 27, 2009 5:38 pm
"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 ... thing.html
Link to reddit discussion
Of course! Why didn't I think of that! ;)
-- xytroxon
-- 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 ... thing.html
Link to reddit discussion
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"...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.
Of course! Why didn't I think of that! ;)
-- xytroxon