Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

mgmarlow.com

Post reply on HN
Print view View original

51–60 of 146 posts

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

#51

Post by dgb23 »

tlb wrote: post #48
dgb23 wrote: post #32

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 o…

I ran out of JS stack, walking the dependency graph of a big computation. Dependency graphs can be very deep relative to their overall size. It was a big pain to rewrite with an explicit stack of to-be-visited nodes. TCO wouldn't have saved me, though. It just needs a big stack. Node defaults to just under 1 MB, which doesn't go very far.

That's interesting and quite valid, haven't thought of this. And I agree, recursion is often more intuitive and concise for these things.

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

#52

Post by foldr »

ynniv wrote: post #39
foldr wrote: post #18

Earlier quoted context omitted.

The problem that’s hard to get around is this: 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

Good point, but surely there's a compromise somewhere. Keep the first TCO'd frame for reference maybe? Perfect stack traces aren't required.

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.

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

#53

Post by asciimov »

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.

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

#54

Post by hajile »

thayne wrote: post #22

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.

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.

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

#55

Post by adamddev1 »

asciimov wrote: post #44
dgb23 wrote: post #32

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 o…

The utility would be in the computational space, particularly when solving a problem functionally.

Yes absolutely. After learning about problem solving through recursive algorithms (SICP/HTDP) I was quite sad to find that JavaScript/TypeScript didn't have this.

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

#56

Post by soegaard »

MrBuddyCasino wrote: post #12
leoh wrote: post #8

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

Pretty good arguments in there: - TCO only addresses recursion that can easily be replaced by a loop - loosing stack frames makes debugging harder - its not just an optimization, as soon as code depends on it to not blow the stack its a required feature for all implementations - functional languages with no side effects need recursion, everyone else really doesn't Personally, I think TCO is bad in a similar way as as…

Principles of functional programs also apply when computing with objects.

"Object-Oriented Programming in languages that don’t require tail-call optimizations makes no sense."

- Matthias Felleisen

Why? See part 3 of this presentation from ECOOP 2004.

https://web.archive.org/web/20180324164849/http://www.ccs.ne...

Another quote: > One common misunderstanding about TCO is due to the word 'optimization'. It is indeed a space optimization (don't use more space than goto, as Guy said in the 1970s) but a language should implement TCO in support of PROPER DESIGN. To wit, go through the OO design pattern books and inspect all the little patterns. Pick some -- say interpreter or composite -- and design your Java program accordingly. Then run a stress test and weep. Java blows up even if all the method calls are tail-recursive because it doesn't support TCO. Now do the same in PLT Scheme's class system and smile. It works -- for all inputs.

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

#57

Post by hajile »

asciimov wrote: post #53

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 l…

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.

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

#58

Post by [deleted] »

MrBuddyCasino wrote: post #12
leoh wrote: post #8

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

Pretty good arguments in there: - TCO only addresses recursion that can easily be replaced by a loop - loosing stack frames makes debugging harder - its not just an optimization, as soon as code depends on it to not blow the stack its a required feature for all implementations - functional languages with no side effects need recursion, everyone else really doesn't Personally, I think TCO is bad in a similar way as as…

[deleted]

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

#59

Post by Jtsummers »

layer8 wrote: post #36
pmelendez wrote: post #13

Earlier quoted context omitted.

I would opt for balance, there is a reason why some languages compile in debug and release mode, because of the tradeoffs. Having code that is optimal in performance often implies a tradeoff in debuggability. If debugging helpfulness is the major design decision of a programming language, that designer is trading off performance.

Tail calls fundamentally isn’t (just) about performance, it’s about language capability. Tail calls allow you to recurse indefinitely (because required stack space remains constant), which is not possible without tail calls (stack grows indefinitely). For example, tail calls make it okay to recurse on variable-length user input, which would be ill-advised in languages not supporting tail calls.

And not just direct recursion as is often considered. Mutual recursion is also handled neatly by this permitting you to write very clear state machines via functions and mutual recursion, if the tail calls get optimized. Very handy for parsing and similar tasks.

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

#60

Post by mst »

RcouF1uZ4gsC wrote: post #3

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.

https://reviews.llvm.org/D99517 is really quite interesting.
Post reply on HN