Continuation-passing style

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

En la programación funcional, el Continuation-passing style (CPS) es un estilo de programación en el cual el Flujo de control se pasa explícitamente en forma de una Continuación, en oposición al estilo directo, que es el estilo habitual de programar.[1][2][3]

La notación CPS (abreviatura de continuation-passing style) es una forma de escribir el código de un programa en la que las Continuaciones se escriben y se pasan de forma explícita.

Cuando se escribe un programa en notación CPS, cada función recibe un parámetro adicional, que representa la Continuación de la función. En lugar de retornar, la función invocará la continuación recibida pasando el valor de retorno. De esta forma, las funciones nunca regresan al código que las llamó, sino que la ejecución del programa transcurre “hacia adelante” sin retornar hasta que el programa finalice.

Cuando desde una función A se desea invocar a una función B, se pasa como continuación de la función B el código que se desea ejecutar a continuación (incluyendo la invocación de la continuación de la función A).

La notación CPS ocasiona que el tamaño de la pila crezca con cada llamada a función, con el peligro de desbordamiento que eso conlleva. Por ello, cualquier implementación que pretenda escribir el código en notación CPS para ser ejecutado emplea la optimización conocida como tail-call optimization (TCO) que en español se traduce como optimización de cola. Esta optimización consiste en aprovechar que el marco de pila de la función actual al realizar una llamada a función no va a volver a ser usado (ya que las funciones no retornan) y por tanto puede ser reutilizado como marco de pila para la función invocada, evitando por tanto el crecimiento desmedido de la pila.[4]

Notes[editar]

  1. Sussman, Gerald Jay; Steele, Guy L., Jr. (December 1975). «Scheme: An interpreter for extended lambda calculus». AI Memo 349: 19. «That is, in this continuation-passing programming style, a function always "returns" its result by "sending" it to another function. This is the key idea.» 
  2. Sussman, Gerald Jay; Steele, Guy L., Jr. (December 1998). «Scheme: A Interpreter for Extended Lambda Calculus» (reprint). Higher-Order and Symbolic Computation 11 (4): 405-439. doi:10.1023/A:1010035624696. «We believe that this was the first occurrence of the term "continuation-passing style" in the literature. It has turned out to be an important concept in source code analysis and transformation for compilers and other metaprogramming tools. It has also inspired a set of other "styles" of program expression.» 
  3. Reynolds, John C. (2015). «The Discoveries of Continuations». Lisp and Symbolic Computation 6 (3-4): 233-248. doi:10.1007/bf01019459. 
  4. Carreño, Carlos Ramos (1993). Compilador para lenguaje basado en continuaciones. pp. 26-27.