再帰呼び出しを再帰呼び出しなしで実現

拙著「コーディングを支える技術」の第5章「関数」では、P.50で「再帰呼び出しを使っているプログラムは、再帰呼び出しを使わなくても書くことができる」と説明しました。この件に関してここで補足記事として解説することにしました。

P.53の簡単な再帰呼び出しの例(total関数)をターゲットにします。これは空行とコメントを除くと8行の簡単な例です。このコードから、挙動を変えずに再帰呼び出しを取り除いてみましょう。腕に自身のある人はは続きを読む前に自分で実装してみるとよいでしょう。

チャレンジする人向けの注意点

今回の対象では再帰呼び出しをしながら行う処理が「要素の足し算」でした。足し算は順番を入れ替えても結果が同じです。なので、うっかり計算の順番を変えてしまっても、結果からは間違いに気付けません。例えば深さ優先探索幅優先探索に変えてしまうと、[1, [2, 3], 4]が本来の1, 2, 3, 4という順番ではなく、1, 4, 2, 3という順番で足されるようになります。実は今回のケースでは幅優先探索に変えてしまうコードの方がシンプルになります。しかしこれは題意を満たさないものとします。

また、今回のケースではresultをすべての関数から読み書きできるところに置いてしまうことができます。これは元のコードでローカル変数であったresultをグローバル変数に変えてしまうことに相当します。これをやると「値をどうやって返すのか」の考察が抜けてしまうので、減点対象ということにします。

最後に、元コードはPythonで書かれていたので、筆者も最初Pythonで実装しました。しかしPythonにはgotoがない為、whileで代用するなどトリッキーなコードになってしまいました。これは解説の都合上よろしくないので、gotoのある言語(C++)で書き直しました。読者のみなさんにもgotoのある言語で試すことをオススメします。

C++への移植

まずはP.50のサンプルコードを、なるべく逐語訳でC++11に移植してみました。

int total(const many& xs){
  int result = 0;
  for(const boost::any& x : xs){
    if(is_integer(x)){
      result += any_cast<int>(x);
    }else{
      result += total(any_cast<many>(x));
    }
  }
  return result;
}

is_integerの定義、C++Pythonのリストと同様の「型を気にしないリスト」を作るために使われているboost/any.hppについては今回の記事のスコープではないので割愛します。要望があればまた別途。

foreachの除去

さて、このコードでは「for x in xs」や「BOOST_FOREACH」というforeach構文が使われています。これは「与えられたリストの各要素についてループする」という構文なので、中断したり再開したりすることが難しいです。そこで、まずはこれを普通のfor文に書き換えました。

int total2(const many& xs){
  int i;
  boost::any x;
  int result = 0;

  for(i = 0; i < xs.size(); i++){
    x = xs[i];
    if(is_integer(x)){
      result += any_cast<int>(x);
    }else{
      result += total2(any_cast<many>(x)); // 次はこれを書き換える
    }
  }
  return result;
}

この関数のローカル変数は、xs, i, x, resultの4つですね。

さて、次はこの関数の中での「自分自身の呼び出し」を無くしていくことにします。

スタックを作る

P.48を読んでみましょう。「あとで元の値に戻せるように保存する」を実現するために、スタックを使うのでした。
本では「戻り先のアドレス」を保存するためにスタックを使っていましたが、ここではローカル変数を保存するために使います。

*1

普通にプログラムを買いている時には自分でこの「スタック」を管理することはありません*2が、今回は本物の関数呼び出しを使わずに「関数呼び出しと同じこと」を実現したいわけなので、自分で管理することにします。

とはいえ、それほど大げさなことではありません。空のstd::stackを作って、そこにデータを保存していくことにします。

また、関数からの返り値を入れる変数も作っておきます。

typedef std::tuple<many, int, boost::any, int> frame_t;
std::stack<frame_t> stack;

int function_result;
スタックに保存するべき値は何か

スタックに保存する値は、この関数のローカル変数xs, i, x, resultの4つの値です。そこで先程のコードでは「typedef std::tuple frame_t;」と4つの値を入れるための型を作っています。

「xは保存する必要がない」と思った人はいますか?それは正解です。ただし、それは「xは関数呼び出しから戻った後で読み出されることがない」というこの関数特有の事情を使って最適化をしていることになりますね。

「関数の呼び出し」とは何か

さて、次は「関数の呼び出し」とは何をすることか考えてみましょう。

  • 1: 今のローカル変数をスタックに保存して、後で戻せるようにする
  • 2: 引数xsを書き換える
  • 3: 関数冒頭にジャンプ

やるべきことはこの3つです。*3

そこでまず、関数冒頭にジャンプのためのラベルを作ります。

int total3(many& xs){
 ENTRYPOINT:
  int i;
  boost::any x;
  int result = 0;

そして関数の呼び出しはこうなります。

    if(is_integer(x)){
      result += any_cast<int>(x);
    }else{
      // 1: 現在のローカル変数をスタックに保存する
      stack.push(make_tuple(xs, i, x, result));
      // 2: 引数xsを書き換える
      xs = any_cast<many>(x);
      // 3: 関数冒頭へジャンプ
      goto ENTRYPOINT;

値を返す

ループが終わったら何をすればよいでしょうか。元のコードでは return result; していました。これは何でしょうか。

  • 4: 返り値を「返り値を置く場所」に置く。(これは人間が呼び出し規約で決めたもので、x86上でC++を書いているならEAXレジスタになる。今回はfunction_resultという変数を作った)
  • 5: 関数呼び出しの直後にジャンプ

やるべきことはこの2つです。

まずはジャンプのためのラベルを作っておいて…

      goto ENTRYPOINT;

    RETURNPOINT: // 6: 呼び出された関数からreturnするとここに戻ってくる

関数の最後でそこへジャンプするようにします。

    // 4: 返り値を決められた場所に保存
    function_result = result;
    // 5: 関数呼び出し直後(上記6)に戻る
    goto RETURNPOINT;

戻ってきた後に何をするか

関数呼び出しから戻ってきたあとには何をすればよいでしょうか。

  • 7: スタックに保存しておいた値を復元する
  • 8: 関数の返り値を使う

やるべきことはこの2つです。
長々と話しているうちに忘れてしまったかもしれないので再掲しますが、 いまやろうとしていることは「result += total(…);」を関数呼び出し無しで実現することでした。関数を呼び出し、その後で返り値をローカル変数のresultに足す必要があります。

    RETURNPOINT: // 6: 呼び出された関数からreturnするとここに戻ってくる
      // 7: スタックに保存しておいた値を復元する
      frame_t f = stack.top();
      stack.pop();
      xs = std::get<0>(f);
      i = std::get<1>(f);
      x = std::get<2>(f);
      result = std::get<3>(f);

      // 8: 関数の返り値を使う
      result += function_result;

全体

全体のソースコードはこちら。

https://github.com/nishio/learn_language/blob/master/langbook/extra/recursive/recursive.cpp

筆者の環境(Mac OS X 10.7.5)ではこんな感じで実行出来ます。

$ clang++ -std=c++11 -stdlib=libc++ -Wall -DVERBOSE recursive.cpp && ./a.out

一応期待通りには動いていますが、これは筆者にとって初めてのC++11プログラミングなので、なにかおかしなところがあればぜひご指摘下さい。

Q&A

なぜ再帰呼び出しをなくしたいのか ?

「なぜ再帰呼び出しをなくしたいのか」というご質問がありました。拙著では「普段あたりまえのように使っている構文の裏側がどのように動いているか」を理解するために4章で

  • if文のelse節を使わずに、同じ挙動を実現する(P.32)
  • while文を使わずに、同じ挙動を実現する(P.36)
  • for文を使わずに、同じ挙動を実現する(P.37)

という説明をしました。これはその続編です。5章で「関数がどう動いているか」の説明をしたので、これも「関数呼び出しを使わずに、同じ挙動を実現する」をやってみました。

そういえば昔「クラスを使わずに『インスタンスの作成』『継承』を実現する」をやったことがありました。これも改めて解説すると良いかもしれませんね。 (thanks: id:thujikun)

末尾再帰最適化ではスタックを使わないのでは?

「末尾呼び出しが最適化されている場合はとかスタックを使わないのでは」というご質問がありました。そうですね。

この記事では以下のように書きました。

「xは保存する必要がない」と思った人はいますか?それは正解です。ただし、それは「xは関数呼び出しから戻った後で読み出されることがない」というこの関数特有の事情を使って最適化をしていることになりますね。

今回の対象コードは関数呼び出しの後、いくつかの変数を使います。なので復元できるようにこれらをスタックに積む必要があったわけです。一方、末尾呼び出しは「関数の末尾」に関数呼び出しがあるわけですから、「関数呼び出しの後で使う変数」がありません。なので積むべき変数がないわけです。

今回の対象コードでは「xは使わないから積まなくてもいいよね」という最適化ができるわけですが、これがもっと進んで「何も使わないから何も積まなくていいよね」になったのが末尾呼び出しの最適化というわけです。(thanks: id:bouzuya)


拙著「コーディングを支える技術」の読者から頂いた質問など対して、こんな感じで補足記事を書いて行きたいと思っています。質問・感想はおきがねなくどうぞ。

この解説は拙著の第5章「関数」のP.56あたりに挿入されるのが適切かと思います。

拙著に関する他のエントリーは「「コーディングを支える技術」著者公式ページ」からたどれるようにします。

*1:脚注:実際にx86上のCでの関数呼び出しをした際にどうスタックに積まれているかを表示したりしてコラムにする?呼出規約の話に触れる?

*2:アセンブリ言語を使う場合はもちろん別

*3:呼出規約によっては引数xsを書き換えるのは呼び出された側の仕事、という点を補足するべきか