Hacker News Reader

Comment by tekknolagi | Hacker News Reader

Author here! Feel free to ask questions or leave comments or whatever.

Thanks for the write-up.

Neil Jones' (free) book about partial evaluation deserves a mention here, since it explains how/why it works in some detail.

Query languages are a very cool application of this stuff. I was planning to use wasm for Mangle implementation (a language extending datalog, with its implementation a library for deductive database), following Tiark Rompf and Nada Amin's "a SQL to C compiler in 500 lines of code"... but of course I only have the interpreter for now and started a Rust rewrite instead.

The free book on partial evaluations: http://www.itu.dk/people/sestoft/pebook/

Is the book enlightening beyond what one can learn from sources like this post and the aforementioned paper by Rompf and Amin? I'm trying to decide whether I should spend the time to dig deeper into it.

I understand that by making the bytecode constant a lot of optimization become possible. But I can't see how you can unroll the interpreter loop past unknown inputs to the program?

That is, if the program is a pure function like power(x, y) (from the top of the article) then I understand if the bytecode is constant and the inputs x, y are constant then you can unroll completely. In fact, in that case, you can just do a full evaluation of the entire program to a constant. But, if x and y are unknown at compile time then you can do very little, I think?

I guess the example at the top of the article is saying that if you know y but not x then partial evaluation can still help a lot. But in a real-world program the first unknown input that causes a significant branch in execution will block progress, won't it? (edit: in particular unrolling has to stop, unless you consider multiple paths)

Weval has intrinsics that unroll the loop and specialize on the PC, merging paths with the same PC. So if you pick a good specialization context like PC, the unrolling stops eventually.

For a given function like `power`, you can unroll the interpreter loop and eliminate branches on the instruction, so the code has less branching overall.

But can you only do that when you know what the inputs are? That is, if x and y are determined only at runtime for power(x, y) then I don't see what can be optimized. But that seems like the common case to me. Likely I'm missing something and maybe not asking the question clearly, sorry.

> That is, if x and y are determined only at runtime for power(x, y) then I don't see what can be optimized.

Yes, the example in Max's post is specifically assuming one wants to generate a specialized version of `power` where `y` is fixed.

To take it back to weval: we can know what the bytecode input to the interpreter is; we provide an intrinsic (part of the "wevaling" request) to indicate that some function argument is a pointer to memory with constant, guaranteed-not-to-change content. That, together with context specialization on PC (another intrinsic), allows us to unroll the interpreter loop and branch-fold it so we get the equivalent of a template method compiler that reconstitutes the CFG embedded in the bytecode.

Thanks, I think I see now. So `y` is the bytecode, in the analogy. Makes sense.

(For me at least a concrete example would have helped, something like showing the specialized output of running on the bytecode for `power` with that interpreter. But maybe that would be too verbose...)

Reply on news.ycombinator.com