kmizuの日記

プログラミングや形式言語に関係のあることを書いたり書かなかったり。

Scalaの限定継続を使って、C#のyieldぽいものを実現するライブラリを書いてみた

Scalaの限定継続を使って遊んでいたら副産物的にできたもので、実用に供することができるものではないですが、まあこんなこともできますという例として。なんかキャストとか使っていてあまり綺麗じゃないですが、型安全なように書こうとすると複雑になる上に、どうもたまたま自分の書いたコードがコンパイラのバグを踏んでしまったらしく、コンパイラが例外吐いて落ちたので仕方なくこうなっています。ただし、型安全でないのはライブラリ内部の実装だけであって、Generatorのユーザは型安全に使えるようになっている(はず)です。

//scala 2.8.0 + continuation pluginが無いとコンパイルできない
import scala.continuations.ControlContext._
import scala.continuations._
import scala.collection._

trait Generator[+A] extends Traversable[A] {
  def moveNext(): Boolean
  def current: A
  def foreach[U](f: A => U): Unit = {
    while(moveNext()) {
      f(current)
    }
  }
}

object Generator {
  type susp = cps[Any, Any]
  def make[A](body: (A => Unit @susp) => Unit @susp): Generator[A] = new Generator[A] {
    val yields: A => Unit @susp = {v =>
      shift{k: (Unit => Any) => (k, v):Any }
    }
    var thunk: Unit => Any = {x: Unit =>
      reset {
        body(yields)
        None
      }
    }
    var value: A = _
    def moveNext(): Boolean = {
      val result = thunk()
      result match {
        case (k, v) => 
          thunk = k.asInstanceOf[(Unit => Any)]
          value = v.asInstanceOf[A]
          true
        case None =>
          false
      }
    }
    def current: A = value
  }
}

以下、利用例。再帰的な関数も問題無く取り扱えていることがわかる。

import Generator._

/* 既存の高階関数は継続のキャプチャに対応していないので、対応したものを自前で作成 */
object Control {
  def upto[A](from: Int, to: Int)(f: Int => A @susp): Unit @susp = {
    if(from <= to) { f(from); upto(from + 1, to)(f) }
  }
  def each[A](t: Iterable[A])(f: A => (Unit @susp))
    : Unit @susp = {
    val it = t.iterator
    def loop: Unit @susp = {
      if(it.hasNext) {
        f(it.next())
        loop
      }
    }
    loop
  }
}

import Control._
import scala.xml._

object User {
  def main(args: Array[String]) {
    // 1から10までの数を列挙するジェネレータ
    val g1 = make[Int] {yields =>
      upto(1, 10) {i =>
        yields(i)
      }
    }
    // XMLの要素を列挙するジェネレータ
    def elements(n: Node) = make[Elem]{yields =>
      def eachElem(n: Node): Unit @susp = {
        n match { case e:Elem => yields(e); case _ => }
        each(n.child)(eachElem(_))
      }
      eachElem(n)
    }
    val g2 = elements(
      <html>
        <head>
          <title>Scala Delimited Continuation Test</title>
        </head>
        <body>
          <p>Test</p>
        </body>
      </html>
    )
    g1.foreach(println)
    g2.foreach(e => println(e.label)) //要素名を出力
  }
}

実行結果。

>scala -classpath selectivecps-library.jar;. User
1
2
3
4
5
6
7
8
9
10
html
head
title
body
p

追記: 内部イテレータを外部イテレータ(ジェネレータ)に変換する例も作ってみた。このような例はC#のyieldだと実現が難しいと思う(たぶん)。

object User2 {
  //内部イテレータを受け取り、外部イテレータ(ジェネレータ)に変換するメソッド
  def internal2External[A](f: (A => Unit @susp) => Unit @susp) = make[A]{yields =>
    f{a => yields(a)}
  }
  def main(args: Array[String]) {
    val g = internal2External(upto(1, 15))
    //ちゃんとジェネレータになっていることを確認
    while(g.moveNext()) {
      println(g.current)
    }
  }
}

実行結果。

>scala -classpath selectivecps-library.jar;. User2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15