3 ms·

You’re preaching to the choir! But one objection we will both encounter repeatedly is that if a language supports feature X, and you work on a team/inherit cod

You’re preaching to the choir! But one objection we will both encounter repeatedly is that if a language supports feature X, and you work on a team/inherit code/use libraries, there will always be people who don’t want to use feature X but wind up dealing with it any ways because someone else used it. So the naysayers will claim that if it’s added to the core language, it’s only a matter of time before they wind up dealing with it whether they like it or not. Given the way that most Ruby users have to live with monkey-patching in Ruby whether they do it themselves or not, I fully expect that if await and defer are added to core CS, there will be libraries or CommonJS modules that use it and presto, you may find yourself looking at some of its output in the debugger one day. I’d rather use the feature myself and benefit from it, but I can accept what the luddites are saying even if I don’t end up coming to the same conclusion about whether the feature should be added or withheld :-) UPDATE: I recall being told that tail-call optimization should not be added to certain languages because it encourages programmers to write recursive functions that are “hard to read.” You might argue that if you never write recursive functions, why should you care? But people do care.

drostie 15y ago
Maybe. Tail recursion optimizes itero-recursive algorithms, turning them into iterative algorithms by eliminating the overhead. Confused? Here are the iterative, recursive, and itero-recursive ways of writing the factorial function: function fact_r(N) { return N <= 0 ? 1 : N * fact_r(N - 1); } function fact_i(N) { var acc = 1, i; for (i = 1; i <= N; i += 1) { acc *= i; } return acc; } function fact_ir(N, acc) { acc = acc || 1; // default value of acc return N <= 0 ? acc : fact_ir(N - 1, N * acc); } So the accumulator variable becomes an argument variable which may have to be separately initialized. The key feature which makes something optimized for "tail calls" is that when f(something) wants to recurse, it returns f(something else). In other words, certain conditional logics can happen, but don't leave an operation like the "n " in "n recurse(n - 1)" on the stack or else you can't get rid of the function call. It's not even a special optimization -- basically you can move one line in the compiler a couple steps ahead of where you might have automatically written it, and it suddenly treats iteration and tail-recursion the same. So that's the difference. If you can understand fact_ir, which does the iterative idea in a recursive syntax, then you can understand tail recursion.

drostie 15y ago

Maybe. Tail recursion optimizes itero-recursive algorithms, turning them into iterative algorithms by eliminating the overhead. Confused? Here are the iterative, recursive, and itero-recursive ways of writing the factorial function: function fact_r(N) { return N <= 0 ? 1 : N * fact_r(N - 1); } function fact_i(N) { var acc = 1, i; for (i = 1; i <= N; i += 1) { acc *= i; } return acc; } function fact_ir(N, acc) { acc = acc || 1; // default value of acc return N <= 0 ? acc : fact_ir(N - 1, N * acc); } So the accumulator variable becomes an argument variable which may have to be separately initialized. The key feature which makes something optimized for "tail calls" is that when f(something) wants to recurse, it returns f(something else). In other words, certain conditional logics can happen, but don't leave an operation like the "n " in "n recurse(n - 1)" on the stack or else you can't get rid of the function call. It's not even a special optimization -- basically you can move one line in the compiler a couple steps ahead of where you might have automatically written it, and it suddenly treats iteration and tail-recursion the same. So that's the difference. If you can understand fact_ir, which does the iterative idea in a recursive syntax, then you can understand tail recursion.