Live data from Hacker News

What happened to proper tail calls in JavaScript? (2021)

mgmarlow.com

131–140 of 146 posts

Re: What happened to proper tail calls in JavaScript? (2021)

#131
post #126
post #115

Earlier quoted context omitted.

TCO is kinda binary. If you use a recursive function on small data it doesn't matter. If you use it on big data it fails with stack overflow so they will fix it.

What if you're using it on small data, but inside a loop?

AFAICT, your question doesn't make sense. But I guess you are thinking, "what if we should be using the TAIL_CALL syntax for performance but most people don't, and it's exarbated inside a tight loop?" If so, I'll try to explain:

TCO is not about making code faster, it's about making it not eat up all the (stack) memory. It's a memory, not speed, optimization[1]. (OK, using less memory does make it somewhat faster (even when not swapping), too, due to fewer memory accesses, but it's usually not a big difference, and not what we worry about; what we worry about is eating up so much memory that the computer starts swapping because of it, yes, at that point it would become much slower, but that doesn't happen with "small data in a loop"...let me finish.)

Not using the TAIL_CALL syntax in a tail recursion would use up the stack memory iff the recursion is deep (in this context because the data is not small).

If "inside a loop" in your question means, a self-recursive function call (tail recursion),

    function foo(...) {
        if ... {
            foo(...)
        }
    }
then the answer would be, if it's on small data, it only uses a small amount of stack space. No problem. The problem only comes up if the data is large.

If "inside a loop" means that you're using a for or similar loop syntax:

    for ... {
        foo(...)
    }
then a call to a function inside that loop is not actually a tail call (so the compiler would report an error if you were to use the TAIL_CALL syntax), since at least the test in the loop has to run after returning from the function call.

Does that make sense?

[1] And the memory is only being used until the end condition in the recursion is met, i.e. temporarily; it doesn't contribute to bloat, just uses memory for a bit then releases it again; except when it uses so much memory that you run out of RAM (or stack space if the VM limits stack space separately).

Re: What happened to proper tail calls in JavaScript? (2021)

#132
post #107

Earlier quoted context omitted.

> The whole "issue" is very strange to me. Proper tail calls (PTC) without the extra syntax are literally free performance boosts for existing code. It's bad to create a dangerous performance cliff. There could be some TCO based code that works fine, and then a junior coder makes an 'innocent' change that makes it ineligible for TCO, then that code eventually starts getting OOM crashes on heavy data. I think if they'…

This is simply untrue in practice. Almost 52% of mobile web traffic in the US is iOS/Safari which implements proper tail calls. Despite this, we don't get constant stack overflows. A little more than 1 in 9 use desktop Safari which also implements proper tail calls. We also don't see stack overflow issues here either.

It would be the other way around, you'd get the stack overflow issues in non-Safari browsers.

But because nowadays nobody is coding with TCO in mind, there are no such issues.

What paulhodge is pointing out is that once people start coding with the assumption of TCO, then issues crop up when someone changes a tail call into a non-tail call (or, a browser that doesn't implement TCO runs the program).

Re: What happened to proper tail calls in JavaScript? (2021)

#133
post #101
post #91

Earlier quoted context omitted.

Right, but optimizing tail calls won't lose that structure. But sure, just using goto is a slippery slope to confusion.

Optimizing calls using the same syntax as regular ones risk introducing stack overflow without noticing. function rec(x, y, z) { if (something(z)) { return rec(x, y, z-1); } return 1; } Now you need to add 1 to the result. function rec(x, y, z) { if (something(z)) { return rec(x, y, z-1) + 1; } return 1; } Ups, now it fails with stack overflow for big z values. Hope you have good unit tests to catch this. To avoid th…

Idk, rarely (never?) happened to me, that I make a tail call into a non-tail call, because I ad-hoc add something like in your example to it. Seems like a beginner mistake. When I design a function to be tail recursive, which is all the time in langs supporting that, I wont suddenly disregard all care and add code like that. And hopefully other people will at least spent a minute reading the function they are modifying, before slapping that change on and calling it a day. If not, then some syntax wont protect you from that either.

Re: What happened to proper tail calls in JavaScript? (2021)

#134
post #107

Earlier quoted context omitted.

> The whole "issue" is very strange to me. Proper tail calls (PTC) without the extra syntax are literally free performance boosts for existing code. It's bad to create a dangerous performance cliff. There could be some TCO based code that works fine, and then a junior coder makes an 'innocent' change that makes it ineligible for TCO, then that code eventually starts getting OOM crashes on heavy data. I think if they'…

This is simply untrue in practice. Almost 52% of mobile web traffic in the US is iOS/Safari which implements proper tail calls. Despite this, we don't get constant stack overflows. A little more than 1 in 9 use desktop Safari which also implements proper tail calls. We also don't see stack overflow issues here either.

But right now, unless you are developing exclusively against safari, you can't depend on getting TCO. If all browsers implemented it, you could, and you get the performance cliff.

Maybe the performance gains are worth it, but the current situation doesn't really refute the claim that it could be a problem.

Re: What happened to proper tail calls in JavaScript? (2021)

#135
post #112
post #89

Earlier quoted context omitted.

I disagree. My experience with codebases with programmers who program like that is that you eventually get memory leaks, some of which are near-impossible to debug or fix. You pay for that kind of thinking down-the-line. Enabling new design patterns == good Not thinking about what happens under the hood == bad Catastrophes are rare, but expensive enough to cost more than thinking things through.

Where do memory leaks appear more often, in C, or in Python?

My experience is that Python has *many* more memory leaks than C code.

They're less visible since I ran C code on a computer with 32MB of RAM, and I run Python code on a computer with 32GB of RAM, but they're very common in modern Python programs.

As another comment pointed out, memory issues in Python are less dangerous too. I'm glad not to worry about buffer overflows in Python.

Re: What happened to proper tail calls in JavaScript? (2021)

#136
post #35

One advantage of syntactic tail calls is that you can give an error if you are unable to transform to a tail call. Otherwise, you could have a program that seems to work file, and then you refactor and now your recursion isn’t a tail call anymore, and your stack blows up.

I thought the @tailcall annotation in OCaml was cool. It's not essential to use it to receive the optimisation, but rather it's a way to tell the compiler "I need this call to be optimised, so let me know if you can't do it".

Nice! Scala has @tailrec but I think it only checks that a function’s calls to itself are tail calls.

Re: What happened to proper tail calls in JavaScript? (2021)

#137
We should switch on time travel debugging when it’s worthwhile, and be aware of its actual costs, rather than always paying for stack frames because they might serve as an incomplete history (missing loop iterations and calls that already returned).

Re: What happened to proper tail calls in JavaScript? (2021)

#138
post #102

Earlier quoted context omitted.

> It makes it more difficult to understand during debugging how execution arrived at a certain point since the stack contains discontinuities That's a weird complaint, considering that stacks don't describe "how execution arrived at a certain point". In fact, stacks don't describe the past at all; rather, they describe the future of what's left to do (AKA the "continuation"). For example, consider this code: function…

For execution, a stack is a continuation. For debugging, we pretend like it's a historical record, and mostly get away with it. Various things break the correspondence slightly. TCO breaks it a lot more. Debugging is important . It doesn't get enough respect. Stacks are a pretty critical component of debugging, for better or worse. It would be great if we didn't depend on this fiction quite so much. With native code,…

The hardware stack has always been a crutch that in retrospect was probably a bad idea. We use it for jobs it's not well-suited for (like parameter passing, local variables, and debugging) and it has held back better flow control mechanisms like delimited and first-class continuations. And of course TCO, which wouldn't even be a thing if everybody didn't automatically assume a stack pointer was involved with every call. (Hard to imagine? Yes, but plenty of other flow control models exist.)

Stacks are still useful for low-level jobs like register spilling and interrupt handlers, and they make memory management of such data easy. Nevertheless on modern machines with multicore processors running message-passing programs, the limitations of what can be done in high-level code with a one-dimensional stack pointer should now be obvious.

Re: What happened to proper tail calls in JavaScript? (2021)

#139
> Despite its inclusion in the 2015 language specification, PTC is currently only supported by Safari

Kind of related: I kept hearing about how backward Safari is, but is it really bad?

To me even as a web dev myself, the constant stream of new things pushed into modern browsers seem unsustainable. Saying no sometimes doesnt seem clearly bad, especially considering the fact that all browser vendors have some sort of agenda. Safari and Firefox are the only neutral ones but I'm not sure about the latter anymore.

Re: What happened to proper tail calls in JavaScript? (2021)

#140
post #126

Earlier quoted context omitted.

What if you're using it on small data, but inside a loop?

AFAICT, your question doesn't make sense. But I guess you are thinking, "what if we should be using the TAIL_CALL syntax for performance but most people don't, and it's exarbated inside a tight loop?" If so, I'll try to explain: TCO is not about making code faster, it's about making it not eat up all the (stack) memory. It's a memory, not speed, optimization[1]. (OK, using less memory does make it somewhat faster (ev…

> It's a memory, not speed, optimization

I assumed it was a speed optimization too, since a goto is faster than creating a whole stack frame and then destroying it again. Is that not the case?

By “inside a loop”, I meant a loop that is independent of the function, like this:

    function foo() {
      if (…) {
        foo();
      }
    }

    for (let i = 0; i 
Here it won't cause a stack overflow either way (if foo is used on small data), but I'd assume that the loop would amplify the effect of even a small performance optimization.
Post reply on HN