Could I theoretically use coroutines to split up long stacks into smaller stacks? Basically like “if function X was recursively called 500 times, suspend so that the next iteration starts with an empty stack”. But don’t suspend every call as that adds lots of overhead. In my case for a recursive visitor pattern could cause a huge stack if several are run in parallel on a huge AST 😄

In case it helps this sounds like the classical problem related to stack safety in the JVM that affects FP. It sounds like you want to build a stack safe function that trampolines before the stack blows up. This is what Arrow does in many places internally and there is a public data type for that called

AndThen

that allows you to propagate stack safe function composition https://arrow-kt.io/docs/apidocs/arrow-core-data/arrow.core/-and-then/index.html#andthen It jumps after 127 calls in the stack https://github.com/arrow-kt/arrow/blob/7d9228afc16e451e666c563e9670f6422000a3f7/modules/core/arrow-core-data/src/main/kotlin/arrow/core/AndThen.kt#L200-L214 https://github.com/arrow-kt/arrow/blob/7d9228afc16e451e666c563e9670f6422000a3f7/modules/core/arrow-core-data/src/main/kotlin/arrow/core/AndThen.kt#L73

I guess that would need FP for every single function call plus for the visitor API itself? Doesn't that create that one lambda (+other class instances) per iteration and puts pressure on the GC? I'm not sure how to come up with a good stack limit. There are other user functions (the visit... functions of visitors) in between my recursive calls and the stack usage depends on many local variables they throw on the stack. I found that related suggestion from @elizarov: https://gist.github.com/elizarov/861dda8c3e8c5ee36eaa6db4ad996568 I think it suspends on every recursive call. But I don't really understand the code yet.

What I mean is that the current runtime solution requires a wrapper to move the computation from the stack to the heap but if it was a Lang feature it could be done more efficiently perhaps allocating only in the jump. There is no notion of FP here, AndThen just exists because of the JVM. If you can find a better way we are also interested, this is unrelated to FP but stack safety in general in recursion that can’t be tail eliminated with tailrec.

You can just use my code. Works well, efficient, supports mutual recursion. I’ve already used it multiple times.

Thanks! So there’s likely no noticable performance penalty with tens of thousands of suspend calls?

I’ve used it for DFS on 1m nodes several times. Runs in under 1 second.

👍