最適化コンパイラ屋がHaskellの副作用について考えてみる
Haskellに副作用があるのか？というのは難しいテーマだと思いますが、少なくとも最適化理論での一般的な「副作用」の定義ではHaskellは全く副作用がない言語と言えると思います。
理論的に美しいという点がHaskellの設計の一番重要なところだと思うのですが、バックエンドの泥臭い話も面白いかもと思ったので書いてみます。
私は主に手続き型言語の最適化をやっていて関数型言語は詳しくありませんので、見当違いな事を書いていたら指摘して下さい。
まずは副作用の定義の為に「データ依存関係」(Wikipedia:依存関係)の説明をします。
ある変数xを使用・定義する二つの文を考える時、その評価順序関係には以下の4種類があり、それぞれの関係を以下のように呼びます。
- 真の依存
x = ... ... ... = x
- 逆依存
... = x ... x = ...
- 出力依存
x = ... ... x = ...
- 入力依存
... = x ... ... = x
入力依存は今回の話と関係ありません。
前者３つの依存関係は「順序を入れ替えるとプログラムの意味が変わっていまう」関係です。
最適化はプログラムの意味を変えてはならないというのが大前提なので、これら依存関係を解析した上でプログラムの変換をしなければなりません。
ここで、上の変数xの使用・代入からなる依存は分かりやすいので「自明な依存」と呼ぶ事にします。
さて、「自明でない依存」というのもあります。
例えばポインタを使うケース：
*p = ...; ... = x;
これはもし(p == &x)なら依存関係にあります。
次は、集成体を使うケース(例えば配列の場合):
for (i = 0; i < n; i++) { a[i+d] = a[i]; }
これは0 < d < nの時のみ並列化できないループです。
そして、グローバルな状態を変更するケース:
f(); g();
これはf()とg()が同じグローバル変数にアクセスするなどの場合に依存関係にあります。
上で述べた自明な依存に加えてこれらの自明でない依存も考慮しなければ正しいプログラム変換ができません。
最適化理論ではこのような「自明でない依存」を引き起こす可能性のある命令が「副作用」を持つと言う事が多いと思います。
ただし、「参照透過的である」のような統一的な定義があるわけでもないですし、自明でない依存もポインタ解析・シンボリック解析・関数間解析などで頑張って調べれば部分的に判別できる場合もあります。
ここでは、仮に「データ依存以外に評価順序を決める要因」全てを「副作用」と定義した場合の話をします。
さて、入出力、グローバル変数への破壊的代入、書き換え可能な集成体・・・等の機能があると*普通は*この手の自明でない依存が生じる事が分かると思います。
Haskellでも入出力は可能だし、グローバル変数への破壊的代入や集成体の書き換えも(メモリの上書きという意味では)可能です。しかし、自明でない依存は存在しません。
例えば以下のコードを見て下さい。
main = do x <- getLine y <- getLine putStrLn x putStrLn y
このレベルで見ると、x <- getLineとy <- getLineの間にはデータ依存がないのにこれらが入れ替えられない事から、一見自明でない依存があるように見えます。
しかしコンパイラが実際に扱うのはこれを脱糖したコードで、おおざっぱに書くと下の様な感じの物になります。(getline,putstrはgetLineやputStrの実際の仕事をするプリミティブのつもり)。
main = IO (\s1 -> let (s2, x) = getline s1 in let (s3, y) = getline s2 in let (s4, _) = putstr x s3 in putstr y s4 )
前で定義されたsNを次の命令に渡している事から、これらの間には真の依存があります。これは「自明な依存」です。
つまり、Haskellは自明でない依存を、上のように変数を引き渡す事で自明な依存に直しているのです。
do記法という構文糖衣の上から見るとこの変数は見えないので、人間側からはあたかも副作用が存在しているかのように見える訳です。
というわけで、Haskellは「真の依存」のみによって評価順序が決定されるので、例えばラムダ計算の様な体系にそのまま乗っける事が出来るし、難しい事考えなくても項書き換えシステムで正しく動作させる事が出来るし、自由自在にプログラムを変換してもその意味が決して変わらないのでアグレッシブな最適化が出来るわけです。
副作用がないというのはユーザだけでなくコンパイラにとっても大きなメリットなのです。
一方で、デメリットは
- ユーザにとってはプログラムの字面から評価順序を判別する事が難しくなる
- 本来依存関係にない命令間に依存が生じる(上の例だとy <- getLineとputStrLn xの間には本来は依存がないのに、データ依存が生じている)
などでしょうか。特に後者の為に、思ったほどはHaskellの並列化は楽ではなかったりするのだと思います。
まとめると
という話でした。
