- 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
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.
Enabling new design patterns == good
Not thinking about what happens under the hood == bad
Catastrophes are rare, but expensive enough to cost more than thinking things through.
function frobnicate_something(foo, bar) {
let baz = antifrobnicate(foo, bar);
// Hey, I'm a tail call!
return exfoliate_meteor(baz);
}
This is the rationale behind the proposal to support tail calls only on explicit scenarios, where the developer opts in to throwing away stack frames.
- Only tail recurse once the stack is n objects deep. Having a 10,000 element stack trace isn't helpful.
- Keep a log of which functions were called, but not a full stack trace of each call. That's O(1).
I mentioned both of those in my post.
This is kind of amusing to hear considering that Python seems to actively design itself around making typical functional programming constructs difficult and JavaScript has a bunch of weird quirks with how it implements things (you’ve seen the “map” joke perhaps?)
The remaining 30% is awkward, but usually possible.
JavaScript is convoluted.... but after the learning curve, it does functional as well as anything, and better than most other things it does. It certainly does functional better than OO.
This misses the mark a bit. C++ destructors allow for multiple exits. Design at the level of an individual subroutine is not very important, ultimately.
Garbage collection is useful because it enables greater modularity, at the level of full applications and protocols. It does not force details of memory management and ownership into api contracts, leaving them free to be changed. (This, incidentally, is one of the reasons smarter people than I take issue with rust: it forces details of ownership into api contracts, reducing modularity. It is also the reason why reference counting is less modular than tracing gc: it does not deal with cycles, so cyclicality is part of api contracts, and a very subtle part at that.)
There's no need to dismiss the those who disagree as just having a lack of familiarity. There is a technical trade off to be made, with pros and cons each way. The only people that are objectively wrong are those that claim the decision is clear cut.
The con, in particular, is language complexity. You only have to look at C++ to see that it is possible to include to many features in a language. There's no disputing that tail calls are useful. The question is whether they are so useful that everyone who learns the language has to understand them.
As a former C++ programmer working on a large code base when/before Java was introduced, garbage collection was seen as expensive and slow, but definitely not a waste of time. I would have given my right arm to be free (pun intended) from the need to manually manage my heap across threads. Adding a free() call was never not a big deal.
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.
It's bad to create a dangerous performance cliff. There could be some TCO based code that works fine, and then a junior coder makes an 'innocent' change that makes it ineligible for TCO, then that code eventually starts getting OOM crashes on heavy data.
I think if they're gonna do TCO then it really should be syntactic. If someone is writing their code around an assumption of TCO, then they almost always want an explicit guarantee of TCO, and they want to fail fast if TCO isn't happening.
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)
Here are some strawman syntax examples from the Syntactic Tail Calls proposal.
Return Continue
function factorial(n, acc = 1) {
if (n === 1) {
return acc;
}
return continue factorial(n - 1, acc * n)
}
let factorial = (n, acc = 1) => continue
n == 1 ? acc
: factorial(n - 1, acc * n);
// or, if continue is an expression form:
let factorial = (n, acc = 1) =>
n == 1 ? acc
: continue factorial(n - 1, acc * n);
// # sigil, though it's already 'claimed' by private state.
#function() { /* all calls in tail position are tail calls */ }
// Note that it's hard to decide how to readably sigil arrow functions.
// This is probably most readable.
() #=> expr
// This is probably most in line with the non-arrow sigil.
#() => expr
// rec sigil similar to async functions
rec function() { /* likewise */ }
rec () => expr
function () { !return expr }
// It's a little tricky to do arrow functions in this method.
// Obviously, we cannot push the ! into the expression, and even
// function level sigils are pretty ugly.
// Since ! already has a strong meaning, it's hard to read this as
// a tail recursive function, rather than an expression.
!() => expr
// We could do like we did for # above, but it also reads strangely:
() !=> expr
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?
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.
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 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)
- performance
- developer tools
- Error.stack
- cross-realm tail calls
- developer intent
See: 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
- 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
1. more difficult to understand during debugging
2. less information about execution flow which may break telemetry
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.
http://neopythonic.blogspot.com/2009/04/tail-recursion-elimi...
Outside pure functional languages, I think the best way to implement them is to have explicit tail call declaration for functions and/and tail positions and ability to disable them for debugging (or have debugger aware of them).
This way you can actually use them to implement useful stuff and rely on them. You get a compiler error if tail call can't be implemented.
Erlang isn't pure, and has tail calls without an explicit syntax.
- 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 async functions. It is an exception from the general mental model of how function calls work, makes tooling much more complex and the alternative is just writing a loop, which I know is beneath the average Lambda The Ultimate subscriber, but its just how some people earn their money.
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.
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.reverberate.org/2021/04/21/musttail-efficient-i...
* http://lua-users.org/lists/lua-l/2011-02/msg00742.html
* https://cantortrading.fi/rust_decimal_str/
Now does JavaScript really need/care about any of this? Probably not.
This is fundamentally false.
TCO addresses recursion that is implemented through the arbitrarily complex composition of functions, enabling one to define arbitrarily complex loop constructs through function composition.
There are many such interesting compositions that cannot be “unrolled” into a single high-level imperative for loop without essentially having to rewrite the code of all the functions being composed, including code that controls looping in interesting ways (e.g. automatically terminating on error, collecting all errors, parallelizing execution, etc.)
> It is an exception from the general mental model of how function calls work
It’s not, though — unless you have an incorrect mental model of how function calls work.
When calling a function, the return address is first pushed on the stack (or on some architectures, stored in a link register).
The target function returns from execution by popping the return address from the stack (or reading it from a link register), and jumping to that address.
When calling a function, if the call is in a tail position, the calling function can provide it’s original return address, and then jump to the target function it’s calling.
That’s how functions actually work. That’s the mental model.
> makes tooling much more complex
What significant complexity does TCO add to tooling, exactly?
> the alternative is just writing a loop
That’s simply not true. See first paragraph above.
"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.
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.
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.
return f(x', y', z')
function fib(n) {
let curr=0, last=1;
for (let i = 0, i < n; i++) {
[ curr, last ] = [curr + last, curr];
}
return curr;
}
function fib(n, i=0, curr=0, last=1) {
if (n == i) return curr;
return fib(n, i + 1, curr + last, curr);
}
Guido gives four reasons, you are quoting the first. The counterpoint there is, tail calls are just rewrites for looping constructs, as Guido admits in point 3. Should we ban loops as not “maximally helpful for debugging” because not every iteration appears on error stack frames? Perish the thought!
So at the end of the day that one just turns out to be, I am a lazy developer and don't want to figure out how to track this looping info in a way that makes sense outside of the call stack, the call stack exists and works, let's just keep it. And like, that's respectable!
The other 3 reasons are better? Reason 2 is correct, Python has multiple implementations and they'd all have to play, cf. the OP where JS implementations didn't. Reason 3 is correct but unimaginative, there's no reason you can't write a loop in this style and use Python's data structures, for that matter you can write in this style and not use any data structures, like the example above! Because the technical objection isn't really there, again, this boils down to just, Guido wants to read Python code and he finds recursion hard to read, and wants the language to make it deliberately slow so that he never has to read it. That one is valid, but it sounds almost borderline unethical? And I will admit that reason 4 fooled me at first! This appears to be a damning problem but in fact it's just smoke and mirrors, right? “I might not know who the forwarding proxy is forwarding in advance.” Yes that's true but we can agree that the forwarding proxy is unnecessary no matter what it is forwarding. Sure, your language sucks at referential transparency, but if you are conflating these two things you are confusing the issue, no?
Okay, so I started out this comment wanting to defend Guido and here I am at the end disagreeing with him...
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.
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.
I wonder about specific use cases where stack allocating recursion actually becomes an issue in the JS world.
The only thing you can think of using recursion for is walking the DOM?
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.
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.
How did PTC sneak into the spec?
> 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.
One may be familiar with "stack overflow" which is when a series of function calls (often recursive) go so deep before actually returning that it exhausts the maximum stack space (essentially an array of scopes containing variables/state for each function). A proper tail call will realize that it can reuse the same existing stack frame instead of adding a new one, which essentially makes exhausting the stack impossible and removes the need for the CPU to do all of that bookkeeping.
In performance sensitive workflows it can make a large difference.
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.
If you think about all the standard statements in a language - if, while, async, etc - all of these kinds of constructs can be built out of normal functions once you have tail calls. This makes the language more extensible and reduces the need to introduce new kinds of built-in language constructs and allows more experimentation.
They're really useful for input processing/parsing, recursion, implementing algorithms, etc.
Another way to think about it is that functions can become little 'named blocks' with defined inputs and outputs, and you can combine them together without worrying so much about the runtime costs of functions that take up stack space. So if you have a function with lots of if conditions, while loops, etc, you can convert it into these 'named blocks' instead, which makes maintenance easier.
There are lots of examples. In a way, the fact that none of the main imperative languages support this simple runtime feature is what's stopping people from realising how great tail calls are. There's a bit of a Catch-22 happening.
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.
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.
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.
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.