Java・関数型言語・並列処理
やっぱり並列処理が鍵
近年、CPUの進化が高速化から並列化へとシフトしつつあることは明らかで、並列処理についてきちっと学ばなければならないと思っている。ここ数年で関数型言語がかなり見直されているのも、並列処理への適性が大きな理由の一つだろう。今や古さの象徴として語られることが多くなってきたJavaも、並列処理をより強くサポートする方向へと進んでいる。以下は一年前の記事だけど、端的にそれが語られている。
「Javaに並列処理と関数型言語の要素を」、ティム・ブレイ氏 -@IT
関数型言語は、一般的な言語とコードの書き方が大きく異なるものの、いずれJavaに関数型プログラミングの要素を入れていくことも必要だとブレイ氏は語る。
さて、それから一年が経った。どんなのものが出てきたのか。
分割統治法（fork/join）
IBMのdeveloperWorksに、Java SE7にて追加される並列処理機能についての詳しい記事があった。まずは、大量データに対するソートや検索のための「分割統治法（fork/join）」という手法について。
Java 7 で登場するフォーク/ジョインのフレームワークを使って細粒度並列処理の活用方法を学ぶ（Java の理論と実践: フォークを活用する、第 1 回）
このアルゴリズムでは、問題を再帰的に副問題に分割していき、副問題に対する解を組み合わせて最終的な結果を得ます。（中略）
並列型の分割統治法アルゴリズムは最初に、問題が小さすぎて逐次型ソリューションの方が早く結果を得られることがないか評価します。通常これは、問題のサイズを何らかのしきい値と比較することで行われます。もし並列分割のメリットを生かせるほど問題が大きければ、その問題を 2 つ以上の副問題に分割し、これらの副問題に対して並行してこのアルゴリズムの再帰的な呼び出しを行い、副問題の結果を待ち、そしてそれらの結果を組み合わせます。
これはMapReduceがとっている戦略そのまんまである。Hadoop（GoogleのMapReduceアルゴリズムのJava実装オープンソースプロジェクト）はそれなりに注目を集めているが、ついにJavaのコア機能にもそのアイデアが入ってくる。
さて、fork/joinは実装レベルでどのように利用されるのだろうか。
ParallelArray
その一例が、やはりJava SE7で登場するParallelArrayだ。これは面白い。
Java 7 の ParallelArray クラスを使ってソートと検索の速度を上げる（Java の理論と実践: フォークを活用する、第 2 回）
概念としては、ParallelArray は構造的に類似したデータ項目のコレクションを表しており、そのデータの分割方法を記述するために ParallelArray のメソッドが使われます。そしてその記述を使って実際の配列操作 (実は裏でフォーク/ジョインのフレームワークが使われています) を並行して実行します。（中略）
ParallelArray が目的としているのは、特定の範囲のデータの選択操作や変換操作を単純に表現することで、そうした操作を容易かつ自動的に並列化できるようにすることだけです。
この説明を読んだだけではよくわからない。しかし、その後に続くサンプルソースを見るとやりたいことがよくわかる。「卒業する生徒の GPA（成績の平均値） の中から最高値を選択する」というサンプルである。
ParallelArray<Student> students = new ParallelArray<Student>(fjPool, data); double bestGpa = students.withFilter(isSenior) .withMapping(selectGpa) .max(); public class Student { String name; int graduationYear; double gpa; } static final Ops.Predicate<Student> isSenior = new Ops.Predicate<Student>() { public boolean op(Student s) { return s.graduationYear == Student.THIS_YEAR; } }; static final Ops.ObjectToDouble<Student> selectGpa = new Ops.ObjectToDouble<Student>() { public double op(Student student) { return student.gpa; } };
Javaっぽくないソースだ。笑
生徒の集合に対して、卒業生というフィルタをかけ（Filtering）、それらの各GPA値を取得し（Mapping）、その中から最大値を取得する（Accumulation）。これはまさに、SICPで見た「公認interfaceとしての並び」であり、GoogleのMapReduce戦略であり、さらに遡るならUnixのパイプ＆フィルタ的な思想だ。うん、並行処理への最適化を進めて行くと必然的にそういう形になるんだな。
それから、
並列配列に対する操作を表現するコードは見掛け倒しで、withFilter() メソッドと withMapping() メソッドは、実際にデータを検索したり変換したりするわけではなく、単に「クエリー」のパラメーターを設定しているにすぎません。実際の作業は最後のステップ (この場合は max() への呼び出し) で行われます。
この辺りの内部実装も気になる。
流れるようなinterfaceを意識していることもわかるし、フィルタやマッパーにはクロージャを利用している（エレガントとは言い難いけど）。関数型言語から強い影響を受けていることがよくわかって面白い。
Seasar2を触ってみる
Seasar2によるスーパーアジャイルなWeb開発 (WEB+DB PRESS plusシリーズ)
- 作者: ひがやすを
- 出版社/メーカー: 技術評論社
- 発売日: 2008/03/25
- メディア: 大型本
- 購入: 36人 クリック: 4,854回
- この商品を含むブログ (50件) を見る
Seasar2はRailsのマネだという人にそろそろ一言いっておくか（ひがやすをBlog）
小規模のアプリケーションならば本当にサクサク構築できそうな印象。僕はJSFは愚かJSPすら触ったことがないが（どうなのよそれ）、半日でちょっとしたサンプルを作るところまでできた。ここまでの印象は以下。
- HOT deploy は素敵すぎる。時間があるときに仕組みを調べたい（参照：HOT deploy完成）。ちなみに、JavaRebelという動的ローダーは見たことあったが、これは販売製品だった。
- 命名規約やアノテーションを徹底的に利用している。Springに比べてかなりシンプルな印象。
- Dolteng(Eclipseプラグイン)がかなり親切。規約による開発をうまく補完してくれる。
動的型付けのSclipt言語あるいは関数型言語が流行している中でよく指摘されるJavaの欠点をうまく解決していると感じた。それによってひがやすを氏は、静的型付言語のメリット（コンパイル時の型チェックやコード補完）を強調することに成功している。
なんにせよもう少しいじってみようと思う。ある程度の大きのサンプルを作るならJSFもちゃんと勉強しなくてはなるまい。
- 作者: 須賀幸次,木村聡,西川麗,高安厚思,白井博章,椎野峻輔,岡薫,藤村浩士,ひがやすを
- 出版社/メーカー: ソフトバンククリエイティブ
- 発売日: 2006/02/25
- メディア: 大型本
- 購入: 7人 クリック: 51回
- この商品を含むブログ (60件) を見る
Light Weight Java―JSF/Hibernate/SpringによるフレームワークでWebアプリケーションの開発効率向上
- 作者: 岡本隆史,金子崇之,吉田英嗣,権藤夏男
- 出版社/メーカー: 毎日コミュニケーションズ
- 発売日: 2005/04
- メディア: 単行本
- 購入: 3人 クリック: 52回
- この商品を含むブログ (26件) を見る
MapReduceの本質
また一つ、『計算機プログラムの構造と解釈』から面白いネタが飛び出してきた。
一見なんでもないようなschemeの例題から、GoogleのIndex生成アルゴリズムとして名高いMapReduceの概要を理解するための機会を得た。
あの例題の本質は何だったのか？
きっかけは、先日の「プロセスの抽象化（シーケンスへの作用）」というエントリーに関して、会社の先輩から興味深い指摘をいただいたことだった。エントリーの内容は、抽象化によって「木構造の要素に対して作用する手続き」を改善するという話だが、その改善前後の手続きをもう一度掲載する。
【A】改善前の実装
(define (sum-odd-squares tree) (cond ((null? tree) 0) ((not (pair? tree)) (if (odd? tree) (square tree) 0)) (else (+ (sum-odd-squares (car tree)) (sum-odd-squares (cdr tree))))))
【B】改善後の実装(define (sum-odd-squares tree) (accumulate + 0 (map square (filter odd? (enumerate-tree tree)))))
僕は【B】への改善の本質的な目的として「可読性の向上」と、「部品の再利用性向上」を挙げた。しかし、先輩から以下の指摘を受けた。
・【A】はそこまで可読性が低いのか？
・【B】では明らかに計算量が増加していることをどう説明するのか？
確かにその通りだ。特に計算量の問題は明らかで（リスト走査の回数が増えている）、そのことには前の記事を書いた段階でも気づいていたものの、「可読性の確保（今や自明ではないが…）」と「部品化による再利用」を行うことがこの例題で伝えたい本質なのだと考えてスルーしてしまった。
実際どの程度計算量が増加していたのか。【A】の計算量（シーケンスに対する全走査１回）をnとした場合、【B】では約３nの計算量を要することがわかる。
n + n + n/2 + n/2 = 3n
※enumerationとfilterが全走査であるため「n」、mapとaccumulationは奇数要素のみに対する作用であるため「n/2」となる。
つまり、計算量を３倍にしてでも【B】のスタイルをとる意味はあるのか？というのが先輩の問いだった。しばらく考えたものの、僕には明確なメリットを提示することができなかった。
MapReduceの戦略
先輩の出した答えは、「並列処理による分散が可能になる」ということだった。
つまり、【B】の場合、accumulation以外の関数（map、filter、enumeration）は引数として与えられるリストからしか影響を受けないため（環境が閉じているため）、各々の処理を個別的に切り出し、並行にスケールできるという話だ*1。例えば、【B】に渡された木構造が超巨大だったとしても、それをいくつかに分割して、走査処理を別のマシンで同時に行い、最後にそれぞれの走査結果を集計(accumulate)すればよい。accumulationを除けば、処理速度は論理的にはマシンの台数に比例して早くなるはずである。もちろん、【A】の設計では、全ての処理要素がメインの再帰手続き内に混在しているため、部分的に切り出してスケールすることはできない。
そして、これこそがGoogleのMapReduceアルゴリズムがとっている戦略に他ならないのだと。もう目から鱗でした。
MapReduceについては、以下の記事が非常によくまとまっている。
Radium Software Development ― MapReduce
map タスクは，膨大な量の元データを分解し，必要な情報を抽出し，有用な形へと変換し出力する，いわゆる「フィルター」の役目を担う。 reduce タスクは，抽出された情報を集約し，一塊のデータとして出力する，いわゆる「アグリゲーター」の役割を担う。このうち map タスクが純粋にフィルターとして振舞う（副作用が無い）ならば，この処理を複数のマシンで手分けして行うことができる。たとえ処理対象のデータがテラバイト単位で存在したとしても，その処理を数百台のマシンへと効率良く分配することができたならば，現実的な時間内で処理することが可能になると考えられる。
今回の例題に置き換えると、mapタスクは map、filtere、numeration であり、reduceタスクは accumulation にあたる。
本当に面白いと思うのが、この単純な「mapによるリソースのフィルタリング → reduceによる集計処理」というモデルで様々な処理を実装できることだ。先に引用した記事では、WEB上の単語出現回数の集約と、逆リンクリスト生成の例が出てきている。
それから、もうひとつ気になる点。mapタスクはスケールするが、reduceタスクはスケールしないという話。
MapReduce を構成するタスクのうち map タスクが並列実行可能であることは自明に思われる。他方で reduce タスクの方は，個々の操作が可換 (commutative) ないしは結合法則を満たす (associative) とすれば階層的に並列実行することが可能だが， MapReduce においてはそのいずれも前提として設けられていない。（中略）明らかに map タスクの方が並列実行に特化されており， reduce タスクの並列性の低さが目に付いてしまう。
このような map と reduce の間に見られる非対称性は，恐らく Google の扱う問題領域の特殊性から生じるものであろうと思われる。
交換法則や結合法則を満たさない集約処理の具体的は述べられていないが、きっと色々難しいことがあるんだろう（適当）。ただ、例えばIndex生成処理の、パフォーマンス上のクリティカル・ポイントは間違いなくmapタスクだ。それを考えればmapタスクのスケーラビリティが充分に高ければよくて、それがGoogleにとっての最適解なのかもしれない。reduceタスクのスケーラビリティを無理に高めようとするとアルゴリズムの複雑度が高くなって、デメリットの方が大きくなってしまうとか。例えば。
とにかく、WEB上の膨大なリソース（テキスト、画像、映像、リンク）を何らかの規約に基づいてフィルタリングし、それをまた何らかの規約によって集計する。Googleにとってこれほど最適かつ簡潔なアルゴリズムのモデルはほかにないだろう。
Joel Spolskyは言いました
関数プログラミングを理解していなければ、GoogleをあれほどスケーラブルにしているアルゴリズムであるMapReduceは発明できない。MapとReduceという用語はLispと関数プログラミングから来ている。純関数プログラムは副作用がなく容易に並列化できるということを6.001に相当するプログラミングの授業で聞いて覚えている人には、MapReduceは容易に理解できる。
今年に入ってから社内でSCIP勉強会を始めた。そのきっかけとなったJoelの記事に上のような一節がある。これを最初に読んだときに比べ、確実に階段を昇っていることが感じられて非常にうれしい。そして、大きな気付きを与えてくれた先輩には感謝感激雨あられです。
流れるようなinterface
最近、Martin Fowler先生のBlogの存在を知り、しかも日本語訳も大量に公開されていることを知った。それを毎日少しずつ読み進める（というより気になった記事から読んでいく）のが現在の僕の唯一娯楽です何か悪いか？
Martin Fowler's Bliki (Blog本家)
日本語翻訳wiki
面白い記事はたくさんあるのだけど、その中から「流れるようなinterface」という記事について。
外部に公開して利用してもらう手続き(interface/API)は、たとえ時間をかけてでも以下の条件を満たすよう設計すべきであるという主張。
・手続きの名称が適切で、それを利用したコードの可読性が高いこと
・利用者への要求が可能な限り少ないこと
そのひとつのあり方が「流れるようなinterface」だ。
このAPIは読みやすさを第一に設計されている。流れるようにするには、設計とAPIの構築に時間がかかるという代償をともなう。コンストラクタ、セッター、addXXXメソッドといったシンプルなAPIは簡単に書くことができるが、ナイスで流れるようなAPIにたどり着くには、それなりの長考が必要だ。
（中略）流れるようなAPIについてもっと考えてみたいのであれば、JMockのコードを見てみるといいだろう。 JMockなどのモックライブラリは、振舞の複雑なスペック（仕様）を作る必要がある。ここ数年で様々なモックライブラリが作られてきたが、JMockには非常にナイスで流れるようなAPIが含まれており、それが正に流れるが如くなのである。以下にエクスペクテーション（期待）の例を挙げる。mock.expects(once()).method("m").with( or(stringContains("hello"), stringContains("howdy")) );
引用したコードを見ると、まさに流れるような。JMockが何者かは知ったことではないが、何をしようとしているのかは一見して推測することができる。このような設計をするための典型的なテクニックが、セッターで値を返すようにするというものだ。一番単純な例ではjavaの StringBuffer.append() などがこの例にあたるか。
興味深いことに上で例示されたjavaのコードは昨日の記事で引用したschemeのコードによく似ている。
■schemeの実装例(『計算機プログラムの構造と解釈』p.67) (define (sum-odd-squares tree) (accumulate + 0 (map square (filter odd? (enumerate-tree tree)))))
最初に引用したjavaのコードは、セッターで値が返る設計であるため、関数型言語に近い構造になったということは言えると思う。それから、セッターとは関係ないが、ObjectCompositionを駆使して設計されている、つまりObject間の委譲関係が適切であるコードは、確かに流れるような形状をしていることが多い（その対局がナイアガラの滝のような巨大な手続きで、あの手のコードを真剣に読んでいると本当に体調が悪くなってくる）。
とにかく、interfaceの設計を正しく行ったオブジェクト指向のプログラムは、非常に読みやすく、部品の入れ替えも容易であることがよくわかる。そもそも、interfaceを定めることはそのObjectの役割を明確にすることであり、プロセスや問題領域の抽象化が充分に行われた結果である可能性が高い。混沌とした領域にinterfaceを定めることなどできるはずがない。混沌には他我もhogeもhugaもないんだから。そして、部品入替えが容易なプログラムはユニットテストを行いやすく、機能追加によるバグに強いことは言うまでもない。
さらに、Seasar2の例
Seasar2の作者、ひがやすおさんが「流れるinterface」について力説されていたので引用させていただく。
流れるようなインターフェースは、うまく実装できれば、Javaのような静的言語と相性が良い。コード補完によって、流れがさらに滑らかになるから。
確かにこれは静的型付言語の強みかもしれない。
流れるようなインターフェースでは、ソースコードを書いている人が、中断することなく流れるようにコーディングできなければいけない。
うん、流れるようなinterfaceとただのメソッドチェーンは違うんだな。
そのことがよくわかる対比が以下の記事に載っていました。Seasar2とHibernateの属性注入プロセスを例に挙げています。
■S2JDBCの流れるインターフェースを使った例
List<Employee> results = jdbcManager.from(Employee.class) .join("department") .where("id in (? , ?)", 11, 22) .orderBy("name") .getResultList();■Hibernateのcriteriaを使った例（メソッドチェーン）
List<Emploee> results = (List<Employee>) session.createCriteria(Employee.class) .add(Restriction.eq("id"), new Integer(11)) .add(Restriction.eq("id"), new Integer(22)) .addOrder(Property.forName("name").asc()) .setFetchMode("department", FetchMode.EAGER) .list();
プロセスの抽象化 ― シーケンスへの作用
『計算機プログラムにおける構造と解釈』の「2.2.3 公認インターフェースとしての並び」(p.65)が非常に面白かった。
ある計算プロセスを手続きとして設計する時、その一連のプロセスは大抵、複数の異なる要素(計算過程)を内包している。それらを最小の要素まで分解し、明確で単純な目的をもつ独立した部品とし、それらをある意図を持って組み合わせることによりプロセスを構成しようという話（これは単なる構造化ではなく、オブジェクトのcompositionに近い発想だ）。
これを説明する例として、「木構造で数値を保持するリストを引数に取り、その中の奇数である葉の二乗の和を返す」関数の設計を改善していく話が出てくる。当初は「木構造を頭から走査」し、要素が「末端」かつ「奇数」であればその「二乗」を再帰的に「加算していく」という愚直な方法で実装する。
■愚直な実装(p.65) (define (sum-odd-squares tree) (cond ((null? tree) 0) ((not (pair? tree)) (if (odd? tree) (square tree) 0)) (else (+ (sum-odd-squares (car tree)) (sum-odd-squares (cdr tree))))))
しかし、このプロセスは実は「シーケンス(並び)に関する作用群」として、以下の4つの要素に部品化することができる。このような要素を抽出する(プロセスを抽象化する)ことができるかどうかがプログラマにとって決定的に重要な力であることを痛感する日々。
| enumeration | 与えられたリソースからシーケンスを生成する［木構造から葉の配列を生成する］ |
| filter | リストから特定の要素を抽出した結果を得る［奇数を抽出したリストを得る］ |
| map | 与えられたシーケンスのある作用に対する写像を得る［全要素を二乗したリストを得る］ |
| accumulation | 与えられたシーケンスの要素を何らかの規約に基づいて集約する［全要素の和を得る］ |
さて、これらの部品を構成することによって、最初に引用した手続きを下のように実装することができる（各部品の内部実装は省く）。
■interfaceのcompositionによる実装(p.67) (define (sum-odd-squares tree) (accumulate + 0 (map square (filter odd? (enumerate-tree tree)))))
まず、この実装は最初のものに比べて可読性が圧倒的に高い。部品の名称からは各々の目的が明確に伝わってきて、全体として何を行いたいのかが一目で伝わってくる。
次に、部品化を行ったことによって、異なるプロセスへの再利用が可能となる。本書の例では「整数nより小さいか等しいkに対して、偶数のFibonacci数のリストを作る手続き」という、最初の例題とは一見似ても似つかないプロセスが、「シーケンスの取得、シーケンスへの作用、それら要素の集約」として抽象化（同一視）可能であることが指摘される。すると、必要な部品を置き換えることによってこのプロセスが実装できる。
■部品を再利用した例(p.76) (define (even-fibs n) (accumulate cons nil (filter even? (map fib (enumerate-interval 0 n)))))
いや、美しい。
読書会メモ 第6回 (第一章終了)
●消化内容
計算機プログラムの構造と解釈
【第６回】第1章 第3節(p41〜p44)
●メモ
ようやく第一章が終了。この会を始めてから３週間で第一章を読み終えたことになる。全ての問題を解きながら進んでいることともあるが、題材として随所にでてくる数学の復習に一番時間を取られているかな。でも、それはそれでよい勉強をさせてもらっている。高校数学でほぼ理解できる内容であることがせめてもの救いだ。
手続きによる抽象
「手続きによる抽象」をテーマにした第一章のハイライトである問題1.46を残しておく。この章では平方根や不動点などの数値計算を様々なアプローチで解いてきた。これが章最後の問題で反復的改良法(予測値を改良しながら解へ近似させていく戦略)として抽象化される。あとで振り返れば至極当然に見える抽象化であっても、左右が見えないまま一歩ずつ階段を昇っていった結果それが現れる瞬間というのはちょっと感動する。
問題1.46 ;反復的改良法 (define (iterative-improve good-enough? improve) (lambda (guess) (define (itr result) (if (good-enough? result) result (itr (improve result)))) (itr guess)) ) ;反復的改良法を用いた平方根算出手続き (define (sqrt x) (let ((good-enough? (lambda (guess) (< (abs (- (square guess) x)) 0.00001))) (improve (lambda (guess) (average guess (/ x guess))))) ((iterative-improve good-enough? improve ) 1.0)) ) ;反復的改良法を用いた不動点算出手続き (define (fixed-point f first-guess) (let ((close-enough? (lambda (guess) (< (abs (- guess (f guess)) 0.00001))))) ((iterative-improve close-enough? f) first-guess)))
洗練された抽象化は非常に美しいと思う。本質を見抜き、抽出し、適切な名前をつける。そのようなコードであれば一見してロジックの大筋をつかむことができる。
われわれはプログラマとして、プログラムの根底にある抽象を見つけ、より強力な抽象化ができるよう、その上に構成し、一般化するようつとめなければならない。これはプログラムを可能な限り抽象的に書くべしというのではない；経験を積んだプログラマは、自分の仕事に適した抽象のレベルを選ぶことを知っている。しかし抽象を使って考えることができるのは、新しい状況になったときに、すぐ応用できるため、大切である。
『計算機プログラムの構造と解釈』p.43
第一章まとめ
本章のテーマは「手続きによる抽象」だったわけだが、そこに至るまでの過程で実に様々な要素を学んできたことがわかる。
[scheme]：scheme文法、再帰手続き、lambda
[解釈系基礎]：置換えモデル、作用的順序と正規順序
[アルゴリズム/数学]：再帰プロセスと反復プロセス、アルゴリズムの効率、離散数学・微積・三角関数…、不動点
[ソフトウェア工学一般]：ブラックボックス抽象、高階手続きによる抽象
講師の先輩によれば、これらバラバラに見える要素が第４章「超言語的抽象」ですべて一つにつながるのだという。この本は全体的(かつ再帰的)にそのような構成をとっているのがわかってきた。つまり、当初はそれと知らされずに出てくる材料が最後にどかんとつながる。それがまた一個上のレベルでつながるというような。著者はかなり意図的にそのような構成にしたのだろう。４章に進むのが楽しみだ。
