Implementieren von Ertrag (Rendite) mit Scala-Fortsetzungen

Question

Wie könnte man C# yield return mithilfe von Scala-Fortsetzungen implementieren? Ich würde gerne in der Lage sein, Scala Iterator s im selben Stil zu schreiben. Ein Stich ist in den Kommentaren this Scala news post, aber es funktioniert nicht (versucht mit der Scala 2.8.0 Beta). Antworten in einem related question deuten darauf hin, dass dies möglich ist, aber obwohl ich seit einiger Zeit mit begrenzten Fortsetzungen spiele, kann ich nicht genau meinen Kopf darum drehen, wie man das macht.

Answer 1

Bevor wir fortfahren, müssen wir eine Infrastruktur aufbauen. Unten ist eine trampoline, die auf Iteration Objekte funktioniert. Eine Iteration ist eine Berechnung, die entweder Yield einen neuen Wert oder Done sein kann.

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 
} 

Das Trampolin verwendet eine interne Schleife, die die Folge von Iteration Objekte in eine Stream dreht. Wir erhalten dann eine Iterator durch Aufruf von iterator auf das resultierende Stream-Objekt. Durch die Verwendung eines Stream ist unsere Bewertung faul; Wir bewerten unsere nächste Iteration erst, wenn sie benötigt wird.

Das Trampolin kann verwendet werden, um einen Iterator direkt zu erstellen.

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

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

Das ziemlich schrecklich ist zu schreiben, also lassen Sie uns begrenzt Fortsetzungen verwenden, um unsere Iteration Objekte automatisch zu erstellen.

Wir verwenden die shift und reset Betreiber die Berechnung zu brechen in Iteration s, dann trampoline verwenden, um die Iteration s in ein Iterator einzuschalten.

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

Jetzt können wir unser Beispiel umschreiben.

val itr2 = iterator[Int] { 
    yld(1) 
    yld(2) 
    yld(3) 
} 

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

Viel besser!

Jetzt ist hier ein Beispiel aus der C# reference page für yield, die einige erweiterte Verwendung zeigt. Die Typen können ein bisschen schwierig zu gewöhnen sein, aber es funktioniert alles.

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

Ich habe es geschafft, einen Weg zu finden, dies zu tun, nach ein paar Stunden Spielzeit. Ich dachte, dass es einfacher wäre, meinen Kopf einzuwickeln als all die anderen Lösungen, die ich bisher gesehen habe, obwohl ich Richards und Miles' Lösungen sehr zu schätzen weiß.

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)