5 ms·

In my mind, the biggest advantage to using tail recursion over vanilla loops is the ability to keep using persistent data structures without any (apparent) muta

In my mind, the biggest advantage to using tail recursion over vanilla loops is the ability to keep using persistent data structures without any (apparent) mutation. At least in theory, a tail recursive call will be converted into a dumb jump, so there shouldn't be a performance penalty, but since from your code's perspective you're passing in the stuff for the next iteration, you can keep using the pretty and easy-to-reason-about structures without creating any kind of mutable reference. I'm not 100% sold on tail recursion in a broader sense, but at least with Clojure's loop/recur stuff it is kind of cool to be able to keep using persistent data structures across iterations of loops.

weitendorf 1y ago
What makes tail recursion "special" is that there exists a semantically equivalent mutable/iterative implementation to something expressed logically as immutable/recursive. [0] Of course, this means that the same implementation could also be directly expressed logically in a way that is mutable/iterative. func pow(uint base, uint n): n == 0 ? return 1 : return n * pow(base, n-1) is just func pow(uint base, uint n): uint res = 1; for(i=0; i<n; i++){ res *= n} return res There is no real "advantage" to, or reason to "sell" anybody on tail call recursion if you are able to easily and clearly represent both implementations, IMO. It is just a compiler/runtime optimization, which might make your code more "elegant" at the cost of obfuscating how it actually runs + new footguns from the possibility that code you think should use TCO actually not (because not all immutable + recursive functions can use TCO, only certain kinds, and your runtime may not even implement TCO in all cases where it theoretically should). As an aside, in C++ there is something very similar to TCO called copy-elision/return-value-optimization (RVO): [1]. As with TCO it is IMO not something "buy into" or sell yourself on, it is just an optimization you can leverage when structuring your code in a way similar to what the article calls "continuation passing style". And just like TCO, RVO is neat but IMO slightly dangerous because it relies on implicit compiler/runtime optimizations that can be accidentally disabled or made non-applicable as code changes: if someone wanders in and makes small semantic to changes to my code relying on RVO/TCO for performance they could silently break something important. [0] EXCEPT in practice all implementation differences/optimizations introduce observable side effects that can otherwise impact program correctness or semantics. For example, a program could (perhaps implicitly) rely on the fact that it errors out due to stack overflow when recursing > X times, and so enabling TCO could cause the program to enter new/undesirable states; or a program could rely on a functin F making X floating point operations taking at least Y cycles in at least Z microseconds, and not function properly when F takes less than Z microseconds after enabling vectorization. This is Hyrum's Law [2]. [1] https://en.wikipedia.org/wiki/Copy_elision#Return_value_optimization https://en.wikipedia.org/wiki/Copy_elision#Return_value_opti... [2] https://www.hyrumslaw.com/ https://www.hyrumslaw.com/
- gleenn 1y ago
  I would argue having the parameters that change during the loop be explicit is a very nice advantage. Agree that the things can be equivalent in terms of execution but the readability and explicitness, and the fact that all the parameters are listed in the same place is great.
  - weitendorf 1y ago
    Agreed. Some people really like FP a lot, and I think it's underrated that the kinds of functions where TCO is applicable tend to be so simple that they are not really that inelegant when expressed imperatively. My true opinion is that relying on TCO is usually choosing ideological adherence to FP (or "code that looks cooler") over reliability/performance/communication. That said, just as I'd expect experienced C++ programmers to be able to recognize others' code using RVO and be careful not to restructure things to break it, I'd concede that experienced FP programmers might be unlikely to accidentally break others' TCO. It's just that ad absurdum you cannot expect every developer to be able to read every other developers' mind and recognize/workaround all implicit behavior they encounter.
    - eru 1y ago
      > [...] and I think it's underrated that the kinds of functions where TCO is applicable tend to be so simple that they are not really that inelegant when expressed imperatively. I suspect you are only thinking of patterns that are basically equivalent to a loop. I might agree with that. TCO really shines when you want to implement state machines. See eg https://news.ycombinator.com/item?id=43076088 https://news.ycombinator.com/item?id=43076088 for an example where using tail calls in Python's interpreter loop gives nice performance benefits. Similar also for LUA. > [...] I'd concede that experienced FP programmers might be unlikely to accidentally break others' TCO. Compiler (or linter) checkable annotations would help here. You are right that you want to make it possible for programmers to statically assert somehow that their function call is a tail call. Btw this reminds me: recursion isn't just something you do in computation, but also in data structures (amongst other things). In eg Rust the members of your data structure are typically just laid out one after another, but when you have a recursive structure (and in certain other cases) you need to box it, otherwise you'd get an infinitely large data structure. Boxing is more or less equivalent to using indirection via a pointer. However, unboxing isn't really like TCO. It's more like in-lining.
ramchip 1y ago
I think you're confusing mutation and variable reassignment?
- tombert 1y ago
  I'm saying that if I do a regular loop, something needs to explicitly mutate, either a reference or a value itself. `for (var i = 0; i < n, i++)`, for example, requires that `i` mutate in order to keep track of the value so that the loop can eventually terminate. You could also do something like: var i = new Obj(); while (!i.isDone()) { //do some stuff i = new Obj(); } There, the reference to `i` is being mutated. For tail recursion, it's a little different. If I did something like Factorial: function factorial(n, acc) { if (n <= 1) return acc; return factorial(n - 1, acc * n); } Doing this, there's no explicit mutation. It might be happening behind the scenes, but everything there from the code perspective is creating a new value. In something like Clojure, you might do something like (defn vrange [n] (loop [i 0 v []] (if (< i n) (recur (inc i) (conj v i)) v))) (stolen from [1]) In this case, we're creating "new" structures on every iteration of the loop, so our code is "more pure", in that there's no mutation. It might be being mutated in the implementation but not from the author's perspective. I don't think I'm confusing anything. [1] https://clojure.org/reference/transients https://clojure.org/reference/transients
  - eru 1y ago
    You could imagine a language like eg Python with a for-each loop that creates a new variable for each run through the loop body. Basically, just pretend the loop body is a lambda that you call for each run through the loop. It might make sense to think of the common loops as a special kind of combinator (like 'map' and 'filter', 'reduce' etc.) And just like you shouldn't write everything in terms of 'reduce', even though you perhaps could, you shouldn't write everything in terms of the common loops either. Make up new combinators, when you need them. For comparison, in Haskell we seldom use 'naked' recursion directly: we typically define a combinator and then use it. That often makes sense, even if you only use the combinator once.
  - ramchip 1y ago
charcircuit 1y ago
>without creating any kind of mutable reference. The parameter essentially becomes a mutable reference.
- tombert 1y ago
  No disagreement on that but that's an implementation detail and from the coder's perspective there's no mutable references.
  - charcircuit 1y ago
    From the coder's perspective it is. There's just different syntax for assigning to them.
    - tombert 1y ago
      No, from the coder's perspective it looks like I'm passing an argument into a function. I suppose you could say that arguments in general are "mutable references", and I guess that's not necessarily "untrue", but that's not generally how I visualize it. If I pass a persistent structure into a tail call, it looks like I'm passing a copy into there, in the same way that I might if I did something like `Math.abs(myValue * 3)`; the compiler converts it to a mutable reference but I see it as the same as passing a value.
  - weitendorf 1y ago
    From the coder's perspective, there are no mutable references only if the coder does not really rely on or care about the possibility that their code uses TCO. If they actively want TCO then they definitely care about the performance benefits they get from underlying mutability/memory reuse/frame elision.
    - tombert 1y ago
      Yeah but that's why I prefer Clojure's loop/recur thing. You're not allowed to have non-tail recursion there, so it's not implicit, so you really can pretend that there's no mutable references.

weitendorf 1y ago

What makes tail recursion "special" is that there exists a semantically equivalent mutable/iterative implementation to something expressed logically as immutable/recursive. [0] Of course, this means that the same implementation could also be directly expressed logically in a way that is mutable/iterative. func pow(uint base, uint n): n == 0 ? return 1 : return n * pow(base, n-1) is just func pow(uint base, uint n): uint res = 1; for(i=0; i<n; i++){ res *= n} return res There is no real "advantage" to, or reason to "sell" anybody on tail call recursion if you are able to easily and clearly represent both implementations, IMO. It is just a compiler/runtime optimization, which might make your code more "elegant" at the cost of obfuscating how it actually runs + new footguns from the possibility that code you think should use TCO actually not (because not all immutable + recursive functions can use TCO, only certain kinds, and your runtime may not even implement TCO in all cases where it theoretically should). As an aside, in C++ there is something very similar to TCO called copy-elision/return-value-optimization (RVO): [1]. As with TCO it is IMO not something "buy into" or sell yourself on, it is just an optimization you can leverage when structuring your code in a way similar to what the article calls "continuation passing style". And just like TCO, RVO is neat but IMO slightly dangerous because it relies on implicit compiler/runtime optimizations that can be accidentally disabled or made non-applicable as code changes: if someone wanders in and makes small semantic to changes to my code relying on RVO/TCO for performance they could silently break something important. [0] EXCEPT in practice all implementation differences/optimizations introduce observable side effects that can otherwise impact program correctness or semantics. For example, a program could (perhaps implicitly) rely on the fact that it errors out due to stack overflow when recursing > X times, and so enabling TCO could cause the program to enter new/undesirable states; or a program could rely on a functin F making X floating point operations taking at least Y cycles in at least Z microseconds, and not function properly when F takes less than Z microseconds after enabling vectorization. This is Hyrum's Law [2]. [1] https://en.wikipedia.org/wiki/Copy_elision#Return_value_optimization https://en.wikipedia.org/wiki/Copy_elision#Return_value_opti... [2] https://www.hyrumslaw.com/ https://www.hyrumslaw.com/

gleenn 1y ago
I would argue having the parameters that change during the loop be explicit is a very nice advantage. Agree that the things can be equivalent in terms of execution but the readability and explicitness, and the fact that all the parameters are listed in the same place is great.
- weitendorf 1y ago
  Agreed. Some people really like FP a lot, and I think it's underrated that the kinds of functions where TCO is applicable tend to be so simple that they are not really that inelegant when expressed imperatively. My true opinion is that relying on TCO is usually choosing ideological adherence to FP (or "code that looks cooler") over reliability/performance/communication. That said, just as I'd expect experienced C++ programmers to be able to recognize others' code using RVO and be careful not to restructure things to break it, I'd concede that experienced FP programmers might be unlikely to accidentally break others' TCO. It's just that ad absurdum you cannot expect every developer to be able to read every other developers' mind and recognize/workaround all implicit behavior they encounter.
  - eru 1y ago
    > [...] and I think it's underrated that the kinds of functions where TCO is applicable tend to be so simple that they are not really that inelegant when expressed imperatively. I suspect you are only thinking of patterns that are basically equivalent to a loop. I might agree with that. TCO really shines when you want to implement state machines. See eg https://news.ycombinator.com/item?id=43076088 https://news.ycombinator.com/item?id=43076088 for an example where using tail calls in Python's interpreter loop gives nice performance benefits. Similar also for LUA. > [...] I'd concede that experienced FP programmers might be unlikely to accidentally break others' TCO. Compiler (or linter) checkable annotations would help here. You are right that you want to make it possible for programmers to statically assert somehow that their function call is a tail call. Btw this reminds me: recursion isn't just something you do in computation, but also in data structures (amongst other things). In eg Rust the members of your data structure are typically just laid out one after another, but when you have a recursive structure (and in certain other cases) you need to box it, otherwise you'd get an infinitely large data structure. Boxing is more or less equivalent to using indirection via a pointer. However, unboxing isn't really like TCO. It's more like in-lining.

ramchip 1y ago

I think you're confusing mutation and variable reassignment?

tombert 1y ago
I'm saying that if I do a regular loop, something needs to explicitly mutate, either a reference or a value itself. `for (var i = 0; i < n, i++)`, for example, requires that `i` mutate in order to keep track of the value so that the loop can eventually terminate. You could also do something like: var i = new Obj(); while (!i.isDone()) { //do some stuff i = new Obj(); } There, the reference to `i` is being mutated. For tail recursion, it's a little different. If I did something like Factorial: function factorial(n, acc) { if (n <= 1) return acc; return factorial(n - 1, acc * n); } Doing this, there's no explicit mutation. It might be happening behind the scenes, but everything there from the code perspective is creating a new value. In something like Clojure, you might do something like (defn vrange [n] (loop [i 0 v []] (if (< i n) (recur (inc i) (conj v i)) v))) (stolen from [1]) In this case, we're creating "new" structures on every iteration of the loop, so our code is "more pure", in that there's no mutation. It might be being mutated in the implementation but not from the author's perspective. I don't think I'm confusing anything. [1] https://clojure.org/reference/transients https://clojure.org/reference/transients
- eru 1y ago
  You could imagine a language like eg Python with a for-each loop that creates a new variable for each run through the loop body. Basically, just pretend the loop body is a lambda that you call for each run through the loop. It might make sense to think of the common loops as a special kind of combinator (like 'map' and 'filter', 'reduce' etc.) And just like you shouldn't write everything in terms of 'reduce', even though you perhaps could, you shouldn't write everything in terms of the common loops either. Make up new combinators, when you need them. For comparison, in Haskell we seldom use 'naked' recursion directly: we typically define a combinator and then use it. That often makes sense, even if you only use the combinator once.
- ramchip 1y ago

charcircuit 1y ago

>without creating any kind of mutable reference. The parameter essentially becomes a mutable reference.

tombert 1y ago
No disagreement on that but that's an implementation detail and from the coder's perspective there's no mutable references.
- charcircuit 1y ago
  From the coder's perspective it is. There's just different syntax for assigning to them.
  - tombert 1y ago
    No, from the coder's perspective it looks like I'm passing an argument into a function. I suppose you could say that arguments in general are "mutable references", and I guess that's not necessarily "untrue", but that's not generally how I visualize it. If I pass a persistent structure into a tail call, it looks like I'm passing a copy into there, in the same way that I might if I did something like `Math.abs(myValue * 3)`; the compiler converts it to a mutable reference but I see it as the same as passing a value.
- weitendorf 1y ago
  From the coder's perspective, there are no mutable references only if the coder does not really rely on or care about the possibility that their code uses TCO. If they actively want TCO then they definitely care about the performance benefits they get from underlying mutability/memory reuse/frame elision.
  - tombert 1y ago
    Yeah but that's why I prefer Clojure's loop/recur thing. You're not allowed to have non-tail recursion there, so it's not implicit, so you really can pretend that there's no mutable references.