Extraido del blog El Manantial de Bits
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 × Y → R
Este tipo significa que f es una función que toma un par de argumentos y devuelve un resultado. De hecho, se usa el tipo producto de X por Y (producto cartesiano).
Lo que se suele escribir es
-
fxy
que significa realmente
-
f(x)(y)
y cuyo tipo es
-
f:: X → (Y → 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
-
fxy
que nos da el resultado, escribimos
-
fx
obtenemos una función que toma un argumento "y" y devuelve el resultado. El tipo de f x es
-
fx:: Y → 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.
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.
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 matemática ya que, gracias a la Turing completitud, el intérprete no es más que un programa.
-
interp(prog,entrada)=salida
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