Worth reading only if "because ignorance" is useful knowledge to you. In any case, you'd be better off starting at http://funcall.blogspot.com/2009/04/you-knew-id-say-somethin..., which tries to clear up some of the misconceptions Guido was laboring under at the time.
> So in my mind, the applicability of reduce() is pretty much limited to associative operators, and in all other cases it's better to write out the accumulation loop explicitly.
Grantparent is right. What you pointed to is in functools, a "functional" utility package in the stdlib, which has even more exotic stuff.
But Python doesn't have a reduce function as a primitive, and Guido and co discourage such uses. So much so, that Python 2 did have, and it was explicitly removed.
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.
- 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.
> 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.
As far as I understand, TCO (or PTC?) gives you "structured goto", i.e something that would be a pain to write as a loop, won't either mess up the state/scope, but still achieve that "loop speed" without stressing the stack.
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”:
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.
In the particular linked case of protobuf parsing, a loop with goto's doesn't produce very well optimized code because of specific internal details about how modern C compilers do optimizations. You could certainly imagine a compiler that can fully optimize a go-to heavy program, in which case the code cleanliness argument would be the only reason.
Tail calls are basically GOTOs, yeah. The bring a HUGE benefit of very clearly defining state flow between gotos which makes the compiler's job super easy.
> TCO only addresses recursion that can easily be replaced by a loop
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.
> There are many such interesting compositions that cannot be “unrolled”.
You're arguing semantics, sure, you cannot mechanically transform code which relies on TCO into a loop. That is not the same as the parents point that TCO functions are isomorphic to loops. In a language without TCO you wouldn't ever find yourself in mess of composition of functions.
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.
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).
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.
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.
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 other loops you either have to return out midloop, or have to explicitly marshal your inputs and outputs of each step into mutable variables, see. So here is the same loop written two ways, the second is probably less familiar to you:
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);
}
These are only different styles for the same thing if you can trust that the call stack does not overflow in the second, which it doesn't have to because it returns a call to a function. So the problem is, if you have too many forwarding proxies in a chain, the language gives up on you.
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...