最後に自分の話

まとまりのない話を最後まで読んでいただきどうもありがとうございます。最後に自分が取り組んでいることの話を少し。
自分が取り組んでいるのはデータベースとリアクティブプログラミングの融合です。リアクティブプログラミングはわりとクライアントサイドメインの方が多く、永続化と絡めて扱われることはわりと少数派なようですが、データベースモデルからアプリケーションロジック、そしてGUIまでを一貫してリアクティブプログラミングで記述できれば色々利点があると思っています。その話はおもに、リアクティブプログラミングに適したデータベースモデルってなんだろうかという方向の話になります。それに関してはまた今度機会があれば書きたいなとおもっております。<追記>2010/12/27
id:kazu-yamamoto さんやその他の方にご指摘いただき誤字を修正しました。
<追記>2010/12/27
思った以上にたくさんの方に読んでいただけたようで感激です。普段は、
http://twitter.com/pokarim
で主にプログラミングパラダイム系のネタをつぶやいているので、よかったらそちらもよろしくです。
<修正>2011/8/28
@twit_e_p_i さんに指摘され、遅延評価も無いことが必要であるようにも読める表現だったので、以下のように修正しました。
「遅延評価や副作用がないこと」=>「副作用が無いことや遅延評価であること」

今後の課題とか

リアクティブプログラミングは関数型プログラミングなどに比べてまだまだマイナーなパラダイムですが、上に述べたようにすでにいくつものライブラリでサポートされていて、ブレイクするのも時間の問題と言いたいところですが、関数型プログラミングだってキャズム越えも近いかな?という状況なのでもうちょい時間がかかるとは思います。
もっぱらの課題は、効率面であることが多いようです。変更の伝播や差分の反映、キャッシュの活用などを、実際に適用領域にあわせて以下に効率よく計算するかという点では、ガベージコレクションの技術などに比べるとまだ発展途上であると感じています。

ライブラリとか

リアクティブプログラミングと関数型プログラミングオブジェクト指向の比較なぞをやりましたが、実際のリアクティブプログラミングの多くは、
関数型プログラミングオブジェクト指向と組み合わせて使われることの方が多いです。
とくに関数型との組み合わせは、FRP(Functional Reactive Programming)と呼ばれたりします。
また用途としては、

  • シミュレーションやアニメーション
  • GUI
  • 非同期イベント処理
  • 並列処理

などが主です。
あと、変更が起こった場所を起点に変更を伝播させていくのをpush-base、振る舞いの現在の値を取得する側を起点に計算を行うのをpull-baseと呼んで、各ライブラリでいろいろな戦略が取られています。
実際のライブラリやフレームワークとしては、

HaskellFRP http://www.haskell.org/haskellwiki/Functional_Reactive_Programming

HaskellにはいくつもFRPのライブラリが存在します。モナドベースだったりアローベースだったりします。
アニメーションやシミュレーション系が多い印象です。

Concurrent Cell http://ccell.forge.ocamlcore.org/

Concurrent Cellは、OCamlのマルチスレッドライブラリで、Erlangのようなメッセージ・パッシングスタイルをサポートするとともに、FRPもサポートされています。

Rx(Reactive Extensions for .NET) http://msdn.microsoft.com/en-us/devlabs/ee794896

Rx(Reactive Extensions for .NET)は、LINQのシーケンス処理をベースに、非同期イベント処理のリアクティブな記述を、push-base、pull-baseの両面からサポートしています。

RxJS(Reactive Extensions for JavaScript) http://channel9.msdn.com/Blogs/Charles/Introducing-RxJS-Reactive-Extensions-for-JavaScript

RxJSは、RxをJavaScriptへポートしたものです。

Flapjax http://www.flapjax-lang.org/

Flapjaxはブラウザ上で動くJavaScriptベースのリアクティブフレームワークで、サーバーサイドの永続化までサポートしています。<追記>

FrTime http://docs.racket-lang.org/frtime/index.html

FrTimeは、RacketというScheme処理系上で実装されたSchemeベースのDSLで、描画統合環境上でリアクティブプログラミングができるようです。
教えていただいたところによると実装上の効率の問題がかなり解決されているようです。
id:osiire様に教えていただきました。ありがとうございます!)

Data binding

GUI上のウィジェットとその背後に用意したモデルを結びつけるリアクティブな手法は、特にData bindingと呼ばれます。
上に述べたライブラリに比べるとシンプルでリアクティブな要素が少ないですが、WikipediaのReactive Programmingのページに例として次に紹介するWPF Data Bindingが載っていたので、Data bindingもReactive Programmingの一部として考えています。

JavaFX Data Binding http://download.oracle.com/javafx/1.3/tutorials/core/dataBinding/

Twitter経由でJavaFXにもData Bindingがあると教えていただきました。

Flex Data Binding http://blog.flexexamples.com/2007/10/01/data-binding-in-flex/

忘れていましたがFlexにもData Bindingはあります。最近のGUIツールキットには軒並み搭載されているようです。

MathematicaのDynamic http://reference.wolfram.com/mathematica/tutorial/IntroductionToDynamic.html

数式処理ソフトのMathematicaに搭載されている動的インタラクティブ機能言語であるところのDynamicは、
上記のData Bindingに似つつもさらに突っ込んだ機能を、WPFなどに先んじて実現しているようです。
id:saiya_moebiusさんに教えていただいた、id:NyaRuRuさんの記事も大変面白いのでぜひご覧ください。
http://d.hatena.ne.jp/NyaRuRu/20080314/p1
http://d.hatena.ne.jp/NyaRuRu/20080317/p1

Verilog HDL http://en.wikipedia.org/wiki/Verilog

いちごさんのコメントで思いだしましたが、ハードウェア記述言語であるところのVerilog HDLも並列動作する電子回路を記述するためにデータフローアーキテクチャが採用されており、これもReactive Programmingの一例とも言えます。

表計算ソフト

あとはExcelに代表される表計算ソフトもリアクティブプログラミングの例として挙げられたりします。
表計算ソフトは、データフローアーキテクチャの文脈でもよく引き合いにだされます。データフローアーキテクチャとリアクティブプログラミングは、それぞれが指す対象が非常にかぶっていて、どちらの定義もわりと曖昧なので、いまいち明確に区別できていません。
ソフトウェアアーキテクチャとみるか、プログラミングパラダイムと見るかの違いでしょうか。

分散処理との関係

DAG

分散処理で使われる計算モデルのひとつに、DAG(directed-acyclic graph:有向非巡回グラフ)
があります。DAGはその名のとおり、向きがあって循環のないグラフで、各ノードで計算が行われ、
各エッジが、その方向へのデータフローとなります。
このDAGは、リアクティブプログラミングにおける依存関係のグラフとそのまま対応します。
相違点としてはリアクティブプログラミングでは循環のあるグラフを扱うこともそうでないこともあります。

計算結果の合成と差分適用

また、分散処理では、データの塊を一度分割してそれぞれ計算を行い、その後、個々の計算結果を合成して最終結果を得るということを行います。
例えば合計値を得る処理を分散、合成すると、次のようなイメージになります。


この計算結果の合成と、リアクティブプログラミングにおける差分の適用は、非常に似た仕組みであると考えることができます。
違いは、リアクティブプログラミングでは、要素の追加だけではなく、削除も扱う点が挙げられます。

分散処理とリアクティブプログラミングは、その目的は違えども、ともにデータフローを扱う計算であることを考えると共通点が
多いのも当然だとも考えられます。組み合わせればいろいろと応用が考えられそうです。

イベントの種類

リアクティブプログラミングでは外部とのやりとりを、外部の「何か」と対応付けられた振る舞いを通じて行います。
対応付けたい内容に応じて、いくつかの種類の振る舞いを使い分けることが必要になります。

状態へのマッピング

もっとも基本的な振る舞いは、単純に外部の状態と対応付けられた振る舞いです
たとえばGUIやHTMLのテキストフィールド、チェックボックス、スライダーなどがもつ値、マウスの現在位置などを
振る舞いとして扱うことです。
モデルのもつ状態とテキストフィールドの状態を関係付ければ、そのまま入出力が実現できます。
Excelのセルもひとつの振る舞いだと考えることもできます。
シミュレーションであれば、温度などのセンサーからの入力値や、電流値、電圧値なども振る舞いとして扱います。

時間へのマッピング

もうひとつの方法は、システム時刻などを振る舞いとして扱うことです。
時刻は当然、外部から入力がなくても自動的に変化していきます
これを振る舞いとして扱うことで、アニメーションやシミュレーションを行うことができます。
たとえば、
bee = render("bee.jpg", x=sin(t), y=cos(t))
とすれば、円を描くアニメーションをさせることができます。
微分積分の演算が提供されていれば、加速度をもつ物体のシミュレーションなどができます。

入力ストリームへのマッピング

状態や時間に対応した振る舞いだけでは、離散的なイベントを扱うことができません。
マウスがクリックされている状態を扱うのではなく、
マウスがクリックされたタイミングで何かを行うには、
マウスのクリックをイベントとして扱う必要があります。
リアクティブプログラミングでは、これらは一般的に離散的なイベントのストリームとして扱います。
たとえばクリックされた回数を数えるには、
mouseClick.count()
とします。ここで、数えた回数自体は、時間変化する値を持つ通常の振る舞いになります。
イベントストリームの処理は、リストの処理などと同様に、フィルタリングや合成を行うことができます。
(mouseClick + keyPress).count()
とすれば、マウスのクリックとキープレスのイベントの両方を数えることができます。
また、マウスの左クリックだけを数える場合はフィルタリングを使って次のようにかけるでしょう。
mouseClick.filter(lambda e:e.key == "left").count()
イベントストリームからイベントストリームを生成することもできます。
たとえば、マウスがクリックされたらアラートを表示するには次のようになるでしょう。
mouseClick.alert()

イベントストリームは、振る舞いとは別のものとして扱われることが多いですが、
見方を変えれば、イベントストリームは「イベントの履歴」という値の振る舞いだと考えることもできます。

計算の工夫

依存グラフとキャッシュの管理

一番基本的な工夫は、状態間の依存関係を管理して、ある状態が変化したとき、その状態に依存する状態だけについて
再計算を行うことです。
a = 1
b = 2
c = 3
d = a + b
e = d * c
の依存グラフはこんなかんじになります。


たとえばc = 5となった場合は、dは影響を受けないので
eだけを再計算すればよいことになります。
これを効率よく計算するには、dの値をキャッシュしておく必要があります。
そうでなければ、dの計算もやり直す必要がでます。
もうひとつの方法は、eの値をキャッシュしておいて、
e_new = e_old / c_old * c_new
を計算することです。
こちらの方法は、値が浮動小数点の場合は丸め誤差がでるため、そのままでは使えないなど
より面倒です。
どちらの方法をとるにせよ、依存グラフとキャッシュを管理することで、計算量を減らすのが、
もっとも基本的な方法になります。

差分計算

もうひとつの工夫は、依存グラフにそって、変更の差分だけを伝えることです。

例えば、次のように整数のリストと、その合計値を定義したとします。
xs = [1,2,3,4]
y = sum(xs)
ここで、リストに対して要素を追加した場合、
追加された要素の情報だけを伝播させれば、
sum(xs)の値を更新することができます。

計算の先延ばし

もうひとつの方法は遅延評価を行うことです。
ある状態が更新しても、その値をすぐに使う必要が無い場合は、
その値が必要とされるときまで、再計算を先延ばしにすることで、無駄な計算を省くことができます。