関数プログラミングのアプローチ (24)

並列実行、分散実行、ソフトウェアトランザクションメモリ

前回は、関数プログラミングがプログラム中の式の評価タイミングを自由に変更できることを説明し、それがプログラマとコンパイラ・インタプリタの双方にとってメリットがあることを説明しました。今回は、さらに柔軟な実行処理について検討します。
関数プログラミングは、１つの式の実行が別の式の実行結果に影響を与えない（つまり、式の実行が副作用をもたない）ことが保証されています。そのことが、式の実行タイミングを柔軟に変更することができる根拠となっていましたが、このことはさらに柔軟に実行処理を構成することを可能にします。
まず、１つめは並列実行です。シングルスレッド化されていない式は、並列実行可能です。式の評価順序を入れ換えてもよいということは、式を並列に評価してもよいということです。並列実行の指示は、プログラマが行う場合と処理系が動的に判断する場合の２つが考えられます。実際に並列実行するには、いくつか技術的な検討課題がありますが、本質的な障害になるものではないと言えます。
並列実行の例は、map関数の代わりにpmap関数を用いて関数適用を並行化するという例を以前取り上げました。これは、プログラマが並列実行可能な箇所を明示することで、並列実行を行う例と言えます。
さらに、関数プログラミングでは、同じ式を評価すると必ず同じ結果を返します。このことは、同じ式であれば、いつどこで評価しても結果は変わらないということです。このことは、プログラムの分散実行を容易にします。
例えば、プログラム中の式をなんらかの形でマーシャリングして、ネットワーク上を転送し、別のマシン上でアンマーシャリングして同じ式を取り出すことができたとします。そうすると、その式を評価した結果は元のマシン上で評価した結果と同じ結果になるはずです。このようなやり方で、プログラムの実行処理の一部を別のマシン上で行うことができます。
その際に気を付けなければならないのが、式に含まれる自由変数の扱いです。別のマシン上で式を評価する際には、式に含まれる自由変数も含めて元のマシンと同じ値でなければ正しい結果を得ることができません。そのため、式をマーシャリングする際には、その式のクロージャ（式とその自由変数が参照する環境を含めた全体）をすべてマーシャリングするように注意しなければなりません。
また、関数プログラミングでは、式の評価に副作用がないため、式を何度評価しなおしてもプログラム全体の実行結果が変わることはありません。この性質は、STM（ソフトウェアトランザクションメモリ）の実装を容易にします。
STMは、マルチスレッドプログラミングにおける共有変数の更新処理について、大域的なロック処理を行わないで安全に更新するための１手法です。共有変数の読み取り、計算、共有変数の書き込みをまとめてトランザクションとし、トランザクションがアトミックに実行される（１つのトランザクションの実行中に他のトランザクションが実行されない）ことを、ソフトウェア的に保証します。
STMの実装では、トランザクションのコミット時に、トランザクション中で利用した共有変数について、共有変数の読み込みから書き込みの間で他のトランザクションが同じ共有変数にアクセスしていないことを確認して、アクセスがあればトランザクション全体を最初から実行しなおします。このような実装では、トランザクションの実行が共有変数の読み書き以外の副作用を持っていると意図通りに動作しないため、関数プログラミングが有効となります。
このように、関数プログラミングでは、参照透明性を守ることで、さまざまな実行処理上の仕組みを実現することが可能になります。

参考文献

マルチプロセッサ環境で並行処理を実装する際の技術的な問題に関しては、次の論文が詳しいです。これは、Haskellの代表的な処理系であるGHCをSMPに対応させる方法について述べたものです。

CleanはDynamicという機構を用いて、式を型安全性を保ったままマーシャリングすることができます。この機能を用いることで、任意の式を別のマシンに転送して評価を行うことが実現できます。Dynamicは言語報告の第８章に説明されています。

CleanのDynamicを用いて、実際に分散実行環境を作成する取り組みについては、次の論文が挙げられます。

STM（ソフトウェアトランザクションメモリ）については、次の論文が詳しいです。