15th November 2012, 13:57
Call stack compression
An idea came to my mind recently - compress the call stack to allow both fully-featured functional programming (ie lots of recursion) and detailed stack traces.
Functional programming means deep call stacks with lots of tail calls. Tail call can be optimized to simple jump and replacement of stack frame, thus avoiding the increase of stored stack frames. But replacement of stack frame means we lose the information that should be in the stack trace.
The question is: can we efficiently compress the call stack, ie achieve good compression ratio every time we do stack frame replacement (ie use jump that replaced the tail call)?
I have a rough idea how to solve that - devise some sort of compressed suffix tree, ie suffix tree whose size is proportional to call stack size and inversely proportional to compression ratio of the call stack. Suffix trees could be too slow for real-time compression so probably a faster method should be invented.
What do you think about it?