miércoles, 17 de febrero de 2010

Continuaciones

Definición
La forma usual de escribir una composición de funciones es algo como:

f(g(3))

Para evaluarla, calculamos g(3) y continuamos pasándole el resultado a f(x). Por esa razón podríamos escribirlo como

(λx.f(x))g(3)

A la función λx.f(x) se la denomina la continuación de g(3) en f(g(3)).

Esto tan tonto no es fácil de explicar. Véase por ejemplo, la Wikipedia.

Las continuaciones se suelen usar explícitamente. Es decir, que cuando calculo g(3) le voy a decir cuál es su continuación. Eso significa que g debe aceptar otro argumento que es la continuación.

g(3, λx.f(x) )

Esto es lo que se denomina el estilo de paso de continuaciones (CPS). Aunque, realmente, la f también debería tener su continuación. La llamaremos k.

g(3, λx.f(x, k) )

Obviamente, la k debemos haberla sacado de algún sitio. En princpio es el contexto en el que se usa todo f(g(3)).

Usos

El efecto más interesante del uso del CPS es que las funciones no retornan jamás. No necesitan devolver el resultado ya que lo que hacen es pasárselo como argumento a la continuación. La continuación será otra función que llamará a la siguiente continuación y así hasta que se acabe el programa.

Esta es la razón por la que existe una continuación especial, primitiva, que significa "no hacer nada más" o bien "cálculo acabado". En el caso de la k de arriba, podríamos pensar que es esta continuación inicial. El significado sería entonces: calcula g(3), continúa pasando el resultado a λx.f(x) y continúa acabando el cálculo.

Dicho esto, hay que mencinar que ya hemos usado continuaciones sin saberlo en los lenguajes imperativos como C o Java. Por ejemplo, el "return" de una función es equivalente a ejecutar su continuación inmediatamente. Es decir, salir de la función.

El "break" en los bucles es equivalente a ejecutar la continuación del bucle. De esta forma, se sale del bucle.

Las excepciones que salen de varias funciones y bloques "try" en C++ o Java, son similares a ejecutar, en vez de la continuación normal, la continuación que nos lleva al bloque "catch".

Los lenguajes que cuentan con las continuaciones como valores de primera clase (como Scheme o Ruby) tienen una llamada especial que se denomina "call with current continuation". Esta llamada pasa la continuación de la propia llamada, la continuación actual, a una función pasada como argumento. ¿Qué es la continuación actual? Pues pensemos en algo así como la dirección de retorno de una subrutina o llamada. La única diferencia es que ahora podemos retornar de llamadas, bucles o cualquier otro bloque de código. Esto incluye varios bloques y funciones tal y como hacen las excepciones.

Los usos anteriores son los llamados "hacia delante" ya que salimos de una llamada, bloque, etc. Existe otros usos que son "hacia atrás" y permiten realizar bucles y recursiones.

Pero no seguiremos más por mor de brevedad.

2 comentarios:

Eduardo dijo...

En el penúltimo párrafo, probablemente quisiste decir "continuaciones de primera clase". "De primer orden" y "de primera clase" significan cosas muuuuuuy distintas. :-P

Gadelan dijo...

Tienes toda la razón del mundo, Eduardo. Voy a corregirlo.

Publicar un comentario en la entrada