61

Having read Dr Rauschmayer's description of recursive tail call optimisation in es6, I've since been trying to recreate the 'zero-stack' execution of the recursive factorial function he details.

Using the Chrome debugger to step between stack frames, I'm seeing that the tail optimisation is not occurring and a stack frame is being created for each recursion.

I've also tried to test the optimisation by calling the function without the debugger, but instead passing 100000 to the factorial function. This throws a 'maximum stack' error, which implies that it is, in fact, not optimised.

Here is my code:

const factorial = (n, acc = 1) => n <= 1 ? acc : factorial(n - 1, n * acc)
console.log( factorial(100000) )

Result:

Uncaught RangeError: Maximum call stack size exceeded
Sam Hanlan
  • 643
  • 1
  • 7
  • 6
  • Additional: `let acc = 1, n = 1e+5; while (n > 1) acc *= n--; console.log(acc)` –  Mar 14 '17 at 15:27
  • @Matheus awesome solution, nicely done! I know it's not recursive, but tbh it's a 'real' solution which is what really counts, right? – Sam Hanlan Mar 16 '17 at 13:34
  • Thanks, it's doing the same thing as the recursive function yes ! It's resulting `Infinity`, but `n` is equal to `1` at the end xd –  Mar 16 '17 at 14:45
  • The function must be in strict mode for the recursion to count as a “proper tail call” that gets optimized in at least Webkit browsers. Thus, `const factorial = (n, acc) => { "use strict"; return n <= 1 ? acc || 1 : factorial(n - 1, n * (acc || 1)); }` allows `factorial(100000)` to return `Infinity` in Safari, but not the code shown in the question, unless used in an already strict context. See https://webkit.org/blog/6240/ecmascript-6-proper-tail-calls-in-webkit/ for more information. – Otto G Jan 11 '22 at 11:16

2 Answers2

94

V8, the JavaScript engine in Chrome, had TCO support for a while, but as of this updated answer (November 2017) it no longer does, there is no active development on TCO in V8, and none is planned. You can read the details in the V8 tracking bug for it.

TCO support seems to have reached a decent level in V8 at one point, but remained behind a flag for several reasons (debugging issues, bugs). But then several things happened, not least that the V8 team raised significant issues with TCO and strongly supported a spec change called syntactic tail calls (STCs) that would require that tail calls be flagged in source code intentionally (e.g., return continue doThat();). That proposal became inactive in July 2017, though. Also in July, with no TCO work being done, the V8 team removed the code for supporting TCO from the source for TurboFan* as it would otherwise be subject to bitrot. (E.g., become a maintenance pain and source of bugs.)

So at present (Nov 2017) it's not clear that "invisible" TCO will ever be in V8, whether some kind of STCs will come in, or what. The Chrome Platform Status page for this indicates "mixed" public signals from Mozilla (Firefox/SpiderMonkey) and Microsoft (Edge/Chakra) on supporting TCO, that Safari is shipping with TCO, and that web developers are "positive" about the feature. We'll see where we go from here. If anywhere.

* (TurboFan = the current cutting-edge JIT compiler in V8, now they've switched from Full-Codegen [JIT] + Crankshaft [aggressive optimizing JIT] to Ignition [interpreter+] and TurboFan [aggressive optimizing JIT])

T.J. Crowder
  • 1,031,962
  • 187
  • 1,923
  • 1,875
  • Well for optimizing tail-calls at the internal language, supposing it's ES3, there could be avoided the creation of next scopes, etc... do u think it's possible? –  Mar 14 '17 at 14:47
  • 2
    Chrome (and by extension, The Internet) will probably never have proper tail call implementation, unfortunately. See answer below. – Freewalker Nov 09 '17 at 16:57
  • 2
    @T.J.Crowder You're right, it may not be totally dead in the water - in this WebAssembly meeting, none of the groups present voted against considering further (all were neutral or positive). Thanks for the nudge to look a bit more! https://github.com/WebAssembly/meetings/blob/master/2017/CG-07.md#tail-call – Freewalker Nov 09 '17 at 18:24
  • 1
    @captain-yossarian - I haven't heard any. As far as I can tell, this is still at stalemate: JavaScriptCore implements them, V8 and SpiderMonkey don't. I don't think there's anyone interested in driving it to a resolution, in any of the ways it could be resolved (removing them from the spec, V8 and SpiderMonkey implementing them as-is, or replacing them with an explicit syntax [which Apple didn't like in 2016]). This illustrates the wisdom of the current path proposals take (which tail calls predates), where things don't go in the spec until there are 2+ implementations. – T.J. Crowder Oct 05 '20 at 10:07
19

The V8 (Chrome's JS engine) team is not implementing TCO, for the time being. It's ripped out of the most recent versions (see this thread).

Of the major browsers, only Safari has actually implemented the feature (described in this 2016 Webkit blog post).

In Node.JS version 8 and later, TCO is not available.

There may be some hope of TCO being implemented: in a 2017 WebAssembly meeting, Google and all the other groups present were neutral or positive toward exploring TCO implementation further.

Freewalker
  • 6,329
  • 4
  • 51
  • 70
  • I updated the post to mention V8 instead of Chromium, thanks. However I think the thread referenced is pretty clear that barring further developments this is dead in the water. I'd love to hear if there's other info out there! Personally I definitely want this feature in JS.The V8 check-in in July removing all TCO work says: "The tail call implementation... is known to be broken in a variety of cases, including clusterfuzz security issues (see sample Chromium issues below). To avoid letting the implementation bitrot further on trunk, this patch removes it." – Freewalker Nov 09 '17 at 18:18
  • @T.J.Crowder Really interesting, I appreciate the discussion! We keep moving further toward FP everywhere, and this would be a really nice step. – Freewalker Nov 09 '17 at 18:26
  • @ftor: That's where we are, though. *["...we currently have no plans to do work on tail calls in V8."](https://bugs.chromium.org/p/v8/issues/detail?id=4698#c75)*. – T.J. Crowder Nov 10 '17 at 18:59
  • 1
    @T.J.Crowder thanks for following up this subject. That really is a big disappointment! –  Nov 10 '17 at 19:05
  • 1
    Just tested it on Safari (12.0.2) with factorial(100000) and got "Maximum call stack size exceeded" exception. [link]https://jsfiddle.net/j076L5v8/1/ – Ofir Meguri Apr 04 '19 at 15:07
  • The link to the WebAssembly meeting is dead. :( – jamesh625 Sep 11 '20 at 12:25
  • 1
    @jamesh625 Updated, thanks, looks like it was removed from the repo but still present in a previous repo version. – Freewalker Sep 11 '20 at 16:18