5 ms·

Tail call optimization was added to the Javascript language specification in ES6 (ES2015). However most Javascript runtimes don't support it. This is a shame be

Tail call optimization was added to the Javascript language specification in ES6 (ES2015). However most Javascript runtimes don't support it. This is a shame because recursive operations like Haskell's foldl/r would more straightforward to translate to Javascript. Minus the automatic currying and lazy evaluation of course. More info: https://2ality.com/2015/06/tail-call-optimization.html https://2ality.com/2015/06/tail-call-optimization.html Edit: Babel may have tried, but couldn't do it for all cases, so they stopped trying? https://github.com/babel/babel/issues/256 https://github.com/babel/babel/issues/256

bjoli 6y ago
It would simplify things a great deal for people compiling to JS. Forcing one looping facility into the behaviour of another can be hard. Implenting just about any looping facility as recursion is a matter of thinking for a while and then sitting down and doing it.
ganafagol 6y ago
Hm what does TCO have to do with a language spec? It impacts neither syntax nor semantics of a language, which is what a language spec should be about. It's a detail of the compiler. So I'm curious what this has to do with the languagr spec? Couldn't a smart compiler/interpreter do this before ES6 already?
- KMag 6y ago
  "Optimization" is a misnomer with TCO. Optimization implies that only execution speed is affected without the optimization. Without TCO, potentially infinite mutually tail-recursive algorithms (or code transformed into continuation-passing style) can't be implemented without emulating tail recursion using a heap-allocated stack/linked list of states or manually transforming the mutually recursive functions into a trampoline variant of continuation passing style. function factorial(n, accumulator=1) { if (n <= 1) { if (n < 0) throw "Arument must not be negative"; return accumulator; } return factorial(n-1, n * accumulator); } TCO doesn't just affect the speed of this factorial implementation, it greatly affects the largest value that can be computed. It's not to tricky to manually convert tail recursion into a loop, but for mutually recursive functions, you'd probably be best off manually transforming your mutually recursive functions into a trampoline variant of continuation passing, where each function returns a tuple of function and arguments to a trampoline loop that just repeatedly invokes the returned function on the returned arguments. function trampoline(f, ... args) { while (true) { f, args = f(*args); if (args == null) { return f; } } } function fatorial_impl(n, accumulator) if (n <= 1) { if (n < 0) throw "Arument must not be negative"; return [accumulator, null]; } return [factorial_impl, [n-1, n * accumulator]]; } function factorial(n) { return trampoline(factorial_impl, n, 1); } It's all very mechanical, and you'd prefer that the compiler does it. The main argument against TCO is that it's easy for an unobservant programmer to accidentally make a change that prevents TCO. Ideally, the language would have a construct allowing a programmer to cause a given return site to be a syntactic error if it's not a TCO-able tail call.
  - kazinator 6y ago
    "optimization" does not imply that only execution speed is impacted.
    - KMag 6y ago
      Fair enough, but in most people's minds, it suggests that the correctness of an implementation doesn't depend on which optimizations are applied, and in this sense, TCO isn't an optimization. TCO isn't merely an optimisation in the same sense of local/global value numbering/common sub-expression elimination , dead-code elimination, loop-invariant expression hoisting, etc.
    - masklinn 6y ago
      > "optimization" does not imply that only execution speed is impacted. No but "optimisation" implies the normally observable semantics are not altered, which is not the case at all with TCE (aka "guaranteed TCO"). Removing TCE from a language makes it a completely different language e.g. Erlang would be severely restricted as it has no imperative loops.
- bcherny 6y ago
  Automatic TCO affects stack traces, which programs might rely on at runtime, requiring that browsers agree on what the right behavior should be; on the flip side, manual TCO (with annotations) would need to be a language feature.
  - EE84M3i 6y ago
    This is the correct answer per the linked article. In particular this is runtime inspectable via func.caller so it really is a behavioral language change to allow the elision of stack frames.
  - DarkWiiPlayer 6y ago
    > Automatic TCO affects stack traces, which programs might rely on at runtime, requiring that browsers agree on what the right behavior should be; Browsers don't have a say in this. They're making the decision to not be compliant with the specification, so they effectively don't support ES6.
  - pygy_ 6y ago
    Safari supports proper tail calls per the ES6 spec. If your code relies on the non-elimination of tail calls it will not work in Safari, and thus not be Web compatible.
  - zelphirkalt 6y ago
    One could argue, that writing programs, which rely on the stack trace is a bad practice. Handling of exceptions should take care of unexpected situations. I don't know of any scenario, where a program needs its own stack trace, which could not be solved by making use of exception handling properly. Perhaps anyone can give an example?
- haberman 6y ago
  > It impacts neither syntax nor semantics of a language It impacts the correctness of algorithms. For some algorithms it's the difference between using O(1) stack space and O(n) or more, where the latter would blow the stack and effectively crash the program.
- im3w1l 6y ago
  People want guaranteed TCO so that they can write code relying on it. If TCO ends up not happening such code will leak stack memory or hit max-recursion-limits.
  - ganafagol 6y ago
    As far as I understand, TCO can't be applied in all situations so it may be risky to rely on it. If you need to rely on in (meaning that your program breaks if it's not applied, as opposed to just being a bit slower), then shouldn't the language provide a way to enforce it? That is, the language semantics specifies O(1) memory for tail recursion, for example. If it does not, you are just up for a guessing game and things will break in unexpected ways and moments.
- pjmlp 6y ago
  If not guaranteed by the language specification, e.g. Scheme, you cannot rely on it for certain kinds of algorithms, because it will just blow on your face when changing implementation.
- mcguire 6y ago
  It does have effects on the semantics: without TCO, simple recursion will blow the stack and is therefore a very sketchy technique (few if any specs describe the minimum size of the stack).
  - ganafagol 6y ago
    The C standard does not mention a stack. One can implement a C compiler that puts activation records on the heap or does other magic to avoid a stack that can overflow. A call stack is an implementation detail. Expecting it to exist or not exist is assuming things about the compiler. Those assumptions may be reasonable but are not part of the semantics of the language itself. They are about particular properties of your compiler.
    - mcguire 6y ago
      You are entirely correct[1]. Which is why the Scheme standard says, "Implementations of Scheme must be properly tail-recursive. Procedure calls that occur in certain syntactic contexts called tail contexts are tail calls. A Scheme implementation is properly tail-recursive if it supports an unbounded number of active tail calls. A call is active if the called procedure may still return. Note that this includes regular returns as well as returns through continuations captured earlier by call-with-current-continuation that are later invoked. In the absence of captured continuations, calls could return at most once and the active calls would be those that had not yet returned. A formal definition of proper tail recursion can be found in Clinger's paper [5]. The rules for identifying tail calls in constructs from the (rnrs base (6)) library are described in section 11.20." in Chapter 5, Semantic Concepts (http://www.r6rs.org/final/html/r6rs/r6rs-Z-H-8.html#node_chap_5 http://www.r6rs.org/final/html/r6rs/r6rs-Z-H-8.html#node_cha...). Clinger's paper is "Proper Tail Recursion and Space Efficiency" (https://www.cs.tufts.edu/~nr/cs257/archive/will-clinger/proper-tail-space.pdf https://www.cs.tufts.edu/~nr/cs257/archive/will-clinger/prop...). The Rationale for "properly tail recursive" is, "Intuitively, no space is needed for an active tail call, because the continuation that is used in the tail call has the same semantics as the continuation passed to the procedure containing the call. Although an improper implementation might use a new continuation in the call, a return to this new continuation would be followed immediately by a return to the continuation passed to the procedure. A properly tail-recursive implementation returns to that continuation directly. "Proper tail recursion was one of the central ideas in Steele and Sussman's original version of Scheme. Their first Scheme interpreter implemented both functions and actors. Control flow was expressed using actors, which differed from functions in that they passed their results on to another actor instead of returning to a caller. In the terminology of the report, each actor finished with a tail call to another actor. "Steele and Sussman later observed that in their interpreter the code for dealing with actors was identical to that for functions and thus there was no need to include both in the language. "While a proper tail recursion has been a cornerstone property of Scheme since its inception, it is difficult to implement efficiently on some architectures, specifically those compiling to higher-level intermediate languages such as C or to certain virtual-machine architectures such as JVM or CIL. "Nevertheless, abandoning proper tail recursion as a language property and relegating it to optional optimizations would have far-reaching consequences: Many programs written with the assumption of proper tail recursion would no longer work. Moreover, the lack of proper tail recursion would prevent the natural expression of certain programming styles such as Actors-style message-passing systems, self-replacing servers, or automata written as mutually recursive procedures. Furthermore, if they did not exist, special “loop” constructs would have to be added to the language to compensate for the lack of a general iteration construct. Consequently, proper tail recursion remains an essential aspect of the Scheme language." (http://www.r6rs.org/final/html/r6rs-rationale/r6rs-rationale-Z-H-7.html#node_sec_5.3 http://www.r6rs.org/final/html/r6rs-rationale/r6rs-rationale...) The language specification describes, indirectly, all of the valid programs in the language. With proper tail call elimination as part of the language semantics, simple recursion is a valid iteration technique in those programs. Without proper tail call elimination as part of the language semantics, it is not. [1] Technically, a hardware stack is not required. However, any programming language with a 'function' abstraction will be required to record the return location somewhere (if not function arguments and other stuff); without tail call elimination, the space for those records grows linearly with function call depth, no matter how it is stored.
devwastaken 6y ago
Chrome supports tail call on desktop and mobile for Wasm. Not the same as JS, but it is definitely thought of. Obviously this is just support in the instructions.
DarkWiiPlayer 6y ago
It's sad that browsers decided to do this. In my opinion, this just means that Chrome, Firefox & co. just don't support ES6. They don't support it but with a small foot note, they just don't support it. Period. I just wish we'd live in a world where people were willing to write code using TCE and just say "wontfix" when users of non-compliant browsers complain that "the code crashes", but alas, in 2021 browsers can just choose to not fix non-compliances and blame the website instead. This is just fucked up.
ballenf 6y ago
If you want to play with TCO in a node-type environment, the built-in JSC on MacOS is one option. It doesn't include system integration tools (file operations, etc.) and isn't suitable for production (at least not in any way I'm comfortable with). https://stackoverflow.com/questions/6830192/how-to-run-javascript-using-jsc-on-os-x https://stackoverflow.com/questions/6830192/how-to-run-javas...
pygy_ 6y ago
Safari supports it. Chrome had it ready, behind a feature flag. It was then dumped for FUDdy reasons centered around user concerns that turned out not to be warranted (Safari has proper tail calls per the ES6 spec, and no one complains about it). The truth is that it would have been very expensive for MS to add it to Edge (which was built around incompatible calling conventions), and that cross-realm tail calls (calling into code from another I frame) would be hard to implement in Firefox. Now that Edge switched to Chromium, the only problem left is with FF. It could be spec’ed around, but the consensus in the TC-39 isn’t there anymore :-(
eru 6y ago
For folds over lists you don't need tail call optimization: You just implement them any which way (eg with loops), and the user of those functions never has to know. That's how eg reduce or map or filter work in Python. That holds in general for combinators. Haskell is actually a bad example to use here, because the tail recursive foldl is rarely used. Thanks to laziness, foldr is usually preferred, and it is not tail recursive. OCaml or Scheme are perhaps better references? Especially given the history of Javascript: the author originally wanted to write a Lisp, but got told by management to add curly braces.
- vmchale 6y ago
  > Thanks to laziness, foldr is usually preferred, and it is not tail recursive. With guarded recursion. foldl' has its place.
  - eru 6y ago
    Yes, hence my weasel-y expression of 'usually preferred'.

bjoli 6y ago

It would simplify things a great deal for people compiling to JS. Forcing one looping facility into the behaviour of another can be hard. Implenting just about any looping facility as recursion is a matter of thinking for a while and then sitting down and doing it.

ganafagol 6y ago

Hm what does TCO have to do with a language spec? It impacts neither syntax nor semantics of a language, which is what a language spec should be about. It's a detail of the compiler. So I'm curious what this has to do with the languagr spec? Couldn't a smart compiler/interpreter do this before ES6 already?

KMag 6y ago
"Optimization" is a misnomer with TCO. Optimization implies that only execution speed is affected without the optimization. Without TCO, potentially infinite mutually tail-recursive algorithms (or code transformed into continuation-passing style) can't be implemented without emulating tail recursion using a heap-allocated stack/linked list of states or manually transforming the mutually recursive functions into a trampoline variant of continuation passing style. function factorial(n, accumulator=1) { if (n <= 1) { if (n < 0) throw "Arument must not be negative"; return accumulator; } return factorial(n-1, n * accumulator); } TCO doesn't just affect the speed of this factorial implementation, it greatly affects the largest value that can be computed. It's not to tricky to manually convert tail recursion into a loop, but for mutually recursive functions, you'd probably be best off manually transforming your mutually recursive functions into a trampoline variant of continuation passing, where each function returns a tuple of function and arguments to a trampoline loop that just repeatedly invokes the returned function on the returned arguments. function trampoline(f, ... args) { while (true) { f, args = f(*args); if (args == null) { return f; } } } function fatorial_impl(n, accumulator) if (n <= 1) { if (n < 0) throw "Arument must not be negative"; return [accumulator, null]; } return [factorial_impl, [n-1, n * accumulator]]; } function factorial(n) { return trampoline(factorial_impl, n, 1); } It's all very mechanical, and you'd prefer that the compiler does it. The main argument against TCO is that it's easy for an unobservant programmer to accidentally make a change that prevents TCO. Ideally, the language would have a construct allowing a programmer to cause a given return site to be a syntactic error if it's not a TCO-able tail call.
- kazinator 6y ago
  "optimization" does not imply that only execution speed is impacted.
  - KMag 6y ago
    Fair enough, but in most people's minds, it suggests that the correctness of an implementation doesn't depend on which optimizations are applied, and in this sense, TCO isn't an optimization. TCO isn't merely an optimisation in the same sense of local/global value numbering/common sub-expression elimination , dead-code elimination, loop-invariant expression hoisting, etc.
  - masklinn 6y ago
    > "optimization" does not imply that only execution speed is impacted. No but "optimisation" implies the normally observable semantics are not altered, which is not the case at all with TCE (aka "guaranteed TCO"). Removing TCE from a language makes it a completely different language e.g. Erlang would be severely restricted as it has no imperative loops.
bcherny 6y ago
Automatic TCO affects stack traces, which programs might rely on at runtime, requiring that browsers agree on what the right behavior should be; on the flip side, manual TCO (with annotations) would need to be a language feature.
- EE84M3i 6y ago
  This is the correct answer per the linked article. In particular this is runtime inspectable via func.caller so it really is a behavioral language change to allow the elision of stack frames.
- DarkWiiPlayer 6y ago
  > Automatic TCO affects stack traces, which programs might rely on at runtime, requiring that browsers agree on what the right behavior should be; Browsers don't have a say in this. They're making the decision to not be compliant with the specification, so they effectively don't support ES6.
- pygy_ 6y ago
  Safari supports proper tail calls per the ES6 spec. If your code relies on the non-elimination of tail calls it will not work in Safari, and thus not be Web compatible.
- zelphirkalt 6y ago
  One could argue, that writing programs, which rely on the stack trace is a bad practice. Handling of exceptions should take care of unexpected situations. I don't know of any scenario, where a program needs its own stack trace, which could not be solved by making use of exception handling properly. Perhaps anyone can give an example?
haberman 6y ago
> It impacts neither syntax nor semantics of a language It impacts the correctness of algorithms. For some algorithms it's the difference between using O(1) stack space and O(n) or more, where the latter would blow the stack and effectively crash the program.
im3w1l 6y ago
People want guaranteed TCO so that they can write code relying on it. If TCO ends up not happening such code will leak stack memory or hit max-recursion-limits.
- ganafagol 6y ago
  As far as I understand, TCO can't be applied in all situations so it may be risky to rely on it. If you need to rely on in (meaning that your program breaks if it's not applied, as opposed to just being a bit slower), then shouldn't the language provide a way to enforce it? That is, the language semantics specifies O(1) memory for tail recursion, for example. If it does not, you are just up for a guessing game and things will break in unexpected ways and moments.
pjmlp 6y ago
If not guaranteed by the language specification, e.g. Scheme, you cannot rely on it for certain kinds of algorithms, because it will just blow on your face when changing implementation.
mcguire 6y ago
It does have effects on the semantics: without TCO, simple recursion will blow the stack and is therefore a very sketchy technique (few if any specs describe the minimum size of the stack).
- ganafagol 6y ago
  The C standard does not mention a stack. One can implement a C compiler that puts activation records on the heap or does other magic to avoid a stack that can overflow. A call stack is an implementation detail. Expecting it to exist or not exist is assuming things about the compiler. Those assumptions may be reasonable but are not part of the semantics of the language itself. They are about particular properties of your compiler.
  - mcguire 6y ago
    You are entirely correct[1]. Which is why the Scheme standard says, "Implementations of Scheme must be properly tail-recursive. Procedure calls that occur in certain syntactic contexts called tail contexts are tail calls. A Scheme implementation is properly tail-recursive if it supports an unbounded number of active tail calls. A call is active if the called procedure may still return. Note that this includes regular returns as well as returns through continuations captured earlier by call-with-current-continuation that are later invoked. In the absence of captured continuations, calls could return at most once and the active calls would be those that had not yet returned. A formal definition of proper tail recursion can be found in Clinger's paper [5]. The rules for identifying tail calls in constructs from the (rnrs base (6)) library are described in section 11.20." in Chapter 5, Semantic Concepts (http://www.r6rs.org/final/html/r6rs/r6rs-Z-H-8.html#node_chap_5 http://www.r6rs.org/final/html/r6rs/r6rs-Z-H-8.html#node_cha...). Clinger's paper is "Proper Tail Recursion and Space Efficiency" (https://www.cs.tufts.edu/~nr/cs257/archive/will-clinger/proper-tail-space.pdf https://www.cs.tufts.edu/~nr/cs257/archive/will-clinger/prop...). The Rationale for "properly tail recursive" is, "Intuitively, no space is needed for an active tail call, because the continuation that is used in the tail call has the same semantics as the continuation passed to the procedure containing the call. Although an improper implementation might use a new continuation in the call, a return to this new continuation would be followed immediately by a return to the continuation passed to the procedure. A properly tail-recursive implementation returns to that continuation directly. "Proper tail recursion was one of the central ideas in Steele and Sussman's original version of Scheme. Their first Scheme interpreter implemented both functions and actors. Control flow was expressed using actors, which differed from functions in that they passed their results on to another actor instead of returning to a caller. In the terminology of the report, each actor finished with a tail call to another actor. "Steele and Sussman later observed that in their interpreter the code for dealing with actors was identical to that for functions and thus there was no need to include both in the language. "While a proper tail recursion has been a cornerstone property of Scheme since its inception, it is difficult to implement efficiently on some architectures, specifically those compiling to higher-level intermediate languages such as C or to certain virtual-machine architectures such as JVM or CIL. "Nevertheless, abandoning proper tail recursion as a language property and relegating it to optional optimizations would have far-reaching consequences: Many programs written with the assumption of proper tail recursion would no longer work. Moreover, the lack of proper tail recursion would prevent the natural expression of certain programming styles such as Actors-style message-passing systems, self-replacing servers, or automata written as mutually recursive procedures. Furthermore, if they did not exist, special “loop” constructs would have to be added to the language to compensate for the lack of a general iteration construct. Consequently, proper tail recursion remains an essential aspect of the Scheme language." (http://www.r6rs.org/final/html/r6rs-rationale/r6rs-rationale-Z-H-7.html#node_sec_5.3 http://www.r6rs.org/final/html/r6rs-rationale/r6rs-rationale...) The language specification describes, indirectly, all of the valid programs in the language. With proper tail call elimination as part of the language semantics, simple recursion is a valid iteration technique in those programs. Without proper tail call elimination as part of the language semantics, it is not. [1] Technically, a hardware stack is not required. However, any programming language with a 'function' abstraction will be required to record the return location somewhere (if not function arguments and other stuff); without tail call elimination, the space for those records grows linearly with function call depth, no matter how it is stored.

devwastaken 6y ago

Chrome supports tail call on desktop and mobile for Wasm. Not the same as JS, but it is definitely thought of. Obviously this is just support in the instructions.

DarkWiiPlayer 6y ago

It's sad that browsers decided to do this. In my opinion, this just means that Chrome, Firefox & co. just don't support ES6. They don't support it but with a small foot note, they just don't support it. Period. I just wish we'd live in a world where people were willing to write code using TCE and just say "wontfix" when users of non-compliant browsers complain that "the code crashes", but alas, in 2021 browsers can just choose to not fix non-compliances and blame the website instead. This is just fucked up.

ballenf 6y ago

If you want to play with TCO in a node-type environment, the built-in JSC on MacOS is one option. It doesn't include system integration tools (file operations, etc.) and isn't suitable for production (at least not in any way I'm comfortable with). https://stackoverflow.com/questions/6830192/how-to-run-javascript-using-jsc-on-os-x https://stackoverflow.com/questions/6830192/how-to-run-javas...

pygy_ 6y ago

Safari supports it. Chrome had it ready, behind a feature flag. It was then dumped for FUDdy reasons centered around user concerns that turned out not to be warranted (Safari has proper tail calls per the ES6 spec, and no one complains about it). The truth is that it would have been very expensive for MS to add it to Edge (which was built around incompatible calling conventions), and that cross-realm tail calls (calling into code from another I frame) would be hard to implement in Firefox. Now that Edge switched to Chromium, the only problem left is with FF. It could be spec’ed around, but the consensus in the TC-39 isn’t there anymore :-(

eru 6y ago

For folds over lists you don't need tail call optimization: You just implement them any which way (eg with loops), and the user of those functions never has to know. That's how eg reduce or map or filter work in Python. That holds in general for combinators. Haskell is actually a bad example to use here, because the tail recursive foldl is rarely used. Thanks to laziness, foldr is usually preferred, and it is not tail recursive. OCaml or Scheme are perhaps better references? Especially given the history of Javascript: the author originally wanted to write a Lisp, but got told by management to add curly braces.

vmchale 6y ago
> Thanks to laziness, foldr is usually preferred, and it is not tail recursive. With guarded recursion. foldl' has its place.
- eru 6y ago
  Yes, hence my weasel-y expression of 'usually preferred'.