Comment by LegionMammal978
1 day ago
Several people in this thread are saying that tail recursion is superior to imperative iteration in that it explicitly specifies which variables may change in each iteration (assuming a broadly immutable language).
To the contrary, I'd argue that immutability isn't the only alternative to universal mutability: many newer imperative languages (such as Rust) have various forms of controlled mutability, where one must explicitly declare which variables may be modified by imperative assignments.
IME, controlled mutability captures just about all the benefit of immutable languages, without requiring any special data structures or sufficiently-smart compiler analyses to ensure good performance. I've never really understood the desire for tail-recursive versions of iterative algorithms, except for a prior commitment to functional programming.
> I've never really understood the desire for tail-recursive versions of iterative algorithms, except for a prior commitment to functional programming.
Tail-recursion and iteration are broadly equivalent right? So picking one over the other is a matter of style and capability.
You can't use iteration if your language isn't capable of it, but no worries, you can use tail recursion.
Similarly, you can't use tail recursion if your language isn't capable of it, but no worries, you can use iteration, at least for iterative tail recursion. Otoh, there are uses of tail call elimination that aren't recursion (or aren't direct recursion) ... that can get akward if your language can't manage it.
> Tail-recursion and iteration are broadly equivalent right? So picking one over the other is a matter of style and capability.
Tail recursion is more closely related to goto statements. So one could argue that imperative iteration constructs, as with other forms of structured programming, are superior in giving the reader immediate knowledge of the broad control flow, while tail recursion (especially mutual tail recursion) could have all sorts of weird behaviors.
> while tail recursion (especially mutual tail recursion) could have all sorts of weird behaviors.
What "weird behaviors" have you encountered with tail recursion?
Well, by broadly equivalent, I mean that it's generally easy to translate from one form to another; not that they exactly match. Iteration isn't really capable of expressing all the things you can express with mutual tail calls, but otherwise.
You can certainly argue about which of two forms is clearer, but I don't know that it's a decidable problem, so like ... do whatever you feel. I write in multiple programming languages and try to blend with the local idioms, so I write loops with foreach and with recursion, and they're both fine. If you have pattern matched function clauses, I don't find recursion to be lacking in indications of the broad control flow; if you're in a language that lacks that, then recursive loops look pretty ugly. But something like a loop to sum values would be (in Erlang)
Assuming you know the syntax and the idioms, this is very clear. If you don't know the idioms, Acc means 'accumulator', H means 'head', T means 'tail', so if you call sum(List), it calls into the recursive sum with an initial accumulator of 0, then one element at a time is taken off the front of the list, and added to the accumulator, when the list is empty, the accumulator is returned.
the same thing in Rust would look like
You could make it generic or whatever if you want. Is one form better at giving the reader immediate knowledge of the broad control flow than the other? I don't know. But the iterative version is 7 lines vs 4 lines in recursion. A list isn't really the same as an array slice of course, so that's a bit of a cheat. Using a tuple in Erlang is similar, but wordier:
And you have to know that Tuples are 1 indexed, and that N indicates the Nth element of a Tuple. You could make sum/1 take a list or a tuple, but you do have two write both versions... you could make the Rust take an IntoIterator and benefit from Traits to not have to write a different version for each kind of container. You could argue about what's a better choice, but I won't :) Maybe you like type annotations, you could add those to the Erlang, but I won't do that either :P
If your iteration has more exciting work than summation, the line count difference doesn't matter so much... maybe the work it shorter in one language than the other anyway. But I don't think either form is obviously and objectively superior. I'd wager iteration has more mind share, but that doesn't indicate that it's superior.
But Rust's semantics make it less ergonomic to pass values and especially once you do any mutation, that code path is no longer trivially up for parallelization/concurrency. There one will have to lean into what Rust offers to make it safe again, which brings along more syntax. When one wants to pass values, one needs to implement clone or copy or something, and then explicitly clone or copy or so.
It is a tradeoff one can make, and it lends itself to high performance but it does come at a cost.
Loops and gootos are just a special case of function calls, that needed to be invented because back in the olden days we had no clue how to design language and write compilers.
I don't understand why someone would want to hold on nostalgically to restrictions we no longer face.
Controlled mutability is a step up, yes. Btw, even languages like Haskell give you plenty of mutability to play with, if you want to. (Eg MVars and TVars are a thing.)
You are right that replacing a loop one for one with a tail recursive version doesn't give you much benefit either way. (Though it does make my life easier, because you don't have to contort my brain around keeping track of mutation.)
However that's a bit of a straw man and misses the broader picture.
What you'd want to do is define combinators that encapsulate the specific pattern of computation you want to implement. The most commonly known combinators are things like 'map' and 'filter'. But there are plenty more useful ones you can define, like various tree traversals or whatever makes sense for use cases and data structures.
Whether those combinators are implemented with tail calls or with loops or gotos or whatever is an implementation detail that their users don't need to worry about.
I know of one major use case where you'd want to use tail recursion directly: state machines and interpreters. See https://en.wikisource.org/wiki/Lambda:_The_Ultimate_GOTO for an example of the former.
> I don't understand why someone would want to hold on nostalgically to restrictions we no longer face.
On the other hand, I don't understand why someone would want to shoehorn all possible forms of control flow into "everything is a function object that can receive argument values that are substituted into parameter variables". I could just as easily say that all programs are a special case of cellular automata or string-rewriting systems or whatever other Turing tarpit.
You call imperative mutation "contorting your brain", but you always have to keep close track of which variables change and which stay the same, even if you shove them into function parameters. Local immutability comes at the cost of disguising which variables may have their values replaced over the course of the execution.
> What you'd want to do is define combinators that encapsulate the specific pattern of computation you want to implement.
Yes, I agree that control-flow combinators are a good model for many forms of programming. But they are mostly orthogonal to the broader imperative vs. functional style for sequential control flow, except for the historical factor of older imperative languages having poor support for capturing values into closures.
> I know of one major use case where you'd want to use tail recursion directly: state machines and interpreters. See https://en.wikisource.org/wiki/Lambda:_The_Ultimate_GOTO for an example of the former.
I can accept that direct threading makes contingent sense in that Python case, given current implementations. It seems to mostly be an unfortunate limitation that the compilers have poor handling of dispatch loops. (Indeed, the author still had to use special implementation-specific contortions to get the compiler to generate acceptable register handling.)
But otherwise, I'd generally prefer structured programming, whether it be with imperative statements or with control-flow combinators, over the totally unstructured control flow offered by bare tail calls.
> On the other hand, I don't understand why someone would want to shoehorn all possible forms of control flow into "everything is a function object that can receive argument values that are substituted into parameter variables".
Huh? Where did you get that impression from?
I was suggesting to remove some special case handling of certain tail recursive constructs (commonly known as 'loops') and just handle them via the general mechanism (via function calls, which are already in practically any language, and just need to be properly compiled) and perhaps at most offer some syntactic sugar to define loops in terms of the underlying tail recursive constructs.
I was not suggesting to 'shoehorn all possible forms of control flow' into function calls. (Sorry, I don't know what a 'function object' is. I just assume you mean a function?)
For example, many languages offer exception handling and there's also async operations and multi-threading and call-with-currenc-continuation and (early) return etc. I have expressed no opinion on those, and I'm not even sure they can all be handled as function calls.
> But otherwise, I'd generally prefer structured programming, whether it be with imperative statements or with control-flow combinators, over the totally unstructured control flow offered by bare tail calls.
I am suggesting to use combinators in most cases, and mostly use (tail) calls to define new combinators, rarely directly. Your compiler (and language) should ideally make this pattern of usage fast (which modern compilers can generally do, because they can eg often in-line the whole combinator thing).
I am observing that the commonly accepted loops are just some special cases of (something like) combinators and shouldn't be raised on a pedestal. Ideally they should be defined in the standard library, and not on the built-in level.