¿Cuáles son continuaciones Scala y por qué se utilizan?

StackOverflow https://stackoverflow.com/questions/1512930

Pregunta

acabo de terminar Programación en Scala , y no tengo estado buscando en los cambios entre 2,7 y 2,8 Scala. El que parece ser el más importante es el plugin continuaciones, pero no entiendo lo que es útil para o cómo funciona. He visto que es bueno para la E / S asíncrona, pero no he sido capaz de averiguar por qué. Algunos de los recursos más populares sobre el tema son los siguientes:

Y esta pregunta desbordamiento de pila:

Por desgracia, ninguna de estas referencias tratan de definir lo que son continuaciones a favor o en lo que el cambio / RESET funciones se supone que deben hacer, y no he encontrado ninguna referencia que lo hacen. No he sido capaz de adivinar la forma en cualquiera de los ejemplos de los artículos en alternancia (o lo que hacen), así que una forma de ayudarme podría ser ir línea por línea a través de una de esas muestras. Incluso este sencillo desde el 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 número 8? Eso probablemente me ayudará a empezar.

¿Fue útil?

Solución

href="http://dcsobral.blogspot.com/2009/07/delimited-continuations-explained-in.html" hace explicar lo reset y shift hacer, por lo que puede leer de nuevo.

Otra buena fuente, que también señalo en mi blog, es la entrada de Wikipedia sobre la continuación del estilo que pasa . Que uno es, con mucho, el más clara sobre el tema, a pesar de que no utiliza la sintaxis Scala, y la continuación se pasa de forma explícita.

El documento sobre continuaciones delimitados, lo que me enlace a mi blog, pero parece haberse convertido roto, da muchos ejemplos de uso.

Sin embargo, creo que el mejor ejemplo de la concepto de continuaciones delimitados es Scala Swarm. En ella, la biblioteca detiene la ejecución del código en un punto, y el cálculo restante se convierte en la continuación. La biblioteca entonces hace algo -. En este caso, la transferencia de la computación a otro host, y devuelve el resultado (el valor de la variable que se accede) para el cálculo que fue detenido

Ahora, usted no entiende incluso el simple ejemplo en la página Scala, por lo que DO leer mi blog. En lo que estoy solamente en cuestión con la explicación de estos conceptos básicos, de por qué el resultado es 8.

Otros consejos

Me pareció que las explicaciones existentes a ser menos eficaz en explicar el concepto de lo que yo esperaría. Espero que éste es clara (y correcta.) No he utilizado continuaciones todavía.

Cuando un cf función de continuación se llama:

  1. Ejecución salta sobre el resto del bloque de shift y comienza de nuevo al final de ella
    • el parámetro pasado a cf es lo que los bloques shift "evalúa" a como 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 que una llamada a reset si no hay bloque)
    • el resultado del bloque de reset (o el parámetro a reset () si no hay un bloque) es lo cf retornos
  3. La ejecución continúa después de cf hasta el final del bloque de shift
  4. Ejecución se salta hasta el final del bloque de reset (o una llamada para restablecer?)

Así que 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 de la trabajo de investigación para continuaciones delimitadas de Scala, modificados ligeramente para la entrada de función a shift se le da el nombre f y por lo tanto ya no es anónimo. 

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 plugin Scala transforma este ejemplo tal que el cálculo (dentro del argumento de entrada de reset) a partir de cada shift a la invocación de reset es sustituye con la función de entrada (por ejemplo f) para shift.

El cálculo sustituido es cambiado (es decir, desplazado) en un k función. El f función introduce la función k, donde k contiene el cálculo sustituido, entradas k x: Int, y el cálculo de k reemplaza shift(f) con x. 

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

¿Qué tiene el mismo efecto que: 

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

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

Otra prestado ejemplo, con la abstracción conceptualmente equivalente, es decir, read es la entrada de 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 en el 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 aclara la abstracción común coherente que fue un tanto ofuscado por la presentación previa de estos dos ejemplos. Por ejemplo, el primer ejemplo canónico se presentó en el documento de investigación rel="noreferrer"> href="http://lampwww.epfl.ch/~rompf/continuations-icfp09.pdf#page=3" 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 read en el prestado segundo ejemplo.

Así continuaciones delimitados crean la ilusión de una inversión de control de "me llamas desde fuera de reset" a "Te llamo dentro reset".

Tenga en cuenta el tipo de retorno de f está, pero k no es, requiere que sea el mismo que el tipo de retorno de reset, es decir f tiene la libertad de declarar cualquier tipo de cambio de k, siempre y cuando f devuelve el mismo tipo que reset . Lo mismo vale para read y capture (véase también ENV abajo).

continuaciones delimitados no implícitamente invierten el control de estado, por ejemplo, read y callback no son funciones puras. Por lo tanto la persona que llama no puede crear expresiones referencialmente transparente y por lo tanto no tiene el control declarativa (también conocido como transparente) sobre la intención imperativo semántica .

Podemos lograr explícitamente funciones puras con continuaciones delimitados. 

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 en el 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á poniendo ruidosa, debido al ambiente explícita.

tangencial nota, Scala no tiene inferencia de tipo global de Haskell y por lo tanto por lo que yo sé no podía soportar la elevación implícita a unit de una mónada estado (como una posible estrategia para ocultar el entorno explícito), porque de Haskell mundial (Hindley- Milner) inferencia de tipos depende de no apoyar diamante múltiples virtual de la herencia .

Continuación captura el estado de un cálculo, que se invoca más tarde.

Piense en el cálculo entre el final de la expresión de cambios y salir de la expresión de reposición en función. Dentro de la expresión cambio de esta función se llama k, es la continuación. Puede pasar alrededor, invocarlo más tarde, incluso más de una vez.

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

Así que con continuaciones se puede envolver un trozo bastante arbitraria y no local de código en una función. Esto puede ser usado para poner en práctica no estándar de flujo de control, tales como coroutining o backtracking.

Así continuaciones deben utilizarse en un nivel de sistema. La aspersión de ellos a través de su código de aplicación sería una receta segura para las pesadillas, mucho peor que el código espagueti peor usando Goto jamás podría ser.

exención de responsabilidad:. que no tienen conocimiento en profundidad de las continuaciones en Scala, sólo se infiere de mirar a los ejemplos y sabiendo continuaciones del Esquema

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

Uno de los ejemplos:

  

Para ver el control de flujo un poco más claramente, 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 del código anterior produce: 

A
B
D
E
G
F
C

Otra (más reciente - Mayo 2016) artículo sobre continuaciones Scala es:
" Time Travel en Scala: CPS en Scala (continuación de Scala) " por Shivansh Srivastava (shiv4nsh) .
También se refiere a Jim McBeath 's artículo menciona en Dmitry Bespalov 's respuesta .

Pero antes de eso, se describe continuaciones de esta manera:

  

Una continuación es una representación abstracta del estado de control de un programa informático .
  Así que lo que realmente significa es que es una estructura de datos que representa el proceso de cálculo en un punto dado en la ejecución del proceso; la estructura de datos creada se puede acceder mediante el lenguaje de programación, en lugar de estar escondido en el entorno de ejecución.

     

Para explicarlo más podemos tener uno de los ejemplo más clásico,

     

Digamos que estás en la cocina en la parte frontal del refrigerador, pensando en un sándwich. Se toma una continuación allí mismo y lo pega en el bolsillo.
  A continuación, se obtiene un poco de pavo y pan de la nevera y hacerte un sándwich, que ahora está sentado en el mostrador.
  Se invoca la continuación en el bolsillo, y usted se encuentra de pie delante de la nevera de nuevo, pensando en un sándwich. Pero, afortunadamente, hay un sándwich en el mostrador, y todos los materiales utilizados en su elaboración se han ido. Así lo comes. : -)

     

En esta descripción, el sandwich es parte de los datos programa (por ejemplo, un objeto en el montón), y en lugar de llamar un “make sandwich” rutina y luego regresar, la persona llama un “ make sandwich with current continuation”de rutina, lo que crea el sándwich y luego continúa cuando la ejecución fue apagado.

Una vez dicho esto, como se anunció en Abril 2014 por Scala 2.11.0-RC1

  

Buscamos mantenedores para hacerse cargo de los siguientes módulos: scala-swing , < a href = "https://github.com/scala/scala-continuations" rel = "nofollow noreferrer"> Scala-continuaciones .
   2,12 no incluirá si no se encuentra un nuevo mantenedor .
  probablemente vamos a seguir manteniendo los otros módulos (Scala-xml, Scala-analizador-combinadores), pero la ayuda está siendo muy apreciado.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top