¿Cuál es un ejemplo de una continuación no implementada como procedimiento?

15

Una discusión interesante sobre la distinción entre devoluciones de llamada y continuaciones sobre SO ha provocado esta pregunta. Por definición, una continuación es una representación abstracta de la lógica necesaria para completar un cálculo. En la mayoría de los idiomas, esto se manifiesta como un procedimiento de un argumento al cual se pasa cualquier valor que necesite un procesamiento continuo.

En un lenguaje puramente funcional (donde todas las funciones son ciudadanos puros y de primera clase), creo que una continuación podría modelarse por completo como una función. Así es, después de todo, cómo he entendido previamente las continuaciones hasta este punto. Sin embargo, el mundo está lleno de estado (suspiro ...) y, por lo tanto, la definición general no requiere que se continúe capturando el estado del programa, solo debe abarcar la intención.

Para ayudar a mi comprensión, ¿se puede proporcionar un ejemplo en un lenguaje funcional donde la continuación se exprese de una manera más abstracta que una función? Sé que Scheme le permite tomar la continuación actual de una manera de primera clase (call / cc), pero aun así, parece que el procedimiento de un argumento pasado a call / cc simplemente se le da la continuación actual en forma de otro procedimiento de argumento al que la función call / cc'd puede aplicar su resultado.

David Cowden
fuente
Quizás la intersección de las continuaciones y la desfuncionalización como: las continuaciones se pueden convertir en estructuras de datos mediante la desfuncionalización; podría ser un área interesante para mirar.
Dan D.
@DanD. ¿Tienes alguna sugerencia de literatura interesante que pueda leer? Ese tema suena útil.
David Cowden

Respuestas:

11

tl; dr; El tipo es la abstracción general sobre una continuación


Una continuación es el tipo de sus entradas y salidas.

Lo más parecido que encontrará a una continuación no basada en el procedimiento es probablemente la mónada de continuación en Haskell, ya que se expresa como un tipo, para lo cual se pueden usar muchas funciones para interactuar con el tipo para interrumpir, reanudar, retroceder, etc.

Puede encapsular ese cierre en un tipo como el Conttipo en Haskell donde obtiene la abstracción de mónada como una "abstracción de nivel superior", y hay otras formas de abstracción sobre las continuaciones que obtiene cuando mira la continuación como un tipo en lugar de simplemente un procedimiento , por ejemplo

  • Puede tomar dos continuaciones y hacer una alternativa entre ellas si el tipo sigue las leyes para ser un monoide
  • Puede abstraer sobre el tipo para cambiar los tipos de entrada o salida de la continuación si encapsula el cierre en un tipo que cumpla con las leyes de un functor
  • Puede aplicar o decorar arbitraria y parcialmente su continuación con funcionalidades como la validación de entrada o la conversión de entrada si encapsula el cierre en un tipo que cumpla con las leyes de un funtor aplicativo

Cierre vs. Procedimiento

Al final del día, básicamente tienes razón; una continuación es un "procedimiento", aunque preferiría referirme a él como un cierre. Muchas veces las continuaciones se expresan mejor como cierres de primera clase que han encerrado un entorno limitado. En un lenguaje funcional puro, podría decir que esto no es particularmente razonable porque carece de referencias; Esto es cierto, pero puede encerrar valores y una sola asignación hace que encerrar el valor frente a la referencia sea exactamente lo mismo. Esto da lugar a en Haskell:

(\x -> \y -> insideYIcanAccess x (and y))

Un lenguaje que carece de la capacidad de encerrar un entorno vinculante técnicamente puede carecer de cierres de primera clase, pero incluso entonces hay algún entorno (generalmente el global) que está disponible para el cierre.

Entonces, diría que es más preciso describir una continuación como: Un cierre que se usa de una manera particular.


Conclusión

A la pregunta de "¿Es una continuación implementable de alguna otra manera que no sea un procedimiento?" No. Si no tiene funciones de primera clase , realmente no puede tener continuaciones como tales (sí, los punteros de funciones cuentan como funciones de primera clase, por lo que, alternativamente, puede ser suficiente el acceso arbitrario a la memoria).

Ahora a la pregunta de "¿Hay alguna forma de expresar una continuación de una manera más abstracta que un procedimiento?" Expresarlo como un tipo le brinda una abstracción mucho mayor, permitiéndole tratar la continuación de manera muy general, de modo que pueda interactuar con la continuación de muchas maneras más que simplemente ejecutarla.

Jimmy Hoffa
fuente
1
Esto se generaliza a "Una continuación puede ser simplemente cualquier cosa que le permita obtener el resultado del resto del programa". Como esto normalmente exige tener un código (el resto del programa), la mayoría de los idiomas usan funciones. Teóricamente puedes construir una continuación de cualquier cosa. Durante la conversión de continuación en mis compiladores, he usado árboles parcialmente llenos.
Daniel Gratzer
1
Los árboles parcialmente rellenos de @jozefg son una representación adecuada de un cálculo como una expresión, pero al final del día, el código real que se escribe es una expresión de tipo que no puede ser identificablemente diferente de un procedimiento, tal como lo entiendo. Aparte de eso, los árboles parcialmente llenos son la representación del compilador; La representación de los desarrolladores es expectativa una norma de expresión de cálculo con la sintaxis y la semántica del lenguaje, que parecería al 99% de los desarrolladores como un "procedimiento", "función" o de otro modo. Estás pensando desde la perspectiva del desarrollador del compilador je
Jimmy Hoffa
2

Un ejemplo que te puede gustar son las corutinas. Por ejemplo, las Coroutines de Lua o los iteradores / generadores de Python o C # son similares en potencia a las continuaciones de un solo disparo (continuaciones que solo se le permite llamar una vez), pero la continuación no se convierte explícitamente en una función. En cambio, tiene formas de avanzar la rutina hasta la siguiente declaración de "rendimiento".

Por ejemplo, considere el siguiente programa de Python:

def my_iterator():
   yield 1
   yield 2
   yield 3

def main():
   it = my_iterator()
   x = it.next()
   y = it.next()
   z = it.next()
   print x + y + z

Es similar al siguiente programa Javascript con devoluciones de llamada explícitas:

function my_iterator()
  return function(cb1){
    cb1(1, function(cb2){
      cb2(2, function(cb3){
        cb3(3, function(cb4){
          throw "stop iteration";
        });
      });
    });
  });
}

function main(){
   var getNext1 = my_iterator();
   getNext1(function(x, getNext2){
      getNext2(function(y, getNext3){
         getNext3(function(z, getNext4){
            console.log(x + y + z);
         });
      });
   });
}

El ejemplo de Javascript es un poco ruidoso porque cada paso debe devolver la siguiente continuación además de devolver el valor cedido (en Python realiza un seguimiento de la continuación dentro del ite

hugomg
fuente