Las proyecciones de Futamura

Parcialización

En los lenguajes funcionales acostumbramos a escribir las funciones currificadas. No se escribe algo como

$$f(x,y)$$

que sería una función con tipo

$$f :: X \times Y \rightarrow R$$

Este tipo significa que f es una función que toma un par de árgumentos y devuelve un resultado. De hecho, se usa el tipo producto de X por Y (producto cartesiano).

Lo que se suele escribir es

$$f x y$$

que significa realmente

$$f(x)(y)$$

y cuyo tipo es

$$f :: X \rightarrow (Y \rightarrow R)$$

Este tipo indica que f es una función que toma un argumento y devuelve otra función que toma el siguiente argumento y que, por fin, devuelve el resultado.

A pasar del primer caso al segundo se llama currificar la función.

Si en vez de escribir

$$f x y$$

que nos da el resultado, escribimos

$$f x$$

obtenemos una función que toma un argumento "y" y devuelve el resultado. El tipo de f x es

$$f x :: Y \rightarrow R$$

A esta función se la llama una parcialización o una evaluación parcial de f. De cierta forma, lo que hacemos es calcular un caso particular de f para cuando sabemos el valor x.

Parcialización explícita

Generalmente parcializamos cuando no introducimos todos los argumentos que la función requiere. Esta parcialización se realiza de forma automática. En parte gracias a la nomenclatura. Sin embargo, esto no suele ser así a la hora de computar realmente. Lo que se suele hacer es usar una función auxiliar que llamaremos "mix" y que obtiene la parcialización de una función con su primer argumento.

En notación matemática:

$$f(x,y)=r$$
$$mix(f,x)=p$$
$$p(y)=r$$
$$mix(f,x)(y)=r$$

De esta forma hemos hecho explícita la parcialización de la función f.

Turing completitud

Una de las características de los modelos de computación tales como el lambda cálculo, la máquina de Turing o un ordenador, es que se pueden simular a sí mismos. Entonces decimos que ese modelo es Turing completo.

Antes de nada, empezaremos viendo cómo funciona un programa cuando queremos ejecutarlo. La idea es que tenemos el programa "prog" y se lo pasamos a otro programa "interp" para que lo interprete. Generalmente también le pasamos una entrada "entrada" y el resultado es una salida.

Todo esto se puede poner en notación metemática ya que, grancias a la Turing completitud, el intérprete no es más que un programa.

$$interp(prog, entrada)=salida$$

Las proyecciones de Futamura

En este punto fue cuando a Futamura (por cierto, significa "dos villas") se le ocurrió parcializar. El resultado es que obtenemos una compilación del programa.

$$interp(prog,entrada)=mix(interp, prog)(entrada)=salida$$
$$mix(interp, prog)=compilado$$
$$compilado(entrada)=salida$$

Esta es la primera proyección de Futamura: La parcialización de un intérprete y un programa es el programa compilado.

Pero este buen hombre no quedó ahí, vio que ¡mix también puede parcializarse!

$$mix(interp, prog)(entrada)=mix(mix, interp)(prog)(entrada)=salida$$
$$mix(interp,prog)=mix(mix, interp)(prog)=compilado$$
$$mix(mix, interp)=compilador$$
$$compilador(prog)=compilado$$
$$compilado(entrada)=salida$$

Así que mix(mix, interp) no es más que el compilador relacionado con el intérprete "interp". Esta es la segunda proyección de Futamura.

Pero podemos seguir y obtener

$$mix(mix, interp)(prog)(entrada) =mix(mix,mix)(interp)(prog)(entrada)=salida$$
$$mix(mix, mix)(interp)=compilador$$
$$compilador(prog)=compilado$$
$$compilado(entrada)=salida$$

Así que llegamos a la tercera y última proyección de futamura. Es un generador de compiladores que, dado un intérprete, obtiene el compilador correspondiente.

$$mix(mix, mix)=generador$$
$$generador(interp)=compilador$$