Futamura's Projections

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.

First Projection

Let $P$ be a progam in any Turing-complete programming language. Let’s say that $P \in \text{Java}$ — that is, $P$ is a Java program.

Let’s say that there exists a program — called an interpreter $INT \in \text{C}$ 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: $\varphi_P(x) = \varphi_{\text{INT}}(P, x) = \varphi_{\text{SPEC}(\text{INT}, P)}(x)$.

The previous line basically states that we’re specializing interpreter $\text{INT}$ on code $P$. We are then compiling program $P$. (Specialization is possible thanks to the s-m-n theorem).

Second Projection

Let’s take $\varphi_{\text{SPEC}}(\text{INT}, P)$. If we apply s-m-n ( $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.

Third Projection

Going even more abstract comes the third projection.

This is basically a generator of compilers: you pass it an interpreter for language $L_1$ written in $L_0$ and you get back a compiler for $L_1$.

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 $L_1$, we can get back a compiler for that same language $L_1$ 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).