CoproductとInjectを使ったFree Monadの合成とExtensible Effects

scala scalaz free monad haskell

Scaladays2014の写真がtwitter上で流れてきて「あーまたrunaroramaさん、Free Monadの話してるのかー」と思ったら、たしかにFree Monadの話もしてたみたいですが、それの発展形(?)的な感じで、Coproductや、Injectという型クラス(?)の話をしていたようです。

それで、*1コードを読んでみたら、それなりにある程度理解できた気がするので、解説を書いてみます。*2


最初に断っておくと、タイトルに"Extensible Effects"と入れましたが、Extensible Effectsあまり理解できてないし、Extensible Effectsの詳しい話はほとんどしません。ただ、今回話すCoproductとInjectによるテクニックと関係してるらしい(?)ので入れました。*3


さて、まず今回話すことを理解するには、Free Monadをある程度わかってないといけません。自分なりのFree Monadの理解を(実用的にプログラムを書くのにあたって使うという視点で)適当にまとめると

  • Functorがあれば任意のデータ型をMonadにできる
  • Coyonedaを使えば Kind が * のものは、FunctorさえなくてもFree Monadにできる(それをOperational Monadと呼ぶらしい)
  • ある意味、IOモナドや、Readerモナドの代替というか、それらを組み合わせたような効果を表現できる(?)
  • FreeでDSLを作っておいて、それを実行するinterpreter*4を切り替えることによって、とても綺麗に副作用を切り離すことができたり、副作用*5の実行部分を超柔軟にあとから切り替えることができる(テストなどで便利)。DIフレームワークや、テスト用のモックライブラリなんていらなかったんや！


とかでしょうか？まぁ日本語でもFree Monadでググればある程度は記事あると思うので、それ読んでください。今回話すのは、Free Monadそのものが本題ではありません。その合成です。


Free MonadでDSLを作るのは便利です。たとえば、具体的には筆者はhttpzという、http clientライブラリをFree Monadで作ってます

https://github.com/xuwei-k/httpz

Haskellで日本人だと、fumiさんがfree-gameというゲーム用のライブラリ作ってたりするのが有名ですね

http://hackage.haskell.org/package/free-game

さて、そのような、ある領域に特化したDSLライブラリをFree Monadで作るのは便利ですが、普通ある程度の大きさのプログラムを書くときはライブラリを1種類だけ使って完結することのほうが少なく、いくつかのライブラリを組み合わせて使いますよね？たとえば、httpz を使ってリクエストを送りつつ、裏ではデータベースにアクセスして、データを保存したりするかもしれません。


組み合わせのやり方には色々あると思います。Monad Transformerが有名ですね。HaskellのFree*6にもFreeTというMonad Transformerがあるらしいです。残念ながらScalaでは、スタックをあふれないようにFreeTを実装することが難しい(というか不可能?)らしく、FreeTは実現できてませんが。

さて、そのように色々あるなかで、今回紹介するのは、なんと「任意のFree Monad同士は、自由に合成できる」という話です。ちなみに、他の手法よりどこが優れていて、どこが劣っているのか？あたりの話はしません(というか、そこまで理解できてないので、できません) *7


やっと本題の説明に入っていきますが、まずはrunaroramaさんのコードを見てみましょう。

https://gist.github.com/runarorama/a8fab38e473fafa0921d

上記のコードは、あえてScalazやその他のライブラリに依存させずに、pure scalaのみで書いてあります。上記のほうがわかりやすい人もいるかもしれませんが、結局Scalazにあるものをある程度再発明しています。

Scalazに入れるような汎用的なものなのか？それとも実際の例の部分なのか？が逆にわかりづらいので、最新のScalaz使って個人的に書き換えてみました。ちゃんとコンパイル通る状態になってるはずです


https://gist.github.com/xuwei-k/fd34a5889f40f6b937bf



もとのコードで再発明していた部分は

などです。Inject以外は、Scalazにある程度以前から存在するものですが、Injectは 7.1.0-M3 から入った新しいものです。現在Injectは7.0.x系にはバックポートされてません。
また、書き換えにあたり、Functorを定義するのが嫌だったというのもあって、CoyonedaをつかってOperational Monadにもしました。



まず、runaroramaさんの例では、以下のような2種類のデータ型が定義されています。

sealed trait Interact[A]
 
case class Ask(prompt: String) extends Interact[String]
 
case class Tell(msg: String) extends Interact[Unit]

sealed trait Auth[A]
 
case class Login(u: UserID, p: Password) extends Auth[Option[User]]
 
case class HasPermission(u: User, p: Permission) extends Auth[Boolean]


Interactのほうは、たとえばコンソールのような、なにか対話式のプログラムを生成するためのDSLです。Freeで包むと、以下のようにプログラムを組み立てることができます。

val prg = for {
  first <- ask("What’s your first name?")
  last  <- ask("What's your last name?")
  _      <- tell(s"Hello, $first, $last!")
} yield ()


上記の「プログラムの組み立て」自体はpureな操作で、実際実行するinterpeterを後から自由に切り替えられるのがFree Monadのポイントの一つでしたね。詳しくは解説しませんが、

  • 実際のコンソール入力のためのインタプリターを定義
  • テスト用に、Writerモナド相当のものを使ったInterperter

の2種類がコード中に定義されてるので、あとはコード読んでください。*8


さて、Authのほうは

  • ユーザーIDとpasswordを受け取る
  • ログイン成功すればUserのオブジェクトを返す

というようなアプリケーションのためのDSLです。ここでポイントなのは、このAuthのデータ型と最初のInteractのデータ型とは、全く独立して定義されている(そして、このあとにそれが組み合わせ可能)ということです。


「そもそも、1つのデータ型として定義してしまえば、組み合わせるとか考えなくて済むのでは？」という疑問を持つ人がいるかもしれません。
たしかにそうですが、その論法で推し進めると、一つのアプリを作るために、すべての状態を網羅した超巨大なデータ型を定義しないといけなくなります。また、他の人がFreeモナドで作ったライブラリと、組み合わせたい場合が出てくるはずですよね？なので、「1つのデータ型として定義」は、あまりいい方法とはいえないとおもいます*9

また、小さい単位でそれぞれデータ型を定義したほうが、プログラム自体がわかりやすいし、モジュール化にもなると思います。


さて、実際の組み合わせ方法ですが、これもまずはコードを見てみましょう

class Interacts[F[_]](implicit I: Inject[Interact,F]) {
  def tell(msg: String): FreeC[F, Unit] = lift(Tell(msg))
  def ask(prompt: String): FreeC[F, String] = lift(Ask(prompt))
}
 
class Auths[F[_]](implicit I: Inject[Auth,F]) {
  def login(id: UserID, pwd: Password): FreeC[F, Option[User]] =
    lift(Login(id, pwd))
  def hasPermission(u: User, p: Permission): FreeC[F, Boolean] =
    lift(HasPermission(u, p))
}
 
object Auths {
  implicit def instance[F[_]](implicit I: Inject[Auth,F]): Auths[F] = new Auths[F]
}
 
object Interacts {
  implicit def instance[F[_]](implicit I: Inject[Interact,F]): Interacts[F] = new Interacts[F]
}


"まずはコードを見てみましょう"と言いましたが、この部分を理論的に正しく説明できる知識はありません・・・（´・ω・｀）
この部分は、ある意味定形コードっぽくなってしまいます。FreeモナドでDSLを作る場合は、まずデータ型を作った後に、それらをFreeで包んだものを返すわけですが、今回のInjectとCoproductを使ったテクニックの場合には、さらにInjectを使って抽象化します。


普通のFree Monadのみだとしたら、たとえば

def tell(msg: String): FreeC[Intract, Unit] = lift(Tell(msg))

というようなメソッドを定義して、IntractのためのDSL なら、FreeC[Intract, A] (もしくはFree[Intract, A] ) というように、Freeの一つ目の型パラメータの部分には、そのDSLの元となるデータ型が当てはめられるはずです。しかし今回のものは、微妙に異なっていて、

def tell(msg: String): FreeC[F, Unit] = lift(Tell(msg))

と、F[_]という型で、さらにその部分が抽象化されたものになっています。


さて、上記のものはボイラプレート的な下準備の部分です。そして実際にプログラムを組んだ例が以下のコードです。

def prg[F[_]](implicit I: Interacts[F], A: Auths[F]) = {
  import I._; import A._
  for {
    uid <- ask("What's your user ID?")
    pwd <- ask("Password, please.")
    u <- login(uid, pwd)
    b <- u.map(hasPermission(_, KnowSecret)).getOrElse(freeCMonad[F].point(false))
    _ <- if (b) tell("UUDDLRLRBA") else tell("Go away!")
  } yield ()
}


それぞれ別のデータ型で定義した、別のDSLだったものが、先ほどのInjectの定義によってなんと一つのモナドになっています！

(試してませんが)これを応用すれば、おそらく2つではなく3つ、4つと、任意の数のFree Monadを自由に組み合わせていけるのだと思います。


ここで一つ重要なポイントは、組み合わせるためになにも制約がないことです。さきほどの少しボイラープレートなコードさえ書けば、「なんらかの型クラスを要求する」というようなものがありません！( kind が * な型なら、上記のようなInjectに関するコードは必ず可能)


これで大体の説明は終了した感じがあります。最後にinterpreterの部分の解説です。ここも面白いところですが、interpreterは新たに作る必要がなく、それぞれのInterpeterが"タダで"で合成できます！

今回の場合は、以下のように、Auth用のinterpeterと、Console用のinterpeterが定義されていました

// 例なので、ユーザー名が直接埋め込まれてるが、実際のアプリならDBへの問い合わせなどを内部でするべきもの

val TestAuth: Auth ~> Id = new (Auth ~> Id) {
  def apply[A](a: Auth[A]) = a match {
    case Login(uid, pwd) =>
      if (uid == "john.snow" && pwd == "Ghost")
        Some(User("john.snow"))
      else None
    case HasPermission(u, _) =>
      u.id == "john.snow"
  }
}

// これは実際に動かす例で、テスト用のinterpreterもある

object Console extends (Interact ~> Id) {
  def apply[A](i: Interact[A]) = i match {
    case Ask(prompt) =>
      println(prompt)
      scala.io.StdIn.readLine
    case Tell(msg) =>
      println(msg)
  }
}


もとのrunaroramaさんのコードの場合は、NaturalTransformationにorというメソッドが追加されていて、interpeter同士が合成できるようになってました。
が、Scalaz使う場合は、たぶんNaturalTransformationにメソッドを生やすより、独立した別のメソッドになっていたほうがいい気がしたので、以下のように定義しました。

def or[F[_], H[_], G[_]](
  fg: F ~> G, hg: H ~> G
): ({ type f[x] = Coproduct[F, H, x]})#f ~> G =
  new (({type f[x] = Coproduct[F,H,x]})#f ~> G) {
    def apply[A](c: Coproduct[F,H,A]): G[A] = c.run match {
      case -\/(fa) => fg(fa)
      case \/-(ha) => hg(ha)
    }
  }

F ~> G と H ~> G という2つのNaturalTransformationをもとに、({ type f[x] = Coproduct[F, H, x]})#f ~> G という、新たなNaturalTransformationを生成します。これが、合成後のプログラムを実行するためのinterpreterです。

この、NaturalTransformationの合成の部分は、おそらくこのパターンでFree Monadを合成すると必ず必要になる汎用的な部分です。なので、Scalaz本体に存在してるべき(だが、このblog書いてる現在は存在しない)なので、もしかしたらそのうち入るかもしれません。




さて、これで説明はおわりです。今回説明したテクニックは、もともと "Data types a la carte" というもので紹介されたもの(これが最初?)らしいです。もっと詳しく理論的な部分が知りたい人は、それを読みましょう

http://www.staff.science.uu.nl/~swier004/Publications/DataTypesALaCarte.pdf

また、この"Data types a la carte"が、Extensible Effectsと少し関係ある？(このあたりよくわかってない)らしいのですが、誰か教えてください・・・。

たとえばstackoverflowで

「“Data types à la carte” vs. nested FreeT transformers」
http://stackoverflow.com/q/21416561/605582

という面白い質問があるのですが、そこのコメント欄に

「ekmett said Extensible Effects ~= Datatypes à la carte + open unions. 」

とかあります。そのekmettさんが言ったというもののリンク先は、extensible effectsについて(完全にmtlの置き換えは不可能という意味で、ある程度否定的なことを書いた)redditです

http://www.reddit.com/r/haskell/comments/1j9n5y/extensible_effects_an_alternative_to_monad/cbcwbsa


ekmettさんは
「By the time you get done this is just the right Kan extension encoding of an open "data types a la carte" free monad, and they embed their effects into an open union type as the base functor.」

と言ってますね？(この意味もよくわかってない)



と、まぁ色々話は尽きないわけですが、別にこのあたりの理論を完璧に理解できてなくても、このInjectとCoproductを使ったFree Monadの合成のテクニック、普通に便利で実用的な気がしたので、なにか思いついたら実際に色々コード書いてみようと思います。

*1:これ最初に書いた時点ではスライドもビデオも公開されてなかったけれど、スライドはもう公開されました。videoはまだ？

*2:改めて日本語で解説書くだけなのと、多少scalaz使った例を追加した程度なので、べつに元の英語のスライド見て分かる人は必ずしも読む必要ないかも？

*3:関係あるどころか、そもそもExtensible Effectsの論文内で、"Data types a la carte" が数回参照されてるし、基本的には "Data types a la carte" の内容を受け継いで、色々と最適化などをしたものがExtensible Effectsという感じらしい？

*4:Scalazの場合なら、つまりそれはNaturalTransformationであり、たとえば runFC など https://github.com/scalaz/scalaz/blob/337ede30265b99/core/src/main/scala/scalaz/Free.scala#L328

*5:べつに副作用に限らなくていいけど

*6:https://github.com/ekmett/free

*7:そもそも、単なる優劣とかじゃなく、使い分けるべきとか、適用範囲違う、とかな気もする

*8:たとえば、これの実行をwebアプリ上でやろうと思えば、それも可能ということ

*9:ここ少し自信ない・・・