5 ms·

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

burakemir 2y ago
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.
- quag 2y ago
  The free book on partial evaluations: http://www.itu.dk/people/sestoft/pebook/ http://www.itu.dk/people/sestoft/pebook/
  - sestep 2y ago
    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.
azakai 2y ago
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)
- tekknolagi 2y ago
  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.
  - deleted 2y ago
    [deleted]
- n_plus_1_acc 2y ago
  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.
  - azakai 2y ago
    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.
    - cfallin 2y ago
      > 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.
      - azakai 2y ago

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.

quag 2y ago
The free book on partial evaluations: http://www.itu.dk/people/sestoft/pebook/ http://www.itu.dk/people/sestoft/pebook/
- sestep 2y ago
  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.

azakai 2y ago

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)

tekknolagi 2y ago
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.
- deleted 2y ago
  [deleted]
n_plus_1_acc 2y ago
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.
- azakai 2y ago
  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.
  - cfallin 2y ago
    > 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.
    - azakai 2y ago