En los lenguajes de programación , una continuación delimitada , una continuación componible o una continuación parcial , es una "porción" de un marco de continuación que se ha cosificado 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 se pueden encontrar alusiones tempranas a las continuaciones componibles y delimitadas en la disertación de Carolyn Talcott en Stanford de 1984, Felleisen et al. [2] , la disertación de Felleisen de 1987, [3] y algoritmos para el retroceso funcional , por ejemplo, para la coincidencia de patrones , para el análisis sintáctico , en el lenguaje de programación funcional de lógica algebraica y en las implementaciones funcionales de Prolog , donde la continuación de falla a menudo se mantiene implícita y la razón de ser de la continuación de éxito es que es componible.
Las continuaciones delimitadas fueron introducidas por primera vez por Felleisen en 1988 [1] con un operador llamado , introducido por primera vez en un informe técnico en 1987, [2] junto con un constructo de solicitud . El operador fue diseñado para ser una generalización de los operadores de control que se habían descrito en la literatura, como de Scheme , el operador J de ISWIM , el operador de John C. Reynolds y otros. Posteriormente, la comunidad de investigación de lenguajes de programación inventó muchos operadores de control delimitados que competían entre sí, como y , [4] y , [5] [6] , [7] y otros.call/ccescapepromptcontrol shiftresetcupto fcontrol
En la literatura de investigación se han propuesto varios operadores para continuaciones delimitadas. [8]
Una propuesta independiente [5] se basa en el estilo de paso de continuación (CPS), es decir, no en marcos de continuación, y ofrece dos operadores de control, shifty reset, que dan lugar a continuaciones delimitadas estáticas en lugar de dinámicas. [9]
El resetoperador establece el límite para la continuación mientras que el shiftoperador captura o reifica la continuación actual hasta el reset. Por ejemplo, considere el siguiente fragmento en Scheme :
( * 2 ( restablecer ( + 1 ( cambiar k ( k 5 ))))) El resetdelimita la continuación que shiftcaptura (nombrada por ken este ejemplo). Cuando se ejecuta este fragmento, el uso de shiftse vinculará ka 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 a shiftup hasta 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 un comportamiento más interesante, por ejemplo, devolviendo la continuación capturada kcomo un valor o invocándolo kvarias veces. El shiftoperador pasa la continuación capturada kal código en su cuerpo, que puede invocarla, producirla como resultado o ignorarla por completo. Cualquier resultado que shiftproduzca se proporciona al más interno reset, descartando la continuación entre resety shift. Sin embargo, si se invoca la continuación, entonces efectivamente reinstala la continuación después de regresar a reset. Cuando se completa todo el cálculo dentro reset, el resultado es devuelto por la continuación delimitada. [10] Por ejemplo, en este código de Scheme :
( restablecer ( * 2 ( shift k CÓDIGO ))) siempre que CODEse invoca (k N), (* 2 N)se evalúa y se devuelve.
Esto es equivalente a lo siguiente:
( sea (( k ( lambda ( x ) ( * 2 x )))) CÓDIGO ) Además, una vez que se completa todo el cálculo dentro shift, se descarta la continuación y la ejecución se reinicia fuera reset. Por lo tanto,
( restablecer ( * 2 ( cambio k ( k ( k 4 ))))) invoca (k 4)primero (que devuelve 8) y luego (k 8)(que devuelve 16). En este punto, la shiftexpresión ha terminado y el resto de la resetexpresión se descarta. Por lo tanto, el resultado final es 16.
Todo lo que ocurre fuera de la resetexpresión queda oculto, es decir, no se ve afectado por la transferencia de control. Por ejemplo, esto devuelve 17:
( + 1 ( restablecer ( * 2 ( cambiar k ( k ( k 4 )))))) Las continuaciones delimitadas fueron descritas por primera vez de forma independiente por Felleisen et al. [2] y Johnson [11] . Desde entonces, se han utilizado en una gran cantidad de dominios, particularmente para definir nuevos operadores de control ; consulte Queinnec [12] para obtener un resumen.
Veamos un ejemplo más complicado. Sea nullla lista vacía:
( restablecer ( comenzar ( shift k ( cons 1 ( k ( void )))) ;; (1) null )) El contexto capturado por shiftes (begin [*] null), donde [*]es el agujero donde kse inyectará el parámetro de . La primera llamada de kinside shiftevalúa este contexto con (void)= #<void>reemplazando el agujero, por lo que el valor de (k (void))es (begin #<void> null)= null. El cuerpo de shift, es decir (cons 1 null)= (1), se convierte en el valor general de la resetexpresión como resultado final.
Para complicar aún más este ejemplo, agregue una línea:
( restablecer ( comenzar ( shift k ( cons 1 ( k ( void )))) ( shift k ( cons 2 ( k ( void )))) null )) Si comentamos el primer shift, ya conocemos el resultado, que es (2); por lo que también podemos reescribir la expresión así:
( restablecer ( comenzar ( shift k ( cons 1 ( k ( void )))) ( lista 2 ))) Esto es bastante familiar y se puede reescribir como (cons 1 (list 2)), es decir, (list 1 2).
Podemos definir yieldusando este truco:
(define (rendimiento x) (desplazamiento k (cons x (k (vacío)))))
y usarlo para crear listas:
( restablecer ( comenzar ( rendimiento 1 ) ( rendimiento 2 ) ( rendimiento 3 ) nulo )) ;; (lista 1 2 3) Si reemplazamos conscon stream-cons, podemos crear transmisiones perezosas:
( define ( stream-yield x ) ( shift k ( stream-cons x ( k ( void ))))) ( definir ejemplo-perezoso ( restablecer ( comenzar ( stream-yield 1 ) ( stream-yield 2 ) ( stream-yield 3 ) stream-null ))) Podemos generalizar esto y convertir listas en secuencias, de una sola vez:
( definir ( lista->stream xs ) ( restablecer ( comenzar ( para-cada stream-yield xs ) stream-null ))) En un ejemplo más complicado a continuación, la continuación se puede envolver de forma segura en un cuerpo de una lambda y usarse como tal:
( define ( for-each->stream-maker for-each ) ( lambda ( colección ) ( reset ( begin ( for-each ( lambda ( elemento ) ( shift k ( stream-cons elemento ( k 'ignorado )))) colección ) stream-null )))) La parte entre resety shiftincluye funciones de control como lambday for-each; esto es imposible de reformular utilizando lambdas [ ¿por qué? ] .
Las continuaciones delimitadas también son útiles en lingüística : consulte Continuaciones en lingüística para obtener más detalles.
A la función curry generalizada se le da una función no currificada fy su aridad (por ejemplo, 3), y devuelve el valor (lambda (v1) (lambda (v2) (lambda (v3) (f v1 v2 v3)))). Este ejemplo se debe a Olivier Danvy y se desarrolló a mediados de la década de 1980. [13]
A continuación se muestra una función de prueba unitaria para ilustrar lo que se espera que haga la función curry generalizada:
( define test-curry ( lambda ( candidato ) ( y ( = ( candidato + 0 ) ( + )) ( = (( candidato + 1 ) 1 ) ( + 1 )) ( = ((( candidato + 2 ) 1 ) 10 ) ( + 1 10 )) ( = (((( candidato + 3 ) 1 ) 10 ) 100 ) ( + 1 10 100 ))) ( = ((((( candidato + 4 ) 1 ) 10 ) 100 ) 1000 ) ( + 1 10 100 1000 )))) Estas pruebas unitarias verifican si currar la función variádica +en una función currada n-aria y aplicar el resultado a n argumentos produce el mismo resultado que aplicarlo +a estos n argumentos, para n = 0, 1, 2, 3 y 4.
La siguiente función recursiva se basa en el acumulador y, eventualmente, invierte el acumulador antes de aplicar la función no currificada dada. En cada instancia del paso de inducción, la función (lambda (v) ...)se aplica explícitamente a un argumento en la aplicación currificada:
( define curry_a ( lambda ( f n ) ( if ( < n 0 ) ( error 'curry_a "entrada negativa: ~s" n ) ( letrec ([ visit ( lambda ( i a ) ( if ( = i 0 ) ( apply f ( reverse a )) ( lambda ( v ) ( visit ( - i 1 ) ( cons v a )))))]) ( visit n ' ()))))) Por ejemplo, evaluar
((( curry_a + 2 ) 1 ) 10 ) se reduce a evaluar
((( visita 2 ' ()) 1 ) 10 ) Lo que se reduce a evaluar
((( lambda ( v ) ( visita 1 ( cons v ' ()))) 1 ) 10 ) que reduce beta para evaluar
(( visita 1 ( contras 1 ' ())) 10 ) Lo que se reduce a evaluar
(( lambda ( v ) ( visita 0 ( cons v ( cons 1 ' ())))) 10 ) que reduce beta para evaluar
( visita 0 ( contras 10 ( contras 1 ' ()))) Lo que se reduce a evaluar
( aplicar + ( revertir ( cons 10 ( cons 1 ' ())))) Lo que se reduce a evaluar
( aplicar + ( contras 1 ( contras 10 ' ()))) que es equivalente a
( + 1 10 ) que delta-reduce al resultado, 11.
La siguiente función recursiva se basa en la continuación y no implica inversión de lista. Asimismo, en cada instancia del paso de inducción, la función (lambda (v) ...)se aplica explícitamente a un argumento en la aplicación currificada:
( define curry_c ( lambda ( f n ) ( if ( < n 0 ) ( error 'curry_c "entrada negativa: ~s" n ) ( letrec ([ visit ( lambda ( i c ) ( if ( = i 0 ) ( c ' ()) ( lambda ( v ) ( visit ( - i 1 ) ( lambda ( vs ) ( c ( cons v vs )))))))]) ( visit n ( lambda ( vs ) ( apply f vs ))))))) Así que evaluando
((( curry_c + 2 ) 1 ) 10 ) se reduce a evaluar
((( visita 2 ( lambda ( vs ) ( aplicar + vs ))) 1 ) 10 ) Lo que se reduce a evaluar
((( lambda ( v ) ( visita 1 ( lambda ( vs ) (( lambda ( vs ) ( aplicar + vs )) ( contras v vs ))))) 1 ) 10 ) que reduce beta para evaluar
(( visita 1 ( lambda ( vs ) (( lambda ( vs ) ( aplicar + vs )) ( contras 1 vs )))) 10 ) Lo que se reduce a evaluar
(( lambda ( v ) ( visita 0 ( lambda ( vs ) (( lambda ( vs ) (( lambda ( vs ) ( aplicar + vs )) ( contras 1 vs ))) ( contras v vs ))))) 10 ) que reduce beta para evaluar
( visita 0 ( lambda ( vs ) (( lambda ( vs ) (( lambda ( vs ) ( aplicar + vs )) ( contras 1 vs ))) ( contras 10 vs )))) Lo que se reduce a evaluar
(( lambda ( vs ) (( lambda ( vs ) (( lambda ( vs ) ( aplicar + vs )) ( contras 1 vs ))) ( contras 10 vs ))) ' ()) que reduce beta para evaluar
(( lambda ( vs ) (( lambda ( vs ) ( aplicar + vs )) ( cons 1 vs ))) ( cons 10 ' ())) que reduce beta para evaluar
(( lambda ( vs ) ( aplicar + vs )) ( cons 1 ( cons 10 ' ()))) que reduce beta para evaluar
( aplicar + ( contras 1 ( contras 10 ' ()))) que es equivalente a
( + 1 10 ) que delta-reduce al resultado, 11.
La siguiente función recursiva, curry_d, es la contraparte de estilo directo de curry_cy presenta el (shift k k)idioma, utilizando la implementación de Andrzej Filinski de shift y reset en términos de una celda mutable global y de call/cc. [14]
En cada instancia del paso de inducción, la abstracción de continuación se aplica implícitamente a un argumento en la aplicación currificada:
( define curry_d ( lambda ( f n ) ( if ( < n 0 ) ( error 'curry_d "entrada negativa: ~s" n ) ( letrec ([ visit ( lambda ( i ) ( if ( = i 0 ) ' () ( cons ( shift k k ) ( visit ( - i 1 )))))]) ( reset ( apply f ( visit n ))))))) El quid de la cuestión es la equivalencia observacional entre (reset (... (shift k k) ...))y (lambda (x) (reset (... x ...)))donde xes fresco y las elipses representan un contexto puro, es decir, uno sin efectos de control.
Así que evaluando
((( curry_d + 2 ) 1 ) 10 ) se reduce a evaluar
((( restablecer ( aplicar + ( visitar 2 ))) 1 ) 10 ) Lo que se reduce a evaluar
((( restablecer ( aplicar + ( cons ( shift k k ) ( visitar 1 )))) 1 ) 10 ) que es observacionalmente equivalente a
((( lambda ( x ) ( restablecer ( aplicar + ( cons x ( visitar 1 ))))) 1 ) 10 ) que reduce beta para evaluar
(( restablecer ( aplicar + ( contras 1 ( visita 1 )))) 10 ) Lo que se reduce a evaluar
(( restablecer ( aplicar + ( cons 1 ( cons ( shift k k ) ( visitar 0 ))))) 10 ) que es observacionalmente equivalente a
(( lambda ( x ) ( restablecer ( aplicar + ( cons 1 ( cons x ( visitar 0 )))))) 10 ) que reduce beta para evaluar
( restablecer ( aplicar + ( contras 1 ( contras 10 ( visita 0 ))))) Lo que se reduce a evaluar
( restablecer ( aplicar + ( cons 1 ( cons 10 ' ())))) que es equivalente a
( restablecer ( + 1 10 )) que delta-reduce para evaluar
( restablecer 11 ) lo que da como resultado, 11.
La definición de curry_dtambién ilustra las continuaciones estáticas delimitadas. Esta extensión estática debe codificarse explícitamente si se desea utilizar controly prompt: [15]
( define curry_cp ( lambda ( f n ) ( if ( < n 0 ) ( error 'curry_cp "entrada negativa: ~s" n ) ( letrec ([ visit ( lambda ( i ) ( if ( = i 0 ) ' () ( cons ( control k ( lambda ( x ) ( prompt ( k x )))) ( visit ( - i 1 )))))]) ( prompt ( apply f ( visit n ))))))) racket/control Racket [1]; los siguientes ejemplos pueden ejecutarse en Racket usando(require racket/control)