Published May 25, 2022 - By Marco Garosi
Futamura’s Projections, in the computability theory, look like one of those silly and useless things you have to go through. But are they? Well, no, not really: Futamura’s Projections are the theoretical basis for the foundation of many Computer Science fields: compilers and interpreters can exist thanks to Futamura’s Projections. Even though they would work in real-life, they are not used; instead, more sophisticated approaches are used to make compilers and interpreters — they would be too slow, otherwise. Yet it is extremely important know and understand them.
Let be a progam in any Turing-complete programming language. Let’s say that — that is, is a Java program.
Let’s say that there exists a program — called an interpreter for Java. We should prove this, but since we use interpreters in our everyday lives, we know that interpreters exist and work. Hence, we won’t deepen the topic — not in this note.
Now, what an interpreter really does is: .
The previous line basically states that we’re specializing interpreter on code . We are then compiling program . (Specialization is possible thanks to the s-m-n theorem).
Let’s take . If we apply s-m-n ( ) again, we get:
This is basically specializing the specializer on the interpreter. What we are really doing, then, is compiling the specializer, which then becomes a compiler.
Going even more abstract comes the third projection..
This is basically a generator of compilers: you pass it an interpreter for language written in and you get back a compiler for .
Why is this so interesting? Well, if you’ve ever tried, writing an interpreter is way easier than writing a compiler. Using Futamura’s Projections, however, we know that if we can write an interpreter for a language , we can get back a compiler for that same language automatically built using the interpreter.
Downsides? Yes, of course. If we wrote compilers this way we would have pretty slow programs: that is why so many people study and develop sophisticated compilers: they take into account optimizations, memory management, etc. Nontheless, from a mathematical and theoretical point of view, that is not necessary: if the only goal is to get a compiler, this is the way to go (well, not actually… but that’s not the point).