La página "Esquema avanzado: algunos bits traviesos" dice:
Las continuaciones son una construcción poderosa de flujo de control de la cual se puede derivar casi cualquier otra estructura de flujo de control.
¿Pensé que Scheme call/cc, al estar relacionado (*) con el operador J de Peter Landin, podría usarse para implementar cualquier estructura de flujo de control conocida?
Con la "estructura de flujo de control", estoy pensando específicamente en la descripción que hace Wikipedia de ellos, por ejemplo, excepciones, corutinas, hilos verdes, etc.
Específicamente, ¿hay ejemplos de estructuras de flujo de control que no se puedan implementar usando call/cc?
(*) No he podido desenterrar ningún documento que establezca que call/ccsea tan poderoso como el operador J. Un artículo de Felleisen (que no he leído y ciertamente tengo problemas para entenderlo completamente) investiga esto, y parece concluir que a pesar de que están en diferentes clases de complejidad, son formalmente equivalentes.
(También tenga en cuenta que he actualizado la pregunta basada en los comentarios a continuación)
Actualizar
Basado en la excelente respuesta de @Neel a continuación, he mirado sitios que comentan sobre continuaciones delimitadas y no delimitadas , y de hecho parece que call/cc, si bien no está delimitado, no es suficiente. Mientras tanto, parece que se pueden usar continuaciones delimitadas de primera clase (como shift/reset) para expresar cualquier estructura de flujo de control.
call/ccno pueden expresar excepciones en ausencia de estado . (Como Thielecke va a señalar, las excepciones pueden ser implementadas por los que pasa alrededor de dos continuaciones, una para el programa y el otro para el manejador de excepciones, sino que requiere algo más que simplementecall/cc.)amboperador, etc.Respuestas:
En esta respuesta, tomaré "expresable" como "macroexpresable" en el sentido de Felleisen 1991, Sobre el poder expresivo de los lenguajes de programación . (Intuitivamente, una característica del lenguaje es macroexpresable si puede definirla como una transformación de fuente local, sin usar una transformación de programa completo).
Con esta definición, la respuesta es no : el control delimitado no es macroexpresable en el cálculo lambda + call / cc. Para expresar operadores de control delimitados usando call / cc. Para implementar los delimitadores de control (la parte de reinicio de shift / reset), necesita algún estado para simular las marcas de continuación, esencialmente para codificar una pila para simular las vidas dinámicas de las marcas de continuación.
Sin embargo, el control delimitado es un efecto universal, en el siguiente sentido. En su tesis doctoral , Andrzej Filinski demostró que cualquier efecto secundario expresable es codificable usando continuaciones delimitadas o call / cc y una sola celda de estado. Aproximadamente, un "efecto secundario expresable" es cualquier efecto cuyo tipo monádico se puede definir en términos de los tipos del lenguaje de programación.
Sorprendentemente, esta idea parece bastante interesante en la práctica. Durante la última década, Gordon Plotkin y John Power han defendido la idea de tomar una semántica algebraica de teorías de efectos : la idea es que especifique las operaciones de efectos secundarios que le interesan y las ecuaciones que espera que satisfagan, y luego genéricamente puedes obtener una semántica tomando la mónada libre sobre esta teoría.
Matija Pretnar y Andrej Bauer adoptaron este enfoque matemático, y luego lo implementaron en su lenguaje Eff para inventar una nueva construcción de lenguaje denominada "manejadores de efectos": puede escribir código que use un conjunto de características imperativas, y luego dar una semántica a las características imperativas escribiendo un conjunto de controladores que dicen cómo implementar cada operación efectiva.
fuente