読者です 読者をやめる 読者になる 読者になる

bitterharvest’s diary

A Bitter Harvestは小説の題名。作者は豪州のPeter Yeldham。苦闘の末に勝ちえた偏見からの解放は命との引換になったという悲しい物語

ボールの衝突をFunctional Reactive Programmingで表現する(1)

今年の夏は、気象庁の発表によれば、平年並みの暑さだったそうである。後半に入って、気温がずっと下がったせいだ。しかし、気温が下がり始めるのと同時にマレーシアに行ったものにとっては、この夏はずっと猛暑であったように感じている。とても、過ごしにくい夏であったと私の脳には記憶されると思う。

5連休のシルバーウィークは秋晴れのよい日が続いたが、夏の暑さからの疲れが出て風邪をひいてしまった。また、大学は、数年前から祭日は授業を行うようになったので、シルバーウィークを楽しむことはできなかった。この春、ぎっくり腰をしてから、腰の調子が今一つということも多く、長いこと座っていられないので、ブログを書く回数も随分と減ってきたが、心機一転、また、いろいろなことを書いてみたいと思う。

1.関数型リアクティブ・プログラミング

12月末に、いよいよ、関数型リアクティブ・プログラミング(FRP:Functional Reactive Programming)の本www.amazon.co.jp
が出版されるそうだ。このブログでも、NetwireとYampaについて説明したが、この本では、Sodiumと呼ばれるリアクティブ・プログラミングのライブラリをもちいて説明してる。これまでは論文でしか知ることができなかった関数型リアクティブ・プログラミングを、体系だって学べる機会が得られることになり、多くの人に知ってもらう良いきっかけになると思う。なお、関数型リアクティブ・プログラミングのライブラリは、Yampa, Netwire, Sodiumの他にもたくさんある。それらについて知りたい人は、frp-zooのブログを参照するとよい。このブログではEvan Czaplicki提案の問題がそれぞれのライブラリでどのようにプログラムとして記述されるかを示しているので、手っ取り早く、比較したい場合には参考にするとよい。

さて、関数型リアクティブ・プログラミングとは何かを簡単に説明しておく。関数型リアクティブ・プログラミングは関数型プログラミングとリアクティブ・プログラミングを混合したものである。

1.1 関数型プログラミング

まず、関数型プログラミングの方から説明する。プログラミングのスタイルのは二つに大別することができる。一つは手続き的であり、もう一つは宣言的である。C, Javaなど広く使われている言語は手続き型に属す。手続き型の言語は、計算の手順を示す。一般にアルゴリズムと呼べれている。例えば、素数を求めるプログラムは、次の手続きをプログラミングする。
1) 2は素数である。それ以上の素数を以下の手順で求める。
2) iを3とする。
3) iという値が素数であるかどうかを調べる。これには、2から始めて\(\sqrt i\)を越えない整数(あるいはこれまでに求めた素数)で割り切れるかどうかを調べる。もし割り切れなければ、iは素数であり、そうでなければ素数ではない。
4) iの数を一つ増やし、2)へ行く。もし、iの値が求める範囲を超えたときは終了する。

HaskellClojureは関数型である。これらの言語では計算の構造をプログラムとして記述する。このため、プログラムは数学の公式のようになる。例えば先の素数は、Haskellで記述すると次のようになる。

primes = fileterPrime [2..]
  where filterPrime (p:xs) =
          p:filterPrime [x | x <-xs, x `mod` p /= 0]

上記のプログラムは次のように読む。素数(prime)は2から始まる整数の列から素数だけを取り出したもの(filterPrime)である。filterPrimeについてはwhereのところで説明があり、これは次のようになっている。
先頭をpそれに続く数列をxsとした数列(p:xs)にfilterPrimeを施したものは、pを素数とし、xsからpで割り切れるものを除いた数列にfilterPrimeを施したものと同値である。また、これが正しいことの証明は簡単である。高校の時に学習した数学的帰納法を用いればよい。即ち、filterPrime [2..]から、最初の出力されるもの(この場合には2)が素数であることを証明し、n番目に出力されるものが素数と仮定すれば、n+1番目に出力されるものも素数であると証明すればよい。

少し、比喩的であるが、手続き型でのプログラミングがHow型であるのに対して、宣言型のそれはwhat型である。宣言型が手続き型に対して優位な点は、数学的な証明が簡単なことであり、これがプログラムの分かりやすさを醸し出している。一方で、文系卒のプログラマーにとってはとっつきにくいと感じられるかもしれない。

1.2 リアクティブ・プログラミング

それでは、リアクティブ・プログラミングの説明に移る。reactiveの意味は、「刺激に反応する」である。ソフトウェアの世界でreactiveなものを考えると、ある値を変えたらそれに関連する値も一緒に代わるがこれに当たる。

身近なところでは、表計算のソフトがこの例の一つである。学生などの成績を表計算ソフトに入力すると、入力した分についての、合計点や平均値を自動的に計算してくれる。一か所を変えると、それに関連するところが、自動的に変わるというのが表計算ソフトである。表計算ソフトはダニエル・ブルックリンによって作り出された。彼が、ハーバード大学ビジネススクールの学生だった頃に、前提条件の数値を変えるたびに再計算しなければならない不便を解消すべく作り出したのが、このソフトである。

関数型リアクティブ・プログラミングで、リアクティブ・プログラミングが多く利用されている分野は、ゲーム、シミュレーション、ロボットなどである。これらの分野では、時間の変化とともに、内容がさまざまに変化していく。例えば、落下するボールを考えると、時間を与えれば、その時の速度と位置を求めることができる。表計算ソフトの時と同じように、時間を記入すれば、速度と位置が表示されるようなものだ。本当はマウスやキーボードからの入力もありもう少し複雑なのだが、これらの入力も時間に紐づけられていると考えると同じになる。

それでは、落下するボールを例にとって、どのようにリアクティブプログラミングが構成されるかを見ていく。重力を\(g\)とし、初速度を\(v_{t_0}\)とし、投げた位置を\(p_{t_0}\)とする。また、議論を簡単にするためにボールはただの点であるとする。\(t\)秒後の速度と位置は、それぞれ、
\(v_t = v_{t_0} -\int g dt\)
\(p_t= p_{t_0} + \int v_t dt\)
になる。

上記の式は連続的な時間に対して定義されているが、コンピュータ上でシミュレーションするときは離散的な時間を用いる。落下時の時間を\(t_0\)とし、微小な時間間隔\(dt\)が\(i\)回すぎたときのの速度と位置を求めると次のようになる。
\(v_{t_i} = v_{t_{i-1}} - g dt\)
\(p_{t_i} = p_{t_{i-1}} + v_{t_{i-1}} dt\)
上記の式は、ひとつ前のボールの速度と位置から現在のボールの速度と位置を得ている。

ところで、ボールは永遠に落下し続けることはない。地面にぶつかって跳ね返ってくる。今、跳ね返りの係数を1とする(完全弾性体)と、衝突した後、高さ方向には反対向きの速度を得て進むことになる(地表面の方向には速度を変えない)。そこで、微小な時間間隔が\(k - 1\)回過ぎて\(k\)回の前でボールが地面に衝突したとする。また、地面の高さを0とすると、衝突する前後での速度と高さは次のようになる。なお、これまで説明してこなかったが、速度と位置はベクトルで、地面で水平でボールが投げられた方向をx成分に、高さ方向をy成分とする。ベクトル\(v\)をその成分で表したものを\((\rm{v_x,v_y})\)で表す。衝突前後のボールの速度と位置は次のようになる

\(v_{t_{k - 1}} = v_{t_{k - 2}} - g dt\)
\(p_{t_{k - 1}} = p_{t_{k - 2}} + v_{t_{k - 2}} dt\) > 0

\(v_{t_k} = (\rm{ v_x, -v_y})\) ここで、 \(({\rm v_x,v_y})= v_{t_{k - 1}} - g dt\)
\(p_{t_k} = -p'_{t_k}\) ここで、\(p'_{t_k}=p_{t_{k - 1}} + v_{t_{k - 1}} dt<0\)

この様子を図で示すと以下のようになる。
f:id:bitterharvest:20150924155618p:plain

ボールの落下運動を描写するプログラムにおいては、紙芝居のように、時間の順番に青い箱が次から次へと提示される(実際に提示されるのは計算の結果得られたボールの落下図である)。図で、青い箱の中にあるのが、速度と位置を求める関数である。リアクティブ・プログラミングではこれらの関数は振舞い(Behavior)と呼ばれることがおおい。速度を求める振舞いは、重力\((-g)\)を入力とし、速度\((v)\)を出力としている。この出力は、次の時間間隔\(dt\)になった時の位置を求めるときに利用される。位置を求める振舞いは、速度\((v)\)を入力とし、位置\((p)\)を
出力としている。この出力はボールの位置を描画するときに利用される。

この部分はとても大雑把なプログラムで示すと次のように記述できる。

rec v             <- integral vo -< (-g, collision)
   (p, collision) <- integral po -< v

上記のプログラムは、出力 <- 処理 -< 入力という形で記述されているが、これはアロー記法と呼ばれる。それぞれの関数では、入力を受けて処理を行い、そして出力する。最初のプログラムは\(v(t) = vo + \int - g dt\)を意味し、次のプログラムは\(p(t) = po + \int v(t) dt\)を意味する。衝突の処理の記述は省いてある。
ここで、vo=\(v_{t_0}\),po=\(p_{t_0}\)である。処理のintegralのところは積分の演算を行う部分である。collisionは、地面と衝突があったかどうかを示すものであるが検出の処理は省いてある。また、衝突があった場合には、速度の方向が変化する。これはスイッチと呼ばれる関数で実現されるがその処理も省いてある。
recは(速度と位置を求める振舞いを)並列に再帰的に実行することを意味する。

上記の例はとても簡単な例であるが、ゲームなどのおいては、人間が介入してくる。これはイベントと称されるが、このイベントは地面との衝突と同じように扱うことができる。

2.ビリヤードのボールの衝突

再帰的リアクティブ・プログラミングの説明が一通り済んだので、次回からは、ビリヤードでのボールの衝突を例にとって説明する。