Think Stitch
PRINCIPIA  最近の更新


継続渡し(Continuation Passing Style, CPS)による順列の計算

Twitter のタイムラインが CPS で埋まっているので :P 、CPS の話を書きたくなりました。

関数型言語のプログラミングスタイルに継続渡し(Continuation Passing Style, CPS)というものがあります。 コンパイラの中間表現に使うなどの応用があるそうです。 継続という概念は理解するのが難しくて、初めて Scheme の Revised Report を読んだときには何を言っているのかさっぱりわかりませんでした。 (いまでも、とても理解したとはいえませんが。) そんなわけで説明できるほど詳しくないので、ちょっとプログラムの断片を見ていただくだけです。 でも知っていることをちょっとだけ書きます。 もしかしたら詳しい人が突っ込みを入れてくれるかもしれないことを期待して。 (こういう見苦しい言い訳のような保険のようなことは書かないようにしていたのに。これもか。ちょっと落ち込んでいるものでご容赦。)

素朴かつ大雑把にいうと、プログラムというのは計算の手順を記述したものですよね。 コンピュータはその記述にしたがって計算を進めて、最後に結果を出します。 コンピュータがあるところまで計算を進めた時点を考えると、中間の結果を持っていて、さらに残っている計算があるでしょう。 この残っている計算のことを継続というのだそうです。 継続は、そこまでの中間結果を受け取って、残りの計算をします(同語反復?)。

中間結果を受け取って計算をするという点から、継続を関数のように考えることができます。 中間結果を引数として受け取り、残りの計算を行う関数です。 実際、関数型言語の一部には、この継続を関数オブジェクトとして取り出すことのできるものがあります。

そのような言語要素を持っていなくても、継続を自分で作る、つまり残りの計算を関数で表すことができます。 ふつう関数は計算した結果を呼び出し元に返します。 こんな感じで。

(define (f x)
  (+ (* x 2) 1))

呼び出し元は返された値を使って何かを計算するのでしょう。 そこで、この計算を関数 k として表して、f に渡してもらうことにします。 関数 f は値を返す代わりに、k を呼び出すのです。 関数 f が計算する値が中間の結果で、関数 k はそれを受け取って残りの計算をするので継続というわけです。

(define (f x k)
  (k (+ (* x 2) 1)))

もう1つ例を見ます。 2分木の中に現れる数を * に置き換える関数を考えます。 ノードの部分(pair?)ではそれぞれの枝に対して再帰的に呼び出しを行います。

(define (censor x)
  (cond ((number? x) '*)
        ((pair? x)
         (cons (censor (car x))
               (censor (cdr x))))
        (else x)))

この関数を、上と同じように継続を受け取って値を渡すようにしてみると、つぎのようになります。

(define (censor x k)
  (cond ((number? x) (k '*))
        ((pair? x)
         (censor (car x)
           (lambda (y)
             (censor (cdr x)
               (lambda (z)
                 (k (cons y z)))))))
        (else (k x))))

関数 (censor x k) は x について処理した結果を継続 k に渡します。 そこでノードの場合は、まず (car x) について計算し、次に (cdr x) について計算し、最後に両方の結果を cons して継続 k に渡します。

かなり複雑になったように見えますが、コードを計算が行われる順番に並べなおしたともいえます。 この書き方には1つ大きな利点があります。 それは再帰がすべて末尾再帰になったことです。 Scheme では末尾再帰が最適化されるので、このコードは与えられた2分木の大きさに関係なく、一定のスタック消費で計算を行うことができます。

さらにちょっと変更を加えてみます。 もし処理の途中で * を見つけたら、継続を無視して #f を返してしまうことにします。

(define (censor x k)
  (cond ((eq? x '*) #f)
        ((number? x) (k '*))
        ((pair? x)
         (censor (car x)
           (lambda (y)
             (censor (cdr x)
               (lambda (z)
                 (k (cons y z)))))))
        (else (k x))))

このように継続を呼び出さないという選択ができます。 計算を途中で投げ出してしまうことができるのです。 ちょっと例外処理に似てますね。 ふつうに値を返す関数の使い方では、口を開けて待っている再帰の呼び出し元(つまり継続)がたくさんいますから、throw などの特殊な機構がないとそれらをすっとばすことはできないでしょう。

まとめると、継続渡しというのは、結果を返す代わりに、引数として受け取った関数に結果を渡すように書くスタイルのことです。 (継続を渡すから CPS なのか、継続に結果を渡すから CPS なのかわかりませんが・・・。) そして、ここで説明した継続渡しの利点は2つです。

スタックを消費しない代わりに、継続を表す関数オブジェクトを作っているのでヒープを消費しているわけです。 スタックを消費しないようにすることだけが目的であれば、自前で再帰を管理すればいいわけですけど、継続渡しの方が考えやすいことが多いように思います。 実際、ふつうに値を返す関数を継続渡しのスタイルに書き換えることは機械的にできる(つまりアルゴリズムがある)そうです。

計算を途中で放棄できることと、コードが複雑になることは、コードの理解しやすさを落とすことになります。 継続はかつての構造化プログラミングの敵 goto みたいなものなんだそうです。

順列を計算する関数 perm

もう1つ例を書きます。 与えられたリストの要素を並べ替えた順列をすべて求める関数 (perm x) です。 まず、ふつうに再帰的に書くとこんな感じです。

(define (perm x)
  (if (null? x)
      '(())
      (append-map
        (lambda (y) (insert (car x) y))
        (perm (cdr x)))))

もし要素がなければ、順列は空列1つだけです。 少なくとも要素が1つある場合は、まず先頭を取り除いたリスト (cdr x) の順列を求めます。 結果はリストで来るわけですが、その要素を例えば (a b c) とすると、元の順列は、このリストの要素の間に (car x) を挿入したものになります。 X = (car x) とすると (X a b c), (a X b c), (a b X c), (a b c X) です。 これを計算するのが関数 insert です。

(define (insert x xs)
  (if (null? xs)
      (list (list x))
      (cons (cons x xs)
            (map (lambda (z) (cons (car xs) z))
                 (insert x (cdr xs))))))

insert の計算は2つに場合わけすることができます。 x を先頭に追加する場合と、それ以外、つまり間に挿入する場合です。 後者の場合は、再帰的に考えて、先頭を取り除いたリストに挿入してから先頭を戻せば求められます。 よくある場合の数を考える問題と同じです。 順列を計算しているのだからあたりまえか。

ではこれを CPS にしてみます。 上の再帰版では append-map がぴったり使えたので簡単でしたけど、末尾再帰以外の再帰を使わないようにするためにはこれも CPS にしなければなりません。 そこでもう1つの関数 insert-appmap-cps を用意します。

(define (perm-cps x k)
  (if (null? x)
      (k '(()))
      (perm-cps (cdr x)
        (lambda (ps)
          (insert-appmap-cps (car x) ps k)))))
(define (insert-appmap-cps x ps k)
  (if (null? ps)
      (k '())
      (insert-cps x (car ps)
        (lambda (qs)
          (insert-appmap-cps x (cdr ps)
            (lambda (rs)
              (k (append qs rs))))))))
(define (insert-cps x xs k)
  (if (null? xs)
      (k (list (list x)))
      (insert-cps x (cdr xs)
        (lambda (ps)
          (k (cons (cons x xs)
                   (map (lambda (ys)
                          (cons (car xs) ys))
                        ps)))))))

ちょっとパズルのようで面白くありませんか? 実用的にもスタックを消費しないので、より大きなリストに対して使うことができます。 (もちろん再帰を自分で開いた方がもっとメモリを節約できますけど。← コストを気にするなんて(?)にせもの Lisper(?!)) ((ついでにもうひとこと。よく、順列計算みたいなおもちゃを実際に使うことはないじゃないかといわれるんですけど、私はテストケースを自動生成するためによく使います。))

Scheme の Hygienic マクロプロセッサとコンパイラを書いていたとき、lambda body の定義と式の境界線を識別する問題を CPS で書きました。 CPS 以外ではちょっと書ける気がしないほど複雑でした。

考えてみたら Scheme の話を書くのはこれが初めてでした。 Scheme については詳しい人が面白いことをたくさん書いているので(CPSもそうですけど)、あまり書くことがなさそうです。

2013/09/17
© 2013,2014,2015 PRINCIPIA Limited