6 ms·

> Nobody has yet convinced me that recursion has any sustained advantage over looping. Looping may require trampolining or defunctionalisation, whilst recursio

> Nobody has yet convinced me that recursion has any sustained advantage over looping. Looping may require trampolining or defunctionalisation, whilst recursion can be written much more directly and simply. As a very simple example (in pseudocode): even(n: uint): boolean = n match { case 0: true case n: odd(n-1) } odd(n: uint): boolean = n match { case 0: false case n: even(n-1) } Whilst these are pretty silly implementations of odd & even, I don't know of a direct analogue using loops. For more realistic examples, just look at any "main loop"; AKA "trampoline boilerplate to work-around our language's lack of tail-call elimination" ;)

roenxi 4y ago
for(range(n)): is_true = !is_true And adjust for all the off by 1 errors. You're managing the same amount of state both ways, but with the loop all the state mutation lives on one line instead of spread throughout a stack.
- chriswarbo 4y ago
  That's not a "direct analogue" of my implementation, for many reasons; you've changed the semantics and engineering tradeoffs so much that we might as well write `n % 2 == 0`. The biggest problem is that, assuming we copy your snippet into a couple of function definitions, we've completely lost the encapsulation/separation-of-concerns/delegation/etc. provided by my `odd` and `even` functions; i.e. all of the "software engineering" stuff that makes source code more maintainable than disassembled binary. Your loop is more like the following, which is not what I wrote: even(n: uint): boolean = n match { case 0: true case n: !even(n-1) } odd(n: uint): boolean = n match { case 0: false case n: !odd(n-1) } The major difference is the use of iteration/tail-recursion in this implementation: - This loop collapses all of the abstraction, forcing each function to implement the entire solution. In contrast, my implementation uses divide-and-conquer: only the zero case is handled directly, and the non-zero case is delegated to a more suitable handler. - Wrapping two copies of this loop into `even` and `odd` functions will completely lose the relationships inherent in my implementation. For example, if we add instrumentation, optimisations, logging, etc. to the `even` function, that will affect my `odd` function but have no effect if we were to write independent loops. - This looping implementation has extra dependencies, specifically on `range` and `!`. The `!` function requires knowledge of boolean algebra, the `range` function requires knowledge of lists/sequences/iterators, and `range` also seems to make more sophisticated use of number theory than the `odd`/`even`/`-` required to understand and maintain my implementation. Note that I'm not claiming either of these is "better"/"worse" than the other. Simply that your loop is not representative of my example; that's specifically why I chose a mutually-recursive example, and not an iterative/tail-recursive one! (Of course, all of these are exaggerations for such a simple example; but complex, real-world codebases require such engineering practices and tradeoffs to be taken seriously for the sake of maintenance)
  - roenxi 4y ago
    I see, so the point you wanted to draw was that if you wanted to implement two functions, mutual recursion might let you separate the implementation logic. That is a nice trick. > you've changed the semantics and engineering tradeoffs so much that we might as well write `n % 2 == 0`. That is a fairly glaring weakness of the example you've chosen - it is taking a simple situation and overthinking it. It doesn't really matter because I see your point and surely one would exist, but do you have an example where this technique is an efficient solution?
    - chriswarbo 4y ago
      Yes, exactly :) Again, it's not always "better", but it's a situation that doesn't seem to map directly to a loop. I gave a more complicated, realistic example in a sibling comment https://news.ycombinator.com/item?id=35466256 https://news.ycombinator.com/item?id=35466256
actionfromafar 4y ago
It's heretic and beside the point, but: bool odd(uint n){return n&1;} bool even(uint n){ return !odd(n);} I can't help but think in terms of classic CPU.
- Joker_vD 4y ago
  fun odd (n: Uint32) -> Bool = let Uint32(n0, _, _, _) = n in let Byte(b0, _, _, _, _, _, _, _) = n0 in b0 Who needs hardware support for integers anyway? If you want a two-complement arithmetic, you can build it yourself (although presumably it'll be in the standard library).
willdearden 4y ago
Here's how I would write the loop version of this. It does involve an optimization since we know parity only depends on n - 1. #include <algorithm> template <typename T> bool even(T n) { bool is_even{true}, is_odd{false}; for (; n--;) { std::swap(is_even, is_odd); } return is_even; }
twic 4y ago
I'm not going to argue this is good, but it's fairly analogous: boolean isEven(int n) { boolean even = true; for (; n > 0; --n) even = !even; return even; }
- chriswarbo 4y ago
  Your implementation has lost the encapsulation of mine, and broken the call-graph relationships. For example: - Updates and bug-fixes to the `isOdd` function will not be inherited by your `isEven` function. - If I set a breakpoint in this function, it won't get triggered when I call `isOdd`. - Your `isEven` function requires an implementation of `!` - etc.
  - twic 4y ago
    > - Updates and bug-fixes to the `isOdd` function will not be inherited by your `isEven` function. > - If I set a breakpoint in this function, it won't get triggered when I call `isOdd`. boolean isOdd(int n) { return !isEven(n); } > - Your `isEven` function requires an implementation of `!` Yes, but this language has one, so that's fine.
chriswarbo 4y ago
Many of the replies to this comment seem to have focused on the problem domain (numbers and booleans); and missed the main feature I was trying to show about recursion, which is a collection of functions delegating sub-tasks between themselves (rather than e.g. trampolining via a "main loop") A closer analogy to my code would be something like this: the domain logic is still abstracted and encapsulated into separate units; the relationships between those units are preserved (e.g. if we set a breakpoint in `even_step`, it will be triggered by `odd`); etc. However, the loop here is literally just a trampoline for thunks, which makes it highly non-idiomatic for imperative/looping style: type STEP[T] = either[T, unit => STEP[T]] stepper[T](current: STEP[T]): T = { for (result = current; result.isRight(); result = result.value(unit)) return result } even(n: uint): boolean = stepper(n match { case 0: left(true) case n: right(() => odd(n-1)) }) odd(n: uint): boolean = stepper(n match { case 0: left(false) case n: right(() => even(n-1)) }) Instead, we could defunctionalise; but that requires some separate data structure and "interpreter": type STEP = ODD(n: uint) | EVEN(n: uint) | RETURN(x: boolean) even_impl(n: uint): STEP = n match { case 0: RETURN(true) case n: ODD(n-1) } odd_impl(n: uint): STEP = n match { case 0: RETURN(false) case n: EVEN(n-1) } interpret(current: STEP): boolean = { while (!current.isReturn) { current = current match { case ODD(n): odd_impl(n) case EVEN(n): even_impl(n) } } return current.x } odd(n: uint): boolean = interpret(ODD(n)) even(n: uint): boolean = interpret(EVEN(n))
- LegionMammal978 4y ago
  I think the underlying claim by the OP is that they don't really run into situations in practice that need this kind of mutual recursion. Certainly, mutual recursion is not at all necessary for this boolean example; you argue that the obvious imperative form is not a direct analogue, but it's not really clear in what situation a direct analogue is desirable in the first place.
  - chriswarbo 4y ago
    > I think the underlying claim by the OP is that they don't really run into situations in practice that need this kind of mutual recursion As mentioned in my comment, this is applicable wherever we have a "main loop". For example, a game might have a bunch of separate functions/methods to handle the various parts of the game; and a "main loop" which passes the return values of some as arguments to others: function main() { world = initWorld() while(true) { if (quitPressed()) break; delta = calculateVelocities(world) world = updatePositions(delta, world) collisions = findCollisions(world) world = handleEvents(mkEvents(collisions), world) } print("Goodbye") quit() } Instead of passing data indirectly, by returning to the "main loop"; we could instead have those functions pass their results directly into whatever comes next. For example: function main() { gameStep(initWorld()) } function gameStep(world) { if (quitPressed()) quit(print("Goodbye")) else worldStep(world) } function worldStep(world) { delta = calculateVelocities(world) updatePositions(delta, world) } function updatePositions(delta, world) { newWorld = <existing logic> collisions = findCollisions(newWorld) handleEvents(mkEvents(collisions), newWorld) } function handleEvents(events, world) { newWorld = <existing logic> gameStep(newWorld) } This is a lot more complicated than the even/odd example, but it's the same pattern. In this case, it's probably clear why we wouldn't want to in-line all of the calculations into one gigantic loop, mixing up physics simulation, collision detection, input handling, combat system, and whatever else this game does. Again, not saying this is better/worse than a "main loop" (e.g. it can be helpful to have a "central location" to prevent spaghetti code); but (a) this style isn't possible without tail-call elimination, and (b) those who don't have tail-call elimination maybe wouldn't consider such an implementation.

roenxi 4y ago

for(range(n)): is_true = !is_true And adjust for all the off by 1 errors. You're managing the same amount of state both ways, but with the loop all the state mutation lives on one line instead of spread throughout a stack.

chriswarbo 4y ago
That's not a "direct analogue" of my implementation, for many reasons; you've changed the semantics and engineering tradeoffs so much that we might as well write `n % 2 == 0`. The biggest problem is that, assuming we copy your snippet into a couple of function definitions, we've completely lost the encapsulation/separation-of-concerns/delegation/etc. provided by my `odd` and `even` functions; i.e. all of the "software engineering" stuff that makes source code more maintainable than disassembled binary. Your loop is more like the following, which is not what I wrote: even(n: uint): boolean = n match { case 0: true case n: !even(n-1) } odd(n: uint): boolean = n match { case 0: false case n: !odd(n-1) } The major difference is the use of iteration/tail-recursion in this implementation: - This loop collapses all of the abstraction, forcing each function to implement the entire solution. In contrast, my implementation uses divide-and-conquer: only the zero case is handled directly, and the non-zero case is delegated to a more suitable handler. - Wrapping two copies of this loop into `even` and `odd` functions will completely lose the relationships inherent in my implementation. For example, if we add instrumentation, optimisations, logging, etc. to the `even` function, that will affect my `odd` function but have no effect if we were to write independent loops. - This looping implementation has extra dependencies, specifically on `range` and `!`. The `!` function requires knowledge of boolean algebra, the `range` function requires knowledge of lists/sequences/iterators, and `range` also seems to make more sophisticated use of number theory than the `odd`/`even`/`-` required to understand and maintain my implementation. Note that I'm not claiming either of these is "better"/"worse" than the other. Simply that your loop is not representative of my example; that's specifically why I chose a mutually-recursive example, and not an iterative/tail-recursive one! (Of course, all of these are exaggerations for such a simple example; but complex, real-world codebases require such engineering practices and tradeoffs to be taken seriously for the sake of maintenance)
- roenxi 4y ago
  I see, so the point you wanted to draw was that if you wanted to implement two functions, mutual recursion might let you separate the implementation logic. That is a nice trick. > you've changed the semantics and engineering tradeoffs so much that we might as well write `n % 2 == 0`. That is a fairly glaring weakness of the example you've chosen - it is taking a simple situation and overthinking it. It doesn't really matter because I see your point and surely one would exist, but do you have an example where this technique is an efficient solution?
  - chriswarbo 4y ago
    Yes, exactly :) Again, it's not always "better", but it's a situation that doesn't seem to map directly to a loop. I gave a more complicated, realistic example in a sibling comment https://news.ycombinator.com/item?id=35466256 https://news.ycombinator.com/item?id=35466256

actionfromafar 4y ago

It's heretic and beside the point, but: bool odd(uint n){return n&1;} bool even(uint n){ return !odd(n);} I can't help but think in terms of classic CPU.

Joker_vD 4y ago
fun odd (n: Uint32) -> Bool = let Uint32(n0, _, _, _) = n in let Byte(b0, _, _, _, _, _, _, _) = n0 in b0 Who needs hardware support for integers anyway? If you want a two-complement arithmetic, you can build it yourself (although presumably it'll be in the standard library).

willdearden 4y ago

Here's how I would write the loop version of this. It does involve an optimization since we know parity only depends on n - 1. #include <algorithm> template <typename T> bool even(T n) { bool is_even{true}, is_odd{false}; for (; n--;) { std::swap(is_even, is_odd); } return is_even; }

twic 4y ago

I'm not going to argue this is good, but it's fairly analogous: boolean isEven(int n) { boolean even = true; for (; n > 0; --n) even = !even; return even; }

chriswarbo 4y ago
Your implementation has lost the encapsulation of mine, and broken the call-graph relationships. For example: - Updates and bug-fixes to the `isOdd` function will not be inherited by your `isEven` function. - If I set a breakpoint in this function, it won't get triggered when I call `isOdd`. - Your `isEven` function requires an implementation of `!` - etc.
- twic 4y ago
  > - Updates and bug-fixes to the `isOdd` function will not be inherited by your `isEven` function. > - If I set a breakpoint in this function, it won't get triggered when I call `isOdd`. boolean isOdd(int n) { return !isEven(n); } > - Your `isEven` function requires an implementation of `!` Yes, but this language has one, so that's fine.

chriswarbo 4y ago

Many of the replies to this comment seem to have focused on the problem domain (numbers and booleans); and missed the main feature I was trying to show about recursion, which is a collection of functions delegating sub-tasks between themselves (rather than e.g. trampolining via a "main loop") A closer analogy to my code would be something like this: the domain logic is still abstracted and encapsulated into separate units; the relationships between those units are preserved (e.g. if we set a breakpoint in `even_step`, it will be triggered by `odd`); etc. However, the loop here is literally just a trampoline for thunks, which makes it highly non-idiomatic for imperative/looping style: type STEP[T] = either[T, unit => STEP[T]] stepper[T](current: STEP[T]): T = { for (result = current; result.isRight(); result = result.value(unit)) return result } even(n: uint): boolean = stepper(n match { case 0: left(true) case n: right(() => odd(n-1)) }) odd(n: uint): boolean = stepper(n match { case 0: left(false) case n: right(() => even(n-1)) }) Instead, we could defunctionalise; but that requires some separate data structure and "interpreter": type STEP = ODD(n: uint) | EVEN(n: uint) | RETURN(x: boolean) even_impl(n: uint): STEP = n match { case 0: RETURN(true) case n: ODD(n-1) } odd_impl(n: uint): STEP = n match { case 0: RETURN(false) case n: EVEN(n-1) } interpret(current: STEP): boolean = { while (!current.isReturn) { current = current match { case ODD(n): odd_impl(n) case EVEN(n): even_impl(n) } } return current.x } odd(n: uint): boolean = interpret(ODD(n)) even(n: uint): boolean = interpret(EVEN(n))

LegionMammal978 4y ago
I think the underlying claim by the OP is that they don't really run into situations in practice that need this kind of mutual recursion. Certainly, mutual recursion is not at all necessary for this boolean example; you argue that the obvious imperative form is not a direct analogue, but it's not really clear in what situation a direct analogue is desirable in the first place.
- chriswarbo 4y ago
  > I think the underlying claim by the OP is that they don't really run into situations in practice that need this kind of mutual recursion As mentioned in my comment, this is applicable wherever we have a "main loop". For example, a game might have a bunch of separate functions/methods to handle the various parts of the game; and a "main loop" which passes the return values of some as arguments to others: function main() { world = initWorld() while(true) { if (quitPressed()) break; delta = calculateVelocities(world) world = updatePositions(delta, world) collisions = findCollisions(world) world = handleEvents(mkEvents(collisions), world) } print("Goodbye") quit() } Instead of passing data indirectly, by returning to the "main loop"; we could instead have those functions pass their results directly into whatever comes next. For example: function main() { gameStep(initWorld()) } function gameStep(world) { if (quitPressed()) quit(print("Goodbye")) else worldStep(world) } function worldStep(world) { delta = calculateVelocities(world) updatePositions(delta, world) } function updatePositions(delta, world) { newWorld = <existing logic> collisions = findCollisions(newWorld) handleEvents(mkEvents(collisions), newWorld) } function handleEvents(events, world) { newWorld = <existing logic> gameStep(newWorld) } This is a lot more complicated than the even/odd example, but it's the same pattern. In this case, it's probably clear why we wouldn't want to in-line all of the calculations into one gigantic loop, mixing up physics simulation, collision detection, input handling, combat system, and whatever else this game does. Again, not saying this is better/worse than a "main loop" (e.g. it can be helpful to have a "central location" to prevent spaghetti code); but (a) this style isn't possible without tail-call elimination, and (b) those who don't have tail-call elimination maybe wouldn't consider such an implementation.