Collapsing towers of interpreters [pdf]

Collapsing towers of interpreters [pdf]
cs.purdue.edu

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.

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 `` (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).

    eval: "expression of type U" -> U
    quote: U -> "expression of type U"