May 13, 2015 - Tagged as: en, partial evaluation, multi-stage programming, ocaml.
I’ve been studying different program transformation techniques recently, and to me Futamura projections are one of the most interesting applications of program transformations. Couple of days ago I finished a small project in which I implemented first Futamura projection(aka. interpreter specialization) using Unlambda as object language. You can see the project here. I tried to write some comments to the source when I get stuck because of a problem or realized something interesting, so I suggest reading the source if you’re interested.
I did two implementations and used a different meta language for each one. There are multiple ways to achieve first Futamura projections: We can use a partial evaluator, a supercompiler(which may actually subsume partial evaluation, depending on how sophisticated it is), or just a “sufficiently smart” compiler. The problem though, we don’t have a lot of(read: any) usable implementations of partial evaluators or supercompilers, so I had to use the only language with a partial evaluator that I could find: Idris1.
There’s one another technique that we can use. The techniques I listed above are all completely automated. If things don’t go as expected we’re on our own to figure out why is that and hack around to make the tool transform the program the way we want. Indeed this is happened even in this project, which is deliberately kept simple and small2.
At the other end of the spectrum is multi-stage programming. In multi-stage programming the programmer specifies, using some annotations3, what code to generate and how to generate it. It clearly separates code that runs in code generation time and generated code. When generated code is printed to be compiled later, multi-stage programming feels like a compiler or a partial evaluator that the programmer can guide to generate the code he/she wants.
My second meta language is MetaOCaml, which is basically OCaml with multi-stage programming constructs. Using these two languages as representatives of two different program generation techniques, I implemented first Futamura projections for Unlambda.
There’s a report file in the repository, and I refer interesting readers to that document. README file contains compilation directives and some interesting executions. One interesting thing is that I later added a simple partial evaluator to MetaOCaml implementation, and in the programs/ directory there’s an Unlambda interpreter, written in Unlambda. Using these two programs, you can do things like partially applying(specializing) Unlambda interpreter to other programs or even itself. Before every experiment, I suggest thinking about what is the generated code you’re expecting(what does it do). What would a “sufficiently smart” partial evaluator generate? What would a simple partial evaluator generate? Similarly, try these while generating first projections.
Finally, if you’re interested in program transformations, stay tuned for more blog posts.
There is actually an implementation of well-known partial evaluator unmix. I knew about the project, but didn’t remember by the time I started this project. Still, I think I’d choose Idris even if I remembered.↩︎
Although some of those problems were implementation related, e.g. Idris was buggy. See the source code for comments and Github issues.↩︎
In MetaOCaml case those annotations are term-level, but there are other cases where annotations happen in type level only. See LMS as an example. (I think it’s the only example for now)↩︎