注: この記事はScala関数型プログラミング&デザイン7章前半の劣化版まとめです

整数列の足し算について考えてみよう。たたみ込みなどがパッと思い付くだろう。

さて上記のたたみ込みだと、列の端から順に足し算を繰り返すことになり、計算を並列化することはできない。 容易に分割できる整数列であるならば、分割したそれぞれのパーツを並列に計算して最後に足し合わせることができそうである。 そこで上のコードを少し改良してみよう。

さて、Scalaでは式は正格評価されるため sum(l) + sum(r) の部分について、 左側の sum(l) の評価が終わってから右側の sum(r) の評価が始まる。

評価を遅らせるためには単純にthunkを作ればよい。 つまり、() => sum(l), () => sum(r) としてやればよい。

しかしこのコードも sumL() の評価が終わってから、sumR()の評価が始まるため何も解決されていない。 val sumL = () => sum(l), val sumR = () => sum(r) の部分で別スレッドで評価を始める計算を得て、 sumL() + sumR() の部分で両スレッドの計算を待ち、値を返すようになれば並列化ができそうである。

そこでそういった機能を持つ関数を実装は置いておいて、とりあえずインターフェースだけ定義しておきましょう。

これを用いると以下のように整数列の足し算を書き直すことができる。

さて unit は引数を受け取った瞬間、その評価を別のスレッドで直ちに開始する実装だとした場合、 確かにsum関数は並列化することを達成できる。

しかしながら、Par.get(sumL) + Par.get(sumR)をインライン展開したとすれば、Par.get(Par.unit(sum(l))) + Par.get(Par.unit(sum(r)))となり並列性が失われる。なぜならば、get は Par[Int] の計算が終わるまで待機するからである。つまり、unit は get に対し副作用を持っているということになる。

ということは、sum関数からPar[Int]を直接返してしまえば問題ない。Par.get(sumL) + Par.get(sumR) としている部分は sumL と sumR を合成したPar[Int]値を返せば良い。そしてこの時点でunitは引数の評価を非正格にする必要がなくなる。

さて、このようにしてできたsum関数に IndexedSeq(1, 2, 3, 4) を渡してみると、 Par.map2(sum(l), sum(r))(_ + ) の部分で左側の引数 sum(l) のほうが先に展開されてしまうという問題がある。したがってmap2関数の引数評価を遅らせる必要があるように思える。ただ Par.map2(Par.unit(1), Par.unit(2))( + _) のような単純な計算については即座に引数を評価したい。そこで、明示的に別スレッドで実行すべきであるという意味をもたせたfork関数を導入しよう。

こうすることにより forkで包まれた sum 関数は直ちに評価されないため、sum(l) と sum(r) は同時に計算が開始される。 さて、こうして定めたインターフェースに対して java.concurrent.ExecutorService を用いて実装を与えてみよう。以下のようになるだろう。