Freeモナドで領域特化言語を作るとプリティミューテーション

多くのプログラミング言語が用途を限定しない汎用の言語として設計されているのに対して、**領域特化言語**(ドメイン固有言語, domain-specific language, DSL)は何らかの目的に特化して設計された言語のことをいいます。領域特化言語を導入する利点のひとつは、プログラムの各部分の役割が明確になり、ソフトウェア全体の設計がよりわかりやすくなるというものがあります。たとえば、ゲームソフトウェアではゲームの描画とゲームの状態更新は完全に分離されているべきです。ゲームで一時的に処理が重くなり、描画を何フレームかスキップして速度を維持したいとしましょう。もし状態更新と描画がきちんと分離されていなければ、描画だけをうまくスキップするということはできなくなってしまいます。もし描画専用の領域特化言語を導入すると、ソフトウェアのコードをその内容に沿って完全に分離するのを強制し、それに違反するようなコードをコンパイル時に防ぐことができます。

Freeモナドを使うと、一定の手順にしたがって命令群を定義するだけで、簡単にそのような領域特化言語を構成する事ができます。しかも、あくまでその領域特化言語は元のプログラミング言語の上で構成されているので、構文そのものは元のプログラミング言語そのままですし、純粋な計算については何ら制限なく自由に使うことができます。しかも、その領域特化言語で書かれたプログラムはデータとして扱うことができ、その解釈を動的に切り替えるようなことも可能です。プログラムをデータとして動的に操作できるというとまるでLisp/Schemeのようですが、Lispのような動的な型付けで何でもありのリストとは異なり、Freeモナドなら静的型付けの上で型安全な言語を定義することができます。動的に命令列を構成し、その解釈も動的に自由に切り替えられる柔軟さと、誤った命令をコンパイル時に検出できる堅牢さを同時に達成できるわけです。

# 領域特化言語を使ってみる

まずは領域特化言語を使ったコードがどのようになるのかを見てみましょう。何か仮想的な命令体系を想定して説明するのもいいですが、既知のAPIのほうが理解も早いだろうということと、現実のAPIを使うことで実用性を匂わせておきたいという意図で、HTML5の[CanvasグラフィックスAPI](https://developer.mozilla.org/ja/docs/Web/Guide/HTML/Canvas_tutorial)に基づいた領域特化言語を考えてみます。これとほぼ同様のものが[purescript-free-canvas](https://github.com/paf31/purescript-free-canvas/)で実装されています。

最近筆者はPureScriptばかりいじっているのでPureScriptの文脈で説明をしていきますが、もちろん他の言語でも同様のことができるはずです。構文もHaskellとほとんど同じなので、雰囲気で理解できると思います。

このテキストで作る領域特化言語には、以下のようなCanvas APIに対応する3つの命令があります。これらは実のところただのPureScriptの関数に過ぎません。

```hs
setFillStyle :: String -> Graphics Unit
measureText :: String -> Graphics TextMetrics
fillText :: String -> Number -> Number -> Graphics Unit
```

`Graphics a`がモナドなので、いつものようにdo記法でだらだらと命令を並べて描画の内容を記述することができます。

```hs
paint :: Graphics Unit
paint = do
    let text = "Lorem ipsum dolor sit amet"
    metrics <- measureText text
    setFillStyle "red"
    fillText text (100.0 - metrics.width) 20.0
```

この`Graphics a`はキャンバスグラフィックス専用のモナドですから、例えば意図しないDOM操作をうっかりねじ込んでしまうというようなことは起こりえません。確実にコンパイルエラーになります。

```hs
paint :: Graphics Unit
paint = do
    let text = "Lorem ipsum dolor sit amet"
    metrics <- measureText text
    appendChild parent child -- コンパイルエラー！勝手にDOMをいじるんじゃない！
    setFillStyle "red"
    fillText text (100.0 - metrics.width) 20.0
```

DOM操作のような別の作用を描画の部分に埋め込むことは禁止されますが、純粋な計算であれば状態に一切悪影響を与えませんから、この領域特化言語内で自由に利用可能です。`100.0 - metrics.width`のような数値計算には何の制限もありません。独自の領域特化言語といっても、PureScript本来の表現力が失われることはありません。

ここで各命令の引数にグラフィックスコンテキストを与えていないことにも注目してください。JavaScriptだと

```js:JavaScript
context.measureText(text)
```

というようにコンテキストも指定しなければなりませんが、ここでは

```hs
measureText text
```

だけの指定で呼び出せています。どのコンテキストに対して描画命令を出すかという構造も分離されているのです。コンテキストを渡さなくて済むのは、単にコーディングの手間が省けるという意味でも便利です。念の為に言っておきますが、決してグラフィックスコンテキストをグローバルに共有しているわけではありません。

また、すでにHaskellやPureScriptを使っている方には言うまでもないようなことですが、同じ命令を繰り返したければいつもの`for`や`for_`を再利用することができます。領域特化言語専用の`for`を改めて定義する必要はありません。`if-then-else`や`when`もいつもどおりです。

```hs
for_ (range 1 3) \i -> do
    fillText text (100.0 - metrics.width) (20.0 * toNumber i)
```

この一連の描画命令を実際に実行するのは、`runGraphics`という関数を呼び出すだけなので簡単です。グラフィックコンテキストを明示的に渡すのはここの一度だけです。

```hs
runGraphics paint context
```

Freeモナドを使うと、こういった領域特化言語を刺し身の上にタンポポを載せるような単純作業で定義することができます。




# Freeモナドを使って領域特化言語を作る

## ライブラリの準備

PureScriptでは[purescript-free](https://github.com/purescript/purescript-free)というモジュールがあって、Freeモナドが一連のライブラリとして提供されています。Haskellだと[ekmett/free](https://github.com/ekmett/free)がありますし、Scalaなら[scalaz](https://github.com/scalaz/scalaz)がよさそうです。その他の言語でももちろん可能ですが、HaskellやPureScriptでさえ結構手順が面倒なので、強力な型システムやモナド用の糖衣構文がない言語ではなかなか苦しいと思います。

Freeモナドを自力で定義してもそれほど大変ではありません。自力で定義したいかたは、記事末尾に挙げた参考文献を御覧ください。

## 命令セット

まずはその領域特化言語にどんな命令を用意するか検討します。説明のためだけに[CanvasRenderingContext2D](https://developer.mozilla.org/ja/docs/Web/API/CanvasRenderingContext2D)のすべてのAPIを実装するわけにはいかないので、以下の３つの命令だけ用意することにしましょう。

```ts:TypeScript
interface CanvasRenderingContext2D { 
    fillStyle: String;
    measureText(String text): TextMetrics;
    fillText(text: String, x: Number, y: Number): void
}
```

これに対応する、領域特化言語でない、直接の作用を起こすほうのAPIの定義は以下のようになります。これは後で解釈関数というのを実装するときに、低レベルなAPIとして使います。

```hs
_setFillStyle :: forall eff . String -> Context2D -> Eff (canvas :: Canvas | eff) Unit

_measureText :: forall eff . String -> Context2D -> Eff (canvas :: Canvas | eff) TextMetrics

_fillText :: forall eff . String -> Number -> Number -> Context2D -> Eff (canvas :: Canvas | eff) Unit
```

## データ型

それでは実際に領域特化言語を作っていきます。最初に、先ほどの命令群に対応するデータ型`GraphicsF`を定義します。代数的データ型を使い、各命令が受け取る引数をフィールドとして持つようなコンストラクタを与えます。

```hs
data GraphicsF more = SetFillStyle String more
                    | MeasureText String (TextMetrics -> more)
                    | FillText String Number Number more
```

このとき、幾つかポイントがあるので注意してください。

* このデータ型には型変数`more`を持たせます。この謎の型変数の意味についてはFreeモナドそのものの定義について調べてみるとわかりますが、このテキストでは気にしないことにします。
* 実行した結果を返さないような命令の場合は、それぞれのコンストラクタの最後のフィールドとして`more`を付け加えます。例えば、`SetFillStyle`はこの命令の結果のようなものはないので、そのまま`more`を付け加えます。
* 実行した結果を返すような命令の場合は、その命令が返す値の型から`more`へ写す関数をフィールドの最後に付け加えます。例えば、`MeasureText`は命令を実行した結果として`TextMetrics`を返しますが、コンストラクタのフィールドの最後に`TextMetrics -> more`を付け加えます。

なお、ここではグラフィックスコンテキストと分離したいので、`Context2D`はフィールドに加えていません。

## Functorのインスタンス

また、`Free`と組み合わせるには`GraphicsF`に`Functor`のインスタンスが(ひとまずは)必要です。ここがちょっとめんどうくさいですが、それぞれのコンストラクタの最後の追加のフィールドのところに関数`f`を噛ませるだけです。

```hs
instance functor_GraphicsF :: Functor GraphicsF where
    fmap f (SetFillStyle style more) = SetFillStyle style (f more)
    fmap f (MeasureText text more) = MeasureText text (f <<< more)
    fmap f (FillText text x y more) = FillText text x y (f more)
```

HaskellだとFunctorを自動で導出できるので簡単ですが、PureScriptにはインスタンスの導出がありません。どうせ単純作業なので、ここでは頑張って自力で定義しますが、実は後述するようにFunctorのインスタンスを自分で書かずに作るテクニックがあります。

## 型の別名

型名としては`Free GraphicsF a`というように`Free`に`GraphicsF`を埋め込んだ形で使うことが多いので、これを別名としておくと便利です。それに、このライブラリを使う側から見ればそれが内部的に`Free`を使っているかどうかは興味のないことなので、隠してしまうという意味もあります。

```hs
type Graphics a = Free GraphicsF a
```

`type`(型の別名)だと中身が`Free`だというのがモロ見えになってしまうので、`newtype`で新しい型を与えて中身を隠してあげるほうが好きな人もいるでしょう。

```hs
newtype Graphics a = Graphics (Free GraphicsF a)
```

たぶん実用上は後者のほうがいいと思いますが、ここでは簡単のために前者の`type`のほうにしておきます。

## 命令

Freeモナドのライブラリには次のような関数`liftF`が定義されています。

```hs
liftF :: forall f a. f a -> Free f a
```

`liftF`は任意の`f a`を`Free f a`という値に『持ち上げる』(lift)関数で、つまり`GraphicsF a`を`Free GraphicsF a`に変えることができます。つぎに`GraphicsF`の各コンストラクタをこの`liftF`で持ち上げ、実際のFreeモナドの値を返すような関数にします。各コンストラクタの最後のフィールドは`unit`や`id`で埋めておきます。

```hs
setFillStyle :: String -> Graphics Unit
setFillStyle s = liftF $ SetFillStyle s unit

measureText :: String -> Graphics TextMetrics
measureText s = liftF $ MeasureText s id

fillText :: String -> Number -> Number -> Graphics Unit
fillText s x y = liftF $ FillText s x y unit
```

ここもめんどうくさいボイラープレートなのですが、PureScriptにはTemplate Haskellのような邪悪なメタプログラミングの仕組みがないので、善の魔法使いである我々はひたすら脳が退化しそうな単純作業に没頭します。命令が3つくらいなら大丈夫ですが、命令の数が多いとここでげんなりしてきます。

これが終われば、命令列を領域特化言語として構成することができるようになりますが、まだこの命令列を実際に実行する機能は与えられていません。



## 解釈関数


最後に、データとして与えられた命令群を実際に解釈して別の何かへと変える関数を実装します。ここでは関数`runGraphics`を定義して`Graphics`をPureScriptのネイティブな作用の型`Eff eff a`に変換して実際に実行可能にします。`Free f a`の値を変換するには、*本来なら(後述)*次のような`foldFree`という関数を使います。

```hs
foldFree :: forall f m a. (Functor f, MonadRec m) => NaturalTransformation f m -> Free f a -> m a
```

ここで`Functor f`の制約があるため。`GraphicsF`に`Functor`のインスタンスが必要だったわけです。

`runFreeM`の最初の引数に渡す関数`interpret`を`runGraphics`の内部で定義しますが、`interpret`では`GraphicsF`のフィールドからデータを取り出して実際の作用を起こすための関数にせっせ移し替え、あとは型の辻褄を合わせるために`const a <$> `や`k <$>`みたいな式を機械的にくっつけます。`interpret`の実装も単調な作業です。

```hs
runGraphics :: forall a eff. Context2D -> Graphics a -> Eff (canvas :: Canvas | eff) a
runGraphics ctx = foldFree interpret
  where
    interpret :: Natural GraphicsF (Eff (canvas :: Canvas | eff))
    interpret (SetFillStyle s a) = const a <$> _setFillStyle s ctx
    interpret (MeasureText s k)  = k <$> _measureText s ctx
    interpret (FillText s x y a) = const a <$> _fillText s x y ctx
```

`Natural`という謎の型コンストラクタが出てきていますが、これは次のような関数の型の別名です。

```hs
type Natural f g = forall a. f a -> g a
```

こういうのを[自然変換](https://ja.wikipedia.org/wiki/%E8%87%AA%E7%84%B6%E5%A4%89%E6%8F%9B)(Natural Transformation)というそうで、型が示している通り`interpret`は関手`GraphicsF`を関手`Eff (canvas :: Canvas | eff)`に変換しているということを意味しています。関数型プログラミングの界隈では圏論の言葉を使って肝試しをするのが流行っていますが、幽霊の正体を見てみたら枯れ尾花だったりすることもよくあるわけで、ここでビビって帰ってしまったら負けです。圏論なんてよくわかりませんが、とにかく型とにらめっこして型パズルを解きさえすればこっちのものです。

作業はこれで完了です。それなりの作業量はあるものの、一旦理解してしまえばここまでの手順はまったくの単純作業です。時給800円くらいで領域特化言語を定義するアルバイト(未経験可)とかありそうです。

ここでは`Eff eff a`に変換して実際に描画する翻訳関数だけを定義しましたが、これとは全然別の複数の翻訳関数を与えることもできます。たとえば、各命令の呼び出しをロギングしたりとか、あるいはリモートのターゲットに対しての描画命令に変換したりできるかもしれません。活かすも殺すも解釈関数しだいです。






## CoyonedaでFunctorを作る

先ほどの過程では、`GraphicsF`の`Functor`インスタンスを自力で定義しなければならないという面倒くさい手順がありました。Haskellだとインスタンスの自動導出でこれを避ける事ができますが、PureScriptではそうはいきません。ところが、インスタンスの導出がなくてもうまい回避策があって、`Coyoneda`というデータ型を使うと、どんなデータ型からでも勝手に`Functor`が構成できてしまうのです。`Coyoneda`の値を作るのは簡単で、次の`liftCoyoneda`という関数を適用するだけです。

```hs
liftCoyoneda :: forall f a. f a -> Coyoneda f a
```

`f`に何の制約もありません。どんな値`f a`でも`liftCoyoneda`であっさりと`Coyoneda f a`の値にすることができてしまいます。そして、

```hs
instance functorCoyoneda :: Functor (Coyoneda f)
```

というように、`f`に何の制約もなくこの`Coyoneda`は`Functor`なのです。こわい。

それでは、今度は`Free`に直接`GraphicsF`を埋め込むのではなく、代わりに`Coyoneda GraphicsF`を埋め込んでみます。

```hs
type Graphics a = Free (Coyoneda GraphicsF) a
```

それぞれの命令の定義も、間に`liftCoyoneda`を挟んで持ち上げるだけ。

```hs
setFillStyle :: String -> Graphics Unit
setFillStyle s = liftF $ liftCoyoneda $ SetFillStyle s unit

measureText :: String -> Graphics TextMetrics
measureText s = liftF $ liftCoyoneda $ MeasureText s id

fillText :: String -> Number -> Number -> Graphics Unit
fillText s x y = liftF $ liftCoyoneda $ FillText s x y unit
```

`runGraphics`も、解釈関数`interpret`を`liftCoyonedaTF`で持ち上げるだけ。よっこいしょ。

```hs
runGraphics :: forall a eff. Context2D -> Graphics a -> Eff (canvas :: Canvas | eff) a
runGraphics ctx = runFreeM $ liftCoyonedaTF interpret
  where
    interpret :: Natural GraphicsF (Eff (canvas :: Canvas | eff))
    interpret (SetFillStyle s a) = const a <$> _setFillStyle s ctx
    interpret (MeasureText s k)  = k <$> _measureText s ctx
    interpret (FillText s x y a) = const a <$> _fillText s x y ctx
```

`Coyoneda`を絡めるだけで、`GraphicsF`に`Functor`インスタンスを与えずに領域特化言語を定義できてしまいました。

`Functor`でないただのデータ型で`Functor`を構成できるとかどう見ても超常現象ですし、おそらくCoyonedaは何か強力な魔術の類だと思うのですが、残念ながら筆者の魔力が不足しているためこれ以上のことはわかりませんでした。ふしぎ！


## purescript-freeの実装

Haskellのekmett/freeのほうでは、`Free f a`のモナドインスタンスは

```hs
instance Functor f => Monad (Free f)
```

というように`f`に`Functor f`の制約がかかっていて、`GraphicsF a`のような型は`Functor`のインスタンスがないと`Free GraphicsF a`がモナドになりません。これが本来のシンプルなFreeモナドなのですが、実はpurescript-freeの実装では最初から`Coyoneda`に相当する構造が埋め込まれているため、`GraphicsF a`に`Functor`のインスタンスは必要ありません。先程は`foldFree`に`Functor f`の制約がかかっているというようなことを言いましたが、それは古いバージョンの話で、現在では以下のように`Functor f`の制約はなくなっています。

```hs
foldFree :: forall f m a. (MonadRec m) => NaturalTransformation f m -> Free f a -> m a
```

同様に`Free f`のモナドインスタンスのほうも`Functor f`の制約がなくなっています。

```hs
instance freeMonad :: Monad (Free f)
```

こうなっているのはどうも最適化の都合のようです。というわけで、purescript-freeを使う場合は明示的にCoyonedaでこよこよする必要はありません。





# さいごに

特定の問題領域に特化した言語を作るのは、ソフトウェアの堅牢さを保証する最も強力な手法のうちのひとつだと思います。そして、`Free`を使えば領域特化言語を作るのは決して難しくはありません。

単にコードの一部に制約を加えたいということであれば、PureScriptでは他にもExtensible Effectsで制御する方法があります。Freeモナドでも複数の種類の作用を混ぜる方法がありますが、他の作用と混ぜたいという場合はExtensible Effectsのほうが便利なときも多いでしょうし、解釈を動的に切り替えたいという場合はやはりFreeモナドを選ぶことになるでしょう。この辺りは目的に応じて使い分けることになると思います。

説明の多くは[Why free monads matter - Haskell for all](http://www.haskellforall.com/2012/06/you-could-have-invented-free-monads.html)を参考にしています。Freeモナドの中身にあまり興味がなくて、とにかく領域特化言語を定義するために道具として使えれば何でもいいやという人もいるでしょうし、Freeモナドがそもそもどのように定義されているのかという説明はこのテキストでは意図的にすべてばっさり省きました。"Why free monads matter"では、そもそもFreeモナドそのものはどのように定義されているのか、どのような考え方で導出するのかとか、FreeモナドはFunctorの不動点なんだとか、Freeモナドで並列処理っぽいものを実装してみるというような面白い話題が数多く紹介されています。興味のある人は是非読んでみることをおすすめします。

ところで、ここで作った言語というのはあくまでPureScriptの言語の構文の範疇にありますが、こう言ったものは**内部領域特化言語**(internal domain-specific language, 内部DSL)と呼ばれているようです。領域特化言語というと、筆者としてはCSSやGLSLみたいに、母体となる言語とは互換性のない全然別の言語というイメージなのですが、こういうCSSのような元の言語と互換性のないものは外部DSL(external domain-specific language)とというようです。でも内部領域特化言語といってもどうせ単なるモナドですし、これを領域特化言語なんて大仰な名前で呼んでいいものかという気もします。だっていつものPureScriptのソースコードなんですから。そんなに大袈裟なことはしていません。

# キャンペーンおよび追加情報

* FRP特集：話題のファンクショナル・リアクティブ・プログラミングを体験したいかたに、[purescript-halogen](https://github.com/slamdata/purescript-halogen)がおすすめ！purescript-freeも内部で使われています。

# この文章を読んだ人はこんな文章も読んでいます

* Gabriel Gonzalez, [Why free monads matter - Haskell for all](http://www.haskellforall.com/2012/06/you-could-have-invented-free-monads.html)
* Edward Kmett, [Monads for Free](http://comonad.com/reader/2008/monads-for-free/)
* Phil Freeman, [Stack Safety for Free](http://functorial.com/stack-safety-for-free/index.pdf)
* Phil Freeman, [PureScript by Example/14. Domain-Specific Languages](https://leanpub.com/purescript/read#leanpub-auto-domain-specific-languages)

* [Extensible Effects in Scala](http://halcat.org/scala/extensible/index.html) 日本語!Scala!

* [A simple crud DSL with an interpreter written as cofree commonad in Purescript](https://github.com/coot/purescript-dsl-example)

# 最も参考になったカスタマーレビュー