¿Qué son las continuaciones de Scala y por qué usarlas?

Acabo de terminar de programar en Scala y he estado investigando los cambios entre Scala 2.7 y 2.8. El que parece ser el más importante es el complemento de continuaciones, pero no entiendo para qué es útil ni cómo funciona. He visto que es bueno para la E / S asíncrona, pero no he podido averiguar por qué. Algunos de los recursos más populares sobre el tema son estos:

• Continuaciones delimitadas y Scala
• Ir a Scala
• A Taste of 2.8: Continuaciones
• Explicación de las continuaciones delimitadas (en Scala)

Y esta pregunta en Stack Overflow:

• ¿Cuáles son las mayores diferencias entre Scala 2.8 y Scala 2.7?

Desafortunadamente, ninguna de estas referencias intenta definir para qué son las continuaciones o qué se supone que deben hacer las funciones de cambio / reinicio, y no he encontrado ninguna referencia que lo haga. No he podido adivinar cómo funciona ninguno de los ejemplos en los artículos vinculados (o qué hacen), por lo que una forma de ayudarme podría ser ir línea por línea a través de una de esas muestras. Incluso este simple del tercer artículo:

reset {
    ...
    shift { k: (Int=>Int) =>  // The continuation k will be the '_ + 1' below.
        k(7)
    } + 1
}
// Result: 8

¿Por qué el resultado es 8? Eso probablemente me ayudaría a empezar.

Mi blog explica qué resety shifthacer, por lo que es posible que desee volver a leerlo.

Otra buena fuente, que también señalo en mi blog, es la entrada de Wikipedia sobre estilo de paso de continuación . Ese es, con mucho, el más claro sobre el tema, aunque no usa la sintaxis de Scala, y la continuación se pasa explícitamente.

El artículo sobre las continuaciones delimitadas, al que enlazo en mi blog pero parece haberse roto, ofrece muchos ejemplos de uso.

Pero creo que el mejor ejemplo del concepto de continuaciones delimitadas es Scala Swarm. En ella, la biblioteca detiene la ejecución de su código en un punto, y el cálculo restante se convierte en la continuación. Luego, la biblioteca hace algo, en este caso, transfiere el cálculo a otro host y devuelve el resultado (el valor de la variable a la que se accedió) al cálculo que se detuvo.

Ahora, ni siquiera comprendes el ejemplo simple en la página de Scala, así que lee mi blog. En él solo me preocupa explicar estos conceptos básicos, de por qué es el resultado 8.

Encontré que las explicaciones existentes son menos efectivas para explicar el concepto de lo que esperaba. Espero que este sea claro (y correcto). No he usado continuaciones todavía.

Cuando cfse llama a una función de continuación :

1. La ejecución salta el resto del shiftbloque y comienza de nuevo al final.
   • el parámetro pasado cfes lo que el shiftbloque "evalúa" a medida que continúa la ejecución. esto puede ser diferente para cada llamada acf
2. La ejecución continúa hasta el final del resetbloque (o hasta una llamada a resetsi no hay ningún bloque)
   • el resultado del resetbloque (o el parámetro to reset() si no hay bloque) es lo que cfdevuelve
3. La ejecución continúa después cfhasta el final del shiftbloque.
4. La ejecución salta hasta el final del resetbloque (¿o una llamada para restablecer?)

Entonces, en este ejemplo, siga las letras de la A a la Z

reset {
  // A
  shift { cf: (Int=>Int) =>
    // B
    val eleven = cf(10)
    // E
    println(eleven)
    val oneHundredOne = cf(100)
    // H
    println(oneHundredOne)
    oneHundredOne
  }
  // C execution continues here with the 10 as the context
  // F execution continues here with 100
  + 1
  // D 10.+(1) has been executed - 11 is returned from cf which gets assigned to eleven
  // G 100.+(1) has been executed and 101 is returned and assigned to oneHundredOne
}
// I

Esto imprime:

11
101

Dado el ejemplo canónico del trabajo de investigación para las continuaciones delimitadas de Scala, modificado ligeramente para que la entrada de la función shiftreciba el nombre fy, por lo tanto, ya no sea anónima.

def f(k: Int => Int): Int = k(k(k(7)))
reset(
  shift(f) + 1   // replace from here down with `f(k)` and move to `k`
) * 2

El complemento Scala transforma este ejemplo de manera que el cálculo (dentro del argumento de entrada de reset) que comienza desde cada uno shifthasta la invocación de resetse reemplaza con la función (por ejemplo f) entrada a shift.

El cálculo reemplazado se desplaza (es decir, se mueve) a una función k. La función fingresa la función k, donde k contiene el cálculo reemplazado, las kentradas x: Inty el cálculo en kreemplaza shift(f)por x.

f(k) * 2
def k(x: Int): Int = x + 1

Que tiene el mismo efecto que:

k(k(k(7))) * 2
def k(x: Int): Int = x + 1

Tenga en cuenta que el tipo Intde parámetro de entrada x(es decir, la firma de tipo de k) fue dado por la firma de tipo del parámetro de entrada de f.

Otro ejemplo prestado con la abstracción conceptualmente equivalente, reades decir, es la entrada de la función para shift:

def read(callback: Byte => Unit): Unit = myCallback = callback
reset {
  val byte = "byte"

  val byte1 = shift(read)   // replace from here with `read(callback)` and move to `callback`
  println(byte + "1 = " + byte1)
  val byte2 = shift(read)   // replace from here with `read(callback)` and move to `callback`
  println(byte + "2 = " + byte2)
}

Creo que esto se traduciría al equivalente lógico de:

val byte = "byte"

read(callback)
def callback(x: Byte): Unit {
  val byte1 = x
  println(byte + "1 = " + byte1)
  read(callback2)
  def callback2(x: Byte): Unit {
    val byte2 = x
    println(byte + "2 = " + byte1)
  }
}

Espero que esto aclare la abstracción común coherente que quedó un tanto confusa por la presentación previa de estos dos ejemplos. Por ejemplo, el primer ejemplo canónico se presentó en el trabajo de investigación como una función anónima, en lugar de mi nombre f, por lo que no está claro para algunos lectores que era análoga a la forma abstracta readen el prestado segundo ejemplo.

Así, las continuaciones delimitadas crean la ilusión de una inversión de control de "me llamas desde fuera reset" a "te llamo desde dentro reset".

Tenga en cuenta que el tipo de retorno de fes, pero kno es, necesario que sea el mismo que el tipo de retorno de reset, es decir, ftiene la libertad de declarar cualquier tipo de retorno ksiempre que fdevuelva el mismo tipo que reset. Lo mismo ocurre con ready capture(ver también más ENVabajo).

Las continuaciones delimitadas no invierten implícitamente el control del estado, por ejemplo, ready callbackno son funciones puras. Por lo tanto, el llamador no puede crear expresiones referencialmente transparentes y, por lo tanto, no tiene control declarativo (también conocido como transparente) sobre la semántica imperativa deseada .

Podemos lograr explícitamente funciones puras con continuaciones delimitadas.

def aread(env: ENV): Tuple2[Byte,ENV] {
  def read(callback: Tuple2[Byte,ENV] => ENV): ENV = env.myCallback(callback)
  shift(read)
}
def pure(val env: ENV): ENV {
  reset {
    val (byte1, env) = aread(env)
    val env = env.println("byte1 = " + byte1)
    val (byte2, env) = aread(env)
    val env = env.println("byte2 = " + byte2)
  }
}

Creo que esto se traduciría al equivalente lógico de:

def read(callback: Tuple2[Byte,ENV] => ENV, env: ENV): ENV =
  env.myCallback(callback)
def pure(val env: ENV): ENV {
  read(callback,env)
  def callback(x: Tuple2[Byte,ENV]): ENV {
    val (byte1, env) = x
    val env = env.println("byte1 = " + byte1)
    read(callback2,env)
    def callback2(x: Tuple2[Byte,ENV]): ENV {
      val (byte2, env) = x
      val env = env.println("byte2 = " + byte2)
    }
  }
}

Esto se está volviendo ruidoso, debido al entorno explícito.

Tenga en cuenta tangencialmente, Scala no tiene la inferencia de tipo global de Haskell y, por lo que yo sé, no podría soportar el levantamiento implícito a una mónada de estado unit(como una posible estrategia para ocultar el entorno explícito), porque la inferencia de tipo global de Haskell (Hindley-Milner) depende de no admitir la herencia virtual múltiple de diamantes .

Continuación captura el estado de un cálculo, para ser invocado posteriormente.

Piense en el cálculo entre dejar la expresión de cambio y dejar la expresión de reinicio como una función. Dentro de la expresión de desplazamiento esta función se llama k, es la continuación. Puede pasarlo, invocarlo más tarde, incluso más de una vez.

Creo que el valor devuelto por la expresión de restablecimiento es el valor de la expresión dentro de la expresión de cambio después de =>, pero no estoy muy seguro de esto.

Entonces, con continuaciones, puede envolver una pieza de código bastante arbitraria y no local en una función. Esto se puede utilizar para implementar un flujo de control no estándar, como corrutina o retroceso.

Entonces, las continuaciones deben usarse a nivel de sistema. Rociarlos a través del código de su aplicación sería una receta segura para las pesadillas, mucho peor de lo que podría ser el peor código espagueti que usa goto.

Descargo de responsabilidad: no tengo una comprensión profunda de las continuaciones en Scala, solo lo infiero al mirar los ejemplos y conocer las continuaciones de Scheme.

Desde mi punto de vista, la mejor explicación se dio aquí: http://jim-mcbeath.blogspot.ru/2010/08/delimited-continuations.html

Uno de los ejemplos:

Para ver el flujo de control con un poco más de claridad, puede ejecutar este fragmento de código:

reset {
    println("A")
    shift { k1: (Unit=>Unit) =>
        println("B")
        k1()
        println("C")
    }
    println("D")
    shift { k2: (Unit=>Unit) =>
        println("E")
        k2()
        println("F")
    }
    println("G")
}

Aquí está la salida que produce el código anterior:

A
B
D
E
G
F
C

Otro artículo (más reciente, mayo de 2016) sobre las continuaciones de Scala es:
" Viaje en el tiempo en Scala: CPS en Scala (continuación de scala) " por Shivansh Srivastava ( shiv4nsh) .
También se refiere a Jim McBeath 's artículo mencionado en Dmitry Bespalov ' s respuesta .

Pero antes de eso, describe Continuaciones así:

Una continuación es una representación abstracta del estado de control de un programa de computadora .
Entonces, lo que realmente significa es que es una estructura de datos que representa el proceso computacional en un punto dado en la ejecución del proceso; el lenguaje de programación puede acceder a la estructura de datos creada, en lugar de estar oculta en el entorno de ejecución.

Para explicarlo más podemos tener uno de los ejemplos más clásicos,

Digamos que estás en la cocina frente al refrigerador, pensando en un sándwich. Toma una continuación allí mismo y se la mete en el bolsillo.
Luego sacas un poco de pavo y pan del refrigerador y te preparas un sándwich, que ahora está sobre la encimera.
Invocas la continuación en tu bolsillo y te encuentras de nuevo frente al refrigerador, pensando en un sándwich. Pero, afortunadamente, hay un sándwich en el mostrador y todos los materiales que se usaron para hacerlo se han ido. Así que te lo comes. :-)

En esta descripción, sandwiches parte de los datos del programa (por ejemplo, un objeto en el montón), y en lugar de llamar a una make sandwichrutina " " y luego regresar, la persona llamó a una make sandwich with current continuationrutina " ", que crea el sándwich y luego continúa donde la ejecución Parado.

Dicho esto, como se anunció en abril de 2014 para Scala 2.11.0-RC1

Buscamos mantenedores para que se hagan cargo de los siguientes módulos: scala-swing , scala-continuations .
2.12 no los incluirá si no se encuentra un nuevo responsable .
Es probable que sigamos manteniendo los otros módulos (scala-xml, scala-parser-combinators), pero la ayuda sigue siendo muy apreciada.

Continuaciones de Scala a través de ejemplos significativos

Definamos from0to10que expresa la idea de iteración de 0 a 10:

def from0to10() = shift { (cont: Int => Unit) =>
   for ( i <- 0 to 10 ) {
     cont(i)
   }
}

Ahora,

reset {
  val x = from0to10()
  print(s"$x ")
}
println()

huellas dactilares:

0 1 2 3 4 5 6 7 8 9 10 

De hecho, no necesitamos x:

reset {
  print(s"${from0to10()} ")
}
println()

imprime el mismo resultado.

Y

reset {
  print(s"(${from0to10()},${from0to10()}) ")
}
println()

imprime todos los pares:

(0,0) (0,1) (0,2) (0,3) (0,4) (0,5) (0,6) (0,7) (0,8) (0,9) (0,10) (1,0) (1,1) (1,2) (1,3) (1,4) (1,5) (1,6) (1,7) (1,8) (1,9) (1,10) (2,0) (2,1) (2,2) (2,3) (2,4) (2,5) (2,6) (2,7) (2,8) (2,9) (2,10) (3,0) (3,1) (3,2) (3,3) (3,4) (3,5) (3,6) (3,7) (3,8) (3,9) (3,10) (4,0) (4,1) (4,2) (4,3) (4,4) (4,5) (4,6) (4,7) (4,8) (4,9) (4,10) (5,0) (5,1) (5,2) (5,3) (5,4) (5,5) (5,6) (5,7) (5,8) (5,9) (5,10) (6,0) (6,1) (6,2) (6,3) (6,4) (6,5) (6,6) (6,7) (6,8) (6,9) (6,10) (7,0) (7,1) (7,2) (7,3) (7,4) (7,5) (7,6) (7,7) (7,8) (7,9) (7,10) (8,0) (8,1) (8,2) (8,3) (8,4) (8,5) (8,6) (8,7) (8,8) (8,9) (8,10) (9,0) (9,1) (9,2) (9,3) (9,4) (9,5) (9,6) (9,7) (9,8) (9,9) (9,10) (10,0) (10,1) (10,2) (10,3) (10,4) (10,5) (10,6) (10,7) (10,8) (10,9) (10,10) 

Ahora, ¿cómo funciona eso?

No es el código de llamada , from0to10y el código de llamada . En este caso, es el bloque que sigue reset. Uno de los parámetros pasados ​​al código llamado es una dirección de retorno que muestra qué parte del código de llamada aún no se ha ejecutado (**). Esa parte del código de llamada es la continuación . El código llamado puede hacer con ese parámetro lo que decida: pasarle el control, ignorarlo o llamarlo varias veces. Aquí from0to10llama a esa continuación para cada número entero en el rango 0..10.

def from0to10() = shift { (cont: Int => Unit) =>
   for ( i <- 0 to 10 ) {
     cont(i) // call the continuation
   }
}

Pero, ¿dónde termina la continuación? Esto es importante porque la última returnde las declaraciones de continuación de control al código de llamada, from0to10. En Scala, termina donde termina el resetbloque (*).

Ahora, vemos que la continuación se declara como cont: Int => Unit. ¿Por qué? Invocamos from0to10como val x = from0to10(), y Intes el tipo de valor al que va x. Unitsignifica que el bloque posterior no resetdebe devolver ningún valor (de lo contrario, habrá un error de tipo). En general, hay 4 firmas de tipo: entrada de función, entrada de continuación, resultado de continuación, resultado de función. Los cuatro deben coincidir con el contexto de invocación.

Arriba, imprimimos pares de valores. Imprimamos la tabla de multiplicar. Pero, ¿cómo salimos \ndespués de cada fila?

La función backnos permite especificar qué se debe hacer cuando el control regrese, desde la continuación hasta el código que lo llamó.

def back(action: => Unit) = shift { (cont: Unit => Unit) =>
  cont()
  action
}

backprimero llama a su continuación y luego realiza la acción .

reset {
  val i = from0to10()
  back { println() }
  val j = from0to10
  print(f"${i*j}%4d ") // printf-like formatted i*j
}

Imprime:

   0    0    0    0    0    0    0    0    0    0    0 
   0    1    2    3    4    5    6    7    8    9   10 
   0    2    4    6    8   10   12   14   16   18   20 
   0    3    6    9   12   15   18   21   24   27   30 
   0    4    8   12   16   20   24   28   32   36   40 
   0    5   10   15   20   25   30   35   40   45   50 
   0    6   12   18   24   30   36   42   48   54   60 
   0    7   14   21   28   35   42   49   56   63   70 
   0    8   16   24   32   40   48   56   64   72   80 
   0    9   18   27   36   45   54   63   72   81   90 
   0   10   20   30   40   50   60   70   80   90  100 

Bueno, ahora es el momento de algunos acertijos. Hay dos invocaciones de from0to10. ¿Cuál es la continuación del primero from0to10? Sigue a la invocación de from0to10en el código binario , pero en el código fuente también incluye la declaración de asignación val i =. Termina donde termina el resetbloque, pero el final del resetbloque no devuelve el control al primero from0to10. El final del resetbloque devuelve el control al segundo from0to10, que a su vez finalmente devuelve el control a back, y es el backque devuelve el control a la primera invocación de from0to10. Cuando from0to10sale la primera (¡sí! ¡1ra!) , Se sale de todo el resetbloque.

Este método de devolver el control se llama retroceso , es una técnica muy antigua, conocida al menos desde los tiempos de Prolog y los derivados Lisp orientados a AI.

Los nombres resety shiftson nombres inapropiados. Es mejor que estos nombres se hayan dejado para las operaciones bit a bit. resetdefine los límites de continuación y shifttoma una continuación de la pila de llamadas.

Nota (s)

(*) En Scala, la continuación termina donde termina el resetbloque. Otro enfoque posible sería dejar que termine donde termina la función.

(**) Uno de los parámetros del código llamado es una dirección de retorno que muestra qué parte del código de llamada aún no se ha ejecutado. Bueno, en Scala, se usa una secuencia de direcciones de retorno para eso. ¿Cuántos? Todas las direcciones de retorno colocadas en la pila de llamadas desde que ingresaron al resetbloque.

UPD Part 2 Descartando Continuaciones: Filtrado

def onEven(x:Int) = shift { (cont: Unit => Unit) =>
  if ((x&1)==0) {
    cont() // call continuation only for even numbers
  }
}
reset {
  back { println() }
  val x = from0to10()
  onEven(x)
  print(s"$x ")
}

Esto imprime:

0 2 4 6 8 10 

Consideremos dos operaciones importantes: descartar la continuación ( fail()) y pasarle el control ( succ()):

// fail: just discard the continuation, force control to return back
def fail() = shift { (cont: Unit => Unit) => }
// succ: does nothing (well, passes control to the continuation), but has a funny signature
def succ():Unit @cpsParam[Unit,Unit] = { }
// def succ() = shift { (cont: Unit => Unit) => cont() }

Ambas versiones de succ()(arriba) funcionan. Resulta que shifttiene una firma divertida, y aunque succ()no hace nada, debe tener esa firma para el balance de tipo.

reset {
  back { println() }
  val x = from0to10()
  if ((x&1)==0) {
    succ()
  } else {
    fail()
  }
  print(s"$x ")
}

como se esperaba, imprime

0 2 4 6 8 10

Dentro de una función, succ()no es necesario:

def onTrue(b:Boolean) = {
  if(!b) {
    fail()
  }
}
reset {
  back { println() }
  val x = from0to10()
  onTrue ((x&1)==0)
  print(s"$x ")
}

de nuevo, imprime

0 2 4 6 8 10

Ahora, definamos a onOdd()través de onEven():

// negation: the hard way
class ControlTransferException extends Exception {}
def onOdd(x:Int) = shift { (cont: Unit => Unit) =>
  try {
    reset {
      onEven(x)
      throw new ControlTransferException() // return is not allowed here
    }
    cont()
  } catch {
    case e: ControlTransferException =>
    case t: Throwable => throw t
  }
}
reset {
  back { println() }
  val x = from0to10()
  onOdd(x)
  print(s"$x ")
}

Arriba, si xes par, se lanza una excepción y no se llama a la continuación; si xes impar, no se lanza la excepción y se llama a la continuación. Se imprime el código anterior:

1 3 5 7 9