使用Scala continuation实现yield（yield return）

Question

使用Scala continuation实现yield（yield return）

scalascala-2.8yieldcontinuationsyield-return

27

如何使用Scala continuation实现C#的`yield return`？我想以相同的风格编写Scala的`Iterator`。在这个Scala新闻帖子的评论中有一种方法，但它不起作用（尝试使用Scala 2.8.0 beta）。一个相关问题中的答案表明这是可能的，但虽然我已经玩了一段时间的delimited continuation，但似乎无法准确地理解如何做到这一点。

- Yang

那个例子有什么问题？它无法编译还是没有产生预期的结果？有一个提到，为了使其正常工作，可能需要一个CPS感知的“foreach”，但无论如何，了解问题会很有帮助。 - Daniel C. Sobral

2

你可能想查看Miles Sabin对我提出的类似问题的回答：https://dev59.com/M3I95IYBdhLWcg3w1BhN#2146456。不确定它是否能让你更接近答案。 - huynhjl

这个问题至少有另外两个答案： https://dev59.com/YnI-5IYBdhLWcg3w0cKG https://dev59.com/M3I95IYBdhLWcg3w1BhN还有一个关于如何使其与“for”语句兼容的答案： https://dev59.com/RWox5IYBdhLWcg3w1X2- - Urban Vagabond

2个回答

5

在玩耍了几个小时后，我设法发现了一种方法来做到这一点。我认为这比我迄今所见到的所有其他解决方案都更容易理解，尽管之后我非常欣赏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)

- Yang

2

Scala的continuations无法处理while循环？哎呀！ - Daniel C. Sobral

确实。:( 希望那个还在进行中，但我认为for-comprehensions绝对不与shift兼容，因为这将意味着拆开map/foreach等等。 - Yang

3

不再如此了。从while循环内调用cps代码已经有一段时间了。不过，for-comprehensions仍然不受支持（我真的不认为它们会得到支持）。 - Przemek Pokrywka

@PrzemekPokrywka：...除非Scala拥有自己的虚拟机，或者Java 12发布了，或者其他什么情况。 - Erik Kaplun

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Rich Dougherty · Accepted Answer

在介绍continuations之前，我们需要构建一些基础设施。下面是一个操作Iteration对象的trampoline。迭代是一种计算，它可以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
}

ampoline使用内部循环将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#参考页面的示例，演示了一些更高级的用法。类型可能有点棘手，但它们都可以工作。

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