4 ms·
Tail recursion isn't just an optimization technique. It enables a broad range of algorithms to work. Anything where the stack grows O(n) can't be done without t
by blagie 4y ago
Tail recursion isn't just an optimization technique. It enables a broad range of algorithms to work. Anything where the stack grows O(n) can't be done without tail recursion because of stack overflows.
There are two camps of programmers:
1) Ones who are used to writing such algorithms (e.g. in Lisp) who cry bloody murder because they can't use them in Python. It's painful to lose that type of expressiveness.
2) Ones who have never used them, and don't realize what they're missing. These will usually complain about surface issues (like nicer stack traces for debugging).
Camps like camp #2 comes up a lot in history.
- In the eighties and nineties, most BASIC programmers had never used pointers, references, or real data structures, and saw them as abstract theoretical constructs without any real-world use.
- C / C++ programmers would call Java programmers lazy for wanting garbage collection (ignorant of the broad set of algorithms enabled if you don't need to keep track of when memory is no longer needed manually).
- Java / C / C++ programmers saw closures and a lot of other functional tools as pointless, complex, theoretical abstractions, until Python / JavaScript / etc. ate their lunch.
- Many people who have never used relational databases before see them as pointless complexity for most systems, aside from very specific use-cases.
... and so on. The other argument always made hinges on the Turing Completeness of languages ("I'd like to do X!" "Well, here's how you do it without Y. If you were just more clever, you'd see why Y is useless complexity.") You can ALWAYS implement any use case in any Turing-complete language. BASIC programmers stuck things into arrays. Java/C++ programmers could use objects instead of a closure. And tail-recursive code can always be translated into iteration.
- jacquesm 4y agoLanguages like LISP, Clojure and Erlang would be a whole lot less useful in practice without tail call optimization, it allows you to write the 'naive' version of an algorithm and magically it 'just works'. Otherwise you'd have to explicitly code a loop where you would much rather use recursion.
- codetrotter 4y ago> Otherwise you'd have to explicitly code a loop where you would much rather use recursion. I find it much easier to reason about loops than to reason about recursion. Likewise I find it much easier to write loops than to write recursive functions. It probably comes down to experience mainly. I spent some time with functional languages, but I have spent far far far more time writing imperative procedural code.
- jacquesm 4y agoEven a simple problem such as the 'Towers of Hanoi' looks to me like a pretty messy solution when done with loops and with recursion it all just falls into place.
- Jensson 4y agoRecursion is great due to the implicit stack. The cases where you don't have an implicit stack, ie where tail call optimization works, are usually easier and much clearer to just do in a loop.
- toast0 4y ago> Otherwise you'd have to explicitly code a loop where you would much rather use recursion. The language would have to change for you to be able to code a loop. And that would have all sorts of consequences: in Erlang, preemption happens at function calls and no loops means a bounded time until you make a function call or terminate, with loops, that changes and preemption gets more difficult.
- pessimizer 4y ago> in Erlang, preemption happens at function calls I didn't think this was true. The secret sauce was that Erlang preempted on reduction counts, so as a result nothing has any responsibility to yield itself. edit: ah, literally no difference between the two in the implementation.
- jacquesm 4y agoThat's mostly an implementation detail though, the thread switch could happen just about anywhere. Function calls are a convenient stopping point but the way the reductions are implemented in Erlang it could theoretically be done on any boundary.
- toast0 4y agoIt's an implementation detail, but it's very convenient and simplifying, like a lot of Erlang implementation details. If you take out enough simplifying implementation details, you no longer have a powerful system built from simple parts.
- jacquesm 4y agoIn this particular case though I don't think it would matter much. I've looked pretty closely at how the BEAM does it's thing and it's a work of art, this particular trade-off is more one of convenience than of necessity. But you are right that Erlang is full of such clever (and beautiful) tricks which make it a very interesting codebase to study.
- markc 4y agoClojure doesn't have TCO. Instead, there's loop/recur where the recur call won't compile except in tail position.