functional-programming - what - pure functional programming languages

¡Simplemente no obtengo continuaciones!

Question

¿Qué son y para qué sirven?

No tengo un título de CS y mi experiencia es VB6 -> ASP -> ASP.NET/C#. ¿Alguien puede explicarlo de una manera clara y concisa?

Answer 1

Básicamente, una continuación es la capacidad de una función para detener la ejecución y luego retomarla donde la dejó en un momento posterior. En C #, puede hacer esto usando la palabra clave yield. Puedo entrar en más detalles si lo desea, pero quería una explicación concisa. ;-)

Answer 2

Un aviso, este ejemplo no es conciso ni excepcionalmente claro. Esta es una demostración de una poderosa aplicación de continuaciones. Como programador VB / ASP / C #, es posible que no esté familiarizado con el concepto de acumulación de sistemas o estado de ahorro, por lo que el objetivo de esta respuesta es una demostración y no una explicación.

Las continuas son extremadamente versátiles y son una forma de guardar el estado de ejecución y reanudarlo más tarde. Aquí hay un pequeño ejemplo de un entorno cooperativo multihilo que usa continuaciones en Scheme:

(Suponga que las operaciones en cola y dequeue funcionan como se esperaba en una cola global no definida aquí)

(define (fork)
  (display "forking/n")
  (call-with-current-continuation
   (lambda (cc)
     (enqueue (lambda ()
                (cc #f)))
     (cc #t))))

(define (context-switch)
  (display "context switching/n")
  (call-with-current-continuation
   (lambda (cc)
     (enqueue
      (lambda ()
        (cc ''nothing)))
     ((dequeue)))))

(define (end-process)
  (display "ending process/n")
  (let ((proc (dequeue)))
    (if (eq? proc ''queue-empty)
        (display "all processes terminated/n")
        (proc))))

Esto proporciona tres verbos que una función puede usar: fork, context-switch y end-process. La operación de horquilla bifurca el hilo y devuelve #t en una instancia y #f en otra. La operación de cambio de contexto cambia entre subprocesos y el proceso final finaliza un subproceso.

Aquí hay un ejemplo de su uso:

(define (test-cs)
  (display "entering test/n")
  (cond
    ((fork) (cond
              ((fork) (display "process 1/n")
                      (context-switch)
                      (display "process 1 again/n"))
              (else (display "process 2/n")
                    (end-process)
                    (display "you shouldn''t see this (2)"))))
    (else (cond ((fork) (display "process 3/n")
                        (display "process 3 again/n")
                        (context-switch))
                (else (display "process 4/n")))))
  (context-switch)
  (display "ending process/n")
  (end-process)
  (display "process ended (should only see this once)/n"))

La salida debe ser

entering test
forking
forking
process 1
context switching
forking
process 3
process 3 again
context switching
process 2
ending process
process 1 again
context switching
process 4
context switching
context switching
ending process
ending process
ending process
ending process
ending process
ending process
all processes terminated
process ended (should only see this once)

Aquellos que han estudiado bifurcar y enhebrar en una clase a menudo reciben ejemplos similares a esto. El propósito de esta publicación es demostrar que con las continuaciones puede lograr resultados similares dentro de un solo hilo al guardar y restaurar su estado - su continuación - manualmente.

PD - Creo que recuerdo algo similar a esto en On Lisp, así que si quieres ver un código profesional, debes consultar el libro.

Answer 3

Probablemente los entiendas mejor de lo que crees.

Las excepciones son un ejemplo de continuación "solo hacia arriba". Permiten que el código en el fondo de la pila llame a un manejador de excepciones para indicar un problema.

Ejemplo de Python:

try:
    broken_function()
except SomeException:
    # jump to here
    pass

def broken_function():
    raise SomeException() # go back up the stack
    # stuff that won''t be evaluated

Los generadores son ejemplos de continuaciones "a la baja". Permiten que el código vuelva a entrar en un bucle, por ejemplo, para crear nuevos valores.

Ejemplo de Python:

def sequence_generator(i=1):
    while True:
        yield i  # "return" this value, and come back here for the next
        i = i + 1

g = sequence_generator()
while True:
    print g.next()

En ambos casos, estos tuvieron que ser agregados al lenguaje específicamente, mientras que en un lenguaje con continuaciones, el programador puede crear estas cosas donde no están disponibles.

Answer 4

Todavía me estoy "acostumbrando" a las continuaciones, pero una forma de pensar sobre ellas que encuentro útiles es como abstracciones del concepto de contador de programas (PC). Una PC "apunta" a la siguiente instrucción para ejecutar en la memoria, pero por supuesto que la instrucción (y casi todas las instrucciones) apunta, implícita o explícitamente, a la instrucción que sigue, así como a las instrucciones que el servicio debe interrumpir. (Incluso una instrucción de NOOP realiza implícitamente un JUMP a la siguiente instrucción en la memoria. Pero si ocurre una interrupción, eso generalmente implicará un JUMP a alguna otra instrucción en la memoria).

Cada punto potencialmente "vivo" en un programa en memoria al cual el control podría saltar en cualquier punto dado es, en cierto sentido, una continuación activa. Otros puntos que se pueden alcanzar son las continuaciones potencialmente activas, pero, más al punto, son continuaciones que son potencialmente "calculadas" (dinámicamente, quizás) como resultado de alcanzar una o más de las continuaciones actualmente activas.

Esto parece un poco fuera de lugar en las introducciones tradicionales a las continuas, en las cuales todos los hilos de ejecución pendientes se representan explícitamente como continuaciones en código estático; pero toma en cuenta el hecho de que, en computadoras de propósito general, la PC apunta a una secuencia de instrucciones que potencialmente podría cambiar el contenido de la memoria que representa una parte de esa secuencia de instrucciones, creando así una nueva (o modificada, si se quiere) ) Continuación sobre la marcha, una que no existe realmente a partir de las activaciones de continuaciones que preceden a esa creación / modificación.

Así que la continuación se puede ver como un modelo de alto nivel de la PC, por lo que conceptualmente subsume la llamada / retorno de procedimiento ordinario (así como el antiguo hierro hizo el procedimiento llamada / retorno mediante JUMP de bajo nivel, también conocido como GOTO, instrucciones más grabación de la PC en llamada y restauración a su regreso), así como excepciones, hilos, corrutinas, etc.

Así como la PC señala que los cálculos tienen lugar en "el futuro", una continuación hace lo mismo, pero a un nivel más alto y más abstracto. La PC se refiere implícitamente a la memoria más todas las ubicaciones de memoria y registros "vinculados" a cualquier valor, mientras que una continuación representa el futuro a través de las abstracciones apropiadas para el lenguaje.

Por supuesto, aunque normalmente puede haber solo una PC por computadora (procesador central), de hecho hay muchas entidades PC-ish "activas", como se mencionó anteriormente. El vector de interrupción contiene un montón, la pila un montón más, ciertos registros pueden contener algunos, etc. Se "activan" cuando sus valores se cargan en la PC de hardware, pero las continuaciones son abstracciones del concepto, no PC o su equivalente preciso (no hay un concepto inherente de una continuación "maestra", aunque a menudo pensamos y codificamos en esos términos para mantener las cosas bastante simples).

En esencia, una continuación es una representación de "qué hacer a continuación cuando se invoca", y, como tal, puede ser (y, en algunos idiomas y en los programas de estilo de paso de continuación, a menudo lo es) un objeto de primera clase que es instanciado, pasado y descartado como cualquier otro tipo de datos, y muy parecido a cómo una computadora clásica trata las ubicaciones de memoria frente a la PC, como casi intercambiable con enteros comunes.

Answer 5

En C #, tiene acceso a dos continuaciones. Uno, al que se accede a través del return , permite que un método continúe desde donde fue llamado. El otro, al que se accede mediante throw , permite que un método continúe en la catch coincidente más cercana.

Algunos idiomas le permiten tratar estos enunciados como valores de primera clase, por lo que puede asignarlos y pasarlos en variables. Lo que esto significa es que puede esconder el valor de return o de throw y llamarlos más tarde cuando esté realmente listo para regresar o tirar.

Continuation callback = return;
callMeLater(callback);

Esto puede ser útil en muchas situaciones. Un ejemplo es como el anterior, donde desea detener el trabajo que está realizando y reanudarlo más tarde cuando sucede algo (como obtener una solicitud web, o algo así).

Los estoy usando en un par de proyectos en los que estoy trabajando. En una, los estoy usando para poder suspender el programa mientras espero IO a través de la red, luego reanudo el programa más tarde. En el otro, estoy escribiendo un lenguaje de programación en el que le doy acceso al usuario a continuaciones como valores para que puedan escribir return y throw para ellos mismos o cualquier otro flujo de control, como while loops, sin necesidad de hacerlo por ellos.

Answer 6

Imagínese si cada línea en su programa fuera una función separada. Cada uno acepta, como parámetro, la siguiente línea / función para ejecutar.

Usando este modelo, puede "pausar" la ejecución en cualquier línea y continuarla más tarde. También puede hacer cosas ingeniosas, como saltar temporalmente la pila de ejecución para recuperar un valor, o guardar el estado de ejecución actual en una base de datos para recuperarlo más tarde.

Answer 7

Piensa en los hilos. Se puede ejecutar un hilo y puede obtener el resultado de su cálculo. Una continuación es un hilo que puede copiar, por lo que puede ejecutar el mismo cálculo dos veces.

Answer 8

Una forma de pensar en una continuación es como una pila de procesadores. Cuando "call-with-current-continuation c" llama a su función "c", y el parámetro pasado a "c" es su pila actual con todas sus variables automáticas (representada como otra función más, llámelo "k "). Mientras tanto, el procesador comienza a crear una nueva pila. Cuando llama a "k", ejecuta una instrucción "return from subroutine" (RTS) en la pila original, saltando de vuelta al contexto de la "call-with-current-continuation" original ("call-cc" a partir de ahora encendido) y permitiendo que su programa continúe como antes. Si pasó un parámetro a "k", se convierte en el valor de retorno de "call-cc".

Desde el punto de vista de su pila original, el "call-cc" se parece a una llamada de función normal. Desde el punto de vista de "c", tu pila original parece una función que nunca regresa.

Hay una vieja broma sobre un matemático que capturó un león en una jaula al trepar a la jaula, encerrarla y declararse a sí mismo fuera de la jaula mientras todo lo demás (incluido el león) estaba dentro de ella. Las continuas son un poco como la jaula, y "c" es un poco como el matemático. Su programa principal cree que "c" está dentro de él, mientras que "c" cree que su programa principal está dentro de "k".

Puede crear estructuras de flujo de control arbitrarias usando continuaciones. Por ejemplo, puede crear una biblioteca de subprocesos. "rendimiento" utiliza "call-cc" para poner la continuación actual en una cola y luego salta a la del encabezado de la cola. Un semáforo también tiene su propia cola de continuaciones suspendidas, y un hilo se reprograma sacandolo de la cola del semáforo y poniéndolo en la cola principal.

Answer 9

Las continuas renovaciones de interés con la programación web se deben a que reflejan bien el carácter de pausa / reanudación de las solicitudes web. Un servidor puede construir una continaution que represente una sesión de usuarios y reanudar si y cuando el usuario continúa la sesión.