undefined | Better HN

0 pointschriswarbo3y ago0 comments

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))

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)) })

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))

0 comments

4 comments · 2 top-level

LegionMammal9783y ago· 2 in thread

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.

chriswarboOP3y 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.

LegionMammal9783y ago

> 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.

Sure, this is an example where tail calls work as well as a central loop to solve the problem. But OP was looking specifically for a situation where recursion has an active "sustained advantage over looping", i.e., where the solution can be expressed far more naturally through recursion than through looping. Failing that, favoring recursion can just be boiled down to the peculiar preferences of the FP zeitgeist. (That is, even if the language does have tail-call elimination, that doesn't automatically make recursion the better solution.)

> 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.

I don't see what that has to do with loops vs. recursion. In real-world imperative code, we'd break up our main loop into calls to separate stages of the cycle, then break up each stage into calls to different encapsulated submodules, etc.; we wouldn't need to make the loop a 100k-line wall of code running every tiny step. (Compilers can do that part on their own.) Do you mean that this mutually-recursive style can assist with encapsulation in some particular way?

willdearden3y ago

FWIW for my comment I essentially used your code and cleaned up compiler-generated imperative code.

So yes it used the fact that it only recursed to n-1 but did not use any optimizations related to booleans. And looking at other examples can see general principles. You store a data structure for each function which acts as a cache. For example, suppose you said even(0) = True, even(1) = False, and even(n) = even(n - 2), then one way would to unroll it would be to use a size 2 ring buffer as a cache.

j / k navigate · click thread line to collapse