LoginSignup
28
8

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

Haskell PerformanceAdvent Calendar 2016

Day 2
@thimura(thimura)

ApplicativeDo 拡張について

Last updated at Posted at 2016-12-05

ICFP2016 の併設ワークショップ Haskell 2016 での ApplicativeDo のトーク Simon Marlow, et. al. ``Desugaring Haskell's do-Notation into Applicative Operations'' がおもしろかったので、ざっくり紹介してみたいと思います。

Applicative と Monad と do 記法

Monad は do 記法が用意されていて簡単に書けるので良く使われる一方で、Applicative には専用の記法がないため、Applicative で十分な場合でもプログラマは do 記法による Monad を使うことが多いようです。

Applicative では逐次実行の能力しかないため、くり返しや条件分岐ができない一方で、(<*>) の両辺は直接依存関係が無いため、Monad の場合と比べて並列度を上げやすいようです。

Haxl の Applicative

これを実際に利用しているライブラリに haxl があります。haxl は効率的なデータアクセスのために facebook で開発されたライブラリで、データベースや Web API といった複数のデータアクセスを自動的に並列で処理したり、キャッシュすることが可能になっています。

Haxl の GenHaxl は ReaderT 相当の機能もあって今回の説明には冗長なので、GenHaxl を適当に簡略化した次のような定義を考えます。

{.haskell}
newtype Haxl a = Haxl { unHaxl :: IO (Result a) }

data Result a = Done a
              | Blocked (Haxl a)

これの Monad の定義は次のようになります。

{.haskell}
instance Monad Haxl where
    return a = Haxl (return (Done a))
    m >>= k = Haxl $ do
        a <- unHaxl m
        case a of
            Done a' -> unHaxl (k a')
            Blocked r -> return (Blocked (r >>= k))

Monad の場合は、前の処理が完了していた場合は次の処理に引き渡し、まだデータ取得が完了せずブロック状態になっている場合は完了するまで待つだけの単純な実装になっています。

一方の Applicative の場合の定義を見てみましょう。

{.haskell}
instance Applicative Haxl where
    pure = return
    Haxl f <*> Haxl a = Haxl $ do
        r <- f
        case r of
            Done f' -> do
                ra <- a
                case ra of
                    Done a' -> return (Done (f' a'))
                    Blocked a' -> return (Blocked (f' <$> a')
            Blocked f' -> do
                ra <- a    -- Blocked 状態でもデータ取得が進む
                case ra of
                    Done a' -> return (Blocked (f' <*> return a'))
                    Blocked a' -> return (Blocked (f' <*> a'))

<*> の左手側の処理が Done 状態の場合は Monad の定義とそれほど変わりませんが、こちらは、Blocked 状態の場合でも右手側のデータ取得を実行しているという違いがあります。

Monad の場合は、前の結果に応じて次の処理を決める条件分岐がありますが、Applicative には逐次実行の能力しか無いため、このようなトリックが可能になっています。

ApplicativeDo 拡張による変換

なるほど便利な仕組みですが、これだけだとプログラマが明示的に Applicative に書き直す必要があり面倒です。そこで、do 記法で書いた場合でも、Applicative で十分な場合は Applicative にしてしまうという拡張が ApplicativeDo です。

ここからは proceedings を元に適当にピックアップしているだけなので、詳しく知りたい方は論文を参照してください。

書き換えの例を見てみましょう。

{.haskell}
do x1 <- A
   x2 <- B
   return (x1, x2)

ここで A と B は任意の式で、B は x1 に依存していません。これは ApplicativeDo を使うと次のように脱糖されます。

{.haskell}
(,) <$> A <*> B

一方で、次のように B が x1 に依存している場合は (<*>) で書くことができないため (>>=) を使う必要があります。

{.haskell}
do x1 <- A
   x2 <- B[x1]
   return (x1, x2)
{.haskell}
A >>= \x1 -> B[x1] >>= \x2 -> return (x1, x2)

Applicative は逐次実行しかできず、条件分岐などの前の計算に依存するような物は Applicative では書くことができないのでした。この違いは (<*>) と (>>=) の型からも見てとることができます。

{.haskell}
(<*>) :: Applicative f => f (a -> b) -> f a        -> f b
(>>=) :: Monad m       => m a        -> (a -> m b) -> m b

(>>=) は m b が前の計算の結果 a を受けとることができる一方、Applicative はそうなっていません。
したがって、do 記法の中の 2 つの文の間に依存関係がある場合は、常に変換後の式のどこかで (>>=) を使う必要があります。

では、依存関係がある部分とそうでない部分の両方が出てくる場合を考えます。

{.haskell}
do x1 <- A
   x2 <- B
   x3 <- C[x1]
   x4 <- D[x2]
   return (x3, x4)

C と D はそれぞれ A と B の結果に依存するため (>>=) が必要ですが、A と B、および C と D は依存関係が無いため並列に実行できます。
この関係を簡単に表すため、並列に実行できる部分を | で、依存関係がある部分を ; で区切る記法を使うことにします。上記の例だと (A | B); (C | D) となります。

これを単純に書き換えると次のようになります。

{.haskell}
((,) <$> A <*> B)
    >>=
    (\(x1, x2) -> (,) <$> C[x1] <*> D[x2])

この方法だと途中で A, B のタプルを作る必要があり無駄に見えます。次のように変換した方が良さそうに見えます。

{.haskell}
(,) <$> (A >>= \x1 -> C[x1])
    <*> (B >>= \x2 -> D[x2])

しかし、この変換は A, B, C, D の順番が入れ替わっているため適切ではありません。State モナドの場合などを考えてみれば、これが問題あることはすぐ分かるでしょう。したがって、ApplicativeDo では順番を入れかえるような変換は行ないません。

なお ApplicativeDo は、上記のような例は実際には join を使って書き換えています。

{.haskell}
join ((\x1 x2 -> (,) <$> C[x1] <*> D[x2])
      <$> A
      <*> B)

こちらは途中でムダなタプルを作らない分良さそうです。

やりかたは一つじゃない

次の例を考えます。

{.haskell}
do x <- A
   y <- B
   z <- C[x]
   return (y+z)

これを変換するには、次の 2 通りの方法があります。

  1. (A | B); C
  2. A; (B | C)

それぞれの処理時間をコストとして考え、"|" で分けられた部分は並列処理されることを考えると、"|" はそれぞれのコストの最大値、";" は前後のコストの和を取ると考えられます。これに基いて、実際に A,B,C にコストを割り当てて全体のコストを評価してみます。

  • A = B = C = 1 の場合: どちらも 2
  • A = 0; B = 1; C = 1 の場合
    • (1) のコストは 2
    • (2) のコストは 1
  • A = 1; B = 1; C = 0 の場合
    • (1) のコストは 1
    • (2) のコストは 2

このことから分かるように、どちらの変換が良いかは A, B, C それぞれの計算コストに依存しますが、実際に do 記法の中にある全ての文のコストについて完全に知ることはできないため、一般には最適な変換を決めることはできません。そこで、ApplicativeDo の場合は全ての文のコストが等しいものとして計算し「最適」な変換を決めています。

変換アルゴリズム

論文では形式的な ApplicativeDo の変換アルゴリズムについての説明がありますが、全部を解説（という名のコピペ）をすると時間も掛かるので（既に4日遅れということもあり）、ここでは割愛させていただいて、変換の概略だけ紹介させていただきます。詳しく知りたい方は論文を参照してください。

変換は、Rearrangement と Desugaring の 2 つのステージに分かれています。

Rearrangement

Rearrangement では do 記法を受けとって、"可能な限り"並列実行できる形式に変換します。

次の場合を考えましょう。

{.haskell}
do x1 <- A
   x2 <- B[x1]
   x3 <- C
   return (x2, x3)

Reaarangement では最後の return については無視して、文のリストだけを考慮します。

最初に、文のリスト $s_1 \cdots s_n$ を分割する位置 $i$ を決めます。この位置は$s_1 \cdots s_i$ で定義された変数が、$s_{i+1} \cdots s_n$ で使われていないという条件から決まります。

$s_{i+1} \cdots s_n$ は $s_1 \cdots s_i$ で定義された変数に依存しないため、両者は並列に実行できます。

したがって、上の例の場合は次のように変換されます。

{.haskell}
rearrange ({ x1 <- A; x2 <- B[x1]; x3 <- C })
→ (split { x1 <- A; x2 <- B[x1] } | split { x3 <- C })

ここで出てくる split は、与えられた文のリスト $s_1 \cdots s_n$ を $s_1 \cdots s_i$ と $s_{i+1} \cdots s_n$ の 2 つに分割し、それぞれに再度 rearrange をかける変換です。分割する位置 $i$ は $i \in 1 \cdots n$ のうち、全体のコストが一番低い物を選びます。

このケースでは 1 通りの分割しかないため、最終的には

{.haskell}
({ x1 <- A; x2 <- B[x1] } | { x3 <- C })

のように変換されます。

とはいえ、split の分割方法で「最適解」を求めようとすると

  • サブシーケンス s_i .. s_j の取り方で $N^2$ 通り
  • 選んだサブシーケンス s_i .. s_j の分割方法の決定で $N$ 通り

の計算量が必要なため、split は全体として $O(N^3)$ の計算量が必要になります。そのため ApplicativeDo 拡張のデフォルトでは、最適解のかわりにヒューリスティック版を使うようになっているようです。

また、rearrange はナイーブにやると指数的に計算量が増えてしまいますが 1、部分列の評価結果は使い回せるので動的計画法を使えば $O(N^3)$ まで落とすことができます。更に、ここでは最適な場合にのみ興味があるため空間計算量を減らすことができ、また最初の分割の結果により探索が必要な部分を大幅に減らすことができる傾向にあるため、ボトムアップ方式で可能なパターンの配列を作るのではなく必要になり次第計算してキャッシュする方式を採用しているようです2。

Desugaring

次に脱糖していきます。

脱糖は下記 5 パターンに分かれています。

  • (0) 空リストの場合

    {.haskell}
    desugar {} e = pure e

  • (1) ひとつの bind のみの場合は <$> に書き換え

    {.haskell}
    desugar {p <- e} e'
    | p == e'       = e
    | otherwise     = (\p -> e') <$> e

  • (2) 一般の bind の場合は >>= に書き換え

    {.haskell}
    desugar {p <- e; l} e' = e >>= \p -> desugar l e'

  • (3) ひとつの並列ブロックのみの場合、<$> と <*> で書き換え

    {.haskell}
    desugar {(l_1 | ... | l_n )} e
    = (\p_1 ... p_n -> e') <$> e_1 <*> ... <*> e_n
  where
    (p_i, e_i) = desugar_arg l_i e

    desugar_arg は

    desugar_arg {p <- e} _ = (p, e)
desugar_arg l e' = ((v_1, ..., v_k), desugar l (v_1, ..., v_k))
  where
    v_1 ... v_k = 束縛変数(l) ∩ 自由変数 (e')

  • (4) 一般の並列ブロックの場合で、並列ブロックが最後に来ていない場合は join を使う

    {.haskell}
    desugar {(l_1 | ... | l_n); s} e
    = join ((\p_1 ... p_n -> e') <$> e_1 <*> ... <*> e_n)
  where
    e' = desugar s e
    (p_i, e_i) = desugar_arg l_i e'

(1) と (3) は他のルールでも代用可能ですが、これらは Monad を使わずに、それぞれ Functor と Applicative のみで書けるため、余計な Monad への依存を無くすため別途パターンを分けています。

rearrange での例を脱糖してみます。

{.haskell}
desugar {{ x1 <- A; x2 <- B[x1] } | { x3 <- C }} (x2, x3)

ここでは (3) のパターンを適用して次のように脱糖します

{.haskell}
(\x2 x3 -> (x2, x3))
    <$> desugar { x1 <- A; x2 <- B[x1] } x2
    <*> desugar { x3 <- C } x3

次に

{.haskell}
desugar { x1 <- A; x2 <- B[x1] } x2

は一般の bind なので (2) を適用して

{.haskell}
A >>= \x1 -> desugar { x2 <- B[x1] } x2

(1) を適用して

{.haskell}
A >>= \x1 -> B[x1]

同様に、desugar { x3 <- C } x3 も (1) を適用して C になるため、最終的に

{.haskell}
(\x2 x3 -> (x2, x3))
    <$> (A >>= \x1 -> B[x1])
    <*> C

が得られます。

実装方式

ApplicativeDo の書き換えの結果によっては、制約が Monad ではなく Applicative や Functor になるため、ApplicativeDo の書き換えは型推論の前に行なう必要があります。

一方で、もし型エラーがあった場合、エラーを出力する際はプログラマが書いたオリジナルのコードに対して出す必要があります。ApplicativeDo の書き換えを型チェックの前に実行してしまうと、オリジナルのコードが失なわれてしまうため不適切です。

この問題を解決するため、ApplicativeDo の rearrangement では、AST に型チェッカが Monad ではなく Applicative を推論できるようにアノテーションを付け、型チェックが走った後の desugaring フェーズで applicative への書き換えを行なっているようです。

結果

著者らが LTS Stackage 3.2 にある 1188 個の Hackage について調査したところ、全体で 38850 個の do 記法があり、そのうちの 41.9% が ApplicativeDo によって少なくとも一つの <*> を含む形で変換できたそうです。更に 28.0% については、完全に Monad を必要とせず Applicative または Functor だけの形に書き換えることができたそうです。

また、全体の 0.6% にあたる 226 個の do 記法については、最適解版のアルゴリズムがヒューリスティック版より良い rearrangement 結果を得たそうです。rearrangement に使うアルゴリズムはオプションで変更できるそうですが、この結果を見る限りでは、ほとんどの場合はヒューリスティック版で十分でしょう。

気になるコンパイル時のオーバーヘッドですが、一つの do 記法の中に 1000 個の文を含み、それぞれが前の結果に依存するワーストケース 3 では、次のような結果になったそうです。

オプション コンパイル時間
ApplicativeDo なしの場合 1.22s
ApplicativeDo あり (ヒューリスティック版) 1.46s (20% slower)
ApplicativeDo あり (最適解版) 55.5s (4549% slower)

もちろん、実際に 1000 文の do 記法があるケースは稀でしょう。
また、平均的なケース (著者らの Haxl コードベース) では ApplicativeDo の有無でのコンパイル時間の違いは、誤差の範囲内だったようです。

Haxl のように、複数のデータを取得して、それを元に何か処理をして結果を返すようなプログラムだと、Applicative と join を組み合わせてごちゃごちゃ書くより、do 記法で愚直に書いた方が分かりやすい場合も多いでしょう。そういう場合でも ApplicativeDo があればコンパイラがよしなに変換してくれるというのは、なかなか便利です。

ApplicativeDo では順番を入れ替えるような変換は行ないませんが、commutative monad の場合は、順番を入れ替える変換をしても問題が無いため更に効率的な変換ができることが期待されます。論文では future work として触れられていました。

そのほかにも optparse-applicative も do 記法で書くことができます。レコードの項目が増えてくると、データ構築子と <$> <*> で書くより do 記法とレコードで書く方がより扱いやすい気がしますし積極的に使っていきたいですね。

最後に

ICFP の proceedings を元にざっくりと ApplicativeDo 拡張の紹介をしてみました。間違いとかツッコミとか、便利な使いかたを見付けたりしたらコメントいただければ幸いです。

AST にアノテーション付ける話は、論文ではちらっとしか 4 触れられていなかったので、ヒマと余力と実力があったら深淵（実装）を覗いてみると楽しいんじゃないかと思います。

  1. 実際の rearrange は 2 以上の分割も扱うので ↩

  2. Haskell なら lazy な Map や配列で簡単に実装できるので ↩

  3. rearrange が並列ブロックに分けることができず、do 記法全体が split に渡されるため ↩

  4. RebindableSyntax とかもあるのでヤバいけど上手くやればなんとかなるとか ↩

28
8
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
28
8

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?