16 ms·

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

130 points by mindB 4y ago

xg15 4y ago
Reads like a sad state of affairs, but the article itself doesn't really explain whatbthe actual concerns where that caused the proposals to be put on ice. From reading, I mostly get "PTC was un-implemented and put on ice because some browser vendors had issues with it; the alternative proposal, STC, was put on ice because other browser vendors had different issues with it. Then everyone (from the browser vendor side) kind of lost interest." But what were the actual issues that blocked the two proposals? Edit: Ah, I'm sorry. The issues with PTC are indeed described, but STC was brought forward specifically to address those reasons. So why wasn't STC implemented then?
- tantalor 4y ago
  It's in the article? 1. more difficult to understand during debugging 2. less information about execution flow which may break telemetry
- munchler 4y ago
  [From the article] Why are browser vendors ignoring PTC? V8 chalks it up to two main reasons: * It makes it more difficult to understand during debugging how execution arrived at a certain point since the stack contains discontinuities, and * error.stack contains less information about execution flow which may break telemetry software that collects and analyzes client-side errors.
  - chriswarbo 4y ago
    > 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 foo() { const bar = someComplexFunction(); performSomeEffect(); baz(bar); } If an error occurs somewhere inside `baz`, the stack trace won't mention anything about `someComplexFunction`, or `performSomeEffect`, or the vast majority of "how we arrived at" the call to `baz`. Yet it will tell us exactly what was remaining to do (namely, `baz` and `foo`). If we eliminate tail calls, stack traces are still an exact description of the continuation. The difference is that "remaining work" doesn't include a bunch of useless identity functions (i.e. redundant stack frames with no further work to do)
    - whizzter 4y ago
      If you're writing imperative code with side-effects (or mixed-style) like much classic JS code is, the existence of foo on the call stack indicates that performSomeEffect has been run, and thus it's side-effects on our global state when we enter baz has to be accounted for. Is it an ideal style to write code in? No. Does real code have this problem, Yes!
    - int_19h 4y ago
      Stack frames also capture locals, and those often provide a lot of information about what just happened. I've had cases before where this was instrumental to figuring out the cause of the bug, and other cases where it likely would have been if TCO hasn't wiped out that information (in C++).
    - sfink 4y ago
      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, there are definitely alternative options now, such as rr[1] and Pernosco[2] where if you want to look back in time—well, you just go back in time. For JavaScript, that's becoming more and more possible with things like Replay[3]. Perhaps before long, the debugging argument will just go away. [1] https://rr-project.org/ https://rr-project.org/ [2] https://pernos.co/ https://pernos.co/ [3] https://www.replay.io/ https://www.replay.io/
      - dreamcompiler 4y ago
        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.
  - dmitriid 4y ago
    This is such a weird complaint given that Erlang exists, with tail calls, and proper async, and..., and is used to create complex software
- richdougherty 4y ago
  The spec for STC has a critique of PTC: - performance - developer tools - Error.stack - cross-realm tail calls - developer intent See: https://github.com/tc39/proposal-ptc-syntax#issues-with-ptc https://github.com/tc39/proposal-ptc-syntax#issues-with-ptc Apple's 2016 response as to why they won't implement STC is here: https://github.com/tc39/ecma262/issues/535 https://github.com/tc39/ecma262/issues/535 - STC is part of the spec and will take too long to change. - Now that they've implemented support for PTC, they don't want to regress web pages that rely on it. - They don't want to discourage vendors from implementing PTC by agreeing to STC. - They don't want to introduce confusion. Some of these arguments about confusion and delays seem wrong hindsight, since on every point things would have been better if they'd just agreed to the compromise of STC. - It would have been part of the spec years ago - STC would have had a clear way for web pages to know when tail calls could be relied on (and PTC would have been optional) - Other vendors didn't implement PTC in any case, despite no agreement on STC - There's even more confusion as things are now
RcouF1uZ4gsC 4y ago
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.
- ape4 4y ago
  Perhaps with a syntax for tail calls, you could do it not at the end of a function.
  - richdougherty 4y ago
    It needs to be at the end of the calling function so you can throw the calling function's stack frame away, since it's still in use. Getting rid of the calling stack frame is what proper tail calls is about.
    - ape4 4y ago
      I was suggesting something like bash `exec`
- frou_dh 4y ago
  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".
  - erik_seaberg 4y ago
    Nice! Scala has @tailrec but I think it only checks that a function’s calls to itself are tail calls.
- mst 4y ago
  https://reviews.llvm.org/D99517 https://reviews.llvm.org/D99517 is really quite interesting.
k__ 4y ago
I had the impression, the ECMAScript spec would only accept proposals "after" they were implemented by the major players. How did PTC sneak into the spec?
- Kwantuum 4y ago
  from the linked PTC proposal in the article (https://github.com/tc39/proposal-ptc-syntax https://github.com/tc39/proposal-ptc-syntax): > Unfortunately, the TC39 process at this time did not require heavy implementation involvement and so while many implementers were skeptical, the feature was included and standardized as part of ES6.
- cwmma 4y ago
  It predates the current model individual proposals that are worked on separately.
- kall 4y ago
  Aside from the points below, it's implemented in Safari IIRC?
  - hajile 4y ago
    It was also implemented in v8
tomxor 4y ago
I've ended up writing a number of things in an equivalent iterative way due to this... which in retrospect feels like a positive thing because I find it far clearer.
- shadowofneptune 4y ago
  There are some forms of control flow which are difficult or impossible to represent in an iterative manner. The big example is VMs, where tail calls or goto provide noticable performance improvements over a large switch statement in a loop. Compilers have trouble optimizing such a large function, just as people have more issues maintaining one. For what it's worth, syntactic tail calls seem to be the way to go when adding this to imperative languages, as it gives more control over stack usage. The WebAssembly VM has a proposal for a 'return_call' instruction, and rust has a reserved 'becomes' keyword.
leoh 4y ago
Worth reading why python doesn’t have it either http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html http://neopythonic.blogspot.com/2009/04/tail-recursion-elimi...
- duxup 4y ago
  > Python's default is and should always be to be maximally helpful for debugging. I can’t say I understand the whole topic but when someone who knows more than me says that…. It is a pretty compelling argument to me.
  - ynniv 4y ago
    It's kind of a weird argument though. How do you expect a for loop to be represented in a stack trace?
    - foldr 4y ago
      The problem that’s hard to get around is this: https://github.com/elixir-lang/elixir/issues/6357 https://github.com/elixir-lang/elixir/issues/6357 Tail calls don’t have to be recursive. See also this old thread: https://news.ycombinator.com/item?id=5376924 https://news.ycombinator.com/item?id=5376924
      - ynniv 4y ago
        Good point, but surely there's a compromise somewhere. Keep the first TCO'd frame for reference maybe? Perfect stack traces aren't required.
        foldr 4y ago
        Yeah, that could work in principle. However, if it's a language that’s using recursion for looping, then you'll loose that history every time you have a loop with more than n iterations (which could be quite often). Given that recursion can be indirect, you can't entirely eliminate that problem just by special casing direct recursion. It might still be better than nothing, though, I agree.
emilecantin 4y ago
I've seen a lot of chatter about tail calls, but I don't think I've ever seen actual examples of what they look like. Does anyone use them or is it just something for language nerds to obsess about?
- suprfsat 4y ago
  Any time a function ends by calling another function and doesn't do anything else besides perhaps return the value you're using a tail call. It's just the name for a function call that's in tail position.
  - User23 4y ago
    > Any time a function ends by calling another function and doesn't do anything else besides perhaps return the value you're using a tail call. It's just the name for a function call that's in tail position It sounds like you already know this, but many people, including myself at one time, think of tail call optimization as a trick for not blowing up the stack when writing recursive functions. However, it's much more general. Tail call optimization doesn't have to be recursive, it can be applied any time the final statement or expression of a function is another function call. It's something like a special form of inlining. And as you say, it's actually possible to apply the optimization in limited cases where the tail called function returns a value![2] That general optimization is very useful for implementing threaded[1] or continuation passing style VMs since it compiles function calls and all their associated baggage down to a jump and maybe some assignments. [1] Forth style, not multithreading. [2] http://jamesrwilcox.com/tail-mod-cons.html http://jamesrwilcox.com/tail-mod-cons.html
    - pessimizer 4y ago
      For me the mental leap was that when I call a function, what I'm saying is "do this, then come back to me so I can finish." What if I don't care if the function comes back, because I've already done all the work I need to do? What if I'm really just handing off my results to the function for it to finish the job itself? Then I should give the function the address of whoever called me, and leave. The function I'm calling is replacing me, not assisting me. If a call stack is a series of waypoints that have to be revisited in reverse after a goal is achieved, with a tail call I'm saying "don't bother coming back to me." I might leave my house, go to an ATM, then go to the grocery store to do my shopping. TCO means that I don't have to stop by the ATM again on the way home. So my mental model actually doesn't have anything to do with recursion.
del_operator 4y ago
Stack frames iirc
thayne 4y ago
So, what happened to syntactic tail calls? I think that's what I would prefer anyway, both because it makes it more clear from a debugging standpoint, since you opt in, and because you can get a warning (or compiler/linter error if using a transpiler or linter) when your function isn't actually tail recursive.
- hajile 4y ago
  The whole "issue" is very strange to me. Proper tail calls (PTC) without the extra syntax are literally free performance boosts for existing code. The whole "stack frames" argument is a red herring: * Nobody expects stack frames to exist for every `for` loop which is the biggest practical use for PTC * Stack frames go away the second you release control back to the event loop which is by far the more pernicious problem. * Stack frames essentially just capture the continuation anyway. If my function `blah()` calls `foo()` and `bar()` before blowing up on `baz()`, neither of those functions will be captured by the stack frame which is no different than a CPS (continuous passing style) with PTC where you have `foo()` that returns `bar()` that returns `baz()` and `baz` throws. In BOTH cases, you'll see the stack frame for `baz`, a stack frame for `blah()` and frames for whatever called `blah()` up to the top of the stack or where the event loop made the stack frames disappear anyway. * EDIT: I almost forgot to mention, but you can activate a "shadow stack" when the debugger is open (just like they already disable most optimizations when it's open) which can give you your reams of useless stack traces as your function executes a million times in a loop. In short, programmers have performance to gain and not much of real value to lose by implementing PTC without syntax.
  - kevingadd 4y ago
    > Stack frames go away the second you release control back to the event loop which is by far the more pernicious problem. Sadly the opposite is true today: If you're doing async/await programming in Chrome (and Firefox too, I think?) the runtime actually tries to carry your stack across event loop turns and this will be visible in Error.stack. This happens even with the debugger closed in my experience (the massive stacks are really annoying)
dgb23 4y ago
I use recursion in JS when implementing generic trees/dags. I'm not worried at all about growing the stack because I use the language for UI stuff, where the depth of the trees is quite shallow and the data is small overall. I don't really know what the utility of TCO/proper tail calls would be. You already have UX constraints that nudge to avoid having a ton of stuff on the screen. As an example of where recursion of generic trees could be applied in a UI: Look at HN threads. Even exceptionally large threads have what, a couple hundred responses? With depth of maybe a dozen? Also you typically have affordances to navigate such a tree and only see the parts of it that you want. So it becomes even more trivially small.
- leroman 4y ago
  Javascript is also a very popular back-end language (Node JS)..
  - dgb23 4y ago
    Yes, but even there it is typically used for stuff that leans towards front-end. People don't typically write databases and messaging systems in Nodejs. I wonder about specific use cases where stack allocating recursion actually becomes an issue in the JS world.
    - zeven7 4y ago
      People do a lot more in JavaScript than you realize.
      - dgb23 4y ago
        That's what I'm wondering about. When was the last time you blew the stack with JS and what did you try to accomplish? Another commenter said they had problems walking a dependency graph.
        zeven7 4y ago
        For some examples: People have 3D game engines running in JavaScript. There's a lot of cryptographic work in JavaScript, including but not limited to cryptocurrencies - a lot of groundbreaking stuff from a technological perspective. Full blown emulators, developer tools, virtual machines... the world of JavaScript is way larger than CRUD applications.
asciimov 4y ago
After thinking about this for a bit, the decision to avoid including this functionality is probably for the best. Even though I would love for this feature to exist, I can see people unintentionally shooting themselves in the foot and not understanding why. Often when you run up against call stack limitations, you actually need to reconsider the algorithm being used. Trampolines can be used to bypass the call stack limitation. As an advanced technique, the majority of people having issues with a call stack problem will reconsider their solution before thinking about jumping on the trampoline.
- hajile 4y ago
  How can this be bad or a footgun? If the algorithm can be PTC optimized, then it is and everything works as efficiently as possible. If not, then it blows the stack either way. Finally, a trampoline is objectively worse. The programmer has to have an even bigger understanding of tail calls. Trampolines involving complex patterns are MUCH more difficult to follow. The trampoline is implemented in JS rather than C++. The trampoline will require additional function overhead that cannot really be eliminated. The Trampoline isn't anywhere near as optimizable by the JIT either. Trampolines are all downsides in comparison with proper tail calls.
  - asciimov 4y ago
    > How can this be bad or a footgun? You are coming from the side of someone who already has a a well planned algorithm that doesn't get stuck in infinite looping or end up diving too deep. My concern was for those without a well planned algorithm, who don't see that it can get stuck in a loop or dives too deep too quickly. In these situations blowing your stack is a good indication you have a problem. This is just my bias of dealing with programmers who don't do well with recursion or love to introduce function call hell.
    - hajile 4y ago
      52% of mobile traffic runs on iOS which implements PTC, but the world doesn't end. 1 in 9 desktops use Safari which also implements PTC without issue. They've been using PTC since 2016 as I recall and all the complaints that the world would break simply haven't happened.
blagie 4y ago
For the most part, programming constructs like these split the world into two camps: - People who point out things can be done without them, who largely see them as useless due to lack of familiarity - People who've used them, and see critical ways to restructure code to make it cleaner using said constructs That's been the case for a lot of progress in programming. Python, and ES2015, have done a wonderful job of bringing many previously-academic (including functional) programming constructs to a broader community, together with models like reactive programming. That's true of about half of the bits of progress in programming. Garbage collection was seen as garbage by C/C++ programmers ("What's the big deal with adding a free() call? Stupid lazy people."). Garbage collections wasn't useful because it omitted free() calls, but because it allowed the design of flows with many exit points (for example, different kinds of exception handling, exiting in the middle of a function, or giving up an object in a half-dozen places an hour later in code where tracking for free() requires building an ad-hoc reference counter or garbage collector). The place where tail calls are a huge deal is when dealing with deep (or even infinitely deep) tree-like structures: if condition: return red(left_child) else: return blue(right_child) I don't mind opt-in versus opt-out versus neither. All the reasons listed for not having them are dumb, though, and have good and easy work-arounds. The major one -- debugging -- it's basically always good enough to just have a list of functions called, without having the whole tree. A 10,000 element stack trace is no help at all. You can, for example, keep the first 20 elements of the stack trace (don't start PTCs unless the stack is of a certain depth), and then still keep a list of functions called: ipython webapp.main webapp.handler render.make_tree [PTC: render.red*91001, render.blue*10201] webapp.callback I have literally never seen a case where having a list of 100k calls in a stack traces is at all useful for anything.
- PathOfEclipse 4y ago
  On a tangent, I've always felt garbage collection, and, more importantly, safe memory management, was important because it allows you to mostly pretend that memory allocation isn't a globally side-effecting operation, as such operations are difficult to reason about. It's the same logic that leads to design choices that don't explicitly use global variables or global state. In reality, all memory allocation is still globally side-effecting, and you'll find that out when your program starts GC spiraling, or consuming more memory than you want it to, but being able to pretend otherwise and mostly get away with it means automatic memory management brings a tangible, measurable productivity multiplier to programming that few, if any, other programming language features can boast of.
kreetx 4y ago
The few real world discussions I've had about the topic of tail calls revealed that people mostly don't know about them and are thus more "afraid of the unknown" rather than against the thing itself.
adamddev1 4y ago
Someone start a petition page. :-)
erik_seaberg 4y ago
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).
nsonha 4y ago
> 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.

130 points by mindB 4y ago

xg15 4y ago

Reads like a sad state of affairs, but the article itself doesn't really explain whatbthe actual concerns where that caused the proposals to be put on ice. From reading, I mostly get "PTC was un-implemented and put on ice because some browser vendors had issues with it; the alternative proposal, STC, was put on ice because other browser vendors had different issues with it. Then everyone (from the browser vendor side) kind of lost interest." But what were the actual issues that blocked the two proposals? Edit: Ah, I'm sorry. The issues with PTC are indeed described, but STC was brought forward specifically to address those reasons. So why wasn't STC implemented then?

tantalor 4y ago
It's in the article? 1. more difficult to understand during debugging 2. less information about execution flow which may break telemetry
munchler 4y ago
[From the article] Why are browser vendors ignoring PTC? V8 chalks it up to two main reasons: * It makes it more difficult to understand during debugging how execution arrived at a certain point since the stack contains discontinuities, and * error.stack contains less information about execution flow which may break telemetry software that collects and analyzes client-side errors.
- chriswarbo 4y ago
  > 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 foo() { const bar = someComplexFunction(); performSomeEffect(); baz(bar); } If an error occurs somewhere inside `baz`, the stack trace won't mention anything about `someComplexFunction`, or `performSomeEffect`, or the vast majority of "how we arrived at" the call to `baz`. Yet it will tell us exactly what was remaining to do (namely, `baz` and `foo`). If we eliminate tail calls, stack traces are still an exact description of the continuation. The difference is that "remaining work" doesn't include a bunch of useless identity functions (i.e. redundant stack frames with no further work to do)
  - whizzter 4y ago
    If you're writing imperative code with side-effects (or mixed-style) like much classic JS code is, the existence of foo on the call stack indicates that performSomeEffect has been run, and thus it's side-effects on our global state when we enter baz has to be accounted for. Is it an ideal style to write code in? No. Does real code have this problem, Yes!
  - int_19h 4y ago
    Stack frames also capture locals, and those often provide a lot of information about what just happened. I've had cases before where this was instrumental to figuring out the cause of the bug, and other cases where it likely would have been if TCO hasn't wiped out that information (in C++).
  - sfink 4y ago
    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, there are definitely alternative options now, such as rr[1] and Pernosco[2] where if you want to look back in time—well, you just go back in time. For JavaScript, that's becoming more and more possible with things like Replay[3]. Perhaps before long, the debugging argument will just go away. [1] https://rr-project.org/ https://rr-project.org/ [2] https://pernos.co/ https://pernos.co/ [3] https://www.replay.io/ https://www.replay.io/
    - dreamcompiler 4y ago
      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.
- dmitriid 4y ago
  This is such a weird complaint given that Erlang exists, with tail calls, and proper async, and..., and is used to create complex software
richdougherty 4y ago
The spec for STC has a critique of PTC: - performance - developer tools - Error.stack - cross-realm tail calls - developer intent See: https://github.com/tc39/proposal-ptc-syntax#issues-with-ptc https://github.com/tc39/proposal-ptc-syntax#issues-with-ptc Apple's 2016 response as to why they won't implement STC is here: https://github.com/tc39/ecma262/issues/535 https://github.com/tc39/ecma262/issues/535 - STC is part of the spec and will take too long to change. - Now that they've implemented support for PTC, they don't want to regress web pages that rely on it. - They don't want to discourage vendors from implementing PTC by agreeing to STC. - They don't want to introduce confusion. Some of these arguments about confusion and delays seem wrong hindsight, since on every point things would have been better if they'd just agreed to the compromise of STC. - It would have been part of the spec years ago - STC would have had a clear way for web pages to know when tail calls could be relied on (and PTC would have been optional) - Other vendors didn't implement PTC in any case, despite no agreement on STC - There's even more confusion as things are now

RcouF1uZ4gsC 4y ago

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.

ape4 4y ago
Perhaps with a syntax for tail calls, you could do it not at the end of a function.
- richdougherty 4y ago
  It needs to be at the end of the calling function so you can throw the calling function's stack frame away, since it's still in use. Getting rid of the calling stack frame is what proper tail calls is about.
  - ape4 4y ago
    I was suggesting something like bash `exec`
frou_dh 4y ago
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".
- erik_seaberg 4y ago
  Nice! Scala has @tailrec but I think it only checks that a function’s calls to itself are tail calls.
mst 4y ago
https://reviews.llvm.org/D99517 https://reviews.llvm.org/D99517 is really quite interesting.

k__ 4y ago

I had the impression, the ECMAScript spec would only accept proposals "after" they were implemented by the major players. How did PTC sneak into the spec?

Kwantuum 4y ago
from the linked PTC proposal in the article (https://github.com/tc39/proposal-ptc-syntax https://github.com/tc39/proposal-ptc-syntax): > Unfortunately, the TC39 process at this time did not require heavy implementation involvement and so while many implementers were skeptical, the feature was included and standardized as part of ES6.
cwmma 4y ago
It predates the current model individual proposals that are worked on separately.
kall 4y ago
Aside from the points below, it's implemented in Safari IIRC?
- hajile 4y ago
  It was also implemented in v8

tomxor 4y ago

I've ended up writing a number of things in an equivalent iterative way due to this... which in retrospect feels like a positive thing because I find it far clearer.

shadowofneptune 4y ago
There are some forms of control flow which are difficult or impossible to represent in an iterative manner. The big example is VMs, where tail calls or goto provide noticable performance improvements over a large switch statement in a loop. Compilers have trouble optimizing such a large function, just as people have more issues maintaining one. For what it's worth, syntactic tail calls seem to be the way to go when adding this to imperative languages, as it gives more control over stack usage. The WebAssembly VM has a proposal for a 'return_call' instruction, and rust has a reserved 'becomes' keyword.

leoh 4y ago

Worth reading why python doesn’t have it either http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html http://neopythonic.blogspot.com/2009/04/tail-recursion-elimi...

duxup 4y ago
> Python's default is and should always be to be maximally helpful for debugging. I can’t say I understand the whole topic but when someone who knows more than me says that…. It is a pretty compelling argument to me.
- ynniv 4y ago
  It's kind of a weird argument though. How do you expect a for loop to be represented in a stack trace?
  - foldr 4y ago
    The problem that’s hard to get around is this: https://github.com/elixir-lang/elixir/issues/6357 https://github.com/elixir-lang/elixir/issues/6357 Tail calls don’t have to be recursive. See also this old thread: https://news.ycombinator.com/item?id=5376924 https://news.ycombinator.com/item?id=5376924
    - ynniv 4y ago
      Good point, but surely there's a compromise somewhere. Keep the first TCO'd frame for reference maybe? Perfect stack traces aren't required.
      - foldr 4y ago
        Yeah, that could work in principle. However, if it's a language that’s using recursion for looping, then you'll loose that history every time you have a loop with more than n iterations (which could be quite often). Given that recursion can be indirect, you can't entirely eliminate that problem just by special casing direct recursion. It might still be better than nothing, though, I agree.

emilecantin 4y ago

I've seen a lot of chatter about tail calls, but I don't think I've ever seen actual examples of what they look like. Does anyone use them or is it just something for language nerds to obsess about?

suprfsat 4y ago
Any time a function ends by calling another function and doesn't do anything else besides perhaps return the value you're using a tail call. It's just the name for a function call that's in tail position.
- User23 4y ago
  > Any time a function ends by calling another function and doesn't do anything else besides perhaps return the value you're using a tail call. It's just the name for a function call that's in tail position It sounds like you already know this, but many people, including myself at one time, think of tail call optimization as a trick for not blowing up the stack when writing recursive functions. However, it's much more general. Tail call optimization doesn't have to be recursive, it can be applied any time the final statement or expression of a function is another function call. It's something like a special form of inlining. And as you say, it's actually possible to apply the optimization in limited cases where the tail called function returns a value![2] That general optimization is very useful for implementing threaded[1] or continuation passing style VMs since it compiles function calls and all their associated baggage down to a jump and maybe some assignments. [1] Forth style, not multithreading. [2] http://jamesrwilcox.com/tail-mod-cons.html http://jamesrwilcox.com/tail-mod-cons.html
  - pessimizer 4y ago
    For me the mental leap was that when I call a function, what I'm saying is "do this, then come back to me so I can finish." What if I don't care if the function comes back, because I've already done all the work I need to do? What if I'm really just handing off my results to the function for it to finish the job itself? Then I should give the function the address of whoever called me, and leave. The function I'm calling is replacing me, not assisting me. If a call stack is a series of waypoints that have to be revisited in reverse after a goal is achieved, with a tail call I'm saying "don't bother coming back to me." I might leave my house, go to an ATM, then go to the grocery store to do my shopping. TCO means that I don't have to stop by the ATM again on the way home. So my mental model actually doesn't have anything to do with recursion.

del_operator 4y ago

Stack frames iirc

thayne 4y ago

So, what happened to syntactic tail calls? I think that's what I would prefer anyway, both because it makes it more clear from a debugging standpoint, since you opt in, and because you can get a warning (or compiler/linter error if using a transpiler or linter) when your function isn't actually tail recursive.

hajile 4y ago
The whole "issue" is very strange to me. Proper tail calls (PTC) without the extra syntax are literally free performance boosts for existing code. The whole "stack frames" argument is a red herring: * Nobody expects stack frames to exist for every `for` loop which is the biggest practical use for PTC * Stack frames go away the second you release control back to the event loop which is by far the more pernicious problem. * Stack frames essentially just capture the continuation anyway. If my function `blah()` calls `foo()` and `bar()` before blowing up on `baz()`, neither of those functions will be captured by the stack frame which is no different than a CPS (continuous passing style) with PTC where you have `foo()` that returns `bar()` that returns `baz()` and `baz` throws. In BOTH cases, you'll see the stack frame for `baz`, a stack frame for `blah()` and frames for whatever called `blah()` up to the top of the stack or where the event loop made the stack frames disappear anyway. * EDIT: I almost forgot to mention, but you can activate a "shadow stack" when the debugger is open (just like they already disable most optimizations when it's open) which can give you your reams of useless stack traces as your function executes a million times in a loop. In short, programmers have performance to gain and not much of real value to lose by implementing PTC without syntax.
- kevingadd 4y ago
  > Stack frames go away the second you release control back to the event loop which is by far the more pernicious problem. Sadly the opposite is true today: If you're doing async/await programming in Chrome (and Firefox too, I think?) the runtime actually tries to carry your stack across event loop turns and this will be visible in Error.stack. This happens even with the debugger closed in my experience (the massive stacks are really annoying)

dgb23 4y ago

I use recursion in JS when implementing generic trees/dags. I'm not worried at all about growing the stack because I use the language for UI stuff, where the depth of the trees is quite shallow and the data is small overall. I don't really know what the utility of TCO/proper tail calls would be. You already have UX constraints that nudge to avoid having a ton of stuff on the screen. As an example of where recursion of generic trees could be applied in a UI: Look at HN threads. Even exceptionally large threads have what, a couple hundred responses? With depth of maybe a dozen? Also you typically have affordances to navigate such a tree and only see the parts of it that you want. So it becomes even more trivially small.

leroman 4y ago
Javascript is also a very popular back-end language (Node JS)..
- dgb23 4y ago
  Yes, but even there it is typically used for stuff that leans towards front-end. People don't typically write databases and messaging systems in Nodejs. I wonder about specific use cases where stack allocating recursion actually becomes an issue in the JS world.
  - zeven7 4y ago
    People do a lot more in JavaScript than you realize.
    - dgb23 4y ago
      That's what I'm wondering about. When was the last time you blew the stack with JS and what did you try to accomplish? Another commenter said they had problems walking a dependency graph.
      - zeven7 4y ago
        For some examples: People have 3D game engines running in JavaScript. There's a lot of cryptographic work in JavaScript, including but not limited to cryptocurrencies - a lot of groundbreaking stuff from a technological perspective. Full blown emulators, developer tools, virtual machines... the world of JavaScript is way larger than CRUD applications.

asciimov 4y ago

After thinking about this for a bit, the decision to avoid including this functionality is probably for the best. Even though I would love for this feature to exist, I can see people unintentionally shooting themselves in the foot and not understanding why. Often when you run up against call stack limitations, you actually need to reconsider the algorithm being used. Trampolines can be used to bypass the call stack limitation. As an advanced technique, the majority of people having issues with a call stack problem will reconsider their solution before thinking about jumping on the trampoline.

hajile 4y ago
How can this be bad or a footgun? If the algorithm can be PTC optimized, then it is and everything works as efficiently as possible. If not, then it blows the stack either way. Finally, a trampoline is objectively worse. The programmer has to have an even bigger understanding of tail calls. Trampolines involving complex patterns are MUCH more difficult to follow. The trampoline is implemented in JS rather than C++. The trampoline will require additional function overhead that cannot really be eliminated. The Trampoline isn't anywhere near as optimizable by the JIT either. Trampolines are all downsides in comparison with proper tail calls.
- asciimov 4y ago
  > How can this be bad or a footgun? You are coming from the side of someone who already has a a well planned algorithm that doesn't get stuck in infinite looping or end up diving too deep. My concern was for those without a well planned algorithm, who don't see that it can get stuck in a loop or dives too deep too quickly. In these situations blowing your stack is a good indication you have a problem. This is just my bias of dealing with programmers who don't do well with recursion or love to introduce function call hell.
  - hajile 4y ago
    52% of mobile traffic runs on iOS which implements PTC, but the world doesn't end. 1 in 9 desktops use Safari which also implements PTC without issue. They've been using PTC since 2016 as I recall and all the complaints that the world would break simply haven't happened.

blagie 4y ago

For the most part, programming constructs like these split the world into two camps: - People who point out things can be done without them, who largely see them as useless due to lack of familiarity - People who've used them, and see critical ways to restructure code to make it cleaner using said constructs That's been the case for a lot of progress in programming. Python, and ES2015, have done a wonderful job of bringing many previously-academic (including functional) programming constructs to a broader community, together with models like reactive programming. That's true of about half of the bits of progress in programming. Garbage collection was seen as garbage by C/C++ programmers ("What's the big deal with adding a free() call? Stupid lazy people."). Garbage collections wasn't useful because it omitted free() calls, but because it allowed the design of flows with many exit points (for example, different kinds of exception handling, exiting in the middle of a function, or giving up an object in a half-dozen places an hour later in code where tracking for free() requires building an ad-hoc reference counter or garbage collector). The place where tail calls are a huge deal is when dealing with deep (or even infinitely deep) tree-like structures: if condition: return red(left_child) else: return blue(right_child) I don't mind opt-in versus opt-out versus neither. All the reasons listed for not having them are dumb, though, and have good and easy work-arounds. The major one -- debugging -- it's basically always good enough to just have a list of functions called, without having the whole tree. A 10,000 element stack trace is no help at all. You can, for example, keep the first 20 elements of the stack trace (don't start PTCs unless the stack is of a certain depth), and then still keep a list of functions called: ipython webapp.main webapp.handler render.make_tree [PTC: render.red*91001, render.blue*10201] webapp.callback I have literally never seen a case where having a list of 100k calls in a stack traces is at all useful for anything.

PathOfEclipse 4y ago
On a tangent, I've always felt garbage collection, and, more importantly, safe memory management, was important because it allows you to mostly pretend that memory allocation isn't a globally side-effecting operation, as such operations are difficult to reason about. It's the same logic that leads to design choices that don't explicitly use global variables or global state. In reality, all memory allocation is still globally side-effecting, and you'll find that out when your program starts GC spiraling, or consuming more memory than you want it to, but being able to pretend otherwise and mostly get away with it means automatic memory management brings a tangible, measurable productivity multiplier to programming that few, if any, other programming language features can boast of.

kreetx 4y ago

The few real world discussions I've had about the topic of tail calls revealed that people mostly don't know about them and are thus more "afraid of the unknown" rather than against the thing itself.

adamddev1 4y ago

Someone start a petition page. :-)

erik_seaberg 4y ago

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).

nsonha 4y ago

> 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.