Futamura's Projections

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.

First Projection

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

Let’s say that there exists a program — called an interpreter INTCINT \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: φP(x)=φINT(P,x)=φSPEC(INT,P)(x)\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 INT\text{INT} on code PP. We are then compiling program PP. (Specialization is possible thanks to the s-m-n theorem).

Second Projection

Let’s take φSPEC(INT,P)\varphi_{\text{SPEC}}(\text{INT}, P). If we apply s-m-n ( SmnS_m^n) again, we get:

φSPEC(INT,P)=φSPEC(SPEC,INT)(P) \varphi_{\text{SPEC}}(\text{INT}, P) = \varphi_{\text{SPEC}(\text{SPEC}, \text{INT})}(P)

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.

φSPEC(SPEC,INT)=φCOMP=φSPEC(SPEC,SPEC)(INT)\varphi_{\text{SPEC}}(\text{SPEC}, \text{INT}) = \varphi_{\text{COMP}} = \varphi_{\text{SPEC}(\text{SPEC}, \text{SPEC})}(\text{INT}).

This is basically a generator of compilers: you pass it an interpreter for language L1L_1 written in L0L_0 and you get back a compiler for L1L_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 L1L_1, we can get back a compiler for that same language L1L_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).

Share on: