En el lenguaje de programación de computadoras Scheme , la subrutina o función llamada-con-continuación-actual , llamada abreviada / cc , se usa como operador de flujo de control . Ha sido adoptado por varios otros lenguajes de programación.
Tomando una función f
como 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)
equivale a aplicar f
a la continuación actual de la expresión. La continuación actual se obtiene reemplazando (call/cc f)
por una variable c
limitada por una abstracción lambda, por lo que la continuación actual es (lambda (c) (c e2))
. Al aplicarle la función f
se obtiene el resultado final (f (lambda (c) (c e2)))
.
Como ejemplo complementario, en una expresión (e1 (call/cc f))
, la continuación de la subexpresión (call/cc f)
es (lambda (c) (e1 c))
, por lo que toda la expresión es equivalente a (f (lambda (c) (e1 c)))
. En otras palabras, toma una "instantánea" del contexto de control actual o del estado de control del programa como un objeto y se aplica f
a él. El objeto de continuación es un valor de primera clase y se representa como una función, con la aplicación de la función como su única operación. 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 en el "valor de retorno" de la invocación call / cc. Las continuaciones creadas con call / cc se pueden llamar más de una vez, e incluso desde fuera de la extensión dinámica de la aplicación call / cc.
En informática, hacer visible este tipo de estado de programa implícito como un objeto se denomina reificación . ( Scheme no distingue sintácticamente entre aplicar continuaciones o funciones).
Con call / cc se pueden implementar una variedad de operadores de control complejos desde otros lenguajes a través de unas pocas líneas de código, por ejemplo, el operador de McCarthy para una elección no determinista , retroceso al estilo Prolog , corrutinas al estilo Simula 67 y generalizaciones de los mismos, estilo Icon generadores , o motores e hilos o incluso el oscuro COMEFROM .amb
Ejemplos de
Como se muestra en el siguiente ejemplo, call / cc se puede usar para emular la función de la declaración de retorno conocida de los lenguajes de estilo C , que falta en Scheme :
( definir ( f retorno ) ( retorno 2 ) 3 )( mostrar ( f ( lambda ( x ) x ))) ; muestra 3( pantalla ( llamada-con-continuación-actual f )) ; muestra 2
Llamar a f con un argumento de función regular primero aplica esta función al valor 2, luego devuelve 3. Sin embargo, cuando se pasa f a call / cc (como en la última línea del ejemplo), se aplica el parámetro (la continuación) a 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. Esto luego es impreso por la función de visualización.
En el siguiente ejemplo, call / cc se usa dos veces: una vez para generar una continuación de "retorno" como en el primer ejemplo y una vez para suspender una iteración a través de una lista de elementos:
;; [LISTOF X] -> (-> X u 'you-fall-off-the-end) ( define ( generate-one-element-at-a-time lst ) ;; Ambas funciones internas son cierres sobre lst ;; Variable / Función interna que pasa el elemento actual en una lista ;; a su argumento de retorno (que es una continuación), o pasa un marcador de final de lista ;; si no quedan más elementos. En cada paso, el nombre de la función es ;; rebote a una continuación que apunta hacia el cuerpo de la función, ;; mientras que el retorno se recupera a cualquier continuación que especifique la persona que llama. ( define ( control-state return ) ( for-each ( lambda ( elemento ) ( set! return ( call-with-current-continuation ( lambda ( resume-here ) ;; Toma la continuación actual ( set! control-state resume- aquí ) ( elemento de retorno ))))) ;; (elemento de retorno) se evalúa en el siguiente lst de retorno ) ( devuelve 'te-caíste-del-fin )) ;; (-> X u 'te-caíste-al-final) ;; Este es el generador real, que produce un elemento de una lista a la vez. ( definir ( generador ) ( llamada con estado de control de continuación de corriente )) ;; Devolver el generador generador )( definir generar-dígito ( generar-un-elemento-a-la-vez ' ( 0 1 2 )))( generar dígitos ) ;; 0 ( generar dígitos ) ;; 1 ( generar dígitos ) ;; 2 ( generar dígitos ) ;; te caíste del final
Cada vez que el ciclo 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 inicialmente es 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 por ejemplo [LISTOF X]
, el código se generaliza a cualquier colección que se pueda atravesar.
La llamada con continuación de corriente también puede expresar otras primitivas sofisticadas. Por ejemplo, la siguiente muestra realiza tareas múltiples cooperativas utilizando continuaciones:
;; Multitarea cooperativa usando llamada-con-continuación-actual ;; en 25 líneas de esquema;; La lista de subprocesos a la espera de ejecutarse. Esta es una lista de uno ;; funciones de no retorno de argumentos (continuaciones, en su mayoría) ;; Una continuación es una función que no devuelve, como (salir), ;; en el sentido de que nunca cede el control a lo que sea que lo llame.( definir lista lista ' ());; Una función de no retorno. Si hay algún otro hilo ;; esperando ser ejecutado, hace que se ejecute el siguiente hilo si existe ;; es cualquier dejado para ejecutar, de lo contrario, llama a la salida original ;; que sale de todo el entorno. ( define exit ;; La salida original que anulamos. ( let (( exit exit )) ;; La función de anulación. ( lambda () ( if ( not ( null? ready-list )) ;; Hay otro hilo esperando para be run. ;; Entonces lo ejecutamos. ( let (( cont ( car ready-list ))) ( set! ready-list ( cdr ready-list )) ;; Dado que la lista lista solo no devuelve ;; funciones, esto no regresará. ( cont #f )) ;; No queda nada por ejecutar. ;; La (salida) original es una función que no regresa, ;; así que esta es una función que no regresa. ( salir )))) );; Toma una función de un argumento con un dado ;; argumento y lo bifurca. La función bifurcada es nueva ;; el hilo saldrá si / cuando la función salga alguna vez. ( define ( fork fn arg ) ( set! ready-list ( append ready-list ;; Esta función agregada a la ;; lista-lista no regresa, ;; ya que la salida no regresa. ( list ( lambda ( x ) ( fn arg ) ( salir ))))));; Cede el control del siguiente hilo que espera ser ejecutado. ;; Aunque eventualmente regresará, cede el control ;; y solo lo recuperará cuando se llame a la continuación. ( define ( rendimiento ) ( call-with-current-continuation ;; Capture la continuación que representa ESTA llamada para rendir ( lambda ( cont ) ;; Péguelo en la lista lista ( set! lista-lista ( agregar lista-lista ( lista cont ))) ;; Obtiene el siguiente hilo, y empezar a hacerlo funcionar. ( dejar que (( cont ( auto -lista preparada ))) ( set! -lista preparada ( CDR -lista preparada )) ;; ejecutarlo. ( cont #f )))))
En 1999, David Madore (inventor de la unlambda lenguaje de programación) descubrió accidentalmente un término unlambda de 12 caracteres, haciendo uso de la llamada / cc, que imprime todos los números naturales de forma secuencial en la representación unaria: ``r`ci`.*`ci
. [1] Este programa y el aparente misterio que rodea a su efecto han atraído cierta atención y se conocen comúnmente como el rompecabezas del yin-yang . [2] Una traducción del esquema, proporcionada por Madore, es la siguiente:
( let * (( yin (( lambda ( cc ) ( mostrar # \ @ ) cc ) ( llamada-con-continuación-actual ( lambda ( c ) c )))) ( yang (( lambda ( cc ) ( mostrar # \ * ) cc ) ( llamada-con-continuación-actual ( lambda ( c ) c ))))) ( yin yang ))
Crítica
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 para implementar operadores de control, aboga por el uso de continuaciones delimitadas en lugar de las continuaciones de pila completa que call / cc manipula: "Ofrecer call / cc como una función de control central en términos de la cual se deben implementar todas las demás funciones de control resulta una mala idea. El rendimiento, las pérdidas de memoria y recursos, la facilidad de implementación, la facilidad de uso, la facilidad de razonamiento, todos argumentan en contra de call / cc. " [3]
Relación con la lógica no constructiva
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 del 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 de estilo de paso de continuación . [4]
Idiomas que implementan call / cc
- Esquema
- Raqueta
- ML estándar [5]
- Haskell en la continuación Mónada
- Rubí [6]
- Unlambda
- C ++ [7]
- R [8]
Ver también
- Ir
- Estilo de continuación-pase
- Fibra (informática)
Referencias
- ^ David Madore, "call / cc mind-boggler"
- ^ Yin Wang, "Comprender el rompecabezas Yin-Yang"
- ^ "Un argumento en contra de call / cc" .
- ^ Sørensen, Morten Heine; Urzyczyn, Paweł (2007). "Operadores de control y lógica clásica". Conferencias sobre el isomorfismo de Curry-Howard (1ª ed.). Boston, MA: Elsevier. ISBN 0444520775.
- ^ "La firma CONT" . ML estándar de Nueva Jersey . Bell Labs, Lucent Technologies. 1997-10-28 . Consultado el 15 de mayo de 2019 .
- ^ "Clase: Continuación" . Ruby-doc.org . Neurogami, James Britt . Consultado el 15 de mayo de 2019 .
- ^ Kowalke, Oliver (2014). "Cambio de contexto con llamada / cc" . Boost.org . Consultado el 15 de mayo de 2019 .
- ^ https://stat.ethz.ch/R-manual/R-devel/library/base/html/callCC.html
enlaces externos
- Una breve introducción a call-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
Este artículo se basa en material extraído del Diccionario gratuito de informática en línea antes del 1 de noviembre de 2008 e incorporado bajo los términos de "renovación de licencias" de la GFDL , versión 1.3 o posterior.