CPS変換の復習

C#

木構造に対するイテレータに関して、もうちょっと考えると楽しそうな気がしていた（根拠は無く直感的に）のでぼんやりと考えてたら、

  • yield returnはコルーチンだし、コルーチンがあればイテレータが簡単に実装できるのかぁ...
  • そういえばプログラミングGaucheではcall/ccでコルーチン作ったよなぁ...
  • call/ccといえば、継続を取り出す仕組みだったよなぁ...
  • ん！？もしかして！イテレータと継続って何か関係あるのかな？

みたい思考を経て、「イテレータ 継続」でググってみたらとても興味深いブログ記事を見つけた。
内部イテレータを外部イテレータに手動で変換してみる実験 - terazzoの日記
ということで、JavaをC#に置き換えながら読んでみる。

ForEachとGetEnumeratorのようなメソッドをそれぞれ内部イテレータ、外部イテレータと呼ぶらしい。継続渡し形式（CPS、Continuation Passing Style）への変換（CPS変換）というテクニックを使うと、内部イテレータから外部イテレータへ変換できるそうだ。

CPS変換がこういうところに応用できるなんて大興奮だ。

まずは、イテレータの話題の前に、継続渡し形式（CPS、Continuation Passing Style）への変換（CPS変換）に関しておさらい。自分の理解を確認するために平易な説明を試みる。C#ではラムダ式が使えるので、元ネタの無名クラスの部分を置き換えてます。
間違いだらけかもしれないから、コメント欄にてツッコミお願いします。

CPS変換の練習 1. 階乗の計算

まずは通常の再帰バージョン（コード1）

public static int Fact(int n)
{
  if (n == 0)
  {
    return 1;
  }
  else
  {
    return n * Fact(n - 1);
  }
}

nが1以上の場合、Fact(n-1)で一歩手前の階乗を求めて、それにnを掛けると求めたい値が得られる。つまり、Fact(n-1)が返した結果とnを使って計算をするんだけど、そこには「Factは計算結果を返す」という常識が潜んでいる。
この常識を捨ててみると、CPS変換が理解しやすくなるような気がする*1。ということで、「戻り値は存在しない」*2という縛りを導入し、それに従ってFactを書き変えていってみる。
さて、デバッガ上で動いてるプログラムが、ブレークポイントで一時停止しているところを想像して欲しい。今、一時停止していたプログラムを再開しよう。再開後に行われる計算全体を、ブレークポイントにおける継続と呼ぶ。デバッガ中だけでなくて、一般的に、ある時点tより後に行われる処理全体を、時点tにおける継続と呼ぶ。

Factが終わった時点での継続は「たった今求めた値（returnされる値）を、ほげほげして、ふがふがして、ぴよぴよして...」となる。継続渡しというくらいだから、この継続を引数で渡してやる。
とりあえず今はC#で考えているので、継続のシグネチャを決めてやらないといけない。よって、継続は

  • 戻り値を使わない
  • 整数を受け取る（コード1では計算結果を受け取らないといけない）

となるので、ここではAction型の変数contとして渡してやろう。そうすると、n!を求めてほげほげ（以下略）するメソッドFactCpsはこんな格好になる（コード2）。

public static void FactCps(int n, Action<int> cont)
{
  // contをどう使う？？？
}

Factではn!を求めて返す（その値を使って何をやるかは戻ったところに書いてある）けど、FactCpsでは求めたn!をほげほげする部分も渡してやることになる。
contをどう使うかがポイントだろう。場合分けしてみると

  • nが0の場合、つまり0!は定義により1。
  • nが1以上の場合、nと(n-1)!をかける*3。(n-1)!は再帰させる。

となるので、FactCpsは次のようになる（コード3）。

static void FactCps(int n, Action<int> cont)
{
  if (n == 0)
  {
    // 0!をほげほげする
    cont(1);
  }
  else
  {
    // n!をほげほげする。
    // 再帰させたFactCpsから、mに(n-1)!が渡されることを期待している。
    FactCps(n - 1, m => cont(n * m));
  }
}

実行してみたところ：http://ideone.com/nTpWV
ちなみに、非末尾再帰のFactをCPS変換したFactCpsは末尾再帰になっている。

ちょっと待てよ...

FactCps(n - 1, m => cont(n * m))で、-演算子と*演算子の戻り値を使っているので、FactCpsも厳密にはCPSになってないような気がするな...。

CPS変換の練習 2. フィボナッチ数の計算

こちらもまずは通常の再帰バージョン（コード4）

static int Fibo(int n)
{
  if (n == 1  || n == 2)
  {
    return 1;
  }
  else
  {
    return Fibo(n - 1) + Fibo(n - 2);
  }
}

FiboをCPS変換したFiboCpsでも、Factの時と同様に、このメソッドが終了した時点での継続をcontとして渡してやることになる。そうすると、Fiboがreturnしている値をcontに渡しさえすれば、あとはcontがよろしくやってくれる。問題はcontを使ってFibo(n)をどう計算するかだろう。Fact同様に場合分けしてみると、

  • nが1か2の場合、フィボナッチ数は定義より1
  • nが3以上の場合、n-1番目のフィボナッチ数（再帰で求める）とn-2番目のフィボナッチ数（再帰で求める）を足す

となるので、つい以下のようにしたくなる（コード5）。

static void FiboCps(int n, Action<int> cont)
{
  if (n == 1 || n == 2)
  {
    cont(1);
  }
  else
  {
    // こうしたいけど、FiboCpsは値を返さない
    int a = FiboCps(n - 1, ほげほげ);
    int b = FiboCps(n - 2, ふがふが);

    // あとはよろしくねー
    cont(a + b);
  }
}

コメントに書いている通り、困ったことになる。aとbで期待しているもの*4は、戻り値として返ってくるのではなく、「ほげほげ」と「ふがふが」に渡されるはずなので、それぞれ次のように書かなくてはならない（コード6）。

static void FiboCps(int n, Action<int> cont)
{
  if (n == 1 || n == 2)
  {
    cont(1);
  }
  else
  {
    FiboCps(n - 1, a => ほげほげ);  // A
    FiboCps(n - 2, b => ふがふが);  // B

    // aとbを参照できない！
    cont(a + b);                    // C
  }
}

コード6では、別の問題に直面した。コメントに書いている通り、aとbはクロージャの引数なので、C行からアクセスできない。しかしコード6はもう一歩で継続渡しになる。よく見てみると、B行終了直後の継続はC行以降だ。これを引数で渡してやればいいので次のようになる（コード7）。

static void FiboCps(int n, Action<int> cont)
{
  if (n == 1 || n == 2)
  {
    cont(1);
  }
  else
  {
    FiboCps(n - 1, a => ほげほげ);    // D
    FiboCps(n - 2, b => cont(a + b)); // E
  }
}

同じように、E行からはaにアクセスできないが、D行終了直後の継続がE行以降になることから、同様に以下のようにできる。

static void FiboCps(int n, Action<int> cont)
{
  if (n == 1 || n == 2)
  {
    cont(1);
  }
  else
  {
    FiboCps(n - 1, a => FiboCps(n - 2, b => cont(a + b)));
  }
}

あら、いつの間にか完成。ちなみに、コード6ではA行とB行どっちが先にあっても構わないので、継続の順番が逆転しても問題ない。
実行してみたところ：http://ideone.com/qRURN

ということで、

CPS変換が少し理解できた気がする。本題のイテレータ云々は後日。

*1:ただ、余りも強く染みついた考え方なのでなかなか捨てられないんだけど

*2:もしくは、「戻り値には意味がない」

*3:説明になってない...？

*4:aはn-1番目のフィボナッチ数、bはn-2番目のフィボナッチ数