Scala における継続モナドの実装と活用

「Scala秋祭り」の登壇資料
https://scala-aki-matsuri.connpass.com/event/142817/

- v1.0.0 に更新
- v0.1.0 をアップロード

Transcript

1. Scala における 継続モナドの実装と活用 2019/09/16 Scala秋祭り Naoki Aoyama - @aoiroaoino
2. ❖ Naoki Aoyama ❖ Twitter/GitHub: @aoiroaoino ❖ Working at: $ Whoami
3. Agenda ➢ Introduction ◦ 継続、継続渡しとは？ ➢ 継続モナドの実装 ◦ 継続モナドを実装し、合成の意味を考える ➢ 継続モナドの活用 ◦ 継続モナドの活用例 ◦ 注意点 ➢ Conclusion
4. 話さないこと ❖ 継続、継続モナドの歴史や基礎理論 ❖ 継続モナドの発展系について（通称 ContT, IndexedCont など） ❖ Scala 以外の継続、継続モナドについて ❖ Scalaz, Cats などのライブラリ継続モナドの実装や解説
5. Introduction
6. 継続とは？ ❖ 「その後に実行される計算/処理」
7. 継続とは？ ❖ 「その後に実行される計算/処理」
8. 継続とは？ val result = isEven(42) if (result) { println(s"$n is even number") } else { println(s"$n is odd number") }
9. 継続とは？ val result = isEven(42) if (result) { println(s"$n is even number") // 実行される } else { println(s"$n is odd number") // 実行されない（捨てられる処理） }
10. 継続とは？ def add(i: Int, j: Int): Int = i + j def mul(i: Int, j: Int): Int = i * j def show(i: Int): String = s"num: $i" val a = add(1, 2) val b = mul(a, 3) val s = show(b) println(s)
11. 継続とは？ def add(i: Int, j: Int): Int = i + j def mul(i: Int, j: Int): Int = i * j def show(i: Int): String = s"num: $i" val a = add(1, 2) // 計算結果 // その後の計算 val b = mul(a, 3) val s = show(b) println(s)
12. 継続とは？ def add(i: Int, j: Int): Int = i + j def mul(i: Int, j: Int): Int = i * j def show(i: Int): String = s"num: $i" val a = add(1, 2) val b = mul(a, 3) // 計算結果 // その後の計算 val s = show(b) println(s)
13. 継続とは？ def add(i: Int, j: Int): Int = i + j def mul(i: Int, j: Int): Int = i * j def show(i: Int): String = s"num: $i" val a = add(1, 2) val b = mul(a, 3) val s = show(b) // 計算結果 // その後の計算 println(s)
14. 継続渡しスタイル ❖ 引数に「計算結果を受け取って実行する、その後の計算」を追加 ❖ 暗黙的だった継続を関数で表現 ❖ 継続を明示的に(値として)扱えるようになる ❖ CPS: Continuation-passing style
15. 継続渡しスタイル // 通常の計算（直接スタイル） def add(i: Int, j: Int): Int = i + j // 継続渡しスタイル def add[R](i: Int, j: Int)(cont: Int => R): R = { val a = i + j cont(a) }
16. 継続渡しスタイル // 通常の計算（直接スタイル） def show(i: Int): String = s"num: $i" // 継続渡しスタイル def show[R](i: Int)(cont: String => R): R = { val a = s"num: $i" cont(a) }
17. 継続渡しスタイル // 1 + 2 を実行。その後の計算「 10倍する」 scala> add(1, 2)(a => a * 10) res0: Int = 30 // 1 + 2 を実行。その後の計算「引数をそのまま返す」 scala> add(1, 2)(a => a) res1: Int = 3
18. 継続渡しスタイル // 1 を文字列に変換し prefix をつける。その後の計算「 suffix をつける」 scala> show(1)(a => a + " !!") res3: String = num: 1 !! // 1 を文字列に変換し prefix をつける。その後の計算「 Byte 配列を得る」 scala> show(1)(a => a.getBytes(java.nio.charset.StandardCharsets.UTF_8)) res4: Array[Byte] = Array(110, 117, 109, 58, 32, 49)
19. 継続渡しスタイル // 直接スタイル（再掲） val a = add(1, 2) val b = mul(a, 3) val s = show(b) println(s)
20. 継続渡しスタイル // 直接スタイル（再掲） val a = add(1, 2) val b = mul(a, 3) val s = show(b) println(s) // 継続渡しスタイル add(1, 2){ a => mul(a, 3){ b => show(b){ s => println(s) } } }
21. もしや、モナドでは？
22. 継続モナドの実装
23. 継続を値として扱う def add[R](i: Int, j: Int)(cont: Int => R): R = { val a = i + j cont(a) } def show[R](i: Int)(cont: String => R): R = { val a = s"num: $i" cont(a) }
24. 継続を値として扱う def add[R](i: Int, j: Int)(cont: Int => R): R = { val a = i + j cont(a) } def show[R](i: Int)(cont: String => R): R = { val a = s"num: $i" cont(a) }
25. 継続を値として扱う // 継続部分を関数に変更 def add[R](i: Int, j: Int): (Int => R) => R = { cont => ??? } def show[R](i: Int) : (String => R) => R = { cont => ??? }
26. 継続を値として扱う // 継続部分を関数に変更 def add[R](i: Int, j: Int): (Int => R) => R = { cont => ??? } def show[R](i: Int) : (String => R) => R = { cont => ??? } // (A => R) => R という関数に Cont[R, A] と名前をつける type Cont[R, A] = (A => R) => R def add[R](i: Int, j: Int): Cont[R, Int] = { cont => ??? } def show[R](i: Int) : Cont[R, String] = { cont => ??? }
27. 継続を値として扱う // Scala ではしばしばラップするデータ型を定義 final case class Cont[R, A](run: (A => R) => R) // もちろん、ケースクラス版 Cont[R, A] を用いて add, show が定義できる def add[R](i: Int, j: Int): Cont[R, Int] = Cont { cont => ??? } def show[R](i: Int) : Cont[R, String] = Cont { cont => ??? }
28. モナドってなんだっけ？ ❖ モナド則を満たすように pure/flatMap を実装したもの（ざっくり）
29. モナドってなんだっけ？ // M[_] はモナドの型 def pure[A](a: A): M[A] def flatMap[B](f: A => M[B]): M[B] // 右単位元 fa.flatMap(a => pure(a)) == fa // 左単位元 pure(a).flatMap(f) == f(a) // 結合律 fa.flatMap(f).flatMap(g) == fa.flatMap(a => f(a).flatMap(g))
30. 継続モナドの実装 object Cont { def pure[R, A](a: A): Cont[R, A] = ??? } final case class Cont[R, A](run: (A => R) => R) { def flatMap[B](f: A => Cont[R, B]): Cont[R, B] = ??? def map[B](f: A => B): Cont[R, B] = ??? }
31. 継続モナドの実装 object Cont { def pure[R, A](a: A): Cont[R, A] = ??? } final case class Cont[R, A](run: (A => R) => R) { def flatMap[B](f: A => Cont[R, B]): Cont[R, B] = ??? def map[B](f: A => B): Cont[R, B] = flatMap(a => Cont.pure(f(a))) // モナドのデフォルト実装 }
32. 継続モナドの実装 object Cont { def pure[R, A](a: A): Cont[R, A] = Cont(ar => ar(a)) // a をそのまま継続に渡すだけ } final case class Cont[R, A](run: (A => R) => R) { def flatMap[B](f: A => Cont[R, B]): Cont[R, B] = ??? def map[B](f: A => B): Cont[R, B] = flatMap(a => Cont.pure(f(a))) }
33. 継続モナドの実装 object Cont { def pure[R, A](a: A): Cont[R, A] = Cont(ar => ar(a)) } final case class Cont[R, A](run: (A => R) => R) { def flatMap[B](f: A => Cont[R, B]): Cont[R, B] = Cont(br => ???) // 継続 br に対する計算結果を考える def map[B](f: A => B): Cont[R, B] = flatMap(a => Cont.pure(f(a))) }
34. 継続モナドの実装 object Cont { def pure[R, A](a: A): Cont[R, A] = Cont(ar => ar(a)) } final case class Cont[R, A](run: (A => R) => R) { def flatMap[B](f: A => Cont[R, B]): Cont[R, B] = Cont(br => run(a => f(a)/* Cont[R, B] */)) // 自身の継続に引数 f の結果を渡す def map[B](f: A => B): Cont[R, B] = flatMap(a => Cont.pure(f(a))) }
35. 継続モナドの実装 object Cont { def pure[R, A](a: A): Cont[R, A] = Cont(ar => ar(a)) } final case class Cont[R, A](run: (A => R) => R) { def flatMap[B](f: A => Cont[R, B]): Cont[R, B] = Cont(br => run(a => f(a).run(br))) // f から得られた継続に外側の継続を渡して実行 def map[B](f: A => B): Cont[R, B] = flatMap(a => Cont.pure(f(a))) }
36. 継続モナドの実装 object Cont { def pure[R, A](a: A): Cont[R, A] = Cont(ar => ar(a)) } final case class Cont[R, A](run: (A => R) => R) { def flatMap[B](f: A => Cont[R, B]): Cont[R, B] = Cont(br => run(a => f(a).run(br)) def map[B](f: A => B): Cont[R, B] = flatMap(a => Cont.pure(f(a))) }
37. 実装した継続モナドはモナド則を満たすか？ // ScalaCheck v1.14.0 を使用 class ContMonadSpec extends Properties("Monad[Cont[R, ?]]") { def inc(i: Int): Cont[Int, Int] = Cont(_(i + 1)) property("rightIdentity") = Prop.forAll { i: Int => inc(i).flatMap(Cont.pure).run(identity) == inc(i).run(identity) } property("leftIdentity") = Prop.forAll { i: Int => Cont.pure[Int, Int](i).flatMap(inc).run(identity) == inc(i).run(identity) } // ... }
38. 実装した継続モナドはモナド則を満たすか？ // ScalaCheck v1.14.0 を使用 class ContMonadSpec extends Properties("Monad[Cont[R, ?]]") { // ... def add_: Cont[String, String] = Cont(_(s + "!")) def add_?[R](s: String): Cont[String, String] = Cont(_(s + "?")) property("associativity") = Prop.forAll { s: String => Cont.pure(s).flatMap(add_!).flatMap(add_?).run(identity) == Cont.pure(s).flatMap(a => add_!(a).flatMap(add_?)).run(identity) } }
39. 実装した継続モナドはモナド則を満たすか？ sbt:check_cont_monad_law> test [info] + Monad[Cont[R, ?]].rightIdentity: OK, passed 100 tests. [info] + Monad[Cont[R, ?]].leftIdentity: OK, passed 100 tests. [info] + Monad[Cont[R, ?]].associativity: OK, passed 100 tests. [info] Passed: Total 3, Failed 0, Errors 0, Passed 3
40. 継続モナドを for 式で合成する def add[R](i: Int, j: Int): Cont[R, Int] = Cont(ar => ar(i + j)) def mul[R](i: Int, j: Int): Cont[R, Int] = Cont(ar => ar(i * j)) def show[R](i: Int): Cont[R, String] = Cont(ar => ar(s"num: $i")) def prog[R]: Cont[R, String] = for { a <- add(1, 2) b <- mul(a, 3) s <- show(b) } yield { s.toUpperCase }
41. 継続モナドを for 式で合成する scala> prog.run(s => s.toList) res18: List[Char] = List(N, U, M, :, , 9) scala> prog.run(s => s.length) res19: Int = 6 scala> prog.run(s => s) res20: String = NUM: 9
42. 継続モナドを for 式で合成する def prog[R]: Cont[R, String] = for { a <- add(1, 2) b <- mul(a, 3) s <- show(b) } yield { s.toUpperCase } def prog[R]: Cont[R, String] = add(1, 2).flatMap { a => mul(a, 3).flatMap { b => show(b).map { s => s.toUpperCase } } }
43. 継続モナドを for 式で合成する def prog[R]: Cont[R, String] = for { a <- add(1, 2) b <- mul(a, 3) s <- show(b) } yield { s.toUpperCase } def prog[R]: Cont[R, String] = add(1, 2).flatMap { a => mul(a, 3).flatMap { b => show(b).map { s => s.toUpperCase } } } ：Cont[R, A] { ar => ??? } の ar に渡される関数 　※厳密には ar には run の引数も含まれる
44. 継続モナドを for 式で合成する def prog[R]: Cont[R, String] = for { a <- add(1, 2) b <- mul(a, 3) s <- show(b) } yield { s.toUpperCase } def prog[R]: Cont[R, String] = add(1, 2).flatMap { a => mul(a, 3).flatMap { b => show(b).map { s => s.toUpperCase } } } ：Cont[R, A] { ar => ??? } の ar に渡される関数 　※厳密には ar には run の引数も含まれる
45. 継続モナドを for 式で合成する def prog[R]: Cont[R, String] = for { a <- add(1, 2) b <- mul(a, 3) s <- show(b) } yield { s.toUpperCase } def prog[R]: Cont[R, String] = add(1, 2).flatMap { a => mul(a, 3).flatMap { b => show(b).map { s => s.toUpperCase } } } ：Cont[R, A] { ar => ??? } の ar に渡される関数 　※厳密には ar には run の引数も含まれる
46. 継続モナドの「文脈」 各種モナドはそれぞれ何かしらの「文脈」を持つ。 ➢ Option モナド ◦ 値の有無、失敗しうる可能性のある計算 ➢ List モナド ◦ 複数の解があるような、非決定計算 ➢ State モナド ◦ 状態を持つような計算 では、継続モナドは？
47. 継続モナドの「文脈」 ❖ 継続を値として扱える計算
48. 継続モナドの活用
49. 継続モナドの活用例 ❖ 計算結果による分岐 ❖ エラーハンドリング ❖ リソースの管理 ❖ タイムアウト ❖ リトライ ❖ … etc ※ ここに列挙しているものは継続モナドでなくても実現可能です。
50. 【活用例】計算結果による分岐 def fizzCont(i: Int): Cont[String, Int] = Cont { cont => if (i % 3 == 0) { "Fizz" // 継続(cont)を実行しないので計算が "Fizz" で終了する } else { cont(i) // 継続(cont)に i を渡し、後続の処理を実行する } } // 以下、同様の実装 def buzzCont(i: Int): Cont[String, Int] = ... def fizzBuzzCont(i: Int): Cont[String, Int] = ...
51. 【活用例】計算結果による分岐 def fizzBuzz(i: Int): Cont[String, Int] = for { a <- fizzBuzzCont(i) b <- fizzCont(a) c <- buzzCont(b) } yield c scala> LazyList.from(1).map(fizzBuzz(_).run(_.toString)).take(15).toList res54: List[String] = List(1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz)
52. 【活用例】エラーハンドリング // - Some(a) の場合、継続に値(a)を渡して実行 // - None の場合、継続を破棄して ifNone の結果を返す def someValueOr[R, A](fa: Option[A])(ifNone: => R): Cont[R, A] = Cont(ar => fa.fold(ifNone)(ar)) // - Success(a) の場合、継続に値(a)を渡して実行 // - Failure(e) の場合、継続を破棄して ifFailure の結果を返す def successValueOr[R, A](fa: Try[A])(ifFailure: Throwable => R): Cont[R, A] = Cont(ar => fa.fold(ifFailure, ar))
53. 【活用例】エラーハンドリング // input より、指定された key に対応する値を取り出し、数値型に変換する def parseInt(input: Map[String, String], key: String): Cont[String, Int] = for { s <- someValueOr(input.get(key))(s"not found: $key") i <- successValueOr(Try(s.toInt))(_.toString) } yield i
54. 【活用例】エラーハンドリング // 例えば下記のような input を仮定すると val input = Map("name" -> "John", "age" -> "17") scala> parseInt(input, "address").run(i => s"result: $i") res99: String = not found: address scala> parseInt(input, "name").run(i => s"result: $i") res100: String = java.lang.NumberFormatException: For input string: "John" scala> parseInt(input, "age").run(i => s"result: $i") res101: String = result: 17
55. 【活用例】リソースの管理 // Loan パターンの例 def using[A <: AutoCloseable, B](a: => A, n: String)(f: A => B): B = try f(a) finally a.close() // Scala 2.13.0 から scala.util.Using が入った(話簡略化のため例外投げる版を使用 ) def resource[R, A](resource: R)(body: (R) => A)(implicit r: Releasable[R]): A // resource メソッドを継続モナドでラップ def resource[R, A](a: => A)(implicit r: Releasable[A]): Cont[R, A] = Cont(ar => Using.resource(a)(ar))
56. 【活用例】リソースの管理 def lines(reader: BufferedReader): Iterator[String] = ... // Using.Manager を使わず、しかも for 式で合成できる val prog: Cont[List[String], List[String]] = for { a <- resource(new BufferedReader(new FileReader("/tmp/file1.txt"))) b <- resource(new BufferedReader(new FileReader("/tmp/file2.txt"))) c <- resource(new BufferedReader(new FileReader("/tmp/file3.txt"))) } yield (lines(a) ++ lines(b) ++ lines(c)).toList scala> prog.run(identity) res140: List[String] = List(Hello, 1, Hello, 2, Hello, 3)
57. 【活用例】リソースの管理 // close() 実行時に println する独自 Releasable を定義 def r(n: String): Using.Releasable[AutoCloseable] = _.close().tap(_ => println(s"call close() for $n")) // Releasable を明示的に渡して実行 val prog: Cont[List[String], List[String]] = for { a <- resource(new BufferedReader(new FileReader("/tmp/file1.txt")))(r("f1")) b <- resource(new BufferedReader(new FileReader("/tmp/file2.txt")))(r("f2")) c <- resource(new BufferedReader(new FileReader("/tmp/file3.txt")))(r("f3")) } yield (lines(a) ++ lines(b) ++ lines(c)).toList
58. 【活用例】リソースの管理 // きちんとリソースの評価順と逆順に close() が実行されている scala> prog.run(identity) call close() for f3 call close() for f2 call close() for f1 res145: List[String] = List(Hello, 1, Hello, 2, Hello, 3)
59. 活用する際の注意点 - 例外処理 type User = String type Result = String def findAll[R](): Cont[Result, List[User]] = Cont { ar => try { ar(List("foo", "bar")) // DB への問い合わせは成功したとする } catch { case _: Throwable => "query execution error" } }
60. 活用する際の注意点 - 例外処理 // 全て成功する場合 val prog: Cont[Result, List[User]] = for { users <- findAll() names <- Cont.pure(users.map(n => s"[$n]")) } yield names scala> prog.run(_.mkString(", ")) res132: Result = [foo], [bar]
61. 活用する際の注意点 - 例外処理 // 継続の深いところで例外が投げられた場合 val prog: Cont[Result, List[User]] = for { users <- findAll() names <- Cont.pure(users.map(n => s"[$n]")) _ = 1 / 0 // java.lang.ArithmeticException: / by zero } yield names // 全く関係のないメッセージが ... scala> prog.run(_.mkString(", ")) res133: Result = query execution error
62. 活用する際の注意点 - 実行回数 // 後続の処理をなんとなく二回実行するやつ def twice: Cont[Unit, Unit] = Cont { ar => ar(()); ar(()) } // 絶対に一回しか実行して欲しくない DB への書き込み def insert(s: String): Cont[Unit, Unit] = Cont { ar => println("insert data to database") ar(()) }
63. 活用する際の注意点 - 実行回数 val prog: Cont[Unit, Unit] = for { _ <- twice _ <- insert("some data") } yield () // めでたく二回実行されてしまいました scala> prog.run(identity) insert data to database insert data to database
64. Conclusion
65. 継続モナドを使うメリット ➢ 様々な活用方法がある ◦ 「継続を値として扱える」という性質は想像以上に便利 ◦ 関数を用いた抽象的な概念なので、どのレイヤーでも使える ➢ 処理の流れを合成によって組み立てられる ◦ 継続モナドに限らないが、モナドであることのメリットの一つ ◦ for 式での合成は可読性向上にも寄与 ➢ 再利用性が高い ◦ 小さく作って、組み合わせて使える
66. 継続モナドを使うデメリット(注意点) ➢ 処理に適切に名前をつけないと、何をしているか分からなくなる ◦ 継続をどう扱ってるか、実装を読む必要が出てくる ◦ 複雑なことをすると実装を読んでも分からない場合もある ➢ 気をつけないと意図しない動作になる ◦ 実行回数例外処理などが自分の外側で管理される 複数回実行、意図しない箇所での例外 catch など ➢ for 式の順序と処理の流れ(見た目)が必ずしも一致しない ◦ かえって処理の流れの理解を妨げることも
67. まとめ ➢ 継続の概念と継続モナドの基本的な実装/動作を解説した ➢ エラーハンドリングやリソース管理など様々な場面で活用できる ◦ レイヤー問わず使える便利な道具。再利用性も高い。 ➢ 上手に活用するとシンプルに記述でき、可読性も向上する ◦ ただし直感的でない名前や複雑な実装は可読性が下がるだけでなく、 意図しない動作に悩まされることもある。 薬も過ぎれば毒になるので、用法・用量を守って正しくお使いください
68. Appendix ➢ 補足、参考資料、ソースコードメモなど ◦ https://gist.github.com/aoiroaoino/f017458c29d0b98eeaf239529f04af22