8 ms·

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

130 points by mindB 4y ago

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
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?
- 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
- 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.
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.
- zeven7 4y ago
  > 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. The only thing you can think of using recursion for is walking the DOM?
  - dgb23 4y ago
    Not specifically walking the DOM but doing DOM/UI related stuff with JS is where I sometimes use recursion. This might also be data processing, but that data is often small and shallow enough for stack growth not not matter, because it is typically related to the UI in _some_ way. I don't typically use JS for heavy computation of large datasets that lend themselves to recursion. The only thing I can think of that is somewhat large is data visualizations and drawing graphs interactively, but there you typically have a matrix or just a flat array.
    - adamddev1 4y ago
      Would be nice to be able process huge arrays recursively.
- asciimov 4y ago
  The utility would be in the computational space, particularly when solving a problem functionally.
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

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

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?

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

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.

zeven7 4y ago
> 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. The only thing you can think of using recursion for is walking the DOM?
- dgb23 4y ago
  Not specifically walking the DOM but doing DOM/UI related stuff with JS is where I sometimes use recursion. This might also be data processing, but that data is often small and shallow enough for stack growth not not matter, because it is typically related to the UI in _some_ way. I don't typically use JS for heavy computation of large datasets that lend themselves to recursion. The only thing I can think of that is somewhat large is data visualizations and drawing graphs interactively, but there you typically have a matrix or just a flat array.
  - adamddev1 4y ago
    Would be nice to be able process huge arrays recursively.
asciimov 4y ago
The utility would be in the computational space, particularly when solving a problem functionally.

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.