Rendimento di implementazione (rendimento restituito) utilizzando le continuazioni di Scala

Question

Come si può implementare C# yield return utilizzando le continuazioni di Scala? Mi piacerebbe poter scrivere Scala Iterator nello stesso stile. Una pugnalata è nei commenti su this Scala news post, ma non funziona (provato con Scala 2.8.0 beta). Le risposte in uno related question suggeriscono che questo è possibile, ma anche se ho giocato con continuazioni delimitate per un po ', non riesco a capire esattamente come farlo.

Answer 1

Prima di introdurre le continuazioni, è necessario creare un'infrastruttura. Di seguito è riportato un trampoline che funziona sugli oggetti Iteration. Un'iterazione è un calcolo che può o Yield un nuovo valore o può essere 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 
} 

Il trampolino utilizza un anello interno che accende la sequenza di Iteration oggetti in un Stream. Otteniamo quindi un Iterator chiamando iterator sull'oggetto del flusso risultante. Usando un Stream la nostra valutazione è pigro; non valutiamo la nostra prossima iterazione finché non è necessaria.

Il trampolino può essere utilizzato per costruire direttamente un iteratore.

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

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

che è abbastanza orribile per scrivere, quindi cerchiamo di usare continuazioni delimitati per creare automaticamente i nostri Iteration oggetti.

Usiamo operatori shift e reset per rompere il calcolo su in Iteration s, quindi utilizzare trampoline trasformare i Iteration s in 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(()))) 

Ora possiamo riscrivere il nostro esempio.

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

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

Molto meglio!

Ora ecco un esempio da C# reference page per yield che mostra un utilizzo più avanzato. I tipi possono essere un po 'difficili da abituare, ma tutto funziona.

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

Sono riuscito a scoprire un modo per farlo, dopo qualche ora in più di gioco. Ho pensato che fosse più semplice racchiudere la mia mente rispetto a tutte le altre soluzioni che ho visto fino ad ora, anche se in seguito ho apprezzato molto le soluzioni di Rich e 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)