[phaedrus]

I've been working on techniques to enable a low-level interpreter engine to present (meta level) user function names in stack traces and (meta level) user variables on the debugger watch window, instead of just spilling the guts of the interpreter when you break into it with a C++ debugger. The basic idea is to design the API of the expression-building library so that the user code is always written in the form of callback functions which support staged execution. The first stage builds the expression object to be interpreted; subsequent stages could be all nops yet still serve the purpose of tracing execution and explaining generated plans.

It's encouraging to me that starting from a different goal, I reached a similar point in design-space as you describe in this paper.

I want to ask you about the role of continuation passing style (CPS) in towers of interpreters, and whether you view it as fundamental or merely a feature which is possible to support or not support?

The reason I ask is that in my work on improving debugging, I didn't start out with the a priori intent to use CPS style, but I keep ending up with continuations popping up somewhere. Even when I try to wring them out (to simplify the use of the library) they are still "there", just maybe hidden or disguised.

The intuitive explanation is that, during "tracing mode," it is not enough to simply invoke the callback (and allow it to return). Instead, we want to jump to the callback function, and then leave it's frame open and on the stack while we do additional work. How does the interpreter regain control before the user's callback function has returned? Probably, via a continuation.

However I think there is also an interesting parallel or connection to coroutines. Yes, CPS can be used to implement coroutines. However, suppose coroutines are instead a language primitive, then similar staging and polymorphism techniques could be used to debug coroutines. By inverting the relationship between "main coroutine" and "worker coroutine", instead of treating the worker as a function called-by the outside world, redefine the worker as the thing driving the program and treat "everything that the rest of the world does between coro-yield and resume" as a subroutine call from the worker coroutine.

What I haven't worked out yet is if and how the third leg of this triangle may be completed: using coroutines to implement the staging and debug tracing mechanism (instead of CPS).

[tiarkrompf]

Sounds interesting. About the role of CPS: for specialization purposes, CPS can have some benefits by splitting control flow. For example, if your input is "if (c) a else b" and c is a staged (=symbolic) value, then a CPS interpreter can ignore the control-flow join that's implied by the if-then-else, and continue processing longer paths independently. However, this also quickly leads to exponential code blow-up, and hence, we do not use CPS for the core model described in the paper.

[phaedrus]

Thanks! The main application I'm looking at is logic programming, so the control flow example you give is apropos. For example a user function which requests A AND B could be written: "if not(A) then fail, else if not(B) then fail, else succ". The first time through, we might want to actually take every branch so that we learn about the whole expression. At this stage it's just building a graph that records edges between variables and constraints, so the exponential factor is averted.

However I keep going back and forth between having the user write logic in a "control flow" representation versus in a "declarative" way (e.g. "return A && B"). The declarative way expresses intent directly, but loses most of the hooks for stepping through in a callback. Expressing it as control flow on the other hand requires some form of custom control flow operators because the built-in ones can't be redefined in C++.

It turns out logical "OR" is very subtle because we want to "actually have taken" exactly one of the options, but we also don't want to fail contexts where the preconditions for both sides are satisfied; we actually just want to arbitrarily pick one (and then the other), but only one per run (except when we're reflecting).

Subtle things like that make me nervous as requirements the user's control flow logic has to abide by. So my main challenge is to either figure out constructs which make this foolproof, or come up with "nearly declarative" forms: code which expresses intent declaratively, but does so in multiple statements so that they can be single-stepped through.