En los lenguajes de programación , una continuación delimitado , la continuación componibles o la continuación parcial , es una "rebanada" de una continuación del marco que se ha materializado en una función . A diferencia de las continuaciones regulares, las continuaciones delimitadas devuelven un valor y, por lo tanto, pueden reutilizarse y componerse . Los delimitadores de control, la base de las continuaciones delimitadas, fueron introducidos por Matthias Felleisen en 1988 [1], aunque las primeras alusiones a las continuaciones componibles y delimitadas se pueden encontrar en Carolyn Talcottdisertación de Stanford 1984, artículo PARL 1987 de Felleisen y Friedman, [2] y disertación de 1987 de Felleisen. [3]
Historia
Las continuaciones delimitadas fueron introducidas por primera vez por Felleisen en 1988 [1] con un operador llamado, presentado por primera vez en un informe técnico en 1987, [2] junto con una construcción rápida. El operador fue diseñado para ser una generalización de los operadores de control que habían sido descritos en la literatura tal como call/cc
desde el Esquema , ISWIM 's operador J , John C. Reynolds ' escape
operador, y otros. Posteriormente, muchos operadores de control delimitados competidores fueron inventados por la comunidad de investigación de lenguajes de programación como prompt
y control
, [4] shift
y reset
, [5] cupto
, [6] fcontrol
, y otros.
Ejemplos de
En la literatura de investigación se han propuesto varios operadores para continuaciones delimitadas. [7]
Una propuesta [5] ofrece dos operadores de control: shift
y reset
. El reset
operador establece el límite para la continuación mientras el shift
operador captura o reifica la continuación actual hasta el cerramiento más interno reset
. Por ejemplo, considere el siguiente fragmento de Scheme :
( * 2 ( restablecer ( + 1 ( desplazamiento k ( k 5 )))))
El reset
delimita la continuación que shift
captura (nombrada por k
en este ejemplo). Cuando se ejecuta este fragmento, el uso de shift
se vinculará k
a la continuación (+ 1 [])
donde []
representa la parte del cálculo que se debe completar con un valor. Esta continuación corresponde directamente al código que rodea el shift
hasta el reset
. Debido a que el cuerpo de shift (es decir, (k 5)
) invoca inmediatamente la continuación, este código es equivalente a lo siguiente:
( * 2 ( + 1 5 ))
En general, estos operadores pueden codificar comportamientos más interesantes, por ejemplo, devolviendo la continuación capturada k
como un valor o invocando k
varias veces. El shift
operador pasa la continuación capturada k
al código en su cuerpo, que puede invocarlo, producirlo como resultado o ignorarlo por completo. Cualquier resultado que shift
produzca se proporciona a lo más íntimo reset
, descartando la continuación entre el reset
y shift
. Sin embargo, si se invoca la continuación, se reinstala efectivamente la continuación después de volver a reset
. Cuando reset
se completa todo el cálculo interno , la continuación delimitada devuelve el resultado. [8] Por ejemplo, en este código de esquema :
( restablecer ( * 2 ( cambiar k CÓDIGO )))
siempre que CODE
invoca (k N)
, (* 2 N)
se evalúa y se devuelve.
Esto es equivalente a lo siguiente:
( deje (( k ( lambda ( x ) ( * 2 x )))) CÓDIGO )
Además, una vez que shift
se completa todo el cálculo interno , la continuación se descarta y la ejecución se reinicia en el exterior reset
. Por lo tanto,
( restablecer ( * 2 ( desplazamiento k ( k ( k 4 )))))
invoca (k 4)
primero (que devuelve 8) y luego (k 8)
(que devuelve 16). En este punto, la shift
expresión ha terminado y el resto de la reset
expresión se descarta. Por tanto, el resultado final es 16.
Todo lo que ocurre fuera de la reset
expresión queda oculto, es decir, no influido por la transferencia de control. Por ejemplo, esto devuelve 17:
( + 1 ( restablecer ( * 2 ( desplazamiento k ( k ( k 4 ))))))
Las continuaciones delimitadas fueron descritas por primera vez de forma independiente por Felleisen et al. [9] y Johnson. [10] Desde entonces se han utilizado en un gran número de dominios, particularmente en la definición de nuevos operadores de control ; ver Queinnec [11] para una encuesta.
Echemos un vistazo a un ejemplo más complicado. Sea null
la lista vacía:
( restablecer ( comenzar ( desplazamiento k ( cons 1 ( k ( anulado )))) ;; (1) nulo ))
El contexto capturado por shift
es (begin [*] null)
, donde [*]
es el agujero donde k
se inyectará el parámetro. La primera llamada de k
inside se shift
evalúa en este contexto con (void)
= #
reemplazando el agujero, por lo que el valor de (k (void))
es (begin #
= null
. El cuerpo de shift
, a saber (cons 1 null)
= (1)
, se convierte en el valor global de la reset
expresión como resultado final.
Para complicar este ejemplo, agregue una línea:
( reiniciar ( comenzar ( cambio k ( cons 1 ( k ( anulado )))) ( cambio k ( cons 2 ( k ( anulado )))) nulo ))
Si comentamos el primero shift
, ya conocemos el resultado, lo es (2)
; así que también podemos reescribir la expresión así:
( restablecer ( comenzar ( cambio k ( cons 1 ( k ( anulado )))) ( lista 2 )))
Esto es bastante familiar, y puede ser reescrito como (cons 1 (list 2))
, es decir, (list 1 2)
.
Podemos definir yield
usando este truco:
(definir (rendimiento x) (desplazamiento k (cons x (k (vacío)))))
y utilícelo en listas de creación:
( restablecer ( comenzar ( rendimiento 1 ) ( rendimiento 2 ) ( rendimiento 3 ) nulo )) ;; (lista 1 2 3)
Si reemplazamos cons
con stream-cons
, podemos construir transmisiones perezosas:
( definir ( flujo-rendimiento x ) ( desplazamiento k ( flujo-cons x ( k ( vacío ))))) ( definir ejemplo-perezoso ( reset ( begin ( stream-yield 1 ) ( stream-yield 2 ) ( stream-yield 3 ) stream-null )))
Podemos generalizar esto y convertir listas en stream, de una sola vez:
( definir ( lista-> flujo xs ) ( restablecer ( comenzar ( para cada flujo-rendimiento xs ) flujo-nulo )))
En un ejemplo más complicado a continuación, la continuación se puede envolver de forma segura en el cuerpo de una lambda y usarse como tal:
( definir ( para-cada-> stream-maker para-cada ) ( lambda ( colección ) ( reset ( begin ( for-each ( lambda ( elemento ) ( shift k ( stream-cons element ( k 'ignored )))) colección ) flujo-nulo ))))
La parte entre reset
e shift
incluye funciones de control como lambda
y for-each
; esto es imposible de reformular usando lambdas [ ¿por qué? ] .
Las continuaciones delimitadas también son útiles en lingüística : consulte Continuaciones en lingüística para obtener más detalles.
Referencias
- ↑ a b Matthias Felleisen (1988). "La teoría y la práctica de indicaciones de primera clase". Principios de lenguajes de programación : 180-190. doi : 10.1145 / 73560.73576 . ISBN 0-89791-252-7.
- ^ a b Felleisen; Friedman; Duba; Merrill (1987). Más allá de las continuaciones (informe técnico). Universidad de Indiana . 87-216.
- ^ Matthias Felleisen (1987). Los cálculos de la conversión de Lambda-v-CS: una teoría sintáctica del control y el estado en lenguajes de programación imperativos de orden superior (PDF) (Tesis).
- ^ Sitaram, Dorai; Felleisen, Matthias (1990). "Control delimitadores y sus jerarquías" (PDF) . Lisp y computación simbólica .
- ^ a b Olivier Danvy; Andrzej Filinski (1990). "Control de abstracción". LISP y programación funcional : 151–160. doi : 10.1145 / 91556.91622 . ISBN 0-89791-368-X.
- ^ Gunter; Rémy; Riecke (1995). "Una generalización de excepciones y control en lenguajes similares a ML". Lenguajes de programación funcional y arquitectura informática .
- ^ Consulte, por ejemplo, los operadores que ofrece labiblioteca
racket/control
Racket [1] ; los siguientes ejemplos pueden ejecutarse en Racket usando(require racket/control)
- ^ Gasbichler, Martin; Sperber, Michael (2002). "Final Shift para Call / cc: implementación directa de Shift y Reset". CiteSeerX 10.1.1.11.3425 . Cite journal requiere
|journal=
( ayuda ) - ^ Felleisen, Matthias; Friedman, Daniel P .; Duba, Bruce; Marrill, John (febrero de 1987). "Más allá de las continuaciones" (PDF) . Informe técnico 216. Departamento de Ciencias de la Computación, Universidad de Indiana . Cite journal requiere
|journal=
( ayuda ) - ^ Johnson, Gregory F. (junio de 1987). "GL: un banco de pruebas denotacional con continuaciones y continuaciones parciales". Proc. Simposio SIGPLAN '87 sobre Intérpretes y Técnicas Interpretativas . págs. 218-225.
- ^ Queinnec, Christian (abril de 1994). "Una biblioteca de operadores de control de alto nivel". École Polytechnique e INRIA -Rocquencourt. CiteSeerX 10.1.1.29.4790 . Cite journal requiere
|journal=
( ayuda )
enlaces externos
- Tutorial de continuaciones componibles en SchemeWiki
- Continuaciones delimitadas en sistemas operativos, por Oleg Kiselyov y Chung-chieh Shan
- Continuaciones nativas delimitadas en (código de bytes y código nativo) OCaml
- Shift / reset для самых маленьких (en ruso)
- Algunos artículos interesantes sobre continuaciones delimitadas y macros de primera clase