On 2011-01-30, at 1:58 PM, chevalma@iro.umontreal.ca wrote:
I guess we'll see when the spec is released whether they mean static or dynamic tail calls. I'm guessing the latter would require a rather tricky analysis to work in JavaScript, and may not be what they will include in the spec.
Does scheme mandate that the compiler must be able to discover tail calls that occur at any point, say, after functions are redefined? For example, if you define some function f to call a function g that is not yet defined, and then later you dynamically define g, and the functions end up being mutually tail-recursive, does scheme mandate this must be optimized through tail recursion?
Of course! The semantics does not make special cases. If a function f calls g in tail position, then it is a tail-call. The time when a function was called has no effect on the semantics. Remember that Scheme, like JavaScript, are dynamic languages, in the sense that the semantics is described in terms of operations that happen at run time. Static analysis is viewed as an optimization (i.e. discovering some properties at compile time, such as types, that in the general case would require an execution of the program).
Think of this case:
var g;
function f(n) { print(n); if (n>0) g(n-1); }
if (sometimes) g = f;
Then sometimes f will be a tail-recursion. The fact that f is calling f isn't known statically. It is only at run time that we know f is calling itself.
What would be required to extend the IR "call" instruction to support tail-calls?
Marc