言語ゲーム

とあるエンジニアが嘘ばかり書く日記

Twitter: @propella

論文よみ。Lowering: A Static Optimization Technique for Transparent Functional Reactivity

この期に及んで現実逃避モード。論文を読みます。http://kimbly.com/papers/bck-pepm-2007.pdf

1 枚目

FRP についての説明です。FRP と言っても樹脂じゃなくて関数反応型プログラミングの事です。宣言的プログラミングと命令的プログラミングを上手く混ぜる方法として、伝統的なデータフローを発展させた物だそうです。

FRP は、あっちの値が変化すればそれに反応してこっちの値が変化するような物を作るのに使います。実装方法は、依存関係に応じてグラフ(トーナメント表のような木構造)を作って、反応を伝播させていきます。

透過 FRP では、ふつうの演算が自動的に lift (持ち上げ)されます。lift というのはその場ですぐ演算するんじゃなくて、反応したときに演算するような構造を作る事です。この方式の欠点はどんどんグラフが大きくなって遅く大きくなる事です。この論文で紹介されているのは DrScheme 上に作られたファザータイム(FrTime) という処理系です。FrTime の特徴は以下の通り。

  • DrScheme の普通の演算子がそのまま lift 版の演算子になる。これにより、DrScheme のライブラリがそのまま関数反応型のライブラリになる。
  • 読んで評価して印刷するループで簡単に実験が出来る。

この論文の趣旨は、プログラムの意味を保ったままグラフを平らにしてパフォーマンスを上げる事です。これを lowering と呼びます。FrTime を lowering によって効率的に実行する方法が書いてあります。

2枚目

背景説明があります。IO や状態のあるプログラムを宣言的に書けない点について。例として時間ごとに変わる persephone とwhitefall (SF に出てくる惑星らしい) の距離をプログラムする例があります(何でいきなりこんなややこしい例を挙げるのだろう)。

どんな例か一応説明すると、それぞれの惑星は太陽からの距離と速度で定義されていて、ある時刻 (current-seconds) が決定すると座標が分かるので距離が分かるという物で、時刻を求めるために毎度システム時間を求める事にします。すると結局毎ステップごとに 4回システム時間を求めるので (それぞれのX座標、Y座標ごと) その間にシステム時間がバラバラになってしまう問題があるという話です。これを避けるために一時的にシステム時刻を保存するとプログラムがややこしくなってしまいます。

そこで FRP の出番です。FRP では、システム時刻を関数から求める代わりに、時刻が変化したら反応するシグナルを関数に埋め込みます。あとはランタイム時にステップごとにシグナルが反応するようにしておくと、矛盾無く同時刻の各座標が求まるという具合です。つまり実行順序の違いは以下の通り。

  • 普通のプログラム : 座標を求めるために -> システム時刻取得
  • FRP : システム時刻変化 -> 座標を求める

また、実装系として FrTime の紹介があります。FrTime は Scheme マクロとして定義されています。特徴は REPL による動的実験が出来る事と Scheme のライブラリを再利用できる事です。

3枚目

FrTime のやってる事は単純で、例えば seconds がシグナルの時に (+ 3 seconds) という式が与えられると、その場で計算を行う代わりに「seconds がもし反応したら 3 に加える」という新しいシグナルを返します。これを lift と呼びます。論文にはいまいちはっきり書いてないですが、(lift +) と言うと、+ を lift 化して以下のような関数に変換します。また、lift 化されている値を「普通の」値に戻すための project も定義されています。

(make-signal (lambda ()
               (+ (project a)
                  (project b))) a b)

つまり、

  • lift : 普通の関数から、「シグナルが与えられた時にシグナルを返す関数」に変換
  • project : シグナルから値を取り出す。

lift した関数 f の結果を project したものは、project したシグナルに f を適用する事と同じという等式が成り立つ。

  • (project ( (lift f) s ...)) = (f (project s) ...)
    • 例えば : (project ( (lift +) s1 s2)) = (+ (project s1) (project s2))

この論文では、生の関数を表すのに _underline のように表現します。lift される関数は ^hat のように表現します。

4枚目

dip というもう一つの関数が紹介されます。dipFRP 版の lambda のような物で、シグナルのリストと関数本体があります。シグナルのどれかが反応すると関数本体が実行されます。関数本体は生の関数だけを含みます。dip の定義は以下の通り

  • (dip (依存リスト) 式) の定義
    • (dip (x ...) e) = ( (lift (lambda (x ...) e)) x ...)
      • 例えば (dip (x y) (x + y)) の意味は、
      • ( (lift (lambda (x y) (x + y)) x y) で良いのかな?。
      • ここはややこしい。つまり、lift とは、普通の関数を ^関数 に変換する物で、それにもう一度引数を適用するというのは結局上記の make-signal が出来るという事かな?

5枚目

  • Upper code は、一つの生の関数ずつ一つのデータフローを作った物です。
  • Dipped code は、Upper code と同じに振舞いますが、沢山の生の関数を同時に実行します。

FtTime の最適化とは、複数の lift 関数を一つの dip 関数に纏めることです。最適化はボトムアップに行います。最初に変数や定数から始めて、上位の式を処理します。アルゴリズムは書き換えルールに基づきます。

  • 定数の変換
    • 変換 c -> (dip () c)
  • 変数の変換。変数がシグナルかも知れないので、依存リストに変数そのものを入れます。
    • 変換 id -> (dip (id) id)

6枚目

例として距離を求める関数を変換して行きます。

元の関数
(define ^distance
  (lambda (x1 y1 x2 y2)
    (^sqrt (^+ (^sqr (^- (x1 x2)))
               (^sqr (-^ (y1 y2)))))))

変数 (x1  x2) の変換
(define ^distance
  (lambda (x1 y1 x2 y2)
    (^sqrt (^+ (^sqr (^- (dip (x1) x1)
                         (dip (x2) x2)))
               (^sqr (-^ (y1 y2)))))))
  • e が (dip (x) e) の形をしていたら、以下の変換が適用できる。
  • つまり、引数全部が dip なら、関数全体を囲む dip に変換出来る。
  • (^f e1 e2 ...) -> (dip (x1 x2 ...) (f e1 e2 ...))

というようなルールを次々適用する。

(define ^distance
  (lambda (x1 y1 x2 y2)
    (^sqrt (^+ (^sqr (dip (x1 x2) (_- x1 x2)))
               (^sqr (-^ (y1 y2)))))))

(define ^distance
  (lambda (x1 y1 x2 y2)
    (^sqrt (^+ (dip (x1 x2) (_sqr (_- x1 x2)))
               (^sqr (-^ (y1 y2)))))))

(define ^distance
  (lambda (x1 y1 x2 y2)
    (^sqrt (^+ (dip (x1 x2) (_sqr (_- x1 x2)))
               (dip (y1 y2) (_sqr (_- y1 y2)))))))

(define ^distance
  (lambda (x1 y1 x2 y2)
    (^sqrt (^+ (dip (x1 x2) (_sqr (_- x1 x2)))
               (dip (y1 y2) (_sqr (_- y1 y2)))))))

(define ^distance
  (lambda (x1 y1 x2 y2)
    (dip (x1 y1 x2 y2)
         (_qrt (_+ (_sqr (_- x1 x2))
                   (_sqr (_- y1 y2)))))))

これで、全ての lift 関数を一つの dip に纏める事が出来た。

7枚目

この後、ラムダ抽象や条件分岐、高階関数をどのように最適化するかについてどんどん話が進む。例えば ^map

  • ^map とは、
    • (シグナルをシグナルに変換する関数)のシグナルと、
    • リストのシグナルを受け取り
    • リストのシグナルを返す関数

つまり、引数も答えも全部 lift 化しているという事だが、話がよく分からなかった。機械的には無理で場合に応じて最適化するという事かな。しかも、ユーザが独自の高階関数を定義出来ないと書いてあった。この高階関数の部分が一番この手のプログラミングで面白い話題なのに!この難しさは型の扱いから来てると思う。型を明示的に指定出来ないと言うのは逆に頭の中で型をずっと追いかけ続けなくてはいけないのでかえって苦しい。ここは後で Haskell と比較する予定。と言うわけで結論まで飛ぶ。

10枚目

結論。この方式の良いところは、シグナルによる処理も、よらない処理も同じように書ける所。しかも出来るだけ多くの処理を dip にまとめて、大幅に最適化出来る。lowering の考え方は FRP 以外にも応用出来る。例えばモナドにおいて lift が遅いとき、(lift g) ○ (lift f) -> lift (g ○ f) とすると軽くなる。

難しいのは中の処理にうまい lower counterpart が無い場合(???) これは map の事かな? そういった処理を抜き出す必要があるがその場合実行順序が問題になる。あと、ランタイムでコードを生成すると上手く行くかも。

この研究を、Flapjax という javascript モジュールに応用する計画がある。

感想

普通の関数と、シグナル用の関数を同じ名前を使ってポリフォーミズムでやるのがかっこいいと考えてるようだが、別の名前を使うか明示的に指定した方が良いのではないかと思った。そもそも論文の中で _ やら ^ やら記号をつけて区別する必要があるという事は、本人達にも難しいのでは無いか。もし同じにこだわるなら、型付けの強い言語を使うべきでは無いか?

あと、書いてある事自体は Haskell でも実現出来ている事を知った。SOE p175 にある、time + 5 を展開して Beh(\t -> t + 5) にする例と同じだな。でもこれを我々の、関数型では無い普通の言語で実装する為には、scheme の例は参考になると思った。メモリアロケーションの項目は読み直す予定。次に javascript でやるというのは素晴らしい。