前回の記事では、ReaderモナドやFreeモナドを使ってDependency Injectionを行うための小さなDSLを組み立てた。今回の記事では、まず前回組み立てたDSLの課題であるExpression Problemと、それを解決するための機能Injectと、さらにはTagless Finalを用いたDSLについて述べる。
この記事は前回の記事の知識を前提としているので、分からない言葉などがある場合はまず前回の記事を参照して欲しい。また、文章について不明なことや意図が分かりにくい部分があれば気軽に指摘して欲しい。
注意：
記事の中にあるコードは読みやすさのためにimportなどを省略しているので、このままでは動かない。動かしたい方はGithubのリポジトリを使うとよい。
Expression Problem
Expression Problemとは、こちらのサイトを引用すると次のようになる。
- 静的型を使っていて
- 再コンパイルすることなく
- データ型や
- 操作を増やすのが難しい
ということになる。具体的な例を挙げると、まず今のTwitter操作DSLにツイートを削除する機能を追加しようとしたとする。まず次のようにデータ型を用意する。
sealed trait Twitter[A]
case class Fetch[A](screenName: String, next: WSResponse => A) extends Twitter[A]
case class Update[A](status: String, next: A) extends Twitter[A]
case class Delete[A](id: String, next: A) extends Twitter[A]
この時点では、先ほど既に書いたインタープリターとDSLはDeleteが存在しない時代に書かれたものなので、インタープリターはDeleteについてカバーしていなくてもよいことは自明であるが、Scalaのコンパイラにはそれが分からないので次のような警告が出る。
Warning:(14, 47) match may not be exhaustive.
It would fail on the following input: Delete(_, _)
def map[A, B](a: Twitter[A])(f: A => B) = a match {
^
警告を無視するというのも一つの手だが、ようするにこのアプローチでは一つの代数的データ型を参照するので、その代数的データ型を拡張するとそれを使っている既存のありとあらゆる関数が影響を受けてしまう。
そこで、InjectまたはTagless Finalを用いてこれを回避する。
InjectとCoproduct
Inject（Coproduct）の考え方は、今ある代数的データ型TwitterにDeleteを追加せずに、新たに次のような代数的データ型を作って対応するというものである。
sealed trait DeleteOfTwitter[A]
case class Delete[A](id: String, next: A) extends DeleteOfTwitter[A]
さて、これでTwitterを拡張してはいないのでExpression Problemは発生しないが、このTwitterとDeleteOfTwitterは関係のない型になってしまったので、一つの型としてまとめて取り扱うことができない。そこで、二つの型を取り扱えるようなデータ構造としてCoproductを導入する。
Coproduct
Coproductは次のように定義される。
case class Coproduct[F[_], G[_], A](value: Either[F[A], G[A]])
このように、valueとしてEitherの値を持つだけであるが、これだけで実はもう、TwitterとDeleteOfTwitterを混ぜ合わせることができる。
まず、これからの説明を簡単にするために次の型TwitterWithDeleteを作っておく。
type TwitterWithDelete[A] = Coproduct[Twitter, DeleteOfTwitter, A]
さて、TwitterとDeleteOfTwitterをCoproductを用いて混ぜるためには、Freeモナドの定義を思いだす必要がある。Freeモナドは次のような定義になっている。
case class Done[F[_]: Functor, A](a: A) extends Free[F, A]
case class More[F[_]: Functor, A](k: F[Free[F, A]]) extends Free[F, A]
注目するべきはMoreの引数kである。kの型はF[Free[F, A]]となっており、今までの例ではこのFにTwitterを入れて用いていた。ではTwitterのかわりにTwitterWithDeleteを入れて、つまりFree[TwitterWithDelete, A]とするとどうなるだろうか。そのためにはまず、TwitterWithDeleteの正体であるCoproductをファンクターにしなければならない。
object Coproduct {
implicit def coproductFunctor[F[_], G[_]](implicit F: Functor[F], G: Functor[G]) =
new Functor[({type L[A] = Coproduct[F, G, A]})#L] {
def map[A, B](a: Coproduct[F, G, A])(f: A => B): Coproduct[F, G, B] = a.value match {
case Left(e) => Coproduct[F, G, B](Left(F.map(e)(f)))
case Right(e) => Coproduct[F, G, B](Right(G.map(e)(f)))
}
}
}
一見するとややこしいが、Coproductの中身は単なるEitherなので、Eitherのmapとほとんど同じになる。
これでFree[TwitterWithDelete, A]が作れるようになったので、もう一度FreeにおけるMoreの定義を見直すことにする。
case class More[F[_]: Functor, A](k: F[Free[F, A]]) extends Free[F, A]
FにはTwitterWithDeleteが入るので、Moreの引数kの型はTwitterWithDelete[Free[TwitterWithDelete, A]]となる。TwitterWithDeleteの型パラメーターは何に用いられているのかというと、この型パラメーターはそれぞれTwitterとDeleteOfTwitterの型パラメーターとなっている。ではこれらの定義を見てみよう。
case class Fetch[A](screenName: String, next: WSResponse => A) extends Twitter[A]
case class Update[A](status: String, next: A) extends Twitter[A]
case class Delete[A](id: String, next: A) extends DeleteOfTwitter[A]
つまり、TwitterWithDeleteの型パラメーターFree[TwitterWithDelete, A]はnextの型として渡されていることになる。つまり、nextは次のような能力を持つことになる。
- 次の処理がある（
More）か無い（Done）か - → Freeモナドによる能力
- 次の処理がある場合、それが右（
Twitter）か左（DeleteOfTwitter）か - → Coproductによる能力
このように、CoproductでEither[Twitter, DeleteOfTwitter]の値を持つようにしたため、“どちらか”という能力が強化された。
これを使って次のように二つを併せたDSLを書くことができる1。
object TwitterWithDelete {
type TwitterWithDelete[A] = Coproduct[Twitter, DeleteOfTwitter, A]
def left[A](l: Twitter[A]): Either[Twitter[A], DeleteOfTwitter[A]] = Left(l)
def right[A](r: Delete[A]): Either[Twitter[A], DeleteOfTwitter[A]] = Right(r)
def coproduct[A](a: Either[Twitter[A], DeleteOfTwitter[A]]) = Coproduct[Twitter, DeleteOfTwitter, A](a)
def more[A](k: TwitterWithDelete[Free[TwitterWithDelete, A]]): Free[TwitterWithDelete, A] = More[TwitterWithDelete, A](k)
def done[A](a: A): Free[TwitterWithDelete, A] = Done[TwitterWithDelete, A](a)
val example: Free[TwitterWithDelete, Unit] =
more(coproduct(left(Update("new tweet", more(coproduct(right(Delete("<id>", done()))))))))
}
できあがったDSLは次の部分である。
more(coproduct(left(Update("new tweet", more(coproduct(right(Delete("<id>", done()))))))))
しかし、これはmore(coproduct(right(???)))のような部分が繰り返しあり、どう見ても使い勝手が悪い。なのでInjectを使ってこのDSLを改良する。
Inject
Injectとは次のような関数を提供する型クラスである。
sealed trait Inject[F[_], G[_]] {
def inj[A](sub: F[A]): G[A]
}
このInjectはF[A]からG[A]へ変換する関数（メソッド）injを提供する。FとGがなんでもよいとすれば、例えばList[Int]からOption[Int]へ変換できるということになるが、もちろんそんなことはなく、injを定義するためには次のいずれかの条件を満す必要がある。
これらのパターンについて、どうして関数injが定義できるのかを考える。
まず、最初のケースは元の型と行き先の型が同じFなので、受け取ったものをそのまま返せばよい。
次のパターンは、FはGについて何も知らなかったとしても、Coproduct[F, G, ?]の左側はFであるのでこちらへ行くことができる。
最後のパターンは、まずInject[F, G]を仮定するということについて考える。これを仮定するということはF[A]を引数に取りG[A]を返す関数injが存在するということになる。このinjを用いてまずF[A]をG[A]へ変換すれば、Coproduct[H, G, ?]の右側となるので、こちらへ行くことができる。
これをScalaのコードへ翻訳すると次のようになる。
object Inject {
implicit def reflexive[F[_]: Functor] = new Inject[F, F] {
def inj[A](a: F[A]): F[A] = a
}
implicit def left[F[_]: Functor, G[_]: Functor] =
new Inject[F, ({type L[A] = Coproduct[F, G, A]})#L] {
def inj[A](a: F[A]): Coproduct[F, G, A] = Coproduct[F, G, A](Left(a))
}
implicit def right[F[_]: Functor, G[_]: Functor, H[_]: Functor](implicit I: Inject[F, G]) =
new Inject[F, ({type L[A] = Coproduct[H, G, A]})#L] {
def inj[A](a: F[A]): Coproduct[H, G, A] = Coproduct[H, G, A](Right(I.inj(a)))
}
}
先ほどCoproductで作ったexampleを次のように書きなおせる4。
def inject[A](a: Twitter[A])(implicit I: Inject[Twitter, TwitterWithDelete]) =
I.inj(a)
def inject[A](a: DeleteOfTwitter[A])(implicit I: Inject[DeleteOfTwitter, TwitterWithDelete]) =
I.inj(a)
val example2: Free[TwitterWithDelete, Unit] =
more(inject(Update("new tweet", more(inject(Delete("<id>", done()))))))
さて、なんとかDSLを作ることができたので、後はこれのインタープリターを実装すればよい。
インタープリター
CoproductやInjectを使っても、インタープリターは同じように書ける。
def runTwitterWithDelete[A](dsl: Free[TwitterWithDelete, A], env: UseWSClient with UseOAuthCred): Unit = dsl match {
case Done(a) => ()
case More(x) => x.value match {
case Left(a) => a match {
case Fetch(screenName, f) =>
for {
fws <- fetchUserByScreenName(screenName).run(env)
} yield runTwitterWithDelete(f(fws), env)
case Update(status, next) =>
for {
_ <- updateStatus(status).run(env)
} yield runTwitterWithDelete(next, env)
}
case Right(b) => b match {
case Delete(id, next) => ???
}
}
}
ただ、これはFreeモナドとCoproductの入れ子構造がそのまま反映されており、もしTwitterWithDeleteに対して別のものをさらにInjectした際に大変面倒になる。そこでTwitterとDeleteOfTwitterに対するそれぞれのインタープリターを自然変換を用いて合成するという方法もあるが、この記事では割愛する5。
Tagless Final
Tagless Finalとは、プログラム言語に埋め込みDSLのインタープリターを作るためなどに用いられる手法である。こちらの手法は今まで行ってきたFreeモナドやCoproductとは一線を画する手法である。
InitialとFinal
この文章では次のような代数的データ型（ADT）を構築し、それのインタープリターを作成する伝統的な方法をInitialな方法と呼ぶ
sealed trait Twitter[A] case class Fetch[A](screenName: String, a: Future[WSResponse] => A) extends Twitter[A] case class Update[A](status: String, a: A) extends Twitter[A]
一方で、Tagless Finalではこのような代数的データ型を作成せずにインタープリターを構築する。Intialなアプローチと比較して次のような利点がある。
- ケースクラスのインスタンス化が必要ない
- GADT（一般化代数的データ型）が必要ない6
- Expression Problemを回避することができる
- Higher-order Abstract Syntax（HOAS：高階抽象構文）7を使うことができる
この記事では主にExpression Problemの回避に注目してInitialな方法と比較する。
Expression Problemの回避
Tagless FinalではFreeモナドなどを用いたInitialなアプローチで行なわれていたような、Twitterのような代数的データ型を定義しない。Tagless Finalでは型クラスを用いてDSLを表現する。
trait TwitterSYM[R[_]] {
def string(str: String): R[String]
def fetch(screenName: R[String]): R[WSResponse]
def getScreenName(str: R[WSResponse]): R[String]
def update(status: R[String]): R[String]
}
これを用いて、実際のインタープリターを次のように実装する。
object TwitterSYMInterpreter {
type Twitter[A] = Reader[UseWSClient with UseOAuthCred, A]
implicit val twitterSYMInterpreter = new TwitterSYM[Twitter] {
def string(str: String): Twitter[String] = pure(str)
def fetch(screenName: Twitter[String]): Twitter[WSResponse] =
for {
sn <- screenName
env <- ask
} yield {
Await.result(
env.client.url("https://api.twitter.com/1.1/users/show.json")
.withQueryString("screen_name" -> sn)
.sign(env.cred)
.get(),
Duration.Inf
)
}
def getScreenName(res: Twitter[WSResponse]): Twitter[String] =
for {
raw <- res
env <- ask
} yield (raw.json \ "screen_name").as[String]
def update(status: Twitter[String]): Twitter[String] =
for {
s <- status
env <- ask
} yield {
val res = Await.result(
env.client.url("https://api.twitter.com/1.1/statuses/update.json")
.sign(env.cred)
.post(Map("status" -> Seq(s))),
Duration.Inf
)
(res.json \ "id_str").as[String]
}
}
}
まず型Twitterを定義している。これまでのFreeモナドの例でも同じ名前の型が登場したが、それとは異なるので注意して欲しい。
Tagless Finalはこのように、インタープリターを型クラスTwitterSYMのインスタンスとして定義し、これらのインスタンスを呼び出すという形をとる。
def string(str: String)(implicit T: TwitterSYM[Twitter]): Twitter[String] =
T.string(str)
def fetch(screenName: Twitter[String])(implicit T: TwitterSYM[Twitter]): Twitter[WSResponse] =
T.fetch(screenName)
def getScreeName(res: Twitter[WSResponse])(implicit T: TwitterSYM[Twitter]): Twitter[String] =
T.getScreenName(res)
def update(status: Twitter[String])(implicit T: TwitterSYM[Twitter]): Twitter[String] =
T.update(status)
これだけでもはやDependency InjectionのためのDSLとしての機能を持っている。次のように使うことができる。
update(
getScreeName(fetch(string("_yyu_")))
).run(DefaultEnvironment.defaultEnvironment)
さて、それではFreeの時のようにツイートを削除する機能を後から追加する。先ほど定義したTwitterSYMは型クラスなので、次のように新たな型クラスを追加するだけでExpression Problemを回避することができる。
trait DeleteSYM[R[_]] {
def delete(id:R[String]): R[Boolean]
}
そして、インタープリターもこれのインスタンスとして定義する。
object DeleteSYMInterpreter {
type Twitter[A] = Reader[UseWSClient with UseOAuthCred, A]
implicit val deleteInterpreter = new DeleteSYM[Twitter] {
def delete(id: Twitter[String]): Twitter[Boolean] =
for {
idStr <- id
env <- ask
} yield {
val res = Await.result(
env.client.url(s"https://api.twitter.com/1.1/statuses/destroy/${idStr}.json")
.sign(env.cred)
.post(Map("id" -> Seq(idStr))),
Duration.Inf
)
res.status == 200
}
}
def delete(id: Twitter[String])(implicit T: DeleteSYM[Twitter]): Twitter[Boolean] =
T.delete(id)
}
次のように組み合せられる。
delete(
update(
getScreeName(fetch(string("_yyu_")))
)
).run(DefaultEnvironment.defaultEnvironment)
このように、Tagless Finalは先ほどInjectなどを用いて行った処理の追加を比較的簡単に行うことができる。
Higher-order Abstract Syntax
Higher-order Abstract Syntax（HOAS）とは、変数を束縛するような処理をターゲット言語8に実装する際に、束縛する変数を対象言語のインタープリターなどが取り扱うのではなくて、ホスト言語（Scala）の機能を直接使って実装するテクニックのことである。
例えばこのDSLに変数を束縛して後の式で使うための構文letを使用して、OCamlのように書きたいとする。
let a = string("_yyu_") in
let b = fetch(a) in
let c = getScreeName(b) in
let d = update(c) in delete(d)
このようにaやbといった変数に処理の結果を束縛するような機能をDSLとして提供したい時にHOASは便利である。なぜなら、今回の例では変数名を全て別にしたが、実際にはある変数と同じ変数名が使われることがあり、それらを区別するためにはDe Bruijn Indexなどを用いてプログラムの中にある変数を数字へ変換する必要があるなど、変数束縛の処理は一般的に手間がかかる。ところが、HOASを用いれば変数はScalaの変数をそのまま用いるので、変数の管理をDSLのインタープリターやコンパイラーがする必要はない。
では、実際にTwitterのDSLにHOASのlet文を用意する。まず、次のような型クラスを作る。
trait LetInSYM[R[_]] {
def let[A, B](a: => R[A])(l: R[A => B]): R[B]
def in[A, B](a: R[A] => R[B]): R[A => B]
}
そしてインタープリターを次のように実装する。
object LetInSYMInterpreter {
type Twitter[A] = Reader[UseWSClient with UseOAuthCred, A]
implicit val letInInterpreter = new LetInSYM[Twitter] {
def let[A, B](ta: => Twitter[A])(tf: Twitter[A => B]): Twitter[B] =
for {
a <- ta
f <- tf
} yield f(a)
def in[A, B](f: Twitter[A] => Twitter[B]): Twitter[A => B] = {
reader(e => (x: A) => f(pure(x)).run(e))
}
}
def let[A, B](a: => Twitter[A])(f: Twitter[A => B])(implicit T: LetInSYM[Twitter]): Twitter[B] =
T.let(a)(f)
def in[A, B](f: Twitter[A] => Twitter[B])(implicit T: LetInSYM[Twitter]): Twitter[A => B] =
T.in(f)
}
次のように用いる。
let (string("_yyu_")) (in (a =>
let (fetch(a)) (in (b =>
let (getScreeName(b)) (in (c =>
let (update(c)) (in (d =>
delete(d)
)))))))).run(DefaultEnvironment.defaultEnvironment)
このように、変数を用いているにも関わらず、変数を取り扱う部分をインタープリターに書かなくてもよく実装が大変楽になる。
Inject vs Tagless Final
Tagless Finalにおけるパターンマッチ
Freeモナドを用いた場合、FetchやDeleteといったDSLの命令に対応するケースクラスでパターンマッチができるが、一方でTagless Finalにはケースクラスに相当するものが存在しないので、木構造のデータを取り扱えないように一見すると思える。しかし、それについては解決策が存在する。これについて詳しく知りたい方はTyped Tagless Final Interpretersを参照して欲しい。
Olegさんの指摘
Lambda-the-Ultimateというサイトに、Tagless Finalの論文を発表した著者の一人であるOlegさんによるExpression problem solutions in Haskellという投稿がある。
Tagless-final approach also easily solves the expression problem, both in the first-order and higher-order cases. In the higher-order case, tagless-final permits (very convenient) higher-order abstract syntax. `Data Types a la Carte'9 or other initial encodings cannot handle HOAS because of the contra-variant occurrences of the recursive data type.
これによると、Coproductなどを用いたInitialなアプローチではHOASを取り扱えないと述べられている。再帰的なデータ型ではHOASを取り扱えないという根拠はよく分からないが、少なくともOlegさんはこのように主張している。
まとめ
個人的な感想としては、Tagless Finalの方がInjectやCoproductを使ってDSLを構成するよりもシンプルに思える。この記事でInjectとTagless Finalの性能評価を行う予定であったが、記事が長くなったので次の機会にしようと思う。Tagless Finalを用いたDSLがDependency Injectionのために使われる未来もあるかもしれない。
参考文献
- Free-ScalikeJDBC から見る合成可能なDSLの作り方
- Compositional Application Architecture With Reasonably Priced Monads
- インタプリタ
- Typed Tagless Final Interpreters
- Data types à la carte
- CoproductとInjectを使ったFree Monadの合成とExtensible Effects
- Finally Tagless, Partially Evaluated: Tagless Staged Interpreters for Simpler Typed Languages
- Dependency InjectionとDSL
- Expression problem solutions in Haskell
- 関数型SCALA 型クラス編
-
leftやrightなどといった大量の補助関数は、Scalaの型推論を補助するために定義されている。 ↩ -
Coproductの部分は実際、({type λ[A] = Coproduct[F, G, A]})#λであるが、見やすさのためこのように表記した。 ↩ -
こちらも正しくは、
({type λ[A] = Coproduct[H, G, A]})#λであるが、見やすさのためこのように表記した。 ↩ -
moreの部分が繰り返し表われていて、これを取り除きたかったが、Scala上で上手く型を付けることができなかった。 ↩ -
この手法に興味がある方は、Compositional application architecture with reasonably priced monadsが参考になる。 ↩
-
Scalaには一般化代数的データ型があるので、この部分は大きなメリットになり得ないかもしれない。他にこの機能を持つ言語として例えばOCamlやHaskell、Haxeがある。 ↩
-
HOASについては後述する。 ↩
-
実装の対象となるプログラム言語を指し、この記事ではTwitter用のDSLに対応する。 ↩
-
この記事の前部で触れたCoproductとInjectによるExpression Problemの回避法について述べた論文。 ↩