Hatena::ブログ(Diary)

Conceptual Contexture

 | 

2010-12-26 なぜリアクティブプログラミングは重要か。

リアクティブプログラミングは、「時間とともに変化する値」=「振る舞い」同士の関係性を記述することでプログラミングを行うパラダイムです。

GUIなどのようにインタラクティブなシステムや、シミュレーションやアニメーションのようにダイナミックに状態が変化するようなシステムを宣言的に記述することができます。

これらの「変化する状態」や「外部とのやりとり」が支配的なシステムは、純粋関数型言語が、その強みを発揮しにくい部分でもあります。

本稿では、リアクティブプログラミング副作用を含む系を宣言的に記述することを可能にし、状態の管理という厄介な問題からプログラマを開放する可能性があることを示したいと思います。

(割と独自研究に基づく解釈ばかりなのでその点ご了承ください。あと例としてでてくるコードは、Pythonベースの擬似コードで具体的なライブラリに基づくものではありません。)

リアクティブプログラミングとは 21:26

まず次のような定義を行います。

a = 1

b = a * 3

そしてaに2を代入してみます。

a = 2

そしてbを出力してみましょう。

通常の命令型言語であれば、この結果は、

b -> 3

となります。

しかし、リアクティブプログラミングでは、

b -> 6

となります。

b = a * 3

の意味が、命令型プログラミングリアクティブプログラミングでは異なるわけです。

命令型プログラミングでは、そのときのaの値である1を用いて、

b = a * 3

b = 1 * 3

b = 3

という意味だと解釈され、bは3に束縛されます。

そのあとaの値が書き換えられても、bは変わらず3のままです。

一方、リアクティブプログラミングでは、

b = a * 3

は、

「bは、常にaの3倍である」

という意味になります。

時間がたち、aの値が変化しても、

b = a * 3

という関係は変わりません。

この一見奇妙な振る舞いは、日常の感覚からすると、実は普通だったりします。例えば、「温度計のさす目盛の位置は、温度の関数になっている」と言ったとき、温度によって目盛の位置が決まる、温度が変化すればそれに合わせて目盛りの位置も当然変化します。身長と体重からBMI値が求まるなら、身長や体重が変化すればBMI値も変化するのは当然です。

こういった関係のように、時間が経過し状態が変化しても一定して変わらない関係に着目するのがリアクティブプログラミングだともいえます。

関数型と比較しつつ 21:26

関数型プログラミングにおける式は、値と値の関係を表します。

f:id:pokarim:20101223194415j:image

一方リアクティブプログラミングでは、式は、振る舞いと振る舞いの関係を表します。

f:id:pokarim:20101223194537j:image

純粋な関数型プログラミングでは、参照透明であること、つまり式を値で置き換えてもプログラムの意味が変わらないことが求められます。

変数の再代入を許すと、変数や式を値で置き換えたときにつじつまがあわなくなってしまいます。

なので純粋関数型プログラミングでは変数の再代入を許さないわけです。

一方、リアクティブプログラミングでは振る舞いを扱いますが、

振る舞いも、ある一瞬を切り取れば、ただの値とかわりません。

振る舞い同士の関係は、ただの値同士の関係であり、式は参照透明なものになっています。

そして、時間がたって振る舞いが変化した場合は、値を再計算して他の振る舞いを更新することでつじつまを合わせるわけです。

f:id:pokarim:20101223194734j:image

リアクティブプログラミングでは、この更新の度に再計算するという単純なアイデアにより、宣言的な式により状態の関係性を記述することが可能になるのです。

とは言っても、実際にすべての値を再計算していては時間がかかって仕方ないので、いくつか工夫をします。

計算の工夫 21:26

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

一番基本的な工夫は、状態間の依存関係を管理して、ある状態が変化したとき、その状態に依存する状態だけについて

再計算を行うことです。

a = 1

b = 2

c = 3

d = a + b

e = d * c

の依存グラフはこんなかんじになります。

f:id:pokarim:20101223200512j:image

たとえばc = 5となった場合は、dは影響を受けないので

eだけを再計算すればよいことになります。

これを効率よく計算するには、dの値をキャッシュしておく必要があります。

そうでなければ、dの計算もやり直す必要がでます。

もうひとつの方法は、eの値をキャッシュしておいて、

e_new = e_old / c_old * c_new

を計算することです。

こちらの方法は、値が浮動小数点の場合は丸め誤差がでるため、そのままでは使えないなど

より面倒です。

どちらの方法をとるにせよ、依存グラフとキャッシュを管理することで、計算量を減らすのが、

もっとも基本的な方法になります。

差分計算

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

f:id:pokarim:20101223200513j:image

例えば、次のように整数のリストと、その合計値を定義したとします。

xs = [1,2,3,4]

y = sum(xs)

ここで、リストに対して要素を追加した場合、

追加された要素の情報だけを伝播させれば、

sum(xs)の値を更新することができます。

f:id:pokarim:20101223200514j:image

計算の先延ばし

もうひとつの方法は遅延評価を行うことです。

ある状態が更新しても、その値をすぐに使う必要が無い場合は、

その値が必要とされるときまで、再計算を先延ばしにすることで、無駄な計算を省くことができます。

イベントの種類 21:26

リアクティブプログラミングでは外部とのやりとりを、外部の「何か」と対応付けられた振る舞いを通じて行います。

対応付けたい内容に応じて、いくつかの種類の振る舞いを使い分けることが必要になります。

状態へのマッピング

もっとも基本的な振る舞いは、単純に外部の状態と対応付けられた振る舞いです

たとえばGUIHTMLのテキストフィールド、チェックボックス、スライダーなどがもつ値、マウスの現在位置などを

振る舞いとして扱うことです。

モデルのもつ状態とテキストフィールドの状態を関係付ければ、そのまま入出力が実現できます。

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()

イベントストリームは、振る舞いとは別のものとして扱われることが多いですが、

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

分散処理との関係 21:26

DAG

分散処理で使われる計算モデルのひとつに、DAG(directed-acyclic graph:有向非巡回グラフ)

があります。DAGはその名のとおり、向きがあって循環のないグラフで、各ノードで計算が行われ、

各エッジが、その方向へのデータフローとなります。

このDAGは、リアクティブプログラミングにおける依存関係のグラフとそのまま対応します。

相違点としてはリアクティブプログラミングでは循環のあるグラフを扱うこともそうでないこともあります。

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

また、分散処理では、データの塊を一度分割してそれぞれ計算を行い、その後、個々の計算結果を合成して最終結果を得るということを行います。

例えば合計値を得る処理を分散、合成すると、次のようなイメージになります。

f:id:pokarim:20101223230615j:image

この計算結果の合成と、リアクティブプログラミングにおける差分の適用は、非常に似た仕組みであると考えることができます。

違いは、リアクティブプログラミングでは、要素の追加だけではなく、削除も扱う点が挙げられます。

分散処理とリアクティブプログラミングは、その目的は違えども、ともにデータフローを扱う計算であることを考えると共通点が

多いのも当然だとも考えられます。組み合わせればいろいろと応用が考えられそうです。

ところで、なぜ重要なのか 17:13

Why Reactive Programming Matters.

えーと、リアクティブプログラミングがなぜ重要なのか、というのが本題でした。なので、実はここからがメインです。

なぜ重要だと思うのか書かなければいけません。その理由について、モジュール性の向上と状態管理の自動化という点から見てみたいと思います。

モジュール性は大事

関数プログラミングはなぜ重要か」によれば、

関数型プログラミングの利点は関数モジュール性の高さによるものです。

そして関数モジュール性の高さを遺憾なく発揮するために、副作用が無いことや遅延評価であることが必要なのだと。

リアクティブプログラミングも同じです。副作用を含むシステムをうまくモジュール化できる可能性があるから重要なのです。

構造化プログラミングからオブジェクト指向関数型プログラミングへの進化の歴史は、

モジュール性の向上の歴史でもあり、同時に「変更可能な状態」との戦いの歴史でもあります。

構造化プログラミングは、制御フローをモジュール化することに成功しましたが、

その後に「グローバル変数」の問題が残されました。

制御フローがモジュール化されてもデータがモジュール化されていなかったのです。

そこでオブジェクト指向は、データと手続きをまとめてモジュール化しました。

そこで残った問題は「変更可能なオブジェクト」のモジュール性は、実はそんなに高くないということです。

オブジェクト指向の問題は、状態をオブジェクトに閉じ込めても、各オブジェクトが持つ状態間の相互作用をゼロにすることはできないことです。

状態を持つシステムとやりとりを行うプロトコルの設計を考えればわかりやすいですが、相手が状態をもつ以上、それとやりとりする側も

相手の事情、つまり今どんな状態なのかをまったく無視して話しかけるということはできないのです。

一方純粋関数型プログラミングでは、副作用を排除した関数モジュールとすることで、高いモジュール性を得ました。

しかしそんな純粋関数型プログラミングも外部とやりとりをして仕事をなすためには、

その強力な抽象化能力をもって手続き的な処理をシミュレートせざるを得ませんでした。

こう見ていくと、オブジェクト指向副作用の分割統治を、関数型プログラミング副作用の排除を行うことで、

モジュール性を高めようとしたと考えられます。

リアクティブプログラミングでは、値を直接扱うのではなく、

「時間とともに変化していく値=振る舞い」を扱うことで、関数型プログラミングのような宣言的な記述で

変化する状態をもつ系を記述できるのです。

変化する状態を扱いながらもモジュール性が落ちないのは、状態が変化したときにそれに依存した状態が自動的に更新されるため、

状態の依存関係について意識する必要がないからです。

オブジェクト指向では、状態に依存関係がある場合、まず初期値をセットするロジックを書き、さらにObserverパターンなどを用いて

更新を管理し、さらに効率的な更新のために適切なキャッシュポイントの設定まで明示的に行う必要があります。

リアクティブプログラミングでは、

更新の管理やキャッシュポイントの設定は自動的に行われるため、

プログラマの仕事は振る舞い間の関係性だけを宣言的な式で書くことだけになるのです。

自動化も大事

モジュール性の向上と並んで重要なのが、自動化による利点です。

これはGC(ガベージコレクション)とのアナロジーで考えると分かりやすいと思います。

GCは、メモリの管理を自動化してくれるため、メモリの確保・解放を明示的にする必要がなくなります。

これによってコードの記述量が減らせるのはもちろんですが、もっとも重要なのはメモリリークや無効なポインタに関するバグなどの、

メモリ管理にまつわるバグを削減できることです。

手作業によるメモリ管理は手間がかかるだけでなく、バグの温床にもなりかねないわけですが、一度メモリ管理を自動化する仕組みを作ってそれに任せてしまえば、

場当たり的に実装するよりもバグを減らすことが可能だという理屈です。

これと同じことがリアクティブプログラミングにもあてはまります。

Observerパターンによる状態の管理は、バグを生み出しやすいことで知られています。

状態の更新管理を手作業で一つ一つ指示していくため、メモリ管理と同じく、

抜け漏れがあると特定のパターンでのみ矛盾した状態を招く厄介なバグを生み出す可能性があります。

なので状態の変更を管理する仕組みを作ってそれに任せてしまえばよいというのがリアクティブプログラミングの考え方だともいえます。

ライブラリとか 21:26

リアクティブプログラミング関数型プログラミングオブジェクト指向の比較なぞをやりましたが、実際のリアクティブプログラミングの多くは、

関数型プログラミングオブジェクト指向と組み合わせて使われることの方が多いです。

とくに関数型との組み合わせは、FRP(Functional Reactive Programming)と呼ばれたりします。

また用途としては、

などが主です。

あと、変更が起こった場所を起点に変更を伝播させていくのを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の一部として考えています。

WPF Data Binding http://msdn.microsoft.com/en-us/library/ms750612.aspx
Cocoa Bindings http://developer.apple.com/library/mac/#documentation/Cocoa/Conceptual/CocoaBindings/Concepts/WhatAreBindings.html

<追記>2010/12/27

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に代表される表計算ソフトリアクティブプログラミングの例として挙げられたりします。

表計算ソフトは、データフローアーキテクチャの文脈でもよく引き合いにだされます。データフローアーキテクチャリアクティブプログラミングは、それぞれが指す対象が非常にかぶっていて、どちらの定義もわりと曖昧なので、いまいち明確に区別できていません。

ソフトウェアアーキテクチャとみるか、プログラミングパラダイムと見るかの違いでしょうか。

今後の課題とか 21:55

リアクティブプログラミング関数型プログラミングなどに比べてまだまだマイナーなパラダイムですが、上に述べたようにすでにいくつものライブラリでサポートされていて、ブレイクするのも時間の問題と言いたいところですが、関数型プログラミングだってキャズム越えも近いかな?という状況なのでもうちょい時間がかかるとは思います。

もっぱらの課題は、効率面であることが多いようです。変更の伝播や差分の反映、キャッシュの活用などを、実際に適用領域にあわせて以下に効率よく計算するかという点では、ガベージコレクションの技術などに比べるとまだ発展途上であると感じています。

最後に自分の話 21:55

まとまりのない話を最後まで読んでいただきどうもありがとうございます。最後に自分が取り組んでいることの話を少し。

自分が取り組んでいるのはデータベースリアクティブプログラミングの融合です。リアクティブプログラミングはわりとクライアントサイドメインの方が多く、永続化と絡めて扱われることはわりと少数派なようですが、データベースモデルからアプリケーションロジック、そしてGUIまでを一貫してリアクティブプログラミングで記述できれば色々利点があると思っています。その話はおもに、リアクティブプログラミングに適したデータベースモデルってなんだろうかという方向の話になります。それに関してはまた今度機会があれば書きたいなとおもっております。

<追記>2010/12/27

id:kazu-yamamoto さんやその他の方にご指摘いただき誤字を修正しました。

</追記>

<追記>2010/12/27

思った以上にたくさんの方に読んでいただけたようで感激です。普段は、

http://twitter.com/pokarim

で主にプログラミングパラダイム系のネタをつぶやいているので、よかったらそちらもよろしくです。

</追記>

<修正>2011/8/28

@twit_e_p_i さんに指摘され、遅延評価も無いことが必要であるようにも読める表現だったので、以下のように修正しました。

遅延評価副作用がないこと」=>「副作用が無いことや遅延評価であること」

</修正>

osiireosiire 2010/12/26 23:58 素晴らしい。やや抽象的で概念的な話がすごく平易な言葉で語られている良エントリだと思います。
実装と効率の問題は一筋縄にいかない難しい問題ですが、DrScheme(現Racket)のFrTimeではかなり成功しているらしいです。多分静的型付け言語よりうまくいっているので、python実装の参考になるかもしれません。ご参考まで。

pokarimpokarim 2010/12/27 00:30 ありがとうございます!光栄です!FrTime調べてみます!

いちごいちご 2010/12/27 02:13 個人的にはリアルタイムな値更新の環境として一番に思いつくのがFPGAだったりします。
ノーマルなプログラミング可能領域といくつかの入出力変数を持つFPGA領域を併せ持った環境があればいいのになと思ったりします。
もっというと、あとから、各々の領域をハードウェア的に(或いはソフトウェア的に)増設できるといいんでしょうが。
そうなるとプログラマーは大変でしょうけどねー。

saiya_moebiussaiya_moebius 2010/12/27 11:21 1 アプリケーションとして本気で Reactive Programming している(珍しい)実例として、Mathematica を実際にいじってみるととても面白いですよ。
id:NyaRuRu さんの http://d.hatena.ne.jp/NyaRuRu/20080314/p1 (スライドが消えているのが残念・・・)や http://d.hatena.ne.jp/NyaRuRu/20080317/p1 あたりがその辺の文脈の参考になるかと。

kazu-yamamotokazu-yamamoto 2010/12/27 11:27 すてきな記事をありがとうございます。
一カ所、誤植ではないかと思われる文章を発見しました。
「各オブジェクトもつの状態間の」→「各オブジェクトもつ状態間の」
昨日、ちらっと見たときは「りアクティブ」という誤植もあったような気がしたのですが、
今はないようなので、修正されたのでしょうね。

pokarimpokarim 2010/12/27 13:42 皆様どうもコメントありがとうございます。

> いちごさん
FPGAといえば、Verilog HDLにはReactive Programmingの要素が取り入れられているそうです。
回路設計のほうは守備範囲外なのですが、ハードに近いとまた別の難しさがありそうですね。

> saiya_moebiusさん
Mathematica、すごいらしいという噂だけは聞いていたんですが、たしかにWPF Data Bindingよりかなり突っ込んだ取扱いがされているようですね。もうちょっと調べてみます。

> kazu-yamamotoさん
ありがとうございます。修正させていただきます。
「りアクティブ」の方は昨晩こっそり修正しました。

DrFaustDrFaust 2010/12/28 03:05 興味深いエントリをありがとうございます。このキーワード(リアクティブ・プログラミング)は初めて知ったのですが、ふと思ったのは、単体より上位のソフトウェア・テストの記述を、少ないコード量で網羅的に書けたりできないものかな〜などと。単なる妄想ですが。
的外れだったらごめんなさい。

たーぷらたーぷら 2010/12/28 05:44 パラダイムとしてはデータ駆動型並列計算機(amazonに関連書籍あり)を思い出しました。適用ターゲットとしては大量の時系列データを扱う「ストリームデータ処理」(株のアルゴリズム取引や工場・電力系統等の大量センサを使うインフラ)もありそうです。FPGA回路から大規模ストリームデータ処理まで、一貫して効率よくプログラミングできるようにする言語とか夢がありますね。

pokarimpokarim 2010/12/30 20:51 コメントありがとうございます!

> DrFaustさん
業務アプリ開発を想定されているようにお見受けしますが(外していたらごめんなさい)、
業務アプリ開発に応用して、ソフトウェアの記述を短くすることは可能だと思います。
たとえば、入荷したら在庫数をインクリメント、出荷したらデクリメントと手続的に記述するよりも、
在庫数 = SUM(入荷数) - SUM(出荷数)
と記述するほうが短くかける可能性があります。特に入荷記録の変更や取り消しなどを考えると利点が顕著になります。
ぼくも業務Webアプリへの応用を考えているのでそのうちもう少し詳しく書きたいと思います。
テストの記述への応用も考えられそうですが、ちょっと今の時点では思いつきません。
もうすこし考えてみたいと思います。

>たーぷらさん
データ駆動型という言葉は知りませんでした。簡単に調べてみましたが、データフローに近そうですね。
ストリームデータ処理への応用は大いに考えられます。ストリームデータ処理でも時系列データに対する差分的な計算が登場するので
その部分をより宣言的に書く、というよりむしろストリームデータに対する処理であることを意識しないで記述できるかもしれません。
パフォーマンスがシビアに求められる分野なので、実用には時間がかかるかもしれませんが。
一つのロジックを書けば、それがストリームに対する処理でも分散処理でもFPGA上でも動くというのは夢がありますね。
統一的に扱えるようにするには、やはりデータモデルやデータ構造の部分が重要になると思います。
そこらへんにかんしてもその内書きたいと思っています。

 |