Implementacja yield (yield return) przy użyciu Scala continuations

Question

Implementacja yield (yield return) przy użyciu Scala continuations

Jak można zaimplementować C #yield return używając Scali? Chciałbym móc pisać scale Iteratorw tym samym stylu. W komentarzach do tego postu Scala News, ale to nie działa( próbowałem użyć Scala 2.8.0 beta). Odpowiedzi na powiązane pytanie sugerują, że jest to możliwe, ale chociaż od jakiegoś czasu gram z ograniczonymi kontynuacjami, nie mogę dokładnie zawinąć głowy, jak to zrobić.

27

yield scala scala-2.8 yield-return continuations

Author: Community, 2010-02-04

Source

2 answers

Udało mi się znaleźć sposób, aby to zrobić, po kilku godzinach zabawy. Myślałem, że jest to prostsze do ogarnięcia niż wszystkie inne rozwiązania, które widziałem do tej pory, choć później bardzo doceniam rozwiązania Rich I Milesa.

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)

5

Author: Yang,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2017-05-23 10:31:31

score 41 · Accepted Answer

Zanim wprowadzimy kontynuacje, musimy zbudować jakąś infrastrukturę. Poniżej znajduje się trampolina , która działa na obiektach Iteration. Iteracja to obliczenie, które może być Yield nową wartością lub może być 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
}

Trampolina wykorzystuje wewnętrzną pętlę, która zamienia sekwencję obiektów Iteration W Stream. Następnie otrzymujemy Iterator wywołując iterator na wynikowym obiekcie stream. Używając Stream nasza ocena jest leniwa; nie oceniamy naszej następnej iteracji, dopóki to jest potrzebne.

Trampolina może być używany do budowy iteratora bezpośrednio.

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

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

To jest dość straszne do napisania, więc użyjmy rozdzielonych ciągów, aby automatycznie tworzyć nasze Iteration obiekty.

Używamy operatorów shift i reset do podziału obliczeń na Iteration s, następnie użyj trampoline, aby przekształcić Iteration w 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(())))

Teraz możemy przepisać nasz przykład.

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

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

O wiele lepiej!

Oto przykład z strona referencyjna C # dla yield, która pokazuje bardziej zaawansowane użycie. Typy mogą być trochę trudne, aby się przyzwyczaić, ale to wszystko działa.

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