Let's Talk About Backtraces and Stacks

[Noah Lavine]

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