5 ms·

I remember being really excited about the derive-a-compiler-from-a-partial-evaluator premise when I first ran across it. You genuinely do get a compiler from an

I remember being really excited about the derive-a-compiler-from-a-partial-evaluator premise when I first ran across it. You genuinely do get a compiler from an interpreter plus a partial evaluator. That trick does work. The gotcha I didn't spot at the time is that a compiler is (I think, could be argued either way) easier to write than a partial evaluator. The "get it for free bit" only really applies if someone else gave you the partial evaluator and if you somehow don't need to spend ages debugging why that partial evaluator isn't behaving like you hoped. Now that I'm somewhat more beaten down by toolchain dev, I'm starting to think compilers are easier to write than interpreters. It's definitely not a clear win in favour of the interpreter. If you compile to x64, or to C, or to javascript or whatever, you now have a thing you can debug with whatever tools are native to that target. If you run in an interpreter, you get to debug that interpreter running the program, with whatever somewhat ad hoc debugging tools you put into the interpreter yourself. Getting useful semantic error message out of an interpreter at partial evaluation time (aka the "compile time" of the aggregate tool) is probably solvable but not likely to work out of the box. Partial eval isn't really a phase separation friendly thing.

cfallin 2y ago
This is indeed a good point and something I want to write about when I eventually do a blog post on weval. A few counterpoints that I'd offer (and what led me to still take this approach): - If the target has sub-par debugging infrastructure, it can be easier to debug an interpreter (which is portable) then apply the semantics-preserving PE. In particular when targeting Wasm outside the browser, there is... not really a good debug experience, anywhere, for that. It was way easier to get an interpreter right by developing on native with gdb/rr/whatever, and then separately ensure weval preserves semantics (which I tested with lockstep differential execution). - Maintenance: if one is going to have an interpreter and a compiler anyway (and one often wants this or needs this e.g. to handle eval()), easier for them both to come from the same source. - Amortized cost: in the Wasm world we want AOT compilers for many languages eventually; there are interpreter ports with no Wasm backends; developing weval was a one-time cost and we can eventually apply it multiple times. - If the semantics of the existing interpreter are quite nontrivial, that can push the balance the other way. I designed weval as part of my work on SpiderMonkey; extremely nontrivial interpreter with all sorts of edge cases; replicating that in a from-scratch compiler seemed a far harder path. (It's since been done by someone else and you can find the "wasm32 codegen" patchset in Bugzilla but there are other phasing issues with it from our use-case's PoV; it's not true AOT, it requires codegen at runtime.) I don't think the tradeoff is always clear and if one is building a language from scratch, and targeting a simple ISA, by all means write a direct compiler! But other interesting use-cases do exist.
- JonChesterfield 2y ago
  The divergent semantics risk between the interpreter and the compiler is a really big deal. It's genuinely difficult to get a language implementation to behave exactly as specified, even when the spec is do the same as some other implementation. Treating "compiled code" as specialising the interpreter with respect to the program is a great solution to that, since the bugs in the optimiser/partial-evaluator (they're kind of the same thing) are unlikely to be of the same class as bugs from independent implementations. Wasm is a really solid target for heroic compiler optimisations. It's relatively precisely specified, user facing semantic diagnostics are in some language front end out of sight, aliasing is limited and syscalls are finite with known semantics. Pretty much because it was designed by compiler people. You've picked a good target for this technique.
  - achierius 2y ago
    One problem with Wasm is that in practice there's not as much optimization work to do as you might expect, as the higher-level compiler which produced it already di a lot of the work. Of course you still need to lower the stack machine + locals to actual spills/fills/etc., but still a chunk of the work is already done for you.
titzer 2y ago
> The gotcha I didn't spot at the time is that a compiler is (I think, could be argued either way) easier to write than a partial evaluator. I agree that this is sometimes true, but there are several, IMHO bigger, issues: 1. The partial evaluation of the interpreter might degenerate back to getting a copy of the interpreter loop (or multiple!) and not achieve any speedup, just memory overhead 2. The partial evaluator might need additional annotations on what is and is not mutable; it might need a lot of help in order to constant-fold away a key piece of data. Tuning that and getting wrong and result in #1. 3. Partially evaluating the interpreter is a pretty slow compiler. You need to do the second Futamura projection (apply the partial evaluator to an interpreter loop without the user code) in order to get a fast compiler. That means the partial evaluator needs to be in the same IR as the partial evaluator's input language. That said, I've chatted a bit with Chris offline about this, and I think this work is really cool and promising. I might tinker with this a little in Wizard too.
- JonChesterfield 2y ago
  That is better expressed than my rambling! The futamura projection is satisfied by passing the "program" directly to the interpreter without optimising either, which is sometimes useful as a packaging exercise and does look somewhat like a non-optimising compiler. If you want this trickery to make a useful compiler, the partial evaluator picks up global value numbering, dead code elimination, loop transforms - the effective partial evaluator is very much the optimisation passes of a compiler. It can still be a win if someone else wrote said partial evaluator. Point 2 is the usual "my compiler is not sufficiently smart, I must annotate the program" problem, with the slight twist that you're annotating the interpreter in the hope that it does useful things with the end program. Interacts with hoping someone else built the dependency well. And yeah, generated compilers in this fashion have a reputation for being slow, and for not being great optimising compilers, where self application might dig oneself out of the hole. Very like adding optimisations to your compiler to make your compiler faster when building your compiler. All in all the compiler for free tagline (not specifically this post, it's written on a lot of futamura references) feels a bit like an inside joke. It reminds me of the sad discovery that a metacircular interpreter can't interpret itself after all since what you've written is a heavily obfuscated infinite loop.

cfallin 2y ago

This is indeed a good point and something I want to write about when I eventually do a blog post on weval. A few counterpoints that I'd offer (and what led me to still take this approach): - If the target has sub-par debugging infrastructure, it can be easier to debug an interpreter (which is portable) then apply the semantics-preserving PE. In particular when targeting Wasm outside the browser, there is... not really a good debug experience, anywhere, for that. It was way easier to get an interpreter right by developing on native with gdb/rr/whatever, and then separately ensure weval preserves semantics (which I tested with lockstep differential execution). - Maintenance: if one is going to have an interpreter and a compiler anyway (and one often wants this or needs this e.g. to handle eval()), easier for them both to come from the same source. - Amortized cost: in the Wasm world we want AOT compilers for many languages eventually; there are interpreter ports with no Wasm backends; developing weval was a one-time cost and we can eventually apply it multiple times. - If the semantics of the existing interpreter are quite nontrivial, that can push the balance the other way. I designed weval as part of my work on SpiderMonkey; extremely nontrivial interpreter with all sorts of edge cases; replicating that in a from-scratch compiler seemed a far harder path. (It's since been done by someone else and you can find the "wasm32 codegen" patchset in Bugzilla but there are other phasing issues with it from our use-case's PoV; it's not true AOT, it requires codegen at runtime.) I don't think the tradeoff is always clear and if one is building a language from scratch, and targeting a simple ISA, by all means write a direct compiler! But other interesting use-cases do exist.

JonChesterfield 2y ago
The divergent semantics risk between the interpreter and the compiler is a really big deal. It's genuinely difficult to get a language implementation to behave exactly as specified, even when the spec is do the same as some other implementation. Treating "compiled code" as specialising the interpreter with respect to the program is a great solution to that, since the bugs in the optimiser/partial-evaluator (they're kind of the same thing) are unlikely to be of the same class as bugs from independent implementations. Wasm is a really solid target for heroic compiler optimisations. It's relatively precisely specified, user facing semantic diagnostics are in some language front end out of sight, aliasing is limited and syscalls are finite with known semantics. Pretty much because it was designed by compiler people. You've picked a good target for this technique.
- achierius 2y ago
  One problem with Wasm is that in practice there's not as much optimization work to do as you might expect, as the higher-level compiler which produced it already di a lot of the work. Of course you still need to lower the stack machine + locals to actual spills/fills/etc., but still a chunk of the work is already done for you.

titzer 2y ago

> The gotcha I didn't spot at the time is that a compiler is (I think, could be argued either way) easier to write than a partial evaluator. I agree that this is sometimes true, but there are several, IMHO bigger, issues: 1. The partial evaluation of the interpreter might degenerate back to getting a copy of the interpreter loop (or multiple!) and not achieve any speedup, just memory overhead 2. The partial evaluator might need additional annotations on what is and is not mutable; it might need a lot of help in order to constant-fold away a key piece of data. Tuning that and getting wrong and result in #1. 3. Partially evaluating the interpreter is a pretty slow compiler. You need to do the second Futamura projection (apply the partial evaluator to an interpreter loop without the user code) in order to get a fast compiler. That means the partial evaluator needs to be in the same IR as the partial evaluator's input language. That said, I've chatted a bit with Chris offline about this, and I think this work is really cool and promising. I might tinker with this a little in Wizard too.

JonChesterfield 2y ago
That is better expressed than my rambling! The futamura projection is satisfied by passing the "program" directly to the interpreter without optimising either, which is sometimes useful as a packaging exercise and does look somewhat like a non-optimising compiler. If you want this trickery to make a useful compiler, the partial evaluator picks up global value numbering, dead code elimination, loop transforms - the effective partial evaluator is very much the optimisation passes of a compiler. It can still be a win if someone else wrote said partial evaluator. Point 2 is the usual "my compiler is not sufficiently smart, I must annotate the program" problem, with the slight twist that you're annotating the interpreter in the hope that it does useful things with the end program. Interacts with hoping someone else built the dependency well. And yeah, generated compilers in this fashion have a reputation for being slow, and for not being great optimising compilers, where self application might dig oneself out of the hole. Very like adding optimisations to your compiler to make your compiler faster when building your compiler. All in all the compiler for free tagline (not specifically this post, it's written on a lot of futamura references) feels a bit like an inside joke. It reminds me of the sad discovery that a metacircular interpreter can't interpret itself after all since what you've written is a heavily obfuscated infinite loop.