Todas las funciones están en CPS

Hace algún tiempo hablé del CPS y las continuaciones. Había un detalle que hacía completamente incompatible el estilo CPS con el estilo normal de programación: toda función en CPS requiere un parámetro extra que es la continuación. Una función normal se definiría más o menos así:

doble(x) = x+x

Al hacer el cambio a CPS, y suponiendo que la suma es una operación predefinida que no se pasa a CPS, obtendríamos lo siguiente:

doble_CPS(x,k) = k(x+x)

La nueva función requiere ese argumento extra que es la continuación k. La continuación es una función que no regresa y que representa el resto de la computación. Lo que vamos a hacer con el resultado del doble.

Nota: El que una continuación no regrese es muy interesante desde el punto de vista de la teoría de tipos. Su tipo sería [$T\rightarrow \bot$] que es igual a [$¬ T$], pero dejaré una explicación más profunda para otra entrada más adelante.

Bien. Ahora pensemos qué pasa si tengo un lenguaje de programación en el cual la compilación va a un ensamblador genérico. Una llamada a la función doble, en ensamblador, sería algo así:

PUSH x
CALL doble

Primero insertamos el parámetro en la pila y luego llamamos a doble. Si la llamada fuera la versión CPS tendríamos algo así:

PUSH x
PUSH k
CALL doble_CPS

Esto impediría que un lenguaje cuyo compilador transformase el código a CPS interactuase con otro que no usase la transformación a CPS. En un caso se espera un argumento y en el otro dos.

Sin embargo, esto no es así. Prácticamente todos los procesasores reales (incluyendo el x86) son de estilo CPS y hay que decir, en cada llamada, cuál es la continuación. ¿Cómo? Observando con detenimiento la instrucción de llamada CALL de estos procesadores. La instrucción

CALL f


es equivalente a

PUSH l
JUMP f
l:

Donde l es una etiqueta, un indicador de dirección de código en ensamblador y JUMP una instrucción de salto. Esa es la continuación. La dirección de código l. Eso significa que podríamos llamar a la función doble en modo CPS de la siguiente forma.

PUSH x
PUSH k
JUMP doble

Las dos últimas instrucciones son el equivalente al CALL, pero diciendo que queremos que regrese, no a la instrucción inmediatamente posterior al salto, sino a la que sea k.


De esta manera se pueden mezclar funciones usuales con funciones en CPS. De hecho, las funciones usuales ya están en CPS sólo que "disfrazadas" por el uso de CALL.

Nota: Existe un pequeño detalle extra que es el uso exhaustivo que hace la transformación a CPS de las clausuras léxicas. Las funciones usuales guardan su entorno en la pila por lo que se destruye al salir de la función. Existen técnicas para evitar esto: los upvalues de LUA o en análisis de escape de la función para crear los entornos en el montículo en vez de la pila.