A implementação de rendimento (rendimento de retorno) usando continuações Scala

Question

Como pode um implementar C # yield return usando continuações Scala? Eu gostaria de ser capaz de escrever Iterators Scala no mesmo estilo. Uma punhalada é nos comentários sobre este Scala notícias pós , mas ele não funciona (tentei usar o beta Scala 2.8.0). Respostas em uma questão relacionada sugerem isso é possível, mas embora estive jogando com continuações delimitados por um tempo, eu não consigo quebrar exatamente a minha cabeça em torno de como fazer isso.

Answer 1

Antes de introduzir continuações precisamos construir alguma infra-estrutura. Abaixo está uma trampolim que opera em objetos Iteration . Uma iteração é um cálculo que pode Yield um novo valor ou pode ser 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
}

O trampolim utiliza um circuito interno que liga a sequência de objectos Iteration num Stream. Em seguida, obter um Iterator chamando iterator sobre o objeto de fluxo resultante. Usando um Stream nossa avaliação é preguiçoso; nós não avaliamos nossa próxima iteração até que seja necessário.

O trampolim pode ser usado para construir um iterador diretamente.

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

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

Isso é muito horrível para escrever, então vamos usar continuações delimitados para criar o nosso Iteration objetos automaticamente.

Nós usamos os operadores shift e reset para quebrar o cálculo acima em Iterations, em seguida, usar trampoline para transformar os Iterations em um 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(())))

Agora podemos reescrever nosso exemplo.

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

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

Muito melhor!

Agora, aqui está um exemplo do C página de referência # para yield que mostra algumas utilizações avançadas. Os tipos pode ser um pouco difícil de se acostumar, mas tudo funciona.

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

Eu consegui descobrir uma maneira de fazer isso, depois de mais algumas horas de brincar. Eu pensei que este era mais simples para envolver minha cabeça em torno do que todas as outras soluções que eu vi até agora, embora eu fiz depois aprecio muito Rich e soluções Milhas.

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)