scala - poligono - r grafica

¿Qué son las continuación de Scala y por qué usarlas?

Question

Acabo de terminar la Programación 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 continuación, pero no entiendo para qué es útil ni cómo funciona. He visto que es bueno para E / S asincrónicas, 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: Continuations
• Continuaciones delimitadas explicadas (en Scala)

Y esta pregunta sobre Stack Overflow:

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

Desafortunadamente, ninguna de estas referencias intenta definir para qué son las continuidades 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 funcionan los ejemplos de los artículos vinculados (o lo que hacen), así que una forma de ayudarme podría ser ir línea por línea a través de uno de esos ejemplos. Incluso este sencillo del tercer artículo:

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

¿Por qué es el resultado 8? Eso probablemente me ayude a comenzar.

Answer 1

Dado el ejemplo canónico del trabajo de investigación para las continuaciones delimitadas de Scala, se modificó ligeramente, por lo que a la entrada de función para shift se le da el nombre f y por lo tanto ya no es 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 de Scala transforma este ejemplo de tal manera que el cálculo (dentro del argumento de entrada de reset ) que comienza en cada shift a la invocación de reset se reemplaza con la entrada de la función (por ejemplo, f ) para shift .

El cálculo reemplazado se desplaza (es decir, se mueve) a una función k . La función f ingresa la función k , donde k contiene el cálculo reemplazado, k entradas x: Int , y el cálculo en k reemplaza shift(f) con 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

Obsérvese que el tipo Int del parámetro de entrada x (es decir, la signatura de tipo de k ) viene dada por la firma de tipo del parámetro de entrada de f .

Otro ejemplo borrowed con la abstracción conceptualmente equivalente, es decir, read 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 fue algo ofuscada 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 quedó inmediatamente claro para algunos lectores que era abstractamente análoga a la read en el segundo ejemplo borrowed .

Por lo tanto, las continuaciones delimitadas crean la ilusión de una inversión de control desde "me llamas desde fuera del reset " hasta "te llamo dentro de reset ".

Tenga en cuenta que el tipo de retorno de f es, pero k no es, requerido para ser el mismo que el tipo de reset de retorno, es decir, f tiene la libertad de declarar cualquier tipo de retorno para k siempre y cuando f devuelva el mismo tipo de reset . Lo mismo ocurre con la read y la capture (ver también ENV continuación).

Las continuaciones delimitadas no invierten implícitamente el control de estado, por ejemplo, la read y la callback no son funciones puras. Por lo tanto, la persona que llama 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á haciendo ruidoso debido al entorno explícito.

Tangencialmente, Scala no tiene la inferencia de tipo global de Haskell y, por lo que sé, no podía soportar la elevación implícita a la unit una mónada estatal (como una posible estrategia para ocultar el entorno explícito), porque el tipo global de Haskell (Hindley-Milner) la inferencia depende de no admitir la herencia virtual múltiple del diamante .

Answer 2

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

Cuando se llama a una función de continuación cf :

1. La ejecución omite el resto del bloque de shift y comienza de nuevo al final del mismo
   • el parámetro pasado a cf es a lo que el bloque de shift "evalúa" mientras la ejecución continúa. esto puede ser diferente para cada llamada a cf
2. La ejecución continúa hasta el final del bloque de reset (o hasta una llamada para reset si no hay bloque)
   • el resultado del bloque de reset (o el parámetro para reset () si no hay bloque) es lo que devuelve cf
3. La ejecución continúa después de cf hasta el final del bloque de shift
4. La ejecución se salta hasta el final del bloque de reset (¿o una llamada para restablecer?)

Entonces, en este ejemplo, sigue 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

Answer 3

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 un poco más claro, 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

Answer 4

La continuación captura el estado de un cálculo, que se invocará más tarde.

Piense en la computación entre dejar la expresión de cambio y dejar la expresión de reinicio como una función. Dentro de la expresión de cambio 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 reinicio es el valor de la expresión dentro de la expresión de cambio después de =>, pero sobre esto no estoy muy seguro.

Por lo tanto, con las continuaciones puede resumir un fragmento de código bastante arbitrario y no local en una función. Esto se puede usar para implementar un flujo de control no estándar, como la creación de corintines o el rastreo.

Por lo tanto, las continuaciones deben usarse en un nivel de sistema. Rociarlos a través del código de tu aplicación sería una receta segura para pesadillas, mucho peor de lo que podría ser el peor código de spaghetti con goto.

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

Answer 5

Mi blog explica qué hacen el reset y el shift , por lo que es posible que desee leer eso nuevamente.

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

El documento sobre continuaciones delimitadas, al que me uno 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 él, 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ómputo que se detuvo.

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

Answer 6

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 al artículo de Jim McBeath mencionado en la answer .

Pero antes de eso, describe Continuations como sigue:

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 tiempo de ejecución.

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

Digamos que está en la cocina frente al refrigerador, pensando en un bocadillo. Tomas una continuación allí y la guardas en tu bolsillo.
Luego, saca un poco de pavo y pan del refrigerador y hazte un sándwich, que ahora está sobre el mostrador.
Usted invoca la continuación en su bolsillo, y se encuentra frente a la nevera de nuevo, pensando en un emparedado. Pero afortunadamente, hay un bocadillo en el mostrador, y todos los materiales utilizados para hacerlo desaparecen. Entonces te lo comes :-)

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

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

Estamos buscando mantenedores que se hagan cargo de los siguientes módulos: scala-swing , scala-continuations .
2.12 no los incluirá si no se encuentra un nuevo mantenedor .
Es probable que sigamos manteniendo los otros módulos (scala-xml, scala-parser-combinators), pero la ayuda aún es muy apreciada.