脱関数化を実用する 3 - shiatsumat/fp-papers GitHub Wiki

制御の関数的表現として、継続は脱関数化の自然な標的を与える。このセクションにおいて、私たちは直接的スタイルのプログラムを継続渡しスタイルの (CPS) プログラムに翻訳して [[12](脱関数化を実用する 8#reference12),[49](脱関数化を実用する 8#reference49)]、その継続を脱関数化する、というプロセスを研究する。そのあと私たちはこのプロセスをワンドの継続ベースのプログラム変換戦略 [[54](脱関数化を実用する 8#reference54)] と比較する。

私たちは、言語 {0ⁿ1ⁿ | n ∈ ℕ} の認識器 (recognizer) について考える。私たちはこれを[Int] -> Bool型の関数として書く。入力は整数のリストであり、認識器はそのリストが、ある n について、n 個の 0 からなるリストと n 個の 1 からなるリストを結合したものであるかどうかを確かめる。

まず入力のリストを走査する再帰下降パーサを書こう。

rec0 :: [Int] -> Bool
rec0 xs = walk xs == Just []
  where
    walk :: [Int] -> Maybe [Int]
    walk (0 : xs') = do
      ys <- walk xs'
      case ys of
        1 : xs'' -> return xs''
        _ -> Nothing
    walk xs = return xs

補助関数walkは入力のリストを走査する。この関数は0に出会うたびに自分自身を再帰的に呼び出す。0でないものに出会ったときは、リストの残りを返し、どの返り値も1が見つかることを期待する。ミスマッチした場合（つまり1でないリストの要素が返り値にあった場合、あるいはリストが短すぎたり長すぎたりした場合）、例外が投げられる。［ここではMaybeモナドを例外として使っている。Nothingが例外に当たる。］

walkを継続渡しスタイルで書こう [[12](脱関数化を実用する 8#reference12),[49](脱関数化を実用する 8#reference49)]。

rec1 :: [Int] -> Bool
rec1 xs = walk (xs, \xs' -> xs' == [])
  where
    walk :: ([Int], [Int] -> Bool) -> Bool
    walk (0 : xs', k) = walk (xs',
      \ys -> case ys of
        1 : xs'' -> k xs''
        _        -> False)
    walk (xs, k) = k xs

補助関数walkは入力のリストを末尾再帰的に走査する（そしてそれゆえに例外は必要ない）。この関数は0でない値に出会ったら、現在のリストを現在の継続に送る。もし新しい継続が1で始まっているリストを送られたら、リストの残りを現在の環境に送る。そうでなければ、Falseを返す。最初の継続は、空リストが送られたかどうかを確かめている。

data Cont = Cont0
          | Cont1 Cont

apply2 :: (Cont, [Int]) -> Bool
apply2 (Cont0, xs')        = xs' == []
apply2 (Cont1 k, 1 : xs'') = apply2 (k, xs'')
apply2 (Cont1 k, _)        = False

rec2 :: [Int] -> Bool
rec2 xs = walk (xs, Cont0)
  where
    walk (0 : xs', k) = walk (xs', Cont1 k)
    walk (xs, k)      = apply2 (k, xs)

私たちは、この結果をプッシュダウンのオートマトンを実装することと同一視する [[26](脱関数化を実用する 8#reference26)]。このオートマトンは2つの状態とスタックアルファベットの1要素を持つ。この2つの状態は2つの関数walkとapply2によって表されている。遷移は末尾再帰呼び出しである。このオートマトンは、入力を処理した結果が空のスタックで終わるならば入力を受け入れる。

また、私たちはcontがペアノ数を実装するということも見る。ペアノ数を Haskell の整数で置き換えてみよう。

apply3 :: (Int, [Int]) -> Bool
apply3 (0, xs')      = xs' == []
apply3 (k, 1 : xs'') = apply3 (k-1, xs'')
apply3 (k, _)        = False

rec3 :: [Int] -> Bool
rec3 xs = walk (xs, 0)
  where
    walk :: ([Int], Int) -> Bool
    walk (0 : xs', k) = walk (xs', k+1)
    walk (xs, k)      = apply3 (k, xs)

この結果は、カウンタのある普通の反復的な2状態の認識器である。

要約すると、私たちは一階の再帰的なバージョンから始めて、それをCPS変換して、高階にして脱関数化できるようにした。私たちは脱関数化したプログラムがプッシュダウンのオートマトンを実装するということを確かめた。脱関数化された継続がペアノ算術を実装するということに気付いて、私たちはその表現を組み込みの整数に変えて、得られる結果がカウンタのある普通の反復的な2状態の認識器であるということを確かめた。

ワンドの継続ベースのプログラム変換に関する定評のある研究 [[54](脱関数化を実用する 8#reference54)] は、(1) プログラムをCPS変換し、(2) 継続を表現するデータ構造を設計し、(3) この表現を使って最初のプログラムを改善する、ということを提案している。私たちは、ワンドの論文で述べられた例のそれぞれにおいて、継続を表すデータ構造を見つけるという難題に、脱関数化が答えを与えるということを見ている。これは重要である。そうしたデータ構造の継続を見つけることがこの研究の動機の一つであったのだ。しかし脱関数化は、ワンドの論文に触れている教科書や論文のうち、私たちが気付いているもの（http://citeseer.nj.nec.com/［現 http://citeseer.ist.psu.edu］のリサーチインデクスで見つかるものを含む）では、全く考慮されていない。

ワンドの研究は、CPSを使って遠回りすることでどのように蓄積引数のある反復的なプログラムが生まれるのかを示したという点で、独創性に富んでいる。加えて、レナルズの研究はCPS変換されたプログラムの継続を脱関数化したとき、従来の一階の蓄積引数がどのように生まれるかを示している。

私たちは、脱関数化された継続が、再帰的に定義された関数の呼び出し/返り値のパターン (call/return pattern) を説明するということも見ている。ゆえに、ダイクストラが1950年代後半に指摘したように、脱関数化された継続はスタックのような方法で進化するのである。この発言の必然的帰結は、脱関数化する前は、継続は、制御演算子を使わないプログラムをCPS変換した結果として継続が生まれているのならば、継続はLIFOで使われてもいる、ということである。

CPS変換された一階のプログラムを脱関数化すると、そのプログラムの、プッシュダウンの蓄積引数を使う反復的なバージョンを構成するための、システマティックな方法が得られる。そしてこの蓄積引数の表現は自由に変えることができる。