More info: 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
More info: 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
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 :-(
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.
With guarded recursion. foldl' has its place.
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.
So I'm curious what this has to do with the languagr spec? Couldn't a smart compiler/interpreter do this before ES6 already?
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.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.
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.
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.
In particular this is runtime inspectable via func.caller so it really is a behavioral language change to allow the elision of stack frames.
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.
"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_cha...). Clinger's paper is "Proper Tail Recursion and Space Efficiency" (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...)
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.
https://stackoverflow.com/questions/6830192/how-to-run-javas...
Obviously this is just support in the instructions.