Implementazione di rendimento (yield return) utilizzando continuazioni Scala
-
18-09-2019 - |
Domanda
Come potrebbe una implementare C # yield return
utilizzando continuazioni Scala? Mi piacerebbe essere in grado di scrivere Iterator
s Scala nello stesso stile. Una pugnalata è nei commenti su questa notizia Scala postale , ma non funziona (provato con la versione beta 2.8.0 Scala). Le risposte a una domanda legati suggeriscono che questo è possibile, ma anche se ho giocato con continuazioni delimitati per un po ', io non riesco ad avvolgere esattamente la mia testa intorno come fare questo.
Soluzione
Prima di introdurre continuazioni abbiamo bisogno di costruire alcune infrastrutture.
Sotto è un trampolino che opera su 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 ciclo interno che accende la sequenza di oggetti Iteration
in un Stream
.
Abbiamo poi otteniamo un Iterator
chiamando iterator
sull'oggetto flusso risultante.
Usando una Stream
nostra valutazione è pigro; non valutare la nostra prossima iterazione fino a quando 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) }
Questo è abbastanza orribile a scrivere, quindi cerchiamo di usare continuazioni delimitati per creare oggetti automaticamente il nostro Iteration
.
Usiamo gli operatori shift
e reset
per rompere il calcolo fino in Iteration
s,
quindi utilizzare trampoline
per trasformare le 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 qui è un esempio dal C # pagina di riferimento per yield
che mostra alcuni utilizzo più avanzato.
I tipi possono essere un po 'complicato per abituarsi, 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) }
Altri suggerimenti
Sono riuscito a scoprire un modo per fare questo, dopo un paio di ore di gioco intorno. Ho pensato che questo era più semplice per avvolgere la mia testa intorno rispetto a tutte le altre soluzioni che ho visto finora, anche se ho fatto in seguito molto apprezzare Rich e Miles' soluzioni.
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)