CLOVER🍀

That was when it all began.

Scalaで継続モナド(Continuationモナド)を学ぶ

今年の6月くらいに買った以下のScala実践プログラミングなのですが、いくつかテーマ的には気になるものがありました。

オープンソース徹底活用Scala実践プログラミング

オープンソース徹底活用Scala実践プログラミング

気になっているのは、以下の章。

んで、その中でもデザインパターンの章で登場した継続モナド(Continuationモナド)を、ちょっと勉強したいなと思っていましたが本を見たり、Webで調べてもよくわかりません…。

なので、書いて動かしてみようかと。

まずは、素直に本の写経。
Cont.scala

object Cont {
  def mreturn[A, B](x: A): Cont[A, B] =
    new Cont(k => k(x))
}

class Cont[A, B](m: (A => B) => B) {
  def map[C](f: A => C): Cont[C, B] = 
    new Cont(k => m(x => k(f(x))))

  def flatMap[C](f: A => Cont[C, B]): Cont[C, B] =
    new Cont(k => m(x => f(x).run(k)))

  def run(k: A => B): B = m(k)
}

Continuationモナドの定義です。ところで、Scala実践プログラミングだとコンパニオンオブジェクトの方って特に使っていませんね。いや、別に問題ないんですけど…。

本には使う時には意識しなくても大丈夫と書いていますが、書いた側に立ったからには理解したいというのが心情。ちょっとContクラスの定義を読み解いてみましょう。

コンストラクタ
class Cont[A, B](m: (A => B) => B)

引数としてmを受け取ります。mとは、「型Aを引数に取り型Bの結果を返す関数」を引数に取り型Bの結果を返す関数です。…この時点で、ちょっとゲンナリします。

mapメソッド
  def map[C](f: A => C): Cont[C, B] = 
    new Cont(k => m(x => k(f(x))))

引数としてfを受け取り、Contクラスのインスタンスを返却します。fとは、型Aを引数に取りCを返す関数です。また、戻り値となるContクラスは型C、型Bが適用されます。
ここでは、戻り値として生成されるContクラスが問題ですね…。

新しいインスタンスが型C、型Bで宣言されることを考えると、以下のように分解して考えましょう。

  • newで使用されているkは「型Cを引数に取り型Bの結果を返す関数」である
  • mはコンストラクタの引数だったので、関数として適用すると型Bの結果を返す
  • よって、new Cont(k => m(...))でCont[C, B]となる

では、続いてmに適用されている引数について。

  • xの型はAである
  • fは「型Aを引数に取り型Cの結果を返す関数」だった
  • よって、f(x)はCの結果が返り、これをkに適用することで型Bの結果が返る

つまり、型を省略せずに書くとこうなりますね。

  def map[C](f: A => C): Cont[C, B] = 
    new Cont((k: C => B) => m((x: A) => k(f(x))))
runメソッド
  def run(k: A => B): B = m(k)

flatMapメソッドはrunメソッドに依存しているので、先にこちらを。kは型Aを引数に型Bの結果を返す関数なので、mに適用すると型Bの結果が返る。これだけ見ると、あまり大したことはありません。

が、これが非常に重要なメソッドで、これを呼び出すまではモナドの中身は実行されません。このメソッドを呼び出すことにより、数珠繋ぎになった継続が実行されていきます。

flatMapメソッド
  def flatMap[C](f: A => Cont[C, B]): Cont[C, B] =
    new Cont(k => m(x => f(x).run(k)))

mapメソッドよりも、さらにややこしいですね…。今度は、引数fは型Aを引数に受け取りCont[C, B]を返す関数で、flatMapメソッドの結果としてはCont[C, B]を返します。

まあ、やっぱりこちらも順に見ていきましょう。

最初のnew Cont(k => m(...))のところは、mapメソッドと同じで

  • newで使用されているkは「型Cを引数に取り型Bの結果を返す関数」である
  • mはコンストラクタの引数だったので、関数として適用すると型Bの結果を返す
  • よって、new Cont(k => m(...))でCont[C, B]となる

です。

では、mに適用されている引数について。

  • xの型はAである
  • fは「型Aを引数に受け取りCont[C, B]を返す関数」だった
  • f(x)はCont[C, B]を返すので、runメソッドを呼び出すことができる
  • ここで、kは「型Cを引数に取り型Bの結果を返す関数」である
  • よって、Cont[C, B].run(k)と適用すると、型Bの結果が返る
  • mは「型Aを引数に取り型Bの結果を返す関数」を引数に取り型Bの結果を返す関数だったので、この定義は成立する

こちらは、型を省略せずに書くとこうなります。

  def flatMap[C](f: A => Cont[C, B]): Cont[C, B] =
    new Cont((k: C => B) => m((x: A) => f(x).run(k)))

…正直、書いていて意味がわからなくなってきました。たぶん、型の定義としては嘘は言っていないと思うのですが。要は、Continuationモナド構築時に渡している関数を、Contインスタンスの構築と共に繋いでいくことで成り立っていて、最後にrunメソッドでトリガーを引くことで繋いだモナドの中身を実行するという解釈で合っていると思うのですが。もうちょっと、継続の考え方自体を勉強しないとダメですね。

では、これを使ったサンプル。本と同じようにLoanパターンを使ってみます。
Resources.scala

object Resources {
  type Resource = { def close(): Unit }

  def using[A <: Resource, B](r: A)(body: A => B):B = {
    try {
      body(r)
    } finally {
      if (r != null) {
        r.close()
      }
    }
  }

  def usingCont[A <: Resource, B](resource: A): Cont[A, B] =
    new Cont(k => using(resource)(r => k(r)))

  def withFile(file: String): Cont[scala.io.BufferedSource, Unit] =
    new Cont(k => {
      using(scala.io.Source.fromFile(file)) { r: scala.io.BufferedSource => k(r) }
    })
}

class SimpleResource(val name: String) {
  def close(): Unit = {
    println("[%s] is Closed".format(name))
  }

  override def toString: String = name
}

Resources#withFileは本と同じものですが、usingContはオリジナルです。SimpleResourceクラスは、usingを使うためのダミークラスですね。usingContメソッドを書いた時に、本がなんでジェネリックな宣言になっていないか理由がわかりました…。

では、まずは本と同じような例を。

    val work =
      for {
        contScala <- withFile("src/main/scala/Cont.scala")
        resources <- withFile("src/main/scala/Resources.scala")
      } yield {
        println("Count Files")
        println(contScala.getLines().length + resources.getLines().length)
      }

    println("Get Result")
    work.run(r => r)

実行すると、こうなります。

> run
[info] Compiling 1 Scala source to /xxxxx/continuation-monad/target/scala-2.9.1.final/classes...
[info] Running ContTest 
Get Result
Count Files
43

先に「Get Result」が表示された後に「Count Lines」が表示されているので、work変数を評価しないと中身が実行されないことになります。

では、今度はusingContメソッドとSimpleResourceクラスを使って動きを見てみます。サンプルはこちら。

    val resource1 = new SimpleResource("resource1")
    val resource2 = new SimpleResource("resource2")

    val resultFor1 =
      for (r <- usingCont[SimpleResource, String](resource1)) yield r.name

    println(resultFor1.run(r => r))

    println("------------------------------------------------")

    val resultFor2 =
      for {
        r1 <- usingCont[SimpleResource, String](resource1)
        r2 <- usingCont[SimpleResource, String](resource2)
      } yield {
        println("Called in yield")
        r1.name + ":" + r2.name
      }

    println(resultFor2.run(r => r))

    println("------------------------------------------------")

    val resultFlatMap =
      usingCont[SimpleResource, String](resource1).flatMap {
        r1 => usingCont[SimpleResource, String](resource2).map {
          r2 => r1.name + ":" + r2.name
        }
      }

    println(resultFlatMap.run(r => r))

それぞれ、単純なfor式、ジェネレータ2個のfor式、そしてそれをベタッとflatMap、mapで書き直したもののパターンです。なお、SimpleResourceクラスはclose時にコンソール出力が出るので、少し動きがわかりやすいかも。

実行結果はこちらです。

> run
[info] Compiling 1 Scala source to /xxxxx/continuation-monad/target/scala-2.9.1.final/classes...
[info] Running ContTest 
[resource1] is Closed
resource1
------------------------------------------------
Called in yield
[resource2] is Closed
[resource1] is Closed
resource1:resource2
------------------------------------------------
[resource2] is Closed
[resource1] is Closed
resource1:resource2

とまあ、一応ちゃんと動いています。

が、よくよく見ると

    val resultFor1 =
      for (r <- usingCont[SimpleResource, String](resource1)) yield r.name

のように、usingContにわざわざ型パラメータを与えています。ジェネリックな使い方をしたかったのですが、usingContはContinuationモナドを作るだけなので、結果の型がこの時点では推論できないんですよねぇ。まあ、仕方がないですか。

ちょっと難しいのですが、少しだけ動きは分かった気がします。が、まだまだ勉強不足のようなので、他の言語とかからも勉強してみようかなぁと思います。

この辺りも参考にしつつ。
Haskellでの定義
http://www.sampou.org/haskell/a-a-monads/html/contmonad.html
Scalaサイトによる、CallCCのサンプル
http://www.scala-lang.org/node/46