やねう企画2005年入社問題解答と解説(4)
(id:yaneurao:20051008の解説の続き)
ローカル変数なし、引数なしの再帰関数の非再帰化まで終わったので、今日は、引数ありとローカル変数ありの場合を考えていく。
本当は、こういう内容は、プログラミング“入門”に属するのだが、世にあるプログラミングの入門書籍はどうも言語仕様の解説がほとんどで、重要なことを何ら教えてはくれない。
・ローカル変数なし、引数“あり”、返し値なしの末尾再帰関数
void f(T t){
if (e) return;
g();
f(t+a);
}
ここで、引数の型と示しているTとは、ひとつの変数ではなく、引数の“束”とする。早い話、「int x,int y」が引数であれば、「struct { int x,int y}」とひとつの型のようにみなす。これにより、引数の数がいくつあろうが、このあとの議論が通用する。このT(の型)を型集合と名づけておく。
また、f(t+a)の「t+a」は、tに何らかの作用を与える可能性を意味する。引数が「int x,int y」だとしたら、「f(x+1,y+3)」とするだとか、あるいは、xもyも用いずに単に「f(1,2)」のようにやってしまうだとか、そのへんは問わない。以下の議論でt+aの他にt+b,t+cが出てくるが、それらも同様の意味とする。また、作用させるだけなので、S,Tのように異なる型同士もs+=t;のように演算できるものとする。
さて、上記のプログラムを仮想スタックを導入するとどう書き換えることが出来るだろうか？
void f(T t){
push(t);
while(pop(t)){
if (e) continue;
g();
push(t+a);
}
}
引数無しの場合と同様なので、簡単だろう。この場合はStack Levelを導入しても書き換えられない。なぜなら、whileループ内のpush/popが直接的には相殺しないからである。
ただし、whileループ内で直前でpushしたものを直後にpopしている。要するにスタックは1段しか使用しておらず、スタック経由で受け渡しをしているに過ぎない。よって、これはスタック無しに書き換えることが出来る。
void f(T t){
while(true) {
if (e) break;
g();
t = t + a;
}
}
ローカル変数がある場合についても考えておこう。ローカル変数も、引数と同様の扱いをすれば良い。ローカル変数の型は、Sとし、(T同様に)型集合であるとする。こうしておけば、ローカル変数の数が増えた時も、ここでの議論がそのまま当てはまる。
void f(T t){
S s;
if (e) return ;
g(s);
f(t+s);
}
このプログラムは以下のように書き換えることが出来る。
void f(T t){
S s;
push(t,s);
while(pop(t,s)){
s.init(); // s.init()はsの再初期化構文であるとする。
if (e) continue;
g(s);
push(t+s,s);
}
}
再帰関数においては、引数とローカル変数は両方とも(通例、ハードウェア)スタック上に積まれるものだから、これを仮想スタック上に載せかえれば良い。また、この例の場合でも、スタックは1段しか使用していないので仮想スタック自体を除去できる。
void f(T t){
S s;
while(true){
s.init(); // これはwhileループの末尾にあっても良い
if (e) break;
g(s);
t = t+s;
}
}
以上の議論により、末尾再帰の場合は、引数、ローカル変数は仮想スタックを用いることにより機械的に非再帰化できる。(そして、そのあと、仮想スタックを除去できる) それでは末尾再帰ではない場合にはどうだろうか？(つづく)
