7 ms·

Every recursive algorithm can be made into an iterative algorithm if you use an explicit stack instead of the implicit call stack. It's not always cleaner. In

Every recursive algorithm can be made into an iterative algorithm if you use an explicit stack instead of the implicit call stack. It's not always cleaner. In tail recursive algorithms, there is no stack, it's just a straight loop. def foo(state, acc): # if acc is needed if base-condition(state): return acc return foo(next(state), f(state, acc)) Is simply: def foo(state): acc = initial while not base-condition(state): acc = f(state, acc) state = next(state) return acc If it's not tail recursive you introduce a stack, for instance a DFS on a binary tree: def search(node, val): if node is None: return False # empty tree, only need this check once stack = [node] while stack: n = stack.pop() if n.val == val: return True if n.right: stack.push(n.right) if n.left: stack.push(n.left) return False Note the insertion order is reversed from the recursive calls in a typical DFS. We want left to be searched first and then its children and then we "recur" back to right and deal with its children, so we need to push right into the stack first and then left. When you have multiple mutually recursive functions (as is likely the case in a recursive descent parser) then things become more complicated, but it's still feasible.

LegionMammal978 1y ago
Sometimes the messy translation into an explicit stack and dispatch loop is necessary, if you want to pause the calculation, serialize the current state, and reconstitute it later. (E.g., if you want to add disk-saved checkpoints, a frequent hassle in some of my projects.) Coroutines can get you the equivalent of pausing and resuming for a recursive routine, but I'm not aware of any language that lets you serialize the call stack.
- Jtsummers 1y ago
  > I'm not aware of any language that lets you serialize a whole call stack. That's basically what continuations provide. Scheme, SML, and others provide them.
  - LegionMammal978 1y ago
    Continuations allow an inactive call stack to sit around in memory. But do any of those languages let you save a continuation to a file and resume it in a different execution of the program, without massive contortions to the code? That's what I mean by serialization.
    - kmicinski 1y ago
      Seems potentially interesting to explore what would be required to store durable continuations. Feels very related to incrementalization and provenance, as you can see materializing a continuation to disk (whatever storage backend) requiring dependence tracking to do anything other than simply snapshotting the whole program state. I am just spitballing though, not sure if anyone has actually tried this.
- tylerhou 1y ago
  It is much easier and more maintainable to convert to continuation passing style. If you also use defunctionalization to allocate closures on a stack instead of a fresh heap allocation for every closure, you will achieve performance on par with an explicit stack. (In fact, defunctionalization is a mechanical transformation the produces exactly the data you would store in an explicit stack!) Before I knew about CPS and defunctionalization, I wrote a Python decorator that did exactly the transformation you describe. https://github.com/tylerhou/fiber https://github.com/tylerhou/fiber. Now I know about CPS and defunctionalization, I realize that my work was not the best implementation (but it was a fun learning experience!).
  - LegionMammal978 1y ago
    It's not just pausing and resuming that I'm looking for, but serialization into a form that can be saved to and loaded from files. (Another commenter calls this "materialization" of continuations.) In that regard, the problem with CPS is that continuations are totally opaque (or nearly so) in every language I'm aware of: you aren't able to do anything with them except resume them within the same execution of the program. Do any of your "defunctionalization" implementations offer such a feature?
    - tylerhou 1y ago
      Defunctionalization is a general technique that allows one to serialize functions as data. You’ve almost certainly used this technique before without realizing it was an instance of defunctionalization.
- themk 1y ago
  There is a library for Haskell that will do it. Though it doesn't support all GHC versions. It's very nifty if you need it. https://github.com/jberthold/packman https://github.com/jberthold/packman
fellowniusmonk 1y ago
When TCO recursion was first developed it was very explicitly called out as a syntactic and structurally improved GOTO but still fundamentally a GOTO that could take params. Recursion isn't physically real, any book that teaches the abstraction before explaining either the call stack (for non-TCO recursion) or in the GOTO context is a book actively trying to gatekeeper CS and weed out readers. (Not that any of those old pascal turbo/boreland books from the 90s actually shipped code that compiled.) I had several people on HN of all places try to "teach me" recursion after this simple line inside a larger comment: > It's like acting like recursion is physically real (it's not) when it smuggles in the call stack. Recursion IS real abstractly. It's just not physically real, it was developed before we knew how DNA/RNA encoding handles the same issues in a more performant way.
- achierius 1y ago
  > It's just not physically real, it was developed before we knew how DNA/RNA encoding handles the same issues in a more performant way. That was a sharp left turn -- how do you figure DNA/RNA are relevant here? I feel like iteration pre-dates our modern understanding of RNA in particular (though I could be mistaken) so I struggle to imagine how DNA/RNA were particularly informative in this regard.
- Jtsummers 1y ago
  > Recursion isn't physically real, any book that teaches the abstraction before explaining either the call stack (for non-TCO recursion) or in the GOTO context Do you also believe that loops and functions should only be taught after the call stack and goto are taught? Neither of them are real either by your measure. What a silly sentiment.
  - fellowniusmonk 1y ago
    Loops and functions can be physically represented as a stand alone, they can be physically carved onto a mechanical surface and observed. They don't smuggle anything in conceptually, their abstraction doesn't leave anything critical to their structure out. They are real and can be physicalized as stand alone objects. I see you've never tried to teach a software class to children or other learners, historically recursion is _very_ poorly taught by those who already understand the concept, but I'm not saying you have to care about that, a lot of people think there are too many programers already.
spauldo 1y ago
If you have to use an explicit stack, you're still doing recursion. Useful if you're implementing the Ackermann function in FORTRAN 77, I suppose. Unless you're worried about running out of stack space, it's generally easier to reason about if you just use regular recursion. That only applies for non-primitive recursive functions, though. Most people rarely encounter those. For primitive recursive functions, it's all down to the nature of the function and what's idiomatic for your language. If you're using Scheme, for example, recursion is the name of the game.

LegionMammal978 1y ago

Sometimes the messy translation into an explicit stack and dispatch loop is necessary, if you want to pause the calculation, serialize the current state, and reconstitute it later. (E.g., if you want to add disk-saved checkpoints, a frequent hassle in some of my projects.) Coroutines can get you the equivalent of pausing and resuming for a recursive routine, but I'm not aware of any language that lets you serialize the call stack.

Jtsummers 1y ago
> I'm not aware of any language that lets you serialize a whole call stack. That's basically what continuations provide. Scheme, SML, and others provide them.
- LegionMammal978 1y ago
  Continuations allow an inactive call stack to sit around in memory. But do any of those languages let you save a continuation to a file and resume it in a different execution of the program, without massive contortions to the code? That's what I mean by serialization.
  - kmicinski 1y ago
    Seems potentially interesting to explore what would be required to store durable continuations. Feels very related to incrementalization and provenance, as you can see materializing a continuation to disk (whatever storage backend) requiring dependence tracking to do anything other than simply snapshotting the whole program state. I am just spitballing though, not sure if anyone has actually tried this.
tylerhou 1y ago
It is much easier and more maintainable to convert to continuation passing style. If you also use defunctionalization to allocate closures on a stack instead of a fresh heap allocation for every closure, you will achieve performance on par with an explicit stack. (In fact, defunctionalization is a mechanical transformation the produces exactly the data you would store in an explicit stack!) Before I knew about CPS and defunctionalization, I wrote a Python decorator that did exactly the transformation you describe. https://github.com/tylerhou/fiber https://github.com/tylerhou/fiber. Now I know about CPS and defunctionalization, I realize that my work was not the best implementation (but it was a fun learning experience!).
- LegionMammal978 1y ago
  It's not just pausing and resuming that I'm looking for, but serialization into a form that can be saved to and loaded from files. (Another commenter calls this "materialization" of continuations.) In that regard, the problem with CPS is that continuations are totally opaque (or nearly so) in every language I'm aware of: you aren't able to do anything with them except resume them within the same execution of the program. Do any of your "defunctionalization" implementations offer such a feature?
  - tylerhou 1y ago
    Defunctionalization is a general technique that allows one to serialize functions as data. You’ve almost certainly used this technique before without realizing it was an instance of defunctionalization.
themk 1y ago
There is a library for Haskell that will do it. Though it doesn't support all GHC versions. It's very nifty if you need it. https://github.com/jberthold/packman https://github.com/jberthold/packman

fellowniusmonk 1y ago

When TCO recursion was first developed it was very explicitly called out as a syntactic and structurally improved GOTO but still fundamentally a GOTO that could take params. Recursion isn't physically real, any book that teaches the abstraction before explaining either the call stack (for non-TCO recursion) or in the GOTO context is a book actively trying to gatekeeper CS and weed out readers. (Not that any of those old pascal turbo/boreland books from the 90s actually shipped code that compiled.) I had several people on HN of all places try to "teach me" recursion after this simple line inside a larger comment: > It's like acting like recursion is physically real (it's not) when it smuggles in the call stack. Recursion IS real abstractly. It's just not physically real, it was developed before we knew how DNA/RNA encoding handles the same issues in a more performant way.

achierius 1y ago
> It's just not physically real, it was developed before we knew how DNA/RNA encoding handles the same issues in a more performant way. That was a sharp left turn -- how do you figure DNA/RNA are relevant here? I feel like iteration pre-dates our modern understanding of RNA in particular (though I could be mistaken) so I struggle to imagine how DNA/RNA were particularly informative in this regard.
Jtsummers 1y ago
> Recursion isn't physically real, any book that teaches the abstraction before explaining either the call stack (for non-TCO recursion) or in the GOTO context Do you also believe that loops and functions should only be taught after the call stack and goto are taught? Neither of them are real either by your measure. What a silly sentiment.
- fellowniusmonk 1y ago
  Loops and functions can be physically represented as a stand alone, they can be physically carved onto a mechanical surface and observed. They don't smuggle anything in conceptually, their abstraction doesn't leave anything critical to their structure out. They are real and can be physicalized as stand alone objects. I see you've never tried to teach a software class to children or other learners, historically recursion is _very_ poorly taught by those who already understand the concept, but I'm not saying you have to care about that, a lot of people think there are too many programers already.

spauldo 1y ago

If you have to use an explicit stack, you're still doing recursion. Useful if you're implementing the Ackermann function in FORTRAN 77, I suppose. Unless you're worried about running out of stack space, it's generally easier to reason about if you just use regular recursion. That only applies for non-primitive recursive functions, though. Most people rarely encounter those. For primitive recursive functions, it's all down to the nature of the function and what's idiomatic for your language. If you're using Scheme, for example, recursion is the name of the game.