Hello all, There has been some talk on this list about letting Guile show useful backtraces for tail-recursive functions. I was thinking about how to optimize local variable allocation, and realized that this question is related to that, and to other things too. So I'd like to ask people now how we want to handle this set of related issues, so I can keep working on them.
The standard implementation of this is keeping a ribcage structure, where the backbone is the standard stack and the ribs are bounded lists of tail calls made for each stack frame - say the last 50 tail calls. I can think of two ways we might do this: the ribcage could be part of the standard Scheme stack, with a rib hanging off of each stack frame, or there could be a separate ribcage structure. A separate ribcage would duplicate information and might be slower (in the debug VM at least), but would also give us more freedom for variable allocation in the regular stack (see issue 1). Here are the issues: 1) Variable allocation. I had an idea to allocate lexical variables to slots on the stack in a way that would conserve our stack space as much as possible. It isn't too hard to implement, but if we free lexical variables aggressively, it will make debugging harder because local variable information won't be around. We could provide an option to turn smart allocation off, and choose this option at the REPL. However, if we implement a ribcage separate from the Scheme stack, then we can allocate as aggressively as we want because the debugging information will still be there when we need it. 2) Backtraces for tail calls. In order to give useful backtraces for tail calls, we need to record information about them. We could accomplish this equally well with either of the two implementation strategies. 3) Backtraces from the evaluator. Ideally, I'd like backtraces from the evaluator not to show the evaluator's own functions, unless the user asks for them. That would make backtraces the same in evaluated and compiled code, and would also be easier for the user to understand. If we choose a separate ribcage, I had thought of having the evaluator write to its own ribcage structure, which would be separate from the standard one. The standard one would still be around, but it would only appear on request. If we choose to make the ribcage part of the Scheme stack, the other solution is to let the evaluator provide a filter to the frames on the stack, to make its function calls appear different than they really are, and let the user optionally remove this filter if they want to debug the evaluator itself. It seems to me that it's best for the ribcage to be part of the Scheme stack. Issues 2 and 3 can be addressed reasonably well in either implementation. Issue 1 is easier if the ribcage is separate, but if you're recording information about every variable separately, then you're still using extra storage space no matter how cleverly the regular Scheme stack is allocated, so you might as well just use naive allocation in the regular stack. The one thing that makes me hesitate is that this probably means reserving an extra word in every stack frame (to hold the rib), even if that stack frame is internal to Guile and not meant to be debuggable. Also, I think that MIT Scheme uses a separate ribcage, and they have a working implementation of this. What does everyone else think? Noah
