Cómo derivar un compilador de un intérprete: la primera proyección de Futamura

Veit Heller ha vuelto sobre compfuck, su pequeño compilador de Brainfuck a Carp, y esta vez lo ha dado la vuelta. Lo ha reconvertido en intérprete y ha dejado que un evaluador parcial derive de nuevo el compilador a partir de su código fuente. Es la primera proyección de Futamura contada con las manos: un compilador no es más que un intérprete especializado para un programa concreto.

La fórmula que resume la idea cabe en dos líneas. Especializas el intérprete con el programa y obtienes código compilado; ese resultado, alimentado con una entrada, produce lo mismo que el intérprete original recibiendo programa y entrada. Heller reconoce que llevaba años usando compfuck para explicar el concepto aunque sabía que su versión no era del todo correcta: al elegir a mano qué código emitir para cada instrucción se quedaba en una imitación del mecanismo, no en el mecanismo. La evaluación parcial deduce ese código sola, con el mismo tipo de transformaciones que describe la literatura clásica sobre el tema.

Deshacer el compilador

El primer paso es volver atrás. Las ramas de despacho del compilador original devolvían un fragmento de código citado para cada instrucción de Brainfuck; en el intérprete, ese mismo fragmento se ejecuta en el sitio. Mover el cabezal a la derecha deja de ser una operación que se emite y pasa a ser una operación que se realiza. El recorrido recursivo del código fuente apenas cambia de forma: ahora ejecuta en lugar de acumular trozos.

Lo interesante es averiguar qué partes del intérprete dependen solo del programa. Con la cadena ,[.-] ya se sabe que la primera instrucción lee un carácter y que el cuerpo del bucle imprime y decrementa una celda; lo que no se sabe es cuántas veces girará ese bucle. Al especializar el intérprete con ese programa queda el llamado programa residual: desaparece el recorrido del código fuente y sobreviven las operaciones sobre la cinta y el propio bucle. El compilador antiguo ensamblaba algo muy parecido a mano.

Para que esto funcione hacen falta las dos versiones del intérprete: la que se puede ejecutar y la que se puede inspeccionar. Heller lo resuelve con dos macros de Carp. La primera define una función normal y guarda su cuerpo como metadato, recuperable después. La segunda, defstatic, genera a la vez una función compilada y una de tiempo de compilación a partir del mismo cuerpo, y se usa para el escaneo de corchetes que localiza el ] que cierra cada [. Ese escaneo sigue contando profundidad de anidamiento, pero ahora avanza un índice en vez de ir cortando la cola de la cadena.

Por qué molestarse

Si ya existe un compilador que funciona, deshacerlo parece un ejercicio ocioso. El caso útil es el contrario: cuando tienes un intérprete y todavía no tienes compilador, o cuando la solución manual que valía en Brainfuck no se traslada con la misma facilidad a otro lenguaje. compfuck sirve aquí como banco de pruebas pequeño y conocido para recorrer el mecanismo entero, aunque el entorno de ejecución ya sea perfectamente válido. Queda por ver si el autor lleva la técnica a un lenguaje donde la especialización aporte algo más que didáctica.