This is a very intereresting video featuring one of the authors (Nada Amin). Strangely enough, I watched it a few hours ago. It's a quick overview of the "tower of interpreters" idea and some possibilities that it brings.
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).
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.
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.
I haven't read this paper yet (I've been meaning to), but: a staged programming language is something like quasiquoting in Lisp, but typically with a typing discipline: a value can have the type "expression of type T". A two-stage program might have a type like "expression of type (expression of type U)". This helps to efficiently implement embedded languages just as Lisp macros can expand to faster code than runtime-interpreted metaprogramming; presumably the typing helps in that you don't have to start the compiling from "scratch" at the s-expression level.
Stage polymorphism I guess means abstracting over how many stages there are till you get to plain old non-code data; hopefully someone will chime in who's more up to date or free to read the paper tonight.
No, it's a type. 'list' is a type constructor. Staging is a different beast from types altogether. Read up on MetaOCaml for how staging works in a typed language.
You're probably confused by the fact that typed languages assign types to expressions, but a value of type "expression" is something different. You're reifying the AST of an expression as a value at runtime, and then you can build further expressions, and then compile them all.
A type is an expression. The type of an expression is the result of evaluating the type expression, in this case, "list a". In other words, the type constructor invocation that gives the expression its type is itself an expression. In that context, I'm wondering how type expressions differ from "stages"--does the type expression language need to be sufficiently complex (e.g., Turing complete)?
A type is not an expression. We wouldn't have two words designating the same concept. Even in dependently typed languages where types and expressions are intermingled, they are still distinct concepts.
Now, you can sort of talk about expressions in the "type language", but these are not expressions of the "value language". Even so, an unqualified statement like "a type is an expression" is simply incorrect because "expression" always refers to the value language, so that phrase conveys the completely wrong intention.
Finally, as for how to relate staging to concepts you might be more familiar with, I suggest the paper, Closing the Stage: From Staged Code to Typed Closures [1].
Types (or "type expressions") are expressions whose type is type. In other words, types are higher order expressions. It's a poor definition or discipline that doesn't capture this basic concept.
"Polymorphism" means that a piece of code can be used, unmodified, for multiple situations. Usually this works by adding parameters to the code, and having each situation pass in suitable values of those parameters.
From reading section 3, it seems that "stage polymorphism" allows the same piece of code to be used in different "stages". For example, we might have a function call like `square(4)`: if we evaluate it now, like an interpreter, we get the value `16`; if instead we "stage" it, like a compiler, we get code which (when executed) will call `square(4)`.
The polymorphism comes from parameterising the 'elimination forms' (branching, function calls, etc.). We can think of `square(4)` as being `call(square, 4)`, and we're overloading the choice of `call`: for an interpreter, we use a `call` which does the function call now; for a compiler, we use a `call` which constructs code for doing the call.
As for regular expressions in Javascript, this is more powerful for several reasons. Firstly, regular expressions are so limited that they can't reference other values; hence there's not much difference between interpreting or compiling them.
What about a more powerful embedded language, like `eval` running Javascript from within Javascript? That has the problem that we can't send values between different "levels" of Javascript. Say we have a value `x = 42` and we want to create an 'embedded' program `x + x`. We can pass around a string `"x + x"`, but when it eventually gets sent to `eval` it won't necessarily use the same `x` as we intended (it basically suffers from dynamic scope).
If we had a way to "stage" Javascript from within Javascript, we could ensure the correct value is used, but we'd probably have to write some funky expression like `<,x + ,x>` (depending on the language; take a look at MetaML for an example!). If we want to stage some Javascript which stages some Javascript (and so on), we'd accumulate horrible nesting/escaping boilerplate.
This "stage polymorphism" lets us write `x + x` for all stages, including things which are evaluated immediately. Their technique is also one pass, meaning that we don't have to run evaluators in compilers in evaluators... It also works with reflection, and with interpreters which implement the language semantics differently (they include examples like maintaining a count of how many times a variable is accessed, and for converting to continuation passing style).
Thanks for this explanation. I find the topic interesting because I have been thinking about how to use a similar technique to enable interactive debugging of meta-language expressions using the non-meta-level language's own debugger. Suppose you have a function that builds a (staged) expression object for later interpretation. If an exception occurs while the interpreter is executing it, or perhaps you merely want to see the code showing how/why the expression object was put together how it was, the information you get in the non-meta-level debugger will often be too low-level to be useful. And you can't even walk back up the stack to get it, because the function which built the expression has already returned, having completed it's job which was only to build the expression object, not to run it.
A solution is to make the function which builds the expression object be (1) a callback and (2) polymorphic in the staged sense as you described, where the exact same code 'x + x' can have different meanings in different stages. In the first pass, the objects the callback works with have operations which are defined to just build an expression object without evaluating it. In subsequent passes, the same code (or a differently parameterized specialization of the same generic code) is called again but this time it is manipulating objects bound to actual runtime state. The callback may or may not be actually doing any computation (perhaps the interpreter can or is evaluating the expressions itself, and the operations the callback is doing are all nops).
But just the act of re-threading execution back through the callback function gets the expression builder function's name back onto the stack for exception stack traces. It also provides a sort of "high level user interface for debugging": if the user puts a breakpoint in the callback code, examining the variables in it gives information about the runtime values passing through the interpreter. I.e. it would provide a way for the user to directly look for temporary variable "x" in the interpreter's current running state.
I guess that's in some sense the opposite of collapsing stages? In a way of thinking this is putting stages back in after they have been collapsed, for the purpose of tracing execution.
The usage of the word 'polymorphism' in case of 'generic programming' introduces so much confusion. IMHO, polymorphism should be used only for inheritance (virtual inheritance in C++).
Unless the term 'generic programming' is older than I'm aware of, the word 'polymorphism' has been a technical term in programming language research longer than 'generic programming'. Certainly the word polymorphism has been in use longer than the language C++ has existed. Inheritance polymorphism / class polymorphism is one means of implementing polymorphism. It does cause a moment of confusion the first time you see the word used in a more general sense if you are used to thinking of polymorphism only referring to one kind of polymorphism.
This code is subclass polymorphic, since we can pass in a Dog or a Dolphin, or some other type of Mammal, and it will work unchanged.
Yet this is completely orthogonal to inheritance! There are two ways we might actually implement these constructs:
- Mammal is an interface: Dog implements breathe by operating its lungs and move by operating its legs; Dolphin implements breathe by operating its lungs and move by operating its tail and fins.
- Mammal is an abstract class which implements breathe by operating its lungs. Dog inherits breathe and implements move by operating its legs; Dolphin inherits breathe and implements move by operating its tail and fins.
Both of these are valid approaches, but consider that:
- Only the second approach uses inheritance, so it seems strange to limit "polymorphism" to only this case.
- The checkStatus code doesn't actually care which approach we take. It's "polymorphic in our choice of polymorphism"!
Also, let's say that we did restrict the term "polymorphism" to these sorts of mechanisms. We might say that the above example is "polymorphic in the choice of Mammal". In which case, the "stage polymorphism" of this article is nothing other than "polymorphic in the choice of stage".
We could implement it in a language like C++ something like:
Stages can call functions with arguments
Stages can branch on booleans
...
Interpreter is a Stage
Compiler is a Stage
We achieve polymophism by passing around the currentStage, and writing code like `currentStage.call(myFunc, myArg)`. If `currentStage` is an `Interpreter`, the call will be performed immediately. If `currentStage` is a `Compiler`, code will be generated to perform the call.
The only difference between such an OO setup and the actual implementation in the article is that boilerplate like `currentStage` is all handled implicitly, rather than manually passed around, and we overload the normal language constructs rather than replacing them with methods, e.g. we can write `double(foo)` instead of `currentStage.call(double, foo)`, and `if foo then bar else baz` instead of `currentStage.branch(foo, bar, baz)` (or something even worse, to ensure that `bar` and `baz` get delayed!)
C++ supports multiple kinds of polymorphism depending on if and how they can be implemented with no or low runtime overhead. C++ does tend to conflate class inheritance with interface polymorphism, but there is an implementation reason for doing so.
In C++, an image of the data members of a base class is embedded verbatim inside a derived object. This means that a function compiled to work with a pointer to a block of memory formatted as a Base object can just as well be passed a pointer to the region of memory corresponding to a Base object inside the larger block of memory allocated to a Derived object. So C++ saying that inheritance implies polymorphism is not because they are conceptually the same, but rather that an implementation exists that can give both features at once for little runtime overhead.
Also, C++ doesn't distinguish between interfaces and classes; an interface in C++ is just a class with no data members.
Runtime polymorphism in C++ requires marking methods as virtual. They are not virtual by default. Why not? Because the default assumption is that code can operate directly (and efficiently) on what it statically knows about an object, and in the case when none of the methods are virtual it allows the object and code to be slimmed down slightly.
C++ has many other forms of polymorphism, method overloading or operator overloading (a.k.a. ad hoc polymorphism), templates, etc. The reason they are not all treated as the same is because their implementations are different. Hiding all of the differences would impose a small but fixed cost on all of them, which would be counter to C++'s principle of you don't pay for what you don't use.
Thanks for the info. I'm not sure if it's supporting my point, refuting it, or is an aside :)
> Also, C++ doesn't distinguish between interfaces and classes; an interface in C++ is just a class with no data members.
This doesn't invalidate the point about polymorphism being orthogonal to inheritance. The point is that we can choose whether or not to use inheritance: `breathe` could be implemented in `Mammal` and get inherited by `Dog` and `Dolphin`, or Dog and Dolphin could implement `breathe` themselves and there would be no inheritance. Either way, we still have (subclass) polymorphism, so saying "polymorphism should mean inheritance" seems like a bad idea.
https://www.youtube.com/watch?v=SrKj4hYic5A