llamada con continuación actual

En el lenguaje de programación Scheme , la llamada a procedimiento con continuación de corriente , abreviada como call/cc , se utiliza como operador de control de flujo . También ha sido adoptada por otros lenguajes de programación.

Tomando una función fcomo su único argumento, (call/cc f)dentro de una expresión se aplica a la continuación actual de la expresión. Por ejemplo, ((call/cc f) e2)es equivalente a aplicar fa la continuación actual de la expresión. La continuación actual se obtiene reemplazando (call/cc f)por una variable cligada por una abstracción lambda, por lo que la continuación actual es (lambda (c) (c e2)). Al aplicar la función fa ella se obtiene el resultado final (f (lambda (c) (c e2))).

Como ejemplo complementario, en una expresión (e1 (call/cc f)), la continuación para la subexpresión (call/cc f)es (lambda (c) (e1 c)), por lo que la expresión completa es equivalente a (f (lambda (c) (e1 c))). En otras palabras, toma una "instantánea" del contexto de control actual o estado de control del programa como un objeto y se aplica fa él. El objeto de continuación es un valor de primera clase y se representa como una función, cuya única operación es la aplicación de funciones . Cuando se aplica un objeto de continuación a un argumento, la continuación existente se elimina y la continuación aplicada se restaura en su lugar, de modo que el flujo del programa continuará en el punto en el que se capturó la continuación y el argumento de la continuación se convierte entonces en el "valor de retorno" de la invocación de call/cc. Las continuaciones creadas con call/cc pueden llamarse más de una vez, e incluso desde fuera del alcance dinámico de la aplicación de call/cc.

En informática, hacer visible este tipo de estado implícito del programa como un objeto se denomina reificación . ( Scheme no distingue sintácticamente entre aplicar continuaciones o funciones).

Con call/cc se pueden implementar diversos operadores de control complejos de otros lenguajes mediante unas pocas líneas de código, por ejemplo, el operador de McCarthy para la elección no determinista , el retroceso al estilo de Prolog , las corrutinas al estilo de Simula 67 y sus generalizaciones, los generadores al estilo de Icon , o motores e hilos , o incluso el poco conocido COMEFROM .amb

Como se muestra en el siguiente ejemplo, call/cc se puede utilizar para emular la función de la instrucción return conocida en los lenguajes de estilo C , que falta en Scheme :

( define ( f return ) ( return 2 ) 3 )( f ( lambda ( x ) x )) => 3( llamada-con-continuación-actual f ) => 2

Al llamar a f con un argumento de función normal, primero se aplica esta función al valor 2 y luego se devuelve 3. Sin embargo, cuando f se pasa a call/cc (como en la última línea del ejemplo), aplicar el parámetro (la continuación) al valor 2 fuerza la ejecución del programa a saltar al punto donde se llamó a call/cc, y hace que call/cc devuelva el valor 2. Este valor es luego impreso por la función display.

En el siguiente ejemplo, call/cc se usa dos veces: una para generar una continuación "return" como en el primer ejemplo y otra para suspender una iteración a través de una lista de elementos:

;; [LISTOF X] -> ( -> X u 'te-caíste-del-final) ( define ( genera-un-elemento-a-la-vez lst ) ;; Ambas funciones internas son cierres sobre lst;; Variable interna/Función que pasa el elemento actual de una lista ;; a su argumento de retorno (que es una continuación), o pasa un marcador de fin de lista ;; si no quedan más elementos. En cada paso, el nombre de la función se ;; vuelve a enlazar a una continuación que apunta de nuevo al cuerpo de la función, ;; mientras que el retorno se vuelve a enlazar a la continuación que especifique quien llama. ( define ( control-state return ) ( for-each ( lambda ( element ) ( set! return ( call-with-current-continuation ( lambda ( resume-here ) ;; Toma la continuación actual ( set! control-state resume-here ) ( return element ))))) ;; (return element) se evalúa a next return lst ) ( return 'you-fell-off-the-end )) ;; (-> X u 'you-fell-off-the-end) ;; Este es el generador real, que produce un elemento de una lista a la vez. ( define ( generador ) ( llamada-con-continuación-actual estado-de-control ));; Devuelve el generador generador )( define generate-digit ( generate-one-element-at-a-time ' ( 0 1 2 )))( generar-dígito ) ;; 0 ( generar-dígito ) ;; 1 ( generar-dígito ) ;; 2 ( generar-dígito ) ;; te-caíste-del-final

Cada vez que el bucle está a punto de procesar otro elemento de la lista, la función toma la continuación actual y la asigna a la variable 'control-state'. Esta variable es inicialmente el cierre que itera a través de todos los elementos de la lista. A medida que avanza el cálculo, se convierte en un cierre que itera a través de un sufijo de la lista dada. Si bien el uso de "call/cc" es innecesario para una colección lineal, como [LISTOF X], el código se generaliza a cualquier colección que se pueda recorrer.

La llamada con continuación actual también puede expresar otras primitivas sofisticadas. Por ejemplo, el siguiente ejemplo realiza multitarea cooperativa utilizando continuaciones:

;; Multitarea cooperativa mediante llamada con continuación actual ;; en 25 líneas de esquema;; La lista de hilos esperando para ejecutarse. Esta es una lista de ;; funciones que no devuelven ningún valor (continuaciones, principalmente) ;; Una continuación es una función que no devuelve ningún valor, al igual que (exit), ;; ya que nunca cede el control a quien la llamó.( define ready-list ' ());; Una función que no devuelve ningún valor. Si hay algún otro hilo ;; esperando a ser ejecutado, hace que el siguiente hilo se ejecute si queda ;; alguno por ejecutar; de lo contrario, llama a la salida original ;; que sale de todo el entorno. ( define exit ;; La salida original que sobrescribimos. ( let (( exit exit )) ;; La función que la sobrescribe. ( lambda () ( if ( not ( null? ready-list )) ;; Hay otro hilo esperando a ser ejecutado. ;; Así que lo ejecutamos. ( let (( cont ( car ready-list ))) ( set! ready-list ( cdr ready-list )) ;; Dado que ready-list solo contiene funciones que no devuelven ningún valor, ;; esta no devolverá nada. ( cont #f )) ;; No queda nada por ejecutar. ;; La original (exit) es una función que no devuelve ningún valor, ;; así que esta es una función que no devuelve ningún valor. ( exit )))));; Toma una función de un argumento con un argumento dado ;; y la bifurca. El nuevo ;; hilo de la función bifurcada saldrá si/cuando la función alguna vez salga. ( define ( fork fn arg ) ( set! ready-list ( append ready-list ;; Esta función agregada a la ;; lista lista no devuelve, ;; ya que exit no devuelve. ( list ( lambda ( x ) ( fn arg ) ( exit ))))));; Cede el control al siguiente hilo que espera ser ejecutado. ;; Aunque eventualmente regresará, cede el control ;; y solo lo recuperará cuando se llame a la continuación. ( define ( yield ) ( call-with-current-continuation ;; Captura la continuación que representa ESTA llamada a yield ( lambda ( cont ) ;; Colócala en la lista lista ( set! ready-list ( append ready-list ( list cont ))) ;; Obtiene el siguiente hilo y comienza a ejecutarlo. ( let (( cont ( car ready-list ))) ( set! ready-list ( cdr ready-list )) ;; Ejecútalo. ( cont #f )))))

En 1999, David Madore (inventor del lenguaje de programación Unlambda ) descubrió accidentalmente un término Unlambda de 12 caracteres, utilizando call/cc, que imprimía todos los números naturales secuencialmente en representación unaria: ``r`ci`.*`ci. ^{[ 1 ]} Este programa y el aparente misterio que rodea su efecto han atraído cierta atención y se conocen comúnmente como el rompecabezas del yin-yang . ^{[ 2 ]} Una traducción a Scheme, proporcionada por Madore, es la siguiente:

( let* (( yin (( lambda ( cc ) ( display # \ @ ) cc ) ( call-with-current-continuation ( lambda ( c ) c )))) ( yang (( lambda ( cc ) ( display # \ * ) cc ) ( call-with-current-continuation ( lambda ( c ) c ))))) ( yin yang ))

Oleg Kiselyov, autor de una implementación de continuación delimitada para OCaml y diseñador de una interfaz de programación de aplicaciones (API) para la manipulación de pila delimitada con el fin de implementar operadores de control, aboga por el uso de continuaciones delimitadas en lugar de las continuaciones de pila completa que manipula call/cc: "Ofrecer call/cc como una característica de control central en función de la cual deberían implementarse todas las demás funcionalidades de control resulta ser una mala idea. El rendimiento, las fugas de memoria y recursos, la facilidad de implementación, la facilidad de uso y la facilidad de razonamiento son argumentos en contra de call/cc." ^{[ 3 ]}

La correspondencia de Curry-Howard entre pruebas y programas relaciona call/cc con la ley de Peirce , que extiende la lógica intuicionista a la lógica clásica no constructiva : ((α → β) → α) → α. Aquí, ((α → β) → α) es el tipo de la función f , que puede devolver un valor de tipo α directamente o aplicar un argumento a la continuación de tipo (α → β). Dado que el contexto existente se elimina cuando se aplica la continuación, el tipo β nunca se usa y puede tomarse como ⊥, el tipo vacío.

El principio de eliminación de la doble negación ((α → ⊥) → ⊥) → α es comparable a una variante de call-cc que espera que su argumento f siempre evalúe la continuación actual sin devolver normalmente un valor. Las incrustaciones de la lógica clásica en la lógica intuicionista están relacionadas con la traducción del estilo de paso de continuaciones . ^{[ 4 ]}

• Esquema
• Raqueta
• ML estándar ^{[ 5 ]}
• Haskell en la continuación Monad
• Rubí ^{[ 6 ]}
• Unlambda
• C++ ^{[ 7 ]}
• R ^{[ 8 ]}

• Ir a
• Async/await
• Estilo de pase de continuación
• Fibra (informática)

• Una breve introducción acall-with-current-continuation
• Definición de call-with-current-continuationen la especificación del esquema
• Explicación humorística de call-with-current-continuationRob Warnock en Usenetcomp.lang.lisp
• Multitarea cooperativa en Scheme usando Call-CC