Implementando rendimiento(retorno de rendimiento) usando continuaciones de Scala

scala-2.8 yield

Question

¿Cómo se puede implementar el yield return C # utilizando las continuaciones de Scala? Me gustaría poder escribir Scala Iterator en el mismo estilo. Una puñalada está en los comentarios en esta publicación de noticias de Scala , pero no funciona (intenté usar la versión beta de Scala 2.8.0). Las respuestas en una pregunta relacionada sugieren que esto es posible, pero aunque he estado jugando con continuaciones delimitadas por un tiempo, parece que no puedo entender exactamente cómo hacerlo.

Answer 1

Antes de presentar las continuaciones, necesitamos construir cierta infraestructura. Debajo hay un trampoline que opera en objetos de Iteration . Una iteración es un cálculo que puede Yield un nuevo valor o puede hacerse.

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
}

El trampolín utiliza un bucle interno que convierte la secuencia de objetos de Iteration en una Stream . Luego obtenemos un Iterator al invocar el iterator en el objeto de flujo resultante. Al usar un Stream nuestra evaluación es floja; no evaluamos nuestra próxima iteración hasta que se necesite.

El trampolín se puede usar para construir un iterador directamente.

val itr1 = trampoline {
  Yield(1, () => Yield(2, () => Yield(3, () => Done)))
}

for (i <- itr1) { println(i) }

Eso es bastante horrible de escribir, así que usemos continuaciones delimitadas para crear nuestros objetos de Iteration automáticamente.

Usamos los operadores de shift y reset para dividir el cálculo en Iteration , luego usamos trampoline para convertir la Iteration 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í hay un ejemplo de la página de referencia de C # para yield que muestra un uso más avanzado. Puede ser un poco complicado acostumbrarse a los tipos, pero todo funciona.

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) }

Answer 2

Logré descubrir una manera de hacerlo, después de unas horas más de jugar. Pensé que era más fácil de entender que todas las otras soluciones que he visto hasta ahora, aunque luego valoré mucho Miles'' soluciones de Rich y Miles'' .

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)