Реализация доходности (доходность доходности) с использованием продолжений Scala

Question

Как можно реализовать C# yield return с использованием продолжений Scala? Я бы хотел написать Scala Iterator s в том же стиле. Удар в комментариях на this Scala news post, но он не работает (пробовал использовать бета-версию Scala 2.8.0). Ответы в related question предполагают, что это возможно, но хотя я некоторое время играл с разграниченными продолжениями, я, похоже, не могу точно обдумать, как это сделать.

Answer 1

Прежде чем вводить продолжение, нам необходимо построить некоторую инфраструктуру. Ниже приведено trampoline, которое работает на объектах Iteration. Итерация - это вычисление, которое может либо Yield, либо новое значение, либо оно может быть 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 
} 

Батут использует внутренний цикл, который превращает последовательность Iteration объектов в Stream. Затем мы получаем Iterator, вызывая iterator на результирующем объекте потока. С помощью команды Stream Наша оценка - ленив; мы не оцениваем нашу следующую итерацию, пока она не понадобится.

Батут можно использовать для создания итератора напрямую.

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

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

Это довольно страшно писать, так что давайте использовать разграниченные продолжений для автоматического создания наших Iteration объектов.

Мы используем shift и reset операторов разорвать вычисление вверх в Iteration с, затем использовать trampoline превратить Iteration сек в 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(()))) 

Теперь мы можем переписать наш пример.

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

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

Гораздо лучше!

Теперь вот пример из C# reference page для yield, который показывает более продвинутое использование. Типы могут быть немного сложными, чтобы привыкнуть, но все это работает.

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

Мне удалось найти способ сделать это, после нескольких часов игры. Я подумал, что это проще было обернуть вокруг меня, чем все другие решения, которые я видел до сих пор, хотя впоследствии я очень ценю решения Rich и 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)