Futamura projections

Futamura.lhs

In this article, we we will look at the first three Futamura projections.

> module Futamura where

Suppose we have a program datatype, which takes input to output. This could be
any kind of executable program:§

> data Program i o = Program i o

It is accompanied by an `exec` function which executes the program, and given an
input, yields an output:

> exec :: Program i o -> i -> o
> exec = undefined

We then continue to define an interpreter, which is a `Program` that takes
another `Program i o` and an input `i`, and interprets the program given the
input, yielding an output `o`.

> type Interpreter i o = Program (Program i o, i) o

A partial evaluator is a program that takes a program with input `(i1,i2)`,
where `i1` is the variables that can be evaluated, 

> type PE i1 i2 o = Program ((Program (i1,i2) o), i1) (Program i2 o)
> 
> type Compiler i o = Program (Program i o) (Program i o)
> 
> pe :: PE i1 i2 o
> pe = undefined
> 
> 
> 
> 
> firstProjection :: Program (code, input) o -> code -> Program input o
> firstProjection code i = exec pe (code, i)
> 
> 
> secondProjection :: Interpreter i o -> Compiler i o
> secondProjection interpreter = exec pe (pe, interpreter)
> 
> thirdProjection :: Program (Interpreter input o) (Compiler input o)
> thirdProjection = exec pe (pe,pe)