6 ms·
Collapsing towers of interpreters [pdf]
- sharpercoder 9y agoHow is stage polymorphism different then a language supporting embedded languages (e.g. javascript with regex)?
- abecedarius 9y agoI 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.
- weberc2 9y ago> (Expression of type U) Isn't this how many statically toed functional languages model their type systems? 'list a' is an expression, is it not?
- abecedarius 9y agoThink of this like quoting and eval in Lisp. The type "expression of type U" might work with operations like eval: "expression of type U" -> U quote: U -> "expression of type U" chriswarbo's reply higher up should be taken to supersede my reply -- he's obviously more current on this stuff.
- naasking 9y ago> 'list a' is an expression, is it not 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.
- weberc2 9y agoA 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)?
- naasking 9y ago> A type is an expression. 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]. [1] http://lambda-the-ultimate.org/node/2575 http://lambda-the-ultimate.org/node/2575
- weberc2 9y agoTypes (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.
- chriswarbo 9y ago"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).
- reacweb 9y agoThe 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++).
- minsight 9y agoThis 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. https://www.youtube.com/watch?v=SrKj4hYic5A https://www.youtube.com/watch?v=SrKj4hYic5A
- sindhuabi 9y agoThis is a very intereresting video featuring one of the authors (Nada Amin). Strangely enough, I watched it a few hours ago. It brings some ideas.
- Tarq0n 9y agoThis seems to be a bot, but I can't find a way to report it.
- tiarkrompf 9y agoI'm one of the authors. Happy to answer questions.
- phaedrus 9y agoI'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).