La implementación de rendimiento (retorno de rendimiento) usando continuaciones Scala
-
18-09-2019 - |
Pregunta
¿Cómo puede uno poner en práctica usando C # yield return
continuaciones Scala? Me gustaría ser capaz de escribir Iterator
s Scala en el mismo estilo. Una puñalada es en los comentarios sobre este Scala de prensa posterior , pero no funciona (tratado de utilizar la versión beta Scala 2.8.0). Respuestas en una pregunta relacionada sugieren que esto es posible, pero a pesar de he estado jugando con continuaciones delimitados por un tiempo, me parece que no puede envolver exactamente mi cabeza alrededor de cómo hacer esto.
Solución
Antes de presentar las continuaciones que necesitamos para construir algunas infraestructuras.
A continuación se muestra un trampolín que opera sobre objetos Iteration
.
Una iteración es un cálculo que pueden ya sea Yield
un nuevo valor o puede ser Done
.
sealed trait Iteration[+R]
case class Yield[+R](result: R, next: () => Iteration[R]) extends Iteration[R]
case object Done extends Iteration[Nothing]
def trampoline[R](body: => Iteration[R]): Iterator[R] = {
def loop(thunk: () => Iteration[R]): Stream[R] = {
thunk.apply match {
case Yield(result, next) => Stream.cons(result, loop(next))
case Done => Stream.empty
}
}
loop(() => body).iterator
}
La cama elástica utiliza un bucle interno que convierte la secuencia de objetos Iteration
en un Stream
.
A continuación, obtener una Iterator
llamando iterator
en el objeto de flujo resultante.
Mediante el uso de un Stream
nuestra evaluación es perezosa; no evaluamos nuestra siguiente iteración hasta que se necesite.
La cama elástica puede ser usado para construir un iterador directamente.
val itr1 = trampoline {
Yield(1, () => Yield(2, () => Yield(3, () => Done)))
}
for (i <- itr1) { println(i) }
Eso es bastante horrible para escribir, por lo que vamos a usar continuaciones delimitados para crear nuestra Iteration
objetos automáticamente.
Utilizamos los operadores shift
y reset
para romper el cálculo arriba en Iteration
s,
a continuación, utilizar trampoline
para girar las Iteration
s en un Iterator
.
import scala.continuations._
import scala.continuations.ControlContext.{shift,reset}
def iterator[R](body: => Unit @cps[Iteration[R],Iteration[R]]): Iterator[R] =
trampoline {
reset[Iteration[R],Iteration[R]] { body ; Done }
}
def yld[R](result: R): Unit @cps[Iteration[R],Iteration[R]] =
shift((k: Unit => Iteration[R]) => Yield(result, () => k(())))
Ahora podemos reescribir nuestro ejemplo.
val itr2 = iterator[Int] {
yld(1)
yld(2)
yld(3)
}
for (i <- itr2) { println(i) }
Mucho mejor!
Ahora aquí es un ejemplo de la C # página de referencia para yield
que muestra algunas aplicaciones más avanzadas.
Los tipos pueden ser un poco difícil de acostumbrarse, pero funciona todo.
def power(number: Int, exponent: Int): Iterator[Int] = iterator[Int] {
def loop(result: Int, counter: Int): Unit @cps[Iteration[Int],Iteration[Int]] = {
if (counter < exponent) {
yld(result)
loop(result * number, counter + 1)
}
}
loop(number, 0)
}
for (i <- power(2, 8)) { println(i) }
Otros consejos
Me las arreglé para descubrir una manera de hacer esto, después de unas cuantas horas de jugar. Me pareció que era más fácil de envolver mi cabeza en torno a que todas las otras soluciones que he visto hasta ahora, a pesar de que hice después aprecio mucho Rich y Miles' soluciones.
def loopWhile(cond: =>Boolean)(body: =>(Unit @suspendable)): Unit @suspendable = {
if (cond) {
body
loopWhile(cond)(body)
}
}
class Gen {
var prodCont: Unit => Unit = { x: Unit => prod }
var nextVal = 0
def yld(i: Int) = shift { k: (Unit => Unit) => nextVal = i; prodCont = k }
def next = { prodCont(); nextVal }
def prod = {
reset {
// following is generator logic; can be refactored out generically
var i = 0
i += 1
yld(i)
i += 1
yld(i)
// scala continuations plugin can't handle while loops, so need own construct
loopWhile (true) {
i += 1
yld(i)
}
}
}
}
val it = new Gen
println(it.next)
println(it.next)
println(it.next)