How is stage polymorphism different then a language supporting embedded languages (e.g. javascript with regex)?
"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 no…
Collapsing towers of interpreters [pdf]
11–20 of 25 posts
Re: Collapsing towers of interpreters [pdf]
#12Earlier quoted context omitted.
> (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?
> '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 y…
Re: Collapsing towers of interpreters [pdf]
#13Earlier quoted context omitted.
> '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 y…
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].
Re: Collapsing towers of interpreters [pdf]
#14Re: Collapsing towers of interpreters [pdf]
#15Earlier quoted context omitted.
"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 no…
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++).
Re: Collapsing towers of interpreters [pdf]
#16How is stage polymorphism different then a language supporting embedded languages (e.g. javascript with regex)?
"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 no…
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.
Re: Collapsing towers of interpreters [pdf]
#17Earlier quoted context omitted.
"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 no…
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++).
If we think of a classic OOP example, we might say (in some made-up language):
Mammals can breathe
Mammals can move
Dogs are Mammals
Dolphins are Mammals
From this, we know that Dogs and Dolphins can breathe and move, so we can write code like: function checkStatus(Mammal m) {
try {
m.move();
return "Free";
} catch {
try {
m.breathe();
return "Trapped";
} catch {
return "Dead";
}
}
}
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!)
Re: Collapsing towers of interpreters [pdf]
#18Earlier quoted context omitted.
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++).
Forgive my lack of C++ knowledge, but surely inheritance is a separate topic to polymophism? If we think of a classic OOP example, we might say (in some made-up language): Mammals can breathe Mammals can move Dogs are Mammals Dolphins are Mammals From this, we know that Dogs and Dolphins can breathe and move, so we can write code like: function checkStatus(Mammal m) { try { m.move(); return "Free"; } catch { try { m.…
Re: Collapsing towers of interpreters [pdf]
#19I'm one of the authors. Happy to answer questions.
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).
Re: Collapsing towers of interpreters [pdf]
#20Earlier quoted context omitted.
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++).
Forgive my lack of C++ knowledge, but surely inheritance is a separate topic to polymophism? If we think of a classic OOP example, we might say (in some made-up language): Mammals can breathe Mammals can move Dogs are Mammals Dolphins are Mammals From this, we know that Dogs and Dolphins can breathe and move, so we can write code like: function checkStatus(Mammal m) { try { m.move(); return "Free"; } catch { try { m.…
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.