As usual, I am obligated to plug one of the neatest ideas in this biome of computing: the futamura projection. The key idea is that given a language L, and a partial evaluator peval : L x L -> L, we can get a compiler, and even a JIT compiler out!
A restriction that is sometimes glossed over is that one needs the condition that peval is metacircular: that is, peval in L. See that is not a necessary condition for something to be a partial evaluator: for example, an interpretive partial evaluator obeys the type signature peval: L x L -> L but could be implemented in another language.
Thanks for the links. Implementing a partial evaluator for a small language, capable of the Futamura projections, seems like an interesting hobby project?
Some caveats from the second link:
Does partial evaluation eliminate the need to write compilers? Yes and no. . .
Pro: when given a language definition in the form of an operational semantics, a partial
evaluator eliminates the first and largest order of magnitude: the interpretation
overhead. A virtue is that the method yields target programs that are always
correct with respect to the interpreter. Thus the problem of compiler correctness
seems to have vanished. This approach is clearly suitable for prototype implementation of new languages from interpretive definitions.
Contra: the generated target code is in the partial evaluator’s output language,
typically the language the interpreter is written in. Thus partial evaluation will not
devise a target language suitable for the source language, e.g. Python bytecodes.
It won’t invent new runtime data structures either, so human creativity seems
necessary to gain the full handwritten compiler efficiency.
So what language M are you compiling your hobby language into? You’ll need a partial evaluator for M. For example, in order to use the Futamura projections to compile your hobby language into WASM, you would need an interpreter for the language written in WASM, and a partial evaluator that operates on WASM.
And that’s the problem the OP solves: weval is the partial evaluator you’d need for this.
I have never seen a “link log” before. I think that is a really cool tool (and it is available for others). Does your search look at only the titles of the links?
The software is low-effort symbiosisware, barely serviceable for my own use, and so bad I would not wish it on my worst enemies. It’s basically a single-user pinboard or delicious.
The search is the stupidest thing that could possibly work: it splits the query into words and does substring matches on the titles and urls, and lists the matching entries with the words emboldened. It is absolute shit for brains and works really well.
I’m sure @fanf meant RPython, the toolkit which builds PyPy and similar binaries, performs the first Futamura projection when translating to C. You’re allowed to not think of the JIT as a second Futamura projection, but it’s not a bad perspective when trying to understand how the JIT is optimizing one’s interpreter actions.
Ah, sorry, I may be wrong. Deegen takes “an interpreter” (but really the interpreter is your operational semantics encoded in C++) and generates both an interpreter and a compiler.
I used to think that this technique was magic, but now I think it gives you “A” compiler, but not necessarily a good compiler or the one you want. There are still a lot of engineering tradeoffs, and there’s a lot of work to do to make it fast
I still want to play with it (and weval actually sounds perfect for that), but I see it more as a “side quest”
All of lightweight modular staging (https://scala-lms.github.io/) is based off of the futamura projection, which in my mind was the “academic” establishment that this works “in practice”.
That looks like a nice JIT library to me. I couldn’t see anything about partial evaluation within the first handful of pages; do you have a more pertinent link?
And it looks like weval is an awesome project – In retrospect I’m sorta surprised there isn’t more prior work, since WASM has been backed by multiple expensive-to-develop JITs since ~2017 or so.
In the distant future, one thing I would like to explore is partially evaluating Oils with respect to OSH or YSH. It’s just a bunch of if statements for say shopt -s parse_paren – the bool is false for OSH and true for YSH.
So these if statements have some runtime cost now, and it would be cool to compile them out. (I don’t think this is that significant compared to say allocations, but maybe it will speed it up)
An analogy is if Python has runtime checks for from __future__, or Perl has runtime checks for use strict.
In that case you could theoretically partially evaluate a faster version of the interpreter, specialized to a particular language version.
Very cool! I love partial evaluation.
As usual, I am obligated to plug one of the neatest ideas in this biome of computing: the futamura projection. The key idea is that given a language
L, and a partial evaluatorpeval : L x L -> L, we can get a compiler, and even a JIT compiler out!A restriction that is sometimes glossed over is that one needs the condition that
pevalis metacircular: that is,peval in L. See that is not a necessary condition for something to be a partial evaluator: for example, an interpretive partial evaluator obeys the type signature peval:L x L -> Lbut could be implemented in another language.Anyway, given such a bobble, one can take an iterpreter, and partial evaluate a partially applied partial evaluator to get a JIT compiler :) I can’t explain the idea as well as this technical report can, so I link to “Partial Evaluation and Automatic Program Generation” (PDF).
Thanks for the links. Implementing a partial evaluator for a small language, capable of the Futamura projections, seems like an interesting hobby project?
Some caveats from the second link:
So what language M are you compiling your hobby language into? You’ll need a partial evaluator for M. For example, in order to use the Futamura projections to compile your hobby language into WASM, you would need an interpreter for the language written in WASM, and a partial evaluator that operates on WASM.
And that’s the problem the OP solves:
wevalis the partial evaluator you’d need for this.I enjoy this blog post regarding Futamura projections. There’s diagrams!
http://blog.sigfpe.com/2009/05/three-projections-of-doctor-futamura.html?m=1
When I searched my link log for Futamura I found that blog post and a paper on Graal and Truffle
I have never seen a “link log” before. I think that is a really cool tool (and it is available for others). Does your search look at only the titles of the links?
The software is low-effort symbiosisware, barely serviceable for my own use, and so bad I would not wish it on my worst enemies. It’s basically a single-user pinboard or delicious.
The search is the stupidest thing that could possibly work: it splits the query into words and does substring matches on the titles and urls, and lists the matching entries with the words emboldened. It is absolute shit for brains and works really well.
The Futamura-oriented partial evaluators that I know of are
Are there any more?
It was a science-fictional idea for decades so it’s remarkable to see practical implementations spreading like this.
fwiw now Pypy is meta-tracing, not partial evaluation anymore
I’m sure @fanf meant RPython, the toolkit which builds PyPy and similar binaries, performs the first Futamura projection when translating to C. You’re allowed to not think of the JIT as a second Futamura projection, but it’s not a bad perspective when trying to understand how the JIT is optimizing one’s interpreter actions.
There’s also DeeGen, based on copy and patch, but it’s not released yet
Where does DeeGen use partial evaluation? I’m not seeing that in the source.
Ah, sorry, I may be wrong. Deegen takes “an interpreter” (but really the interpreter is your operational semantics encoded in C++) and generates both an interpreter and a compiler.
FWIW this thread on HN has a good discussion of the tradeoffs of the technique vs. traditional compilers: https://news.ycombinator.com/item?id=40408147
I used to think that this technique was magic, but now I think it gives you “A” compiler, but not necessarily a good compiler or the one you want. There are still a lot of engineering tradeoffs, and there’s a lot of work to do to make it fast
I still want to play with it (and weval actually sounds perfect for that), but I see it more as a “side quest”
All of lightweight modular staging (https://scala-lms.github.io/) is based off of the futamura projection, which in my mind was the “academic” establishment that this works “in practice”.
That looks like a nice JIT library to me. I couldn’t see anything about partial evaluation within the first handful of pages; do you have a more pertinent link?
Awesome post! Very clear demo
And it looks like weval is an awesome project – In retrospect I’m sorta surprised there isn’t more prior work, since WASM has been backed by multiple expensive-to-develop JITs since ~2017 or so.
But there’s probably a lot going on under the hood I don’t see. (e.g. PyPy’s experience - https://www.pypy.org/posts/2018/09/the-first-15-years-of-pypy-3412615975376972020.html#why-did-we-abandon-partial-evaluation )
In the distant future, one thing I would like to explore is partially evaluating Oils with respect to OSH or YSH. It’s just a bunch of if statements for say
shopt -s parse_paren– the bool is false for OSH and true for YSH.So these if statements have some runtime cost now, and it would be cool to compile them out. (I don’t think this is that significant compared to say allocations, but maybe it will speed it up)
An analogy is if Python has runtime checks for
from __future__, or Perl has runtime checks foruse strict.In that case you could theoretically partially evaluate a faster version of the interpreter, specialized to a particular language version.
Egglog was mentioned here last week and it would make a dream partnership with weval.
Does this work with wasm-gc?