StackSafe: Taming recursion in Rust without stack overflow | Hacker News Reader

StackSafe: Taming recursion in Rust without stack overflow

fast.github.io

18 pointsandylokandy7 comments

While I am not versed in Rust, this type of problem has been addressed in other languages with a concept known as Free Monad[0], in which stack space is traded for heap space. While slower, it does eliminate the possibility of stack overflows.

Turns out, there is a Rust crate called higher_free_macro[1] which might fit the bill (to my novice Rust eye).

0 - https://wiki.haskell.org/Free_structure#Free_Monads

1 - https://docs.rs/higher-free-macro/latest/higher_free_macro/

> You must carefully not leaving any recursive functions not annotated with #[recursive]

Isn’t the same true of forgetting #[stacksafe]?

This reminds me of certain Haskell patterns where you selectively make some operations strict instead of lazy for similar reasons. I’m glad this library exists, but I’m sad the Rust compiler itself doesn’t have better support for recursion.

Why would I use a bandaid fix like this that has horrible memory usage, when there are crates[1] that allow tail call recursion?

[1] https://docs.rs/tailcall/latest/tailcall/

This works on functions that can't be tail-recursive, like depth-first search.

Why not just use a stack data structure instead of using the call stack as a stack data structure? Each stack frame is going to take up a lot more space than a straight array used as a stack.

You may disagree with their take on it, but they do address that in the write-up.

> This approach works for simple cases but becomes extremely complex or impossible when any of these conditions apply:

> 1. The algorithm transforms data structures rather than just evaluating them (e.g., optimizing an AST)

> 2. Multiple recursive calls need to be coordinated (e.g., tree balancing algorithms)

> 3. The algorithm doesn’t fit the tail-recursion pattern

I would disagree with "impossible" (pretty sure it's never actually impossible, but some type systems and language features may work together to make it so, I suppose), but definitely agree with "extremely complex".

I definitely do disagree because if you distill it down to making a single recursive call or pushing a value on a stack with local scope, I would say pushing a value on the stack in simpler every time.

If there are multiple recursive calls you could use multiple stacks instead.

All of the debugging is going to be more difficult if you have to move through multiple call stacks to get at the previous values, where you could just see the entire stack values in a debugger or print out the stacks.

For number 3, I think that doesn't apply, since tail-recursion is really a funky way of looping and not a funky way of using the call stack for a stack.

Reply on news.ycombinator.com