a-foton » Understanding Tail Recursion

a-foton » Understanding Tail Recursion — Fri, 08 Aug 2008 03:16:20 GMT

PingBack from http://blog.a-foton.ru/2008/08/understanding-tail-recursion/

re: Understanding Tail Recursion

Mostafa Elhemali — Sun, 10 Aug 2008 00:30:51 GMT

So is there a way in VS to quickly know if a function is tail recursive or not?

re: Understanding Tail Recursion

Dave Bayer — Sun, 10 Aug 2008 13:18:22 GMT

I find it astonishing that in Lisp-like languages (including the ML family), "tail recursion modulo cons" not only has a name, but is rarely implemented. One could generalize this to allowing compilers to exploit associativity, to automatically rewrite your first factorial example as properly tail recursive.

I love functional languages. However, in an ideal world one could be required to have a deep understanding of tail recursion (thanks for spreading an explanation) without being forced to keep track of it in practice. In how many languages does one need to worry about folding left versus right, for purely efficiency reasons? This is as barbaric as asking a programmer to allocate registers; shame on the compiler writers.

A tail-recursive function is a verbose way to express a grammatical transformation on data, either actual or implied by a computation such as factorial. If we could assume all programmers understood e.g. parsing theory, then languages could emerge with more concise, algebraic descriptions of these transformations. Scripting languages take for granted regular expressions on strings, but no language is as fluid with grammatical transformations of other kinds of data.

re: Understanding Tail Recursion

ChrSmith — Mon, 11 Aug 2008 18:41:11 GMT

No, there is no indiciate from the Visual Studio IDE if a function will be compiled as tail-recursive or not. It's something which we've talked about before though.