3 ms·

> 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

by 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.

by titzer 2y ago

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.