4 ms·
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 i
by 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 agoI 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 agoThanks! 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. :-)