MapReduceは副作用なしでどこまで書けるのかな？
例えば、普通にExcelで式を貼り付けるだけなら副作用のあることはしてないから、みんながExcelの式で実装しているくらいのこと（集計とかフィルタとか）はMapReduceでもできますね（もちろんExcelマクロは除きます）。項目が100万行ある見積書でもさくっと合計金額を出せるExcelシートとか。
自分がRubyで書いているコードを見返してみても、本当に副作用（状態遷移）が必要な処理ってそれほど多くない（配列やハッシュに対するフィルタリングの繰り返しだ）。Javaで書いてても、大抵のローカル変数にはfinal付けてるし。
あと、XSLTって確か副作用がなくてチューリング完全だったような。。
http://local.joelonsoftware.com/mediawiki/index.php/Java%E3%82%B9%E3%82%AF%E3%83%BC%E3%83%AB%E3%81%AE%E5%8D%B1%E9%99%BA
関数プログラミングを理解していなければ、GoogleをあれほどスケーラブルにしているアルゴリズムであるMapReduceは発明できない。MapとReduceという用語はLispと関数プログラミングから来ている。純関数プログラムは副作用がなく容易に並列化できるということを6.001に相当するプログラミングの授業で聞いて覚えている人には、MapReduceは容易に理解できる。
http://leoclock.blogspot.com/2008_09_01_archive.html
GoogleのMapReduceではこのような副作用がないというプログラムの意味(semantics)を活用して、個々のmap操作を別々のノードに計算させて超並列化を可能にしています。関数型言語を用いるとこの副作用のない部分を明確に記述できますし、驚くほど多くの計算がmap-reduce の組で書けるようです。例えば、forループで先頭から順に辿らなくても良い場合が見つけやすいと思います。Googleは並列化を促進するために、入力 listのコピーをいつくかのノードに分散して配置する工夫も行っています。検索エンジン用の索引構築なども、このMapReduceのフレームワークで再実装したとMapReduceの論文には書かれています。
http://slashdot.jp/comments.pl?sid=410269&cid=1383256
論理型言語でOSやウィンドウシステムを実装した。
OSのような副作用のカタマリのプログラムを論理型言語で実装できること、ウィンドウシステム(特にメッセージループなど)がGHCの並列プログラミングにうまく適合することを実証した。
KL1(GHC)は副作用がないそうですが、それでもOSとかウィンドウシステムとか実装できるのか！ しかも分散環境で！ さすがICOT！ おれたちにできない事を平然とやってのけるッ！ そこにしび（略
（GHCとか昔よく大学の図書館で読んだな〜もう忘れたけど）
分散化の粒度は違うね
もっとも、KL1やErlangみたいな並列プログラミング言語とMapReduceでは、分散化の粒度とか単位が大きく違う気がする。やっぱりMapReduceはバッチ専門なのかな〜？？ fairyとかSawzallみたいな専用言語から使った場合の粒度が気になる。
非同期呼び出しじゃないと使いにくいね
仮にGAE上でSawzallが公開されて、MapReduceを簡単に呼べるようになったとしても、今のGAEじゃあっという間に（数秒？）タイムアウトしてステータス500エラーとなる。たくさんのノードに処理を依頼したりするヒマはない。
なので、GAE上でMapReduceを使えるようにするには、非同期呼び出しとかプッシュの仕組みも必須になるでしょう。ソケットとかCometで、すべての結果をreduceし終わったらコールバックしてくれる、とか。Google Waveを見ればC10K対応の非同期／プッシュ基盤はもうプロダクションレベルのようなので、そのAPIを公開してくれればバッチリだ。GWTクライアントだけじゃなくてFlex/AIRクライアントもコールバックしてほしい。ついでにOTも使わせてほしい。
6/13追記
http://code.google.com/intl/ja/appengine/docs/roadmap.html
ロードマップによると、「Task queues for performing background processing」というのがあった。これって処理が終わったらコールバックしてくれるのか？ XMPPでお知らせ？
6/16追記
Google I/OのTQ解説によると、MapReduceサポートは予定されているが、すぐには実現できなさそう。
