Continuación delimitada

En los lenguajes de programación , una continuación delimitada , continuación componible o continuación parcial , es una "porción" de un marco de continuación que se ha reificado 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 continuaciones componibles y delimitadas en la disertación de Carolyn Talcott de Stanford de 1984, Felleisen et al. , ^{[ 2 ]} La disertación de Felleisen de 1987, ^{[ 3 ]} y algoritmos para retroceso funcional , por ejemplo, para coincidencia de patrones , para 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 fallos a menudo se mantiene implícita y la razón de ser de la continuación de éxitos es que es componible.

Las continuaciones delimitadas fueron introducidas por primera vez por Felleisen en 1988 ^{[ 1 ]} con un operador llamado${\displaystyle {\mathcal {F}}}$, introducido por primera vez en un informe técnico en 1987, ^{[ 2 ]} junto con una construcción de aviso${\displaystyle \#}$El operador fue diseñado para ser una generalización de los operadores de control que se habían descrito en la literatura, como call/cclos 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 competidores, como y , ^{[ 4 ]} y , ^{[ 5 ] [ 6 ]} , ^{[ 7 ]} , y otros.escapepromptcontrolshiftresetcuptofcontrol

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 continuaciones (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 contenedor más interno reset. Por ejemplo, considérese el siguiente fragmento en Scheme :

( * 2 ( reiniciar ( + 1 ( desplazamiento 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 va a rellenar con un valor. Esta continuación corresponde directamente al código que rodea a shifthasta reset. Debido a que el cuerpo de shift (es decir, (k 5)) invoca inmediatamente la continuación, este código es equivalente al 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ándola 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, esta se reinstala efectivamente después de regresar a reset. Cuando se completa todo el cálculo dentro de reset, el resultado es devuelto por la continuación delimitada. ^{[ 10 ]} Por ejemplo, en este código Scheme :

( reiniciar ( * 2 ( shift k CÓDIGO )))

cada vez que CODEse invoca (k N), (* 2 N)se evalúa y se devuelve.

Esto equivale a lo siguiente:

( let (( k ( lambda ( x ) ( * 2 x )))) CÓDIGO )

Además, una vez que se completa todo el cálculo interno shift, la continuación se descarta y la ejecución se reinicia fuera de reset. Por lo tanto,

( reiniciar ( * 2 ( desplazamiento k ( k ( k 4 )))))

Primero se invoca (k 4)(que devuelve 8), y luego (k 8)(que devuelve 16). En este punto, la shiftexpresión ha terminado y el resto resetse 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 ( reiniciar ( * 2 ( desplazamiento 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 un gran número de dominios, particularmente en la definición de nuevos operadores de control ; véase Queinnec ^{[ 12 ]} para una revisión.

Veamos un ejemplo más complicado. Sea nullla lista vacía:

( reiniciar ( comenzar ( cambiar k ( cons 1 ( k ( vacío )))) ;; (1) nulo ))

El contexto capturado por shiftes (begin [*] null), donde [*]es el hueco donde kse inyectará el parámetro de . La primera llamada de kdentro shiftse evalúa a este contexto con (void)= #<void>reemplazando el hueco, 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:

( reiniciar ( comenzar ( cambiar k ( cons 1 ( k ( vacío )))) ( cambiar k ( cons 2 ( k ( vacío )))) nulo ))

Si comentamos la primera línea shift, ya conocemos el resultado, que es (2); así que también podemos reescribir la expresión de esta manera:

( reiniciar ( comenzar ( cambiar k ( cons 1 ( k ( vacío )))) ( lista 2 )))

Esto es bastante familiar y se puede reescribir como (cons 1 (list 2)), es decir, (list 1 2).

Podemos definirlo yieldusando este truco:

(define (yield x) (shift k (cons x (k (void)))))

y úselo para crear listas:

( reiniciar ( inicio ( rendimiento 1 ) ( rendimiento 2 ) ( rendimiento 3 ) nulo )) ;; (lista 1 2 3)

Si reemplazamos conscon stream-cons, podemos construir flujos perezosos:

( define ( stream-yield x ) ( shift k ( stream-cons x ( k ( void )))))( define lazy-example ( reset ( begin ( stream-yield 1 ) ( stream-yield 2 ) ( stream-yield 3 ) stream-null )))

Podemos generalizar esto y convertir listas en flujos de datos de una sola vez:

( define ( list->stream xs ) ( reset ( begin ( for-each stream-yield xs ) stream-null )))

En el ejemplo más complejo que se muestra a continuación, la continuación se puede envolver de forma segura en el cuerpo de una función lambda y utilizarse como tal:

( define ( for-each->stream-maker for-each ) ( lambda ( collection ) ( reset ( begin ( for-each ( lambda ( element ) ( shift k ( stream-cons element ( k 'ignored )))) collection ) stream-null ))))

La parte entre resety shiftincluye funciones de control como lambday for-each; esto es imposible de reformular usando lambdas .

Las continuaciones delimitadas también son útiles en lingüística : consulte Continuaciones en lingüística para obtener más detalles.

La función curry generalizada recibe una función no currificada fy su aridad (por ejemplo, 3), y devuelve el valor de (lambda (v1) (lambda (v2) (lambda (v3) (f v1 v2 v3)))). Este ejemplo se debe a Olivier Danvy y fue desarrollado a mediados de la década de 1980. ^{[ 13 ]}

Aquí se muestra una función de prueba unitaria para ilustrar lo que se espera que haga la función de 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 al transformar la función variádica +en una función currificada n-aria y aplicar el resultado a n argumentos se obtiene el mismo resultado que al aplicarlo +a estos n argumentos, para n = 0, 1, 2, 3 y 4.

La siguiente función recursiva se basa en un acumulador y, finalmente, invierte dicho 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 beta-reduce a evaluar

(( visita 1 ( cons 1 ' ())) 10 )

lo que se reduce a evaluar

(( lambda ( v ) ( visita 0 ( cons v ( cons 1 ' ())))) 10 )

que beta-reduce a evaluar

( visita 0 ( cons 10 ( cons 1 ' ())))

lo que se reduce a evaluar

( aplicar + ( invertir ( cons 10 ( cons 1 ' ()))))

lo que se reduce a evaluar

( aplicar + ( cons 1 ( cons 10 ' ())))

lo cual es equivalente a

( + 1 10 )

que se reduce delta al resultado, 11.

La siguiente función recursiva se basa en la continuación y no implica inversión de listas. 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 evaluar

((( 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 )) ( cons v vs ))))) 1 ) 10 )

que beta-reduce a evaluar

(( visita 1 ( lambda ( vs ) (( lambda ( vs ) ( aplicar + vs )) ( cons 1 vs )))) 10 )

lo que se reduce a evaluar

(( lambda ( v ) ( visita 0 ( lambda ( vs ) (( lambda ( vs ) (( lambda ( vs ) ( aplicar + vs )) ( cons 1 vs ))) ( cons v vs ))))) 10 )

que beta-reduce a evaluar

( visita 0 ( lambda ( vs ) (( lambda ( vs ) (( lambda ( vs ) ( aplicar + vs )) ( cons 1 vs ))) ( cons 10 vs ))))

lo que se reduce a evaluar

(( lambda ( vs ) (( lambda ( vs ) (( lambda ( vs ) ( aplicar + vs )) ( cons 1 vs ))) ( cons 10 vs ))) ' ())

que beta-reduce a evaluar

(( lambda ( vs ) (( lambda ( vs ) ( aplicar + vs )) ( cons 1 vs ))) ( cons 10 ' ()))

que beta-reduce a evaluar

(( lambda ( vs ) ( aplicar + vs )) ( cons 1 ( cons 10 ' ())))

que beta-reduce a evaluar

( aplicar + ( cons 1 ( cons 10 ' ())))

lo cual es equivalente a

( + 1 10 )

que se reduce delta al resultado, 11.

La siguiente función recursiva, curry_d, es la contraparte de estilo directo de curry_cy presenta el (shift k k)modismo, 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 meollo de la cuestión es la equivalencia observacional entre (reset (... (shift k k) ...)) y (lambda (x) (reset (... x ...))) donde xes fresco y las elipsis representan un contexto puro, es decir, uno sin efectos de control.

Así que evaluar

((( curry_d + 2 ) 1 ) 10 )

se reduce a evaluar

((( restablecer ( aplicar + ( visitar 2 ))) 1 ) 10 )

lo que se reduce a evaluar

((( restablecer ( aplicar + ( cons ( desplazamiento k k ) ( visita 1 )))) 1 ) 10 )

lo cual es observacionalmente equivalente a

((( lambda ( x ) ( reset ( apply + ( cons x ( visit 1 ))))) 1 ) 10 )

que beta-reduce a evaluar

(( restablecer ( aplicar + ( cons 1 ( visita 1 )))) 10 )

lo que se reduce a evaluar

(( restablecer ( aplicar + ( cons 1 ( cons ( shift k k ) ( visitar 0 ))))) 10 )

lo cual es observacionalmente equivalente a

(( lambda ( x ) ( reset ( apply + ( cons 1 ( cons x ( visit 0 )))))) 10 )

que beta-reduce a evaluar

( restablecer ( aplicar + ( cons 1 ( cons 10 ( visitar 0 )))))

lo que se reduce a evaluar

( restablecer ( aplicar + ( cons 1 ( cons 10 ' ()))))

lo cual es equivalente a

( restablecer ( + 1 10 ))

que delta-reduce a evaluar

( reiniciar 11 )

lo que produce el 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 control y 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 )))))))

• Tutorial sobre continuaciones componibles en SchemeWiki
• Continuaciones delimitadas en sistemas operativos, por Oleg Kiselyov y Chung-chieh Shan
• Continuaciones delimitadas nativas en OCaml (código de bytes y código nativo)
• Shift/reset для самых маленьких (en ruso)
• Algunos artículos interesantes sobre continuaciones delimitadas y macros de primera clase.