Hatena::ブログ(Diary)

言語ゲーム このページをアンテナに追加 RSSフィード Twitter

とあるエンジニアが嘘ばかり書く日記
ホームページ | blog | twitter

2007-03-15

論文読み: Arrows, Robots, and Functional Reactive Programming http://www.haskell.org/yampa/AFPLectureNotes.pdf

Haskell のアニメーションライブラリ Yampa についてのチュートリアル。またもや FRP (Functional Reactive Programming) の話題です。SOE の FAL は休憩して、その未来の姿である Yampa に寄り道します。Monad を一般化した Arrow なるものを使って、time / space leak なる物を排除し、モバイルロボットのプログラムをきっちり記述します。

プログラムの例として、シムボット(ロボットシミュレータ)を扱います。シムボットは二つの独立して動く車輪を持ち、ぶつかりセンサーや、前後左右に光学センサーを持ちます。また、他のシムボットの位置を知る事も出来ます。

シグナル (p 3)

一番重要な概念はシグナルです。

  • Signal a = Time -> a

つまり、シグナルとは時間の関数です。例えばシムボットは車輪が二つあるので、それぞれの車輪の速度(speed)を Speed 型で表すとすれば、全体の速度(velocity)は Signal(Speed, Speed) で表現出来ます(speed と velocity の違いは何なのだろう。。。)。という事である時点のシムボットの x, y 座標と方向 theta は以下のようなプログラムで表現します。

  • x = (1/2) * integral ((vr + vl) * cos theta)
  • y = (1/2) * integral ((vr + vl) * sin theta)
  • theta = (1/l) * integral (vr - vl)
  • x, y, theta : シムボットの座標と向き
  • vr, vl : 左右の車輪のスピード
  • l : 左右の車輪の距離
  • integral : 時刻 0 から 時刻 t まで積分する

こんなに上手く行くものか。。。それぞれの変数は暗黙の t が省略されています。例えば x は普通の数学の書き方では x(t) の事で、つまり関数です。積分とか言われると僕はもうサッパリですが、後で考えます。

Arrow

以前の FAL では、時間空間漏れの問題にすごい工夫が必要でしたが、Yampa ではすごい解決策を取っています。シグナルには直接触れず、シグナルの関数だけを操作出来る!そうです。そういった操作を SF 型と呼びます。

  • SF a b = Signal a -> Signal b

つまり、勝手に時間の関数を書かれると絶対問題が起こるので、原始的なシグナルを最初から用意して、シグナルの関数を組み合わせる事で複雑なシグナルを構成するという方法をとります。こういったシグナルの関数(またはコンビネータ)の表現に Arrow を使います。Arrow が Monad と違う所は、Monad による組み合わせが直線的なのに比べて、Arrow ではもっと複雑な線に出来るそうです。

まず最初に必要な操作は、普通の関数をシグナル関数に "lift" する物です。lift というのは普通の言語で言うとコンストラクタの事です。シグナル a をシグナル b に変換する関数 (a -> b) を、arr によって SF 型に格納します。

arr :: (a -> b) -> SF a b

次に、シグナル関数同志を組み合わせる分けですが、関数合成の書き方、つまり f2(f1(x)) と書く代わりに (f2 . f1) x と書く方法をとります。ただし、関数の順序をひっくり返します。例えば f2(f1(シグナル)) のように合成するコンビネータを次のように書きます。

(>>>) :: SF a b -> SF b c -> SF a c
g' :: SF A C
g' = arr g
   = arr f1 >>> arr f2

入力が一つで出力が二つあるような操作を考えます。そういうのは &&& で表現します。

(&&&) :: SF a b -> SF a c -> SF a (b,c)
h' :: SF A (B,C)
h' = arr h
   = arr f1 &&& arr f2

何の役に立つのか分かりませんが、引数が二つあって答えそれぞれに関数を適用して二つの答えを返すのを *** で表現するそうです。

(***) :: SF b c -> SF b' c' -> SF (b,b') (c,c')
f *** g = (arr fst >>> f) &&& (arr snd >>> g)

形式的な定義 (p 6)

Arrow の定義です。Yampa の SF は Arrow のインスタンスとして定義されています。(Java 的に言うと、SF は Arrow インタフェースを持ちます。) 今まで SF (シグナル関数) を組み合わせる基本操作として arr, >>>, &&& が出てきましたが、元々の基本セットは arr, >>>, first だそうです。&&& はここから導く事が出来ます。

class Arrow a where
    arr :: (b -> c) -> a b c
    (>>>) :: a b c -> a c d -> a b d
    first :: a b c -> a (b,d) (c,d)

そして、実はふつうの関数も Arrow のインスタンスです。これは分かりやすい例なので、分からなくなったら普通の関数の例を考えると良いと思います。最初から言えよ!

instance Arrow (->) where
    arr f = f
    f >>> g = g . f
    first f = \(b,d) -> (f b, d)

長々と意味の分からない事を書いてすみません。実は具体的な本当に面白い話が始まるのはこの後なのですが、眠いので寝ます。

シムボットの例を考える。(p 9)

続きを書くと書いたので続けます。シムボットの x 座標は以下の式で表現出来ると書きました。

  • x = (1/2) * integral ((vr + vl) * cos theta)

f:id:propella:20070316154416j:image

これを Yampa で表現するには、シグナル(時間に応じて変化する速度や角度) そのままを扱う事が出来ません。変わりにシグナル関数を使います。例えば vr 右車輪速度の場合 vrSF :: SF SimbotImput Speed つまり、SimbotImput (外界情報シグナル) -> Speed (速度シグナル) の関数として扱います。

  • SF SimbotImput Distance が x 座標取得装置全体を表現します。
    • SimbotInput はシムボットの受け取る状態です。
  • vrSF :: SF SimbotInput Speed は右車輪の速度です。
  • vlSF :: SF SimbotInput Speed は左車輪の速度です。
  • thetaSF :: SF SimbotInput Angle は角度です。
  • arr2 は arr の二引数版。二項演算子を lift します。
xSF :: SF SimbotInput Distance
xSF = let v = (vrSF &&& vlSF) >>> arr2 (+)
          t = thetaSF          >>> arr cos
          in  (v    &&& t)    >>> arr2 (*) >>> integral >>> arr (/2)

この中で、integral だけ妙に分かりにくいと思います。integral は普通の言語の ++ や increaseBy: に相当する物です。例えば integral 5 と言うと、最初の値は 0 で、一秒後が 5 で、二秒後が 10 で、、、と順に増えて行きます。普通と違うのは時間の概念を含む事で、例えば 1.5 秒後だとちゃんと 7.5 になります。内部的には (値 += 前回からの経過時間 * 引数) のようになっているので、引数が 5 のような定数でなく、変数になってくると数学的に積分した値と違って来るのが注意点です。この実装の良し悪しはともかく以下の点で非常に重要なポイントです。

  • integral の内部状態には絶対外からアクセス出来ない。これにより内部状態があるにも関わらず論理破綻が起きない。
  • 加算によって積分するというのは、eToys 最大のコンセプトの一つです。我々が将来 eToys を FRP で実装する際の強力な武器になります。

Arrow 記法 (p 10)

さすがにこれでは難しいだろうという事で、構文糖を使った表現が提案されています。違う部分は &&& を省略できるぐらいで難しさは似たり寄ったりだと思いますが、参考までに。

xSF' :: SF SimbotInput Distance
xSF' = proc inp -> do           -- inp は入力
       vr <- vrSF -< inp        -- 意味は何となく取れるが実は良く分からない。
       vl <- vlSF -< inp
       theta <- thetaSF -< inp
       i <- integral -< (vr+vl) * cos theta
       returnA -< (i/2)

不連続イベント (p11)

つづく!

FlorianFlorian 2007/03/17 18:00 文脈をとらえる限り(やだなぁ、このいい方)Speedはスカラー量、Velocityはベクター量ですね。よく、「速さと速度は異なるものととらえなさい」と物理学や幾何学でいわれたような気がします。
しかし、速度を位置に積分しているところの「1/2」という値が非常に気になります。integralという関数は本物の積分(integral)として自動的に次数を上げて1/2してくれるわけではないのですか……。
微分形式と積分形式を自動で行ったり来たりする(極限という考え方を導入せずに)ような処理系を夢想していたのでちょっと残念でした。
……っていうか、いい加減Haskel覚えろって>自分

propellapropella 2007/03/18 15:17 「速さと速度は異なるものととらえなさい」ですか。高さと高度は違うようなもんですか(違。

この 1/2 は積分の 1/2 じゃ無くて単に左右の車輪の速度を平均してるだけじゃないですかね。内部的に integral は経過時間の重みをつけて += してるだけなので、 1/2 が無くてもそれっぽい値が出るはずです。

参考) http://metatoys.org/propella/js/workspace.cgi/Acceleration

という事は、やっぱりある意味勝手に積分するという事です!ただし、連続と非連続の深遠を行ったり来たりは出来ないです。連続と非連続の断続は、宣言型と命令型の断続にも似て(僕はここに強い相似形を感じています)、FRP の重要なテーマなので、じっくりやって行きたいです。

propellapropella 2007/03/18 15:23 と思ったけど、やっぱり integral の後に 1/2 しているという事は平均じゃないな。上の説明は Yampa の前身である FAL の実装を参考に書いたので、Yampa は変わってるのかも知れない。何か分かったらまた書きます。


カレンダー
<< 2007/03 >>
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31
最新コメント一覧