1. 1
  1.  

  2. 3

    As of this writing, tail-call elimination is in the ES6 spec for JavaScript

    The way I remember it, tail call elimination was added to ES6 in 2015, Google implemented it in Chrome, but then reverted the change due to problems this caused for developers: https://v8.dev/blog/modern-javascript#proper-tail-calls.

    1. 2

      Thanks for the link! I hadn’t heard why Chrome put TCO implementation on hold nor about their syntactic tail calls proposal. Interesting.

      1. 4

        It’s slightly worse than that link makes it appear. There are two things that make tail-call elimination difficult to implement correctly:

        If the calling convention imposes stack cleanup requirements that contradict tail calls. For example, if the callee is required to clean up the stack then the function doing the tail call can set up the new callee’s argument frame and everything is fine. If the caller is responsible for cleaning up the stack then you can only tail call functions that require the same amount of stack space or less for arguments. This is the thing that makes tail call elimination difficult in C, because supporting variadic functions means that the caller must be responsible for cleaning up the stack (the callee doesn’t know how many arguments there are and so doesn’t have enough information to do the cleanup). This should not be a problem for JavaScript, because the JIT is in complete control of the calling convention and can simply pick one that is amenable to the optimisation (technically, all JavaScript functions are variadic, but in practice the JIT can optimise for the cases where the caller and callee agree on the argument count and have a slow path for the first time it encounters a mismatch).

        The second problem is more common in higher-level languages: does your language expose any details of the call stack to introspection? In Smalltalk, there isn’t a stack in the abstract machine, there is a linked list of garbage-collected activation records. Closures capture the activation record where they were created and so can outlive the call frame. More importantly (in this context), the current activation record is exposed into the language as thisContext and you can write code that inspects this and follows the chain to go and inspect all of the higher-level activation records. This lets you implement complex exception-handling logic entirely in a library, for example. The Chrome link talks about the fact that JavaScript exceptions capture the stack, which makes tail-call elimination painful for debugging. In non-standard (but widely supported, though deprecated) JavaScript, there is also a caller property on each function, which contains a pointer to the most recent caller on the stack. I don’t know if this is the only other way of doing stack introspection in JavaScript, but even the simple thing of throwing and catching an exception in the same function and then using it to inspect the captured stack (as hinted to in the Chrome proposal) means that it’s very difficult to implement tail-call elimination in a way that doesn’t alter the programmer-visible language semantics.

        In general, a language has to pick one out of tail-call elimination and stack introspection. C/C++ are in a somewhat interesting middle ground where both the mechanism for stack unwinding and the presence of tail-call elimination are both implementation defined and so any given compiler / runtime can pick the one it wants.