4 ms·

The problem with tail calls destroying stack traces isn't with the recurse-for-the-tree functions. It's with code like this: function frobnicate_something(fo

The problem with tail calls destroying stack traces isn't with the recurse-for-the-tree functions. It's with code like this: function frobnicate_something(foo, bar) { let baz = antifrobnicate(foo, bar); // Hey, I'm a tail call! return exfoliate_meteor(baz); } With tail calls, you now lose the frobnicate_something stack frame and you just see a call to exfoliate_meteor, which can produce confusing results. This lost stack frame is potentially quite injurious, especially when the function that's lost actually does a serious amount of work. This is the rationale behind the proposal to support tail calls only on explicit scenarios, where the developer opts in to throwing away stack frames.

gumby 4y ago
A tail call is just a goto; using a special syntax for it (`for…` or `while…`) is simply syntactic sugar. Nobody complains about the lack of a stack frame in a for loop.
- ajuc 4y ago
  Goto can be anything - a function call, a loop, an if clause, exception handler. That's the whole reason we created structured programming - so we don't have to guess what it is THIS time. Tail call optimization is nice, but it has its problems. What's the downside to requiring special syntax for it? It frees the programmer reading the code from determining if it's a tail call every time.
  - kreetx 4y ago
    Right, but optimizing tail calls won't lose that structure. But sure, just using goto is a slippery slope to confusion.
    - ajuc 4y ago
      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 this problem whenever you modify a possibly recursive function in a language with transparent TCO - you have to look through the code to see if it's using TCO. This is wasted time. And it can be non-trivial if you have recursive functions calling each other and other funny stuff. If instead the language required special syntax for TCO: function rec(x, y, z) { if (something(z)) { return TAIL_CALL rec(x, y, z-1) + 1; } return 1; } This would be a compilation error cause it's not a tail call contrary to the declaration. What is the downside to requiring special syntax?
      - xigoi 4y ago
        The downside is that most web developers don't care about performance, so they wouldn't bother to use it.
        ajuc 4y ago
        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.
        xigoi 4y ago
        What if you're using it on small data, but inside a loop?
        pflanze 4y ago
        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).
  - hajile 4y ago
    The downside is that your code doesn't optimize for free. iOS is over 50% of the mobile browser share in the US and desktop Safari is 11-12% (roughly 1 in 9) and both implement proper tail calls and have for around 6 years now. Despite this, the world has not collapsed and people aren't constantly complaining that websites are constantly breaking.
kreetx 4y ago
The parent mentioned keeping a list of functions called, so a note on calling frobnicate_something isn't lost.
blagie 4y ago
The proposal to be explicit is fine, but there are alternative proposals which avoid this problem too: - Only tail recurse once the stack is n objects deep. Having a 10,000 element stack trace isn't helpful. - Keep a log of which functions were called, but not a full stack trace of each call. That's O(1). I mentioned both of those in my post.

gumby 4y ago

A tail call is just a goto; using a special syntax for it (`for…` or `while…`) is simply syntactic sugar. Nobody complains about the lack of a stack frame in a for loop.

ajuc 4y ago
Goto can be anything - a function call, a loop, an if clause, exception handler. That's the whole reason we created structured programming - so we don't have to guess what it is THIS time. Tail call optimization is nice, but it has its problems. What's the downside to requiring special syntax for it? It frees the programmer reading the code from determining if it's a tail call every time.
- kreetx 4y ago
  Right, but optimizing tail calls won't lose that structure. But sure, just using goto is a slippery slope to confusion.
  - ajuc 4y ago
    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 this problem whenever you modify a possibly recursive function in a language with transparent TCO - you have to look through the code to see if it's using TCO. This is wasted time. And it can be non-trivial if you have recursive functions calling each other and other funny stuff. If instead the language required special syntax for TCO: function rec(x, y, z) { if (something(z)) { return TAIL_CALL rec(x, y, z-1) + 1; } return 1; } This would be a compilation error cause it's not a tail call contrary to the declaration. What is the downside to requiring special syntax?
    - xigoi 4y ago
      The downside is that most web developers don't care about performance, so they wouldn't bother to use it.
      - ajuc 4y ago
        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.
        xigoi 4y ago
        What if you're using it on small data, but inside a loop?
        pflanze 4y ago
        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).
- hajile 4y ago
  The downside is that your code doesn't optimize for free. iOS is over 50% of the mobile browser share in the US and desktop Safari is 11-12% (roughly 1 in 9) and both implement proper tail calls and have for around 6 years now. Despite this, the world has not collapsed and people aren't constantly complaining that websites are constantly breaking.

kreetx 4y ago

The parent mentioned keeping a list of functions called, so a note on calling frobnicate_something isn't lost.

blagie 4y ago

The proposal to be explicit is fine, but there are alternative proposals which avoid this problem too: - Only tail recurse once the stack is n objects deep. Having a 10,000 element stack trace isn't helpful. - Keep a log of which functions were called, but not a full stack trace of each call. That's O(1). I mentioned both of those in my post.