8 ms·

I'd argue this is a pitfall that languages can and should solve. There's no reason why writing a naive recursive descent parser should cause this problem. The f

I'd argue this is a pitfall that languages can and should solve. There's no reason why writing a naive recursive descent parser should cause this problem. The fix, using a separate stack data structure, is telling, since it's the same algorithm, with the same space complexity, you're just saying "my language's call stack isn't a usable implementation, so I need a different stack." Why not just fix the call stack? In languages like rust/c/c++, this might be hard, since you can't grow the stack by moving them (since you'd need to update pointers, which are too visible in those languages, and even identifying a pointer at runtime is undecidable), and segmented stacks cause the "hot-split" problem. But most languages could just make this problem go away by growing the call stack when needed. A few of them (incl. Haskell) do. I'm following suit in a language I'm working on.

anaphor 7y ago
Most purely functional languages (like Haskell) don't really have a "call stack", but the computation is carried out by graph reduction, so it can obviously detect cycles and do some optimizations there, depending on the type of recursion. If you want the gory details https://www.microsoft.com/en-us/research/wp-content/uploads/1992/04/spineless-tagless-gmachine.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/...
- zenhack 7y ago
  Yeah, I've read the STG paper, though its been a while. IIRC there isn't a call stack as we'd normally think of it, but there's still a stack of pending pattern matches, so you actually do hit the same issues. I vaguely recall making deep recursion "just work" in GHC was something that happened just in the past couple years.
jlokier 7y ago
> In languages like rust/c/c++ In another HN thread there is much discussion about Rust using, in effect, segmented stacks to implement async-await. Perhaps you could code a recursive descent parser in Rust using async functions, so that the Rust compiler converts it to a heap-allocated state machine for you.

anaphor 7y ago

Most purely functional languages (like Haskell) don't really have a "call stack", but the computation is carried out by graph reduction, so it can obviously detect cycles and do some optimizations there, depending on the type of recursion. If you want the gory details https://www.microsoft.com/en-us/research/wp-content/uploads/1992/04/spineless-tagless-gmachine.pdf https://www.microsoft.com/en-us/research/wp-content/uploads/...

zenhack 7y ago
Yeah, I've read the STG paper, though its been a while. IIRC there isn't a call stack as we'd normally think of it, but there's still a stack of pending pattern matches, so you actually do hit the same issues. I vaguely recall making deep recursion "just work" in GHC was something that happened just in the past couple years.

jlokier 7y ago

> In languages like rust/c/c++ In another HN thread there is much discussion about Rust using, in effect, segmented stacks to implement async-await. Perhaps you could code a recursive descent parser in Rust using async functions, so that the Rust compiler converts it to a heap-allocated state machine for you.