map :: ( α -> β ) -> [α] -> [β]
第四回 : いざ安全に並列実行
ここまでに、我々はインクリメンタル開発によって以下のような内容を実装してきました。
-
交互に手番が来るタイプのボードゲームに対する一般解
-
○×ゲームのルールに対する特殊解
-
コンピュータが勝負の展開をどう考えているか確認できる追加の 予測 機能
ここで登場したコードは、結果として 純粋関数的 でした。コード中に 代入 や更新される必要のある 状態 は存在せず、それゆえ並列実行したときに問題の原因となりうる可変な状態の共有も発生しません。さらに、コード中には 副作用 もありません。
コードを書いたばかりなので、現に非純粋な書き方をしていないことは憶えています。しかし我々は、実装に関する前提知識がなくとも純粋性を確かめることができます。型システムが教えてくれる のです!
map の純粋性
つまりこういうことです。我々の解法のエントリポイントは map
関数の呼び出しでしたが、map のシグニチャは以下のようになっています。
第一引数の ( α → β )
から見ていきます。
このシグネチャは、map
の第一引数は制約のない任意の型 α
から、やはり制約のない任意の型 β
への関数であることを意味しています。この関数を f と呼びましょう。map
関数は引数として与えられた関数 f を α
型値のリストのすべての要素に適用することで β
型値のリストを生成しますが、f の仕様については関知しません。
今回の場合、f に当たるのは (probe lookahead)
です。この関数により、与えられた 先読み 手数以内で各盤面の 探査、すなわち盤面の評価もしくは勝敗が決する予測のいずれかが行われます。
任意の関数 f を α
型の値からなるリストにマッピングしても、副作用を伴って実行される可能性はありません。もっとも近い状況としては、f が型 β
として IO アクションを返す場合でしょう。しかしこの場合であっても、IO アクションは 生成される だけであって 実行される わけではありません。map
の実装がどのようになっていたとしても、このようなアクションを実行することはできません。これは map
が β
に関して 何も 仮定できず、したがって特にアクションであることを仮定できないからです。
別の言い方をすれば、map
のシグネチャは map f
は純粋であることを表して おり、Frege の 型システム はその純粋性が 呼び出しの連鎖全体 に行き渡ることを強制しているのです! 純粋性に反する部分がないか、また基礎部分に対して後から変更を入れたメンテナがうっかり破壊してしまっていないか、自分自身で前に戻ってコードを確認する必要はありません。
それでは、map
の代わりにmapP
(map
の並列実行版) を使って並列実行を行うと何が起こるでしょう? mapP
の型シグニチャは以下のようになっています。
mapP :: ( α -> β ) -> [α] -> [β]
なんと map
のシグニチャと 全く同じ です! map f
の純粋性について述べた上記の主張はすべて mapP f
にも同様に当てはまります!
インクリメンタル開発における並列性
Frege によって、またもや 非侵入的な追加 を行うことができました。逐次 実行から 並列 実行へ、絶対に安全な方法によってです。純粋性と、それを型システムで扱うことによってこれが可能になったのです。もし他の有名 JVM 言語だったとしたら、どの言語でもこの種の変更は、検出困難なエラーが混入する可能性が非常に高い、極めて 侵入的な (たとえ古いコードを全く編集しなかったとしても、演算の方式を変えるのは侵入的です) 変更になったでしょう。
そしてまた、この非侵入的な追加は あらかじめ計画しておかなくとも 可能でした。Frege で普通に実装しただけであり、それが結果としてうまく機能したことになります。
ほとんどの場合において、map から mapP への変更は安全です。
しかし、すべての map の呼び出しを闇雲に並列実行に書き換える前に、考慮すべき点 がふたつあります。
1) 粒度
ここでは、並列実行の適用を評価の最も浅い部分のみに留め、可能な盤面すべてに至るまで適用することはしませんでした。この判断は、データ並列化されたコードにおいてよくあるパフォーマンス上の問題、すなわち動作単位の大きさに応じて生じるスレッドスケジューリングの相対的オーバーヘッドを考慮した結果です。
2) 無限データ構造
並列実行では通常、遅延評価 は意味をなしません。新たに生成されたスレッドは、リクエストを受けた時に返す結果を準備しておくため、正格に動作を開始しなければならないからです。しかしこのようなアプローチは、無限 データ構造に適用された際には決して終了しないことになってしまいます。
しかし追加開発を行う際には、上記のような考慮事項について我々の考え方ひとつで決めることができます。今ここは粒度について意思決定すべき場面であり、possibleMoves が有限リストであることはすでにわかっています。これは一回の追加開発内で完結する決定です。
並列実行を○×ゲームに適用してみたとき、個人的にはとても奇妙に感じました。map
を mapP
に変え、コードを走らせ、速度を向上させて遊びましたが、そのときいつもの癖で平行性に関する猜疑心に囚われたのです。何かまずいことが起きるとしたらどんな場合だろう?
そんな状況になったにもかかわらず問題が発生する可能性を全く見つけられなかったのは、これが初めてのことでした。
参考文献
John Hughes | |
Tic Tac Toe |