A lot of the stuff they’re doing with wasm is confusing to me. Compiling an interpreter to wasm to run a script in the browser seems, IDK, a bit much.
I’m not seeing how using the first Futamura projection (targeting wasm) wouldn’t both result in a significantly smaller module size and give more opportunity to optimize/specialize the code as it could perform offline analysis. One could even use the second Futamura projection along with the dynamic code loading from TFA and get an online jit compiler virtually for free.
If I was getting paid megabucks to do these types of things that’s where I’d spend my research time.
While the Futamura Projection is undoubtedly very powerful, it's worth being aware that some of its properties are significantly oversold; in practice, useful partial evaluation has a lot of the same kinds of decisions and trade-offs as optimising compilers and being Jones-Optimal isn't the same as being fast.
As an example, imagine a simple case of a program that outputs N verses of the "bottles of beer on the wall" song. A naive partial evaluator given an N will produce the whole output (potentially multi-gigabyte) string during partial evaluation, even if loading and printing that whole string may be slower than just running the original code.
Look at Pypy and GraalVM for partial evaluation in practice; none of it is free and there's a lot of engineering and tweaking involved, not to mention how it can affect debugging.
I think WebAssembly is too low level, making symbolic execution and specialization of a WebAssembly interpreter intractable or at least ineffective for all but the simplest of cases. WebAssembly doesn't even have arrays or structures--just integers, combined with a handful of "types" for global and external objects. Symbolically executing a WebAssembly interpreter (written in any language) over any non-trivial WASM code will be a parade of worst cases for such an approach. Perhaps it can be done, but I doubt it could be done in a manner that makes it a better approach (in developer time or runtime performance) than explicit compilation.
I'm not that familiar with this area, but tried to reacquaint myself by skimming through http://www.itu.dk/people/sestoft/pebook/jonesgomardsestoft-l... (via http://www.itu.dk/people/sestoft/pebook/), especially Chapter 11, "Partial Evaluation for the C Language", which I figured would highlight some the biggest potential roadblocks, even if it's not directly pertinent (i.e. in our case we might be symbolically executing a strongly typed functional language implementation of a WASM interpreter).
Not making a wasm interpreter but using it as the output of $whatever_language you choose abstract interpreter — written in $whatever_ language if you want the “free” jit compiler.
It doesn’t need fancy stuff like arrays or objects since it just operates on the sandboxed wasm memory. Probably need some runtime system to deal with memory management &etc but that’s just some extra code tacked onto the module.
There’s some pretty good algorithms for the first case where you get pretty close to optimal code without having to leave SSA form I’ve been reading about recently. In fact, I totally forgot about the Futamura transformations until I was reading TFA and was wondering why it wouldn’t work.
—edit—
I guess the first case is just a traditional compiler and it would probably not benefit from partial evaluation because there’s also an efficient algorithm that’s part of the mentioned reading to transform SSA -> AST which could be adapted to wasm output quite easily…which is on my laptop and I’m on my phone so…
I haven't read the article yet, but you can pass the emitted Wasm back to the top level JS and have it instantiate a new module, potentially using the same heap.
I experimented with this for native x86 many years ago (https://github.com/kristiandupont/rtasm). I used it to generate BitBlt functions with no conditionals in the hot paths, which created noticeable performance improvements with no compromise in flexibility. Debugging code like that is painful though!
I did implement a math parser a couple of years that did JIT wasm code generation. It operated on 1d array, providing kind of numpy syntax. It achieved a very decent performance. It was quite some fun.
I’m not seeing how using the first Futamura projection (targeting wasm) wouldn’t both result in a significantly smaller module size and give more opportunity to optimize/specialize the code as it could perform offline analysis. One could even use the second Futamura projection along with the dynamic code loading from TFA and get an online jit compiler virtually for free.
If I was getting paid megabucks to do these types of things that’s where I’d spend my research time.
As an example, imagine a simple case of a program that outputs N verses of the "bottles of beer on the wall" song. A naive partial evaluator given an N will produce the whole output (potentially multi-gigabyte) string during partial evaluation, even if loading and printing that whole string may be slower than just running the original code.
Look at Pypy and GraalVM for partial evaluation in practice; none of it is free and there's a lot of engineering and tweaking involved, not to mention how it can affect debugging.
I'm not that familiar with this area, but tried to reacquaint myself by skimming through http://www.itu.dk/people/sestoft/pebook/jonesgomardsestoft-l... (via http://www.itu.dk/people/sestoft/pebook/), especially Chapter 11, "Partial Evaluation for the C Language", which I figured would highlight some the biggest potential roadblocks, even if it's not directly pertinent (i.e. in our case we might be symbolically executing a strongly typed functional language implementation of a WASM interpreter).
It doesn’t need fancy stuff like arrays or objects since it just operates on the sandboxed wasm memory. Probably need some runtime system to deal with memory management &etc but that’s just some extra code tacked onto the module.
If one wanted to get all fancy it would be:
code -> ast -> ir -> optimizer -> partial eval -> wasm
Or just a simple:
code -> ast -> tree walker -> wasm
There’s some pretty good algorithms for the first case where you get pretty close to optimal code without having to leave SSA form I’ve been reading about recently. In fact, I totally forgot about the Futamura transformations until I was reading TFA and was wondering why it wouldn’t work.
—edit—
I guess the first case is just a traditional compiler and it would probably not benefit from partial evaluation because there’s also an efficient algorithm that’s part of the mentioned reading to transform SSA -> AST which could be adapted to wasm output quite easily…which is on my laptop and I’m on my phone so…
We use similar techniques to power Webvm[1], an X86 Virtual Machine that runs linux programs in the browser.
A proper Wasm JIT API in JavaScript would be even better of course, but as the article says, cool things are already possible right now.
I expect to see more projects doing Wasm just-in-time compilation in the future (I believe that V86[2] also already does it)
[1]: https://webvm.io/
[2]: https://github.com/copy/v86
A Wasm trampoline-continuation.
I assume this is what v86 does.
Generating entire modules works, but it has a number of issues.
For example, you need to carefully decide how big your modules are going to be:
- Too small, and you end up compiling many many modules, which eventually crashes the browser if you don't dispose of the old ones
- Too big (many functions batched together), and you have too much latency before your code is available to run
Being able to compile a single function to add to an existing module (or something like that) would help a lot.