Came across Futamura projections while read the wiki for Partial evaluation. I had to admit that it’s mind-flowing to me. The text description in the wiki is quite mouthful, so here’s an attempt to express it using Haskell type systems.
data Source data Value type Excutable = () -> Value type Interpreter = Source -> Value partial :: Interpreter -> Source -> Excutable partial eval source = \() -> eval source
partial does the first projection, that given the
Source, we could obtain the final
Excutable. Not so difficult.
The second projections says that we could construct one compiler out of a interpreter. Realizing that compiler is no more than the following:
type Compiler = Source -> Excutable
partial does the second projection as well with no modification at all. Maybe we are just lucky.
The third projection says that we could construct a tool that converts any interpreter to an equivalent compiler. Isn’t
partial :: Interpreter -> Compiler
It turns out that the
partial we constructed above covers all three projections, which, to some extent, surprised me, and illustrates the powerful
insight from function currying.