New issue
Advanced search Search tips
Note: Color blocks (like or ) mean that a user may not be available. Tooltip shows the reason.

Issue 457 link

Starred by 159 users

Issue metadata

Status: Duplicate
Merged: issue 4698
Owner: ----
Closed: Feb 2016
Cc:
Components:
HW: ----
NextAction: ----
OS: ----
Priority: 2
Type: FeatureRequest



Sign in to add a comment

Implement tail call elimination

Reported by joakim.a...@gmail.com, Oct 1 2009

Issue description

If I open the JavaScript console in Chrome and write this:

function fac(n, a) { if(n == 0) { return a; } else { return fac(n - 1, a *
n) } }; fac(100000, 1);

I get this: RangeError: Maximum call stack size exceeded

I think V8 might be a nice target virtual machine for other programming
languages if it supported tail calls. It's the only big obstacle I can see
for languages with functional features.
 
Status: WorkingAsIntended
Tail call elimination isn't compatible with JavaScript as it is used in the real 
world.  Consider the following:

function foo(x) {
  return bar(x + 1);
}

function bar(x) {
  return foo.arguments[0];
}

foo(1)

This returns 1.  It wouldn't work with tail call elimination.
I see, thank you for the explanation.

Comment 3 by halle...@gmail.com, Dec 4 2009

I don't see how this example stands in the way of tail call elimination when a function 
calls itself.  Is there some way a function can reach through the stack to get the 
arguments object for any invocation of a given calling function other than the most 
recent?
It is true that you can't see invocations other than the top one (except using the 
debugger or the .stack property on exceptions).  However, this doesn't help us for 
general tail call elimination.

I don't think tail call elimination is worth doing if it restricted to recursive calls 
to the function itself.  These cases can be easily rewritten to use iteration instead.

Comment 5 by ager@chromium.org, May 25 2010

 Issue 700  has been merged into this issue.
While valid, the explanation given in comment #1 is a bit lame.  That might be correct JavaScript by specification, but calling it "real world" usage is too much.  I never used that construct in almost 10 years of JS; I didn't even know it exists, and it seems like a very bad practice anyway.

My vote is to break the spec and get TCO (at least optional somehow). :-)

Comment 7 by glath...@yahoo.fr, Jul 9 2010

I completely disagree with comment #1, because tail call elimination must *anyway* "rename" local arguments and variables to avoid conflicts, thus producing a functional equivalent of:

function foo(x){ 
    var y = x + 1;             // Renamed the `x` argument of `bar` as `y`
    return foo.arguments[0];   // body of `bar`, with `x` renamed as `y`
}

foo(1);  // -> 1

.

On the other side, I fully agree with comment #4. Mutual recursion would be meaningful.
Guillaume, seems that you are confusing "inlining" and "tail call optimization". 

You inlined bar into foo in your comment. 

TCO is all about destructively reusing caller's frame for callee's execution. It's totally different thing. 

Comment 9 by erights@google.com, Jul 9 2010

Comment #1 is correct and comment #6 is backwards. function.arguments and function.caller are not sanctioned by any spec. But they are part of de facto JS that any browser must honor to be compatible with the legacy web. 

So TCO, if done, should apply only to strict functions for the reasons stated at http://wiki.ecmascript.org/doku.php?id=strawman:proper_tail_calls

Comment 10 by glath...@yahoo.fr, Jul 9 2010

> Guillaume, seems that you are confusing "inlining" and "tail call optimization". 
> 
> You inlined bar into foo in your comment. 
> 
> TCO is all about destructively reusing caller's frame for callee's execution. It's totally different thing. 

No, I am not confusing the two things. That's why I wrote "functional equivalent of".

In more details: The "x" local variable of "foo" is not the same thing as the "x" local variable of "bar", so tail call elimination has to distinguish the two.

You can just check if people are using that feature, can't you? This is after all a JIT and a compiler.
Now http://wiki.ecmascript.org/doku.php?id=harmony:proper_tail_calls and very likely to be in ES.next.

Since Harmony is based on ES5 strict and ES5 strict poison-pills f.arguments for strict function f, and since tail position is a syntactic property, new code can count on proper tail calls. Old code can't necessarily, and mixing cannot, but that's not a reason to avoid proper tail calls in ES.next.

/be

Comment 14 by mijd...@gmail.com, Jul 18 2011

I'm in the real world and really need tail call elimination. Not supporting it because of backward compatibility is just dumbing down.
Missing a general purpose feature to allow the specific case given in counter example is a non sense.
More and more Javascript is being used as a target for other languages, and some of them need tail calls.
It would not imterfere with existing code if implemented correctly.

Tail call optimization is an optimization done transparently by the compiler and *only* if it is *possible*. This is how it works in every other compiler too. It would only be done when at the moment the recursive call happens the entire stack frame can safely be reused/overwritten for the next iteration because the compiler can proof that *nothing* else will ever use it again (no reference to the previous stack frame *after* the recursive call "returns" and also nothing else holding any reference to it).

Comment 17 Deleted

Comment 18 by he...@opalang.org, Jun 7 2013

As said in earlier comments made a few years ago, now that V8 is used in Node.js, which is a target for several languages and frameworks, tail call optimization is needed more than ever.
Cc: rossberg@chromium.org mstarzinger@chromium.org
Labels: Type-FeatureRequest Harmony
Status: Accepted
Summary: Implement tail call elimination (was: Tail call elimination (feature request))
Why is this ticket marked as "No signals" from developers? It should be positive. Plus, this is now part of harmony spec.

Comment 23 by wi...@igalia.com, Jul 15 2014

The ticket has been accepted, though as you can imagine there is a long backlog of features.  Me-too comments are not helpful; please refrain from such comments in the future, as they are distractions.  Thanks :)

Comment 24 by habl...@google.com, Apr 29 2015

Status: Available
Labels: Area-Language Priority-Medium

Comment 27 Deleted

Comment 28 Deleted

Comment 29 by l...@chromium.org, Feb 2 2016

Cc: l...@chromium.org
Mergedinto: 4698
Status: Duplicate (was: Available)
Labels: Priority-2

Sign in to add a comment