4 ms·

> One drawback of the CPS technique in C is its stack usage, especially because it is quite hard to understand at all what is going on, which makes it very hard

> One drawback of the CPS technique in C is its stack usage, especially because it is quite hard to understand at all what is going on, which makes it very hard to predict how much stack is used. Usually, I get SIGSEGV from pointer misuses (typically NULL), but in debugging this program, instead I got an infinite recursion causing SIGSEGV a couple of times. I think the key missing drawback that isn't stated here is that even if you fix all of your logical bugs, then unless every function call is tail-call optimized by the compiler, then your parser isn't quite safe for untrusted regular expressions. e.g., A user could write `(((((...a...)))))`, and if you don't guard against it with some hard limit on nesting depth, then you're vulnerable to stack overflows. So let's say you implement nesting limits. What limit should be set? /shrug This is why I write my regex parsers without recursion and instead use an explicit stack on the heap. It is then a bit easier to more robustly manage nesting limits.

kindfellow92 9y ago
Parser(s)? As in more than one? Hopefully you’ll ever need to only write one parser (e.g. for Rust) but practically zero since regexs are a solved problem.
- burntsushi 9y ago
  Yes. I wrote Rust's regex crate. The parser has gone through a couple rewrites (and another one is ongoing), so that's where the plural came from. :)
- zodiac 9y ago
  Regexes can't be used for parsing (e.g. the language of balanced parantheses)
  - ThePadawan 9y ago
    I think your parent post referred to using a parser to parse regexes, not using regexes to parse another language.
  - steveklabnik 9y ago
    Regular languages cannot. Many (most?) implementations of “regular expressions” can express more complex grammars. (My sibling is also correct)
Peaker 9y ago
gcc supports auto-generating stack overflow checks. You can implement your own handler for a stack overflow, allowing allocation of additional stack space which can be chained to the original stack. This is how some language runtimes handle [or used to handle] segmented stacks that grow on demand.
- burntsushi 9y ago
  > gcc supports auto-generating stack overflow checks. I don't know what that means. I don't see how auto-generated code would fix my problem. The regex parser should return an error to the caller if the regex exceeds some limit. Dynamically growing the stack sounds like a cute hack. I doubt I'd consider it superior to just using the heap though.
  - Peaker 9y ago
    You can use that to make stack overflow a (relatively) graceful error instead of a segfault.
tinkersleep 9y ago
You are absolutely right! But I'd like to stress that this is a problem of this implementation, but not of the CPS technique as such: CPS is just not used to its extreme here to allow for tail-call optimisation of all functions, which would then result in O(1) stack usage. The problem with this implementation is that gcc cannot tail-call optimise every function call, because continuation results are evaluated in the middle of the computation (e.g. for all 'or' decisions). This means the compiler cannot discard the old stack frame. I should try harder and see what gcc can then do for me! :-)
- burntsushi 9y ago
  I am quite skeptical that it is possible. Because of that, I would love for you to get in touch with me if you achieve it. :) Also, I should have led with this: I very much enjoyed the blog post and perusing the code. Great work!
  - tinkersleep 9y ago
    Thanks! It was fun tinkering. For the regex problem, because of the required backtracking, data usage is definitely not O(1), so the continuation data will not be storable on the stack for an O(1) stack tail-call-only CPS version of regex. That context data for the continuations will need to go to the heap, and so we are basically back to how you'd avoid recursion to avoid unbounded stack: by using some data structures on the heap. And at that point, you could just use more straight-forward data structures than those needed for CPS here. Anyway, the one-phase parsing+matching is still interesting, I think, and it is worth a try to get it to work in O(1) stack by storing the continuation data on the heap. So after fixing SIGSEGVs for infinite recursions, I will go back to fixing memory leaks. :-)

kindfellow92 9y ago

Parser(s)? As in more than one? Hopefully you’ll ever need to only write one parser (e.g. for Rust) but practically zero since regexs are a solved problem.

burntsushi 9y ago
Yes. I wrote Rust's regex crate. The parser has gone through a couple rewrites (and another one is ongoing), so that's where the plural came from. :)
zodiac 9y ago
Regexes can't be used for parsing (e.g. the language of balanced parantheses)
- ThePadawan 9y ago
  I think your parent post referred to using a parser to parse regexes, not using regexes to parse another language.
- steveklabnik 9y ago
  Regular languages cannot. Many (most?) implementations of “regular expressions” can express more complex grammars. (My sibling is also correct)

Peaker 9y ago

gcc supports auto-generating stack overflow checks. You can implement your own handler for a stack overflow, allowing allocation of additional stack space which can be chained to the original stack. This is how some language runtimes handle [or used to handle] segmented stacks that grow on demand.

burntsushi 9y ago
> gcc supports auto-generating stack overflow checks. I don't know what that means. I don't see how auto-generated code would fix my problem. The regex parser should return an error to the caller if the regex exceeds some limit. Dynamically growing the stack sounds like a cute hack. I doubt I'd consider it superior to just using the heap though.
- Peaker 9y ago
  You can use that to make stack overflow a (relatively) graceful error instead of a segfault.

tinkersleep 9y ago

You are absolutely right! But I'd like to stress that this is a problem of this implementation, but not of the CPS technique as such: CPS is just not used to its extreme here to allow for tail-call optimisation of all functions, which would then result in O(1) stack usage. The problem with this implementation is that gcc cannot tail-call optimise every function call, because continuation results are evaluated in the middle of the computation (e.g. for all 'or' decisions). This means the compiler cannot discard the old stack frame. I should try harder and see what gcc can then do for me! :-)

burntsushi 9y ago
I am quite skeptical that it is possible. Because of that, I would love for you to get in touch with me if you achieve it. :) Also, I should have led with this: I very much enjoyed the blog post and perusing the code. Great work!
- tinkersleep 9y ago
  Thanks! It was fun tinkering. For the regex problem, because of the required backtracking, data usage is definitely not O(1), so the continuation data will not be storable on the stack for an O(1) stack tail-call-only CPS version of regex. That context data for the continuations will need to go to the heap, and so we are basically back to how you'd avoid recursion to avoid unbounded stack: by using some data structures on the heap. And at that point, you could just use more straight-forward data structures than those needed for CPS here. Anyway, the one-phase parsing+matching is still interesting, I think, and it is worth a try to get it to work in O(1) stack by storing the continuation data on the heap. So after fixing SIGSEGVs for infinite recursions, I will go back to fixing memory leaks. :-)