Steppers: HoPL 4/5/2004

Presented by Ryan Culpepper
Transcribed by Felix Klock

Here's the naive picture of (buggy) program evaluation:

Program -----------------------------------> Wrong Answer

Q (from Audience (Greg)) : Shouldn't the right hand side really have said "behavior", not "answer", so that we can talk about long-lived systems with input and output, etc
A: That's one way of looking at computation. But we're going to go with a simplified view for the purposes of this discussion.

But this picture is really a lie. Here's what is really going on:

Program -->-->-->-->-->-->-->-->-->-->-->--> Wrong Answer

That is, we don't go from our program to a result in a single step.Instead, we go through a sequence of small steps, until we reach our answer.

We can use this view to discuss the exact point in the evalution where the bug is located: the step where something went counter to our expectation. (marked by a asterisk here)

Program -->-->-->-->-->--*-->-->-->-->-->--> Wrong Answer

But that pictures is really a lie too. Here's what is really going on:

  Px    -->-->-->-->-->--*-->-->-->-->-->--> Wrong Answer

This represents the conversion of our program into some other representation (compilation, macro-expansion, what have you)before going through the rewrite process.

What we want is some relation between the two pictures...

Program -->-->-->-->-->--*-->-->-->-->-->--> Wrong Answer
  |             /|\                              
  |             |||                              
  |             |||                              
 \|/            \|/                              
  Px    -->-->-->-->-->--*-->-->-->-->-->--> Wrong Answer

This way, we can map from one state to the other, and understand the intermediate states of the evaluation in terms of the original source program, and use that information to track down the asterisk.

Where should this mapping come from?

Interpreters? No, they're too slow.

Q (from Audience (Richard)) : But is that statement really justified? Its common practice to turn off optimizations when you debug code. Why not just switch to an interpreter when you need to debug?
A: But then you need to maintain a relationship between your compiler and your interpreter... can you trust it?

Steps Towards Better Debugging Tools for Lisp (Lieberman, '84)

How do we debug? Well, I like to think that we act like a murder mystery detective: we make broad steps (analogous to stepping across function calls) until we determine that something is wrong.

We can't step backward. (But we'd really like to)

The tools presented report the status of the computation in terms of the original source code.

A Debugger for Standard ML (Tolmach and Appel, '90, '93)

The big mapping in the middle of our last picture relies on

Thus, the big mapping is HARD to implement.

Lets take another approach: build the debugging as a Source --> Source* (* means "almost" here) translation. That way, we remove these difficulties.

Q (from Audience (David)) : Doesn't this introduce as much of a slow-down as switching to an interpreter?
A: This is 2 to 5 times slower. An interpreter is 10 to 100 times slower.
Q (from Audience (Sam)) : Isn't this is the same as gdb debuginfo?
A: This is portable; gdb debuginfo is not platform independent.

So now we've made the debugging info part of the observable behavior of the program. (Thus it is safe to compile the output of the above Source --> Source* )

The core language is standard, except that I've added some asterisks at key points:
exp ::= ... | exp * exp | let pattern =>* exp ...

Scribe's Note: Matthias jumped in around here and said: The asterisk here marks points where we switch continuations. Here's how the ideas progressed: Duba adds call/cc to SML. Tolmach and Appel love it, build the backstepping debugger on top of it. However, Duba points out the need for call-with-current-store as well. So they add that, using Tarjan difference arrays as the underlying implementation.

Modelling an Algebraic Stepper (Clements, Flatt, Felleisen '01)

They start with base language Λ.

Then they compile that into Λb which is the base language plus breakpoints.

Then they compile that into Λcm which is the base language plus continuation-marks and an OUTPUT operation.

Q (from Audience (Sam)) : How is this a debugger?
A: The outputs operations feed your debug channel, giving you the input to reconstruct the reduction semantics.

Scribe's Note: Matthias jumped in and said: when you've got a picture like this:
 M0 --> M1 --> M2 --> ... 
 N0 --> N1 --> N2 --> ... 
the debugger is responsible for spitting out the sequence M0, M1, M2, ... when your system is running at the level of the N0, N1, N2, ...

And this is true for any language; Scheme, Java, etc. I don't care what your language has. If you give me your rewrite rules, then I can tell you what your debugger should be doing (see above).