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?
Aside from the points below, it's implemented in Safari IIRC?
What happened to proper tail calls in JavaScript? (2021)
61–70 of 146 posts
Re: What happened to proper tail calls in JavaScript? (2021)
#62Re: What happened to proper tail calls in JavaScript? (2021)
#63Earlier quoted context omitted.
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.
> 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…
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.
Re: What happened to proper tail calls in JavaScript? (2021)
#64So, 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 probl…
> 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)
Re: What happened to proper tail calls in JavaScript? (2021)
#65Worth 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…
Replacing a stack of function calls with a loop may be the same in terms of what happens, but it’s the like inlining code in general. Sometimes packaging it up makes it cleaner and more reusable and testable, relative to inlining it (or sticking it in a for loop).
Re: What happened to proper tail calls in JavaScript? (2021)
#66Worth 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…
> TCO only addresses recursion that can easily be replaced by a loop
This is simply false. Specialized tail recursion optimization, which I've seen a few places, approximately does that, but generally TCO covers a lot of things that aren't easily replaceable with for loops.
> its not just an optimization, as soon as code depends on it to not blow the stack its a required feature for all implementations
True, though that's an argument for it, not against it.
> loosing stack frames makes debugging harder
This is a weird argument to include with the for-loop thing, since the stack frames “lost” would never exist in the for-loop form for the case where there is a straightforward equivalence. In general, I find that this is mildly true (it sometimes make spotting the source of an error from the dump an an unhandled exception harder, but doesn't really make any debugging that involves more than that harder).
> functional languages with no side effects need recursion, everyone else really doesn't
Regardless of whether the language has side effects available, functional code without side effects is easier to analyze and assure important properties of, and it's beneficial to be able to leverage that even if you have a language that allows side effects.
Re: What happened to proper tail calls in JavaScript? (2021)
#67Earlier quoted context omitted.
Being able to guarantee tail calls is a useful optimization in far more cases than code replaceable by loops. I’ve used it myself where dispatch targets themselves are dynamic (so can’t be trivially made into a loop) for significant performance gains. Some other folks who’ve done the same thing (and can post publicly) for code that’s not just “must recurse because loops are for lowly imperative serfs”: * https://blog…
Interesting use case, didn't occur to me that tail calls can also just be a performance optimisation technique to help out the compiler and branch predictor. I assumed hot loops could be implemented just as well using GOTOs, but maybe not?
> I assumed hot loops could be implemented just as well using GOTOs, but maybe not?
Tail calls are GOTOs; that's the whole argument https://apps.dtic.mil/sti/citations/ADA030751
Re: What happened to proper tail calls in JavaScript? (2021)
#68For 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)
ipython
webapp.main
webapp.handler
render.make_tree
[PTC: render.red*91001, render.blue*10201]
webapp.callback
Re: What happened to proper tail calls in JavaScript? (2021)
#69Earlier quoted context omitted.
Being able to guarantee tail calls is a useful optimization in far more cases than code replaceable by loops. I’ve used it myself where dispatch targets themselves are dynamic (so can’t be trivially made into a loop) for significant performance gains. Some other folks who’ve done the same thing (and can post publicly) for code that’s not just “must recurse because loops are for lowly imperative serfs”: * https://blog…
Interesting use case, didn't occur to me that tail calls can also just be a performance optimisation technique to help out the compiler and branch predictor. I assumed hot loops could be implemented just as well using GOTOs, but maybe not?
Everything can be implemented using IF statements and GOTOs. That's how early processors worked, and Turing completeness and all. We don't _really_ need function calls, while loops, or for loops either.
That doesn't mean it's a good idea.
Re: What happened to proper tail calls in JavaScript? (2021)
#70Earlier quoted context omitted.
> 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.
So the whole topic is not terribly hard to understand. When you see return f(x', y', z') in some function g, then g's stack frame just describes a forwarding proxy, “let me take the value returned by f and hand it to whoever called me.” And like with all forwarding proxies you can just delete the middleman and it works fine. You would do this because it gives you an alternate, debatably simpler, model for looping. In…
> The counterpoint there is, tail calls are just rewrites for looping constructs, as Guido admits in point 3
Except they're not. Here are some functions using tail-calls:
checks = {
'odd' : lambda n: False if n - Loops are statements, which can't be used in lambda expressions
- To use statements, we would need to define named functions (using `def`), but that too is a statement
- The names introduced by `def` would need to be unique, to avoid clobbering any existing names. This may require a fresh scope.
- We would need to inline each function's logic into the other
- We would need some intermediate state (separate from the argument 'n') to keep track of whether we're up to even or odd