ブログ「サイバー少年」

ブログ「サイバー少年」へようこそ!
小学六年生ごろからプログラミングを趣味にしている高校生のブログです。
勉強したことについての記事などを書いています。フリーソフトも制作、公開しています。
(当ブログについて詳しくは「ブログ概要紹介」を参照)

サイバー少年が作ったフリーソフトは「サイバー少年の作品展示場」へ

末尾再帰と末尾最適化機能についての考察

記事「再帰はすげえ…けどループを使え!」で、“@jsakamoto”さんから末尾再帰についてのコメントを頂きました。

返信を書くときに、コメントの内容とは関係ない、余計な部分まで熱く語ってしまったのですが、
まだ書き足りないので記事に書きます(笑)

「末尾再帰とは何か」と、「末尾最適化機能って別にすごくないじゃん」という話です。




関数型言語には大抵、末尾最適化の機能がついています。

末尾最適化機能とは、末尾再帰を行うプログラムコードを、それと同等なループ処理に変換してくれる機能のことです。


末尾再帰とは何ぞや?と言われたら、末尾で再帰しているプログラムのことですね。

………と言われても。


まず、末尾再帰の詳しい定義が分かってないといけないので、具体的に末尾再帰はどんなものか説明します。





末尾で再帰しているとはいっても、

関数の末尾で再帰しているという意味ではなく、
関数内の処理の末尾で再帰しているというわけです。


コードで書くと、 return Saiki( となっている関数です。

再帰呼び出しをするのは、returnの右(オペランド?)のみでないといけません。

returnの右以外で再帰呼び出しをすると、末尾再帰をする関数とは言えません。

なぜなら、そこでは処理の最後ではないからです。


関数内での処理の流れを頭の中で追ってみてください。
すると分かります。

高級言語的な思考は止め、処理を1つずつ追っていきます。
そして

処理
処理
処理
再帰呼び出し
return


となっていたら、末尾再帰と言えるでしょう。


処理の一番最後に再帰呼び出しがありますね。

正確に言うと一番最後はreturnなので、これを末尾再帰と呼べるかどうかは疑問ですが、そのことは置いておきます。

少なくとも、末尾最適化では、returnは無いものとして扱われるのです。

よってreturnのことはどうでもいいわけです。


というわけで、 return Saiki( ならば、処理の一番最後に再帰呼び出しがあると言えますね。

「処理の一番最後はreturnだろ」という疑問は、気にしないでください。


return Saiki().ToString(); とかも末尾再帰とは言えませんよ。

再帰呼び出しをして、返ってきて、さらにToStringという処理があるからです。

これは処理の一番最後がToStringになってしまいます。


ちなみに、もちろん関数の最後じゃなくてもいいですね。

再帰呼び出しをしたあと、すぐにreturnで関数を抜けてしまうなら末尾再帰と呼べます。

また、再帰呼び出しが複数あっても全然OKですね。

int Saiki(int arg) { // 特に意味のないプログラム 
if (arg == 0) {
return Saiki(arg + 1);
}
else if (arg == -9) {
return arg;
}
else {
return Saiki(arg - 2);
}
}

なんてのも、条件分岐でどの道をたどっても再帰呼び出しは return Saiki( ですからOKです。

ただ、その中に1つでも、末尾ではない再帰が混ざっていたら、「この関数は100%末尾再帰です」とは言い張れません。


ですが一つ注意点を述べますと、 return Saiki( の形でなくとも、

int a = Saiki(x);
int b = a;
int c = b;
return c;

みたいなコードなら、最適化が働いて return Saiki(x); に直してくれて、末尾再帰になるかもしれません。




さぁ、今からが本題ですよ…。ゼェゼェ
(本題のほうが文章量が少ないかもしれない…)


末尾再帰でない、普通の再帰はループに変換することが難しいです。


なぜ普通の再帰をループに変換できないかというと、
再帰呼び出しをしたあとに、まだ処理が残っているからです。


これは再帰呼び出しに限らず、関数呼び出し全般に言えることですが、
再帰呼び出しが終わったら、残っている処理をしないといけない。

すなわち呼び出し元に戻らないといけませんね。


ループでは、処理が終わると、最初からになってしまいます。

ループでは呼び出し元の状態を再現することができないのです。

(ループは構造化プログラミングの一要素であるため、再帰っぽいことが出来ないのです。再帰は内部でGoToを使い倒しています。)


さて、呼び出し元に戻るには、呼び出し元がどこだったかという情報を保存しないといけませんし、
関数内で定義したローカル変数も、戻ってきたあとに使用するわけですから、保存しないといけません。

呼び出し元の状況を再現しないといけないからです。

(これらのデータをスタック領域というところに溜めています。)


と言うことは、呼び出して、その中でも呼び出して…と繰り返していると、どんどんデータ量が増えていきますね。

最終的に、スタック領域にデータが収まりきらなくなると、スタックオーバーフローを起こしてしまいます。


普通の関数呼び出しでは、そんな事まずありませんが、
再帰の場合は、呼び出してなんぼの処理をする世界です。

再帰は呼び出し回数がかなり多いので、スタックオーバーフローを起こす可能性も大いにあるのです。

これが再帰が嫌われる原因ですね。




さて、末尾再帰だって再帰なのですから、スタックオーバーフローも起こりうります。

まず、これを大前提にしてください。

末尾再帰ならスタックを使わないなんてわけではありません。

そう、末尾最適化機能が現れるまでは…。

冒頭にも書きましたが、末尾最適化機能というのは、
末尾再帰をしているプログラムコードを、それと同等なループ処理に変換してくれる機能のことです。


もちろん普通の再帰はループに変換してくれません。
変換できませんから。


ポイント

変換できない、というのは「機械的に変換できない」という意味であることに注意してください。

プログラマが工夫を凝らして同等の処理を行うループ文を作ることは可能です。

しかし、それは単純な作業ではなく難しいですし、
なにより、末尾最適化では“同じ処理をする”のに対し、
プログラマがループ文を作ったものはあくまでも“同じことをする”だけです。

つまり、末尾最適化は1つ1つの処理、簡単に言うと機械語レベルで全く同じであるループに変換するのです。


というわけで、普通の再帰はループに変換することが難しいのです。




では、なぜ、末尾再帰は簡単にループに変換できてしまうのか。

その理由は意外にもさらっとした説明で分かります。


先ほど言いましたが、なぜループで再帰と同じことが出来ないのかと言うと、

再帰は呼び出しが終わった後に、処理を呼び出し元に戻さないといけない、
しかし、ループでは呼び出し元を保存してそこに戻るなんて機能はないからです。
(ローカル変数の保存等も含め)


そして、末尾再帰とは“処理の”一番最後で行う再帰のことだと言いましたね。

そしてここ重要。

処理の一番最後で再帰するということは、再帰呼び出しが終わった後は何も処理をせずに終わるということです。

再帰呼び出しが終わって、戻ってきても何もすることがないなら、もう戻ってこなくても構わないのでは?


戻ってきて何もすることがないと言ったら嘘で、正確には戻る処理、つまりreturnがありますが、どうせずっとリターンするだけで

return
return
return
return
retrun
   ・
   ・
   ・
再帰関数脱出


という流れにしかなりません。

無駄に繰り返すreturnなんかいらないじゃないかということです。


ところで、再帰をループ文に変換できないのは「ループ文では呼び出し元に戻るような処理ができないから」と言いましたが、

戻らなくても構わない末尾再帰ならループに変換できるのではないでしょうか。




…これでゴールです。


・末尾再帰ならループ文に変換できる。
なぜなら呼び出し元に戻らなくてもいいから。


・末尾再帰をしているプログラムコードを、同等なループ文に変換してくれる“末尾最適化機能”という機能がある。


結局はこの2つが分かっていればOKです。




さてさて、第二のお題です。

末尾最適化機能に対する自分の意見を述べているので、多少の決め付けがあります。
ご了承ください。

しかし、こっちの話をメインでやっていくつもりでしたが、こっちのほうが少なくなりそうですね…(笑)


末尾最適化機能がないと、末尾再帰とて再帰と同じようにスタックオーバーフローのリスクがあります。

それで、末尾最適化機能があれば、末尾再帰をループに変換してくれるわけです。


ここで言いますが、
末尾最適化機能は一般的に関数型言語についています。

C言語などの手続き型言語には、普通はありません。

.NET系の言語でも、C#にはなくてF#にはあります。


C#では末尾再帰のプログラムを書くと、スタックがどんどん積まれていくのに、
F#ではスタックは積まれずに、安全に再帰ができる!


…なんて言われたりします。

しかし待ってください。

C#で末尾再帰をする日が来るでしょうか。

C#ならループで書けばいいのでは?


普通の再帰はループに変換することは難しく、なにより処理内容が異なってしまいます。

しかし、末尾再帰なら簡単にループに変換できると言いました。

ならば自分でループに変換して書くことも容易です。


「末尾再帰なら簡単にループに変換できる理由」を先ほど書きましたが、あれを簡単にいうと、末尾再帰 = ループなんですよ。

内部的には、やっていることは同じなんですよ。

処理内容も変わりません。そのまんま書くことができます。


というわけで、末尾再帰をループ文に変換して書くには、そのまんま書けばいいだけなので、変換は容易なのです。

変換には何の工夫も要りません。
(とは言っても、ループ文に変換するわけですから少しの修正はあります。その内容は最後に書きます。)

つまり、末尾再帰をするような処理は、ループで書けばいいのです。

末尾再帰をする必要がないんだからC言語などには末尾最適化機能がないのです。


では関数型言語はどうかというと、関数型言語にはループ文がありません

関数型言語では、ループ処理は再帰を用いて行います。


ループ処理を使う場面はかなり多いですから、
そのときにスタックオーバーフローする再帰しか使えないというのは、困りものです。

そこで導入されたのが末尾最適化機能というわけです。

単純なループ処理をしたいときは、処理の末尾で再帰をするように書きます。

すると、コンパイラがそれと同等なループ文に変換してくれるのです。

普通の再帰は、まぁ普通に再帰で書けばいいですし。


これで、関数型言語の世界観を崩さずに実用的なループを書けるようになったんですね。


関数型言語はコンピュータの性能を無視している仕組みが多いのが難点ですね。

そもそも、動作環境がコンピュータなのかどうかさえも気にせずに、
美しい文法にすることを最優先に設計したんじゃないでしょうか。


つまり、末尾最適化機能は関数型言語がやむ終えず使っている機能です。

もともとループを書ける手続き型言語は、ただループを書けばいい話です。

手続き型言語で末尾再帰を使うのは止めましょう。
スタックを積むだけです。ループにしよう。


というわけで、末尾最適化機能というのは再帰しかできない言語で力を発揮するのですね。

ですから、関数型言語の魅力の1つに末尾最適化機能を挙げている人がいたら、私は違和感を感じます。

関数型言語だからあるのです。

手続き型言語ではそんな機能は無くても、間に合っているということに注意してください。




いや~、最後は関数型言語を見下したような書き方になってしまいましたが、決してそういうわけじゃないのです。

どんなものにもメリットとデメリットはあるものです。

私は全く関数型言語を扱えませんからメリットが浮かばないのですが…。

まぁ、言語の美しさを保ちつつ、実用的な処理にする末尾最適化機能は素晴らしい機能だと思いますよ。


あと、前半の話で末尾再帰と末尾最適化機能について理解して頂けたなら幸いです。

ただ、手続き型言語ではあまり使いませんが。




おまけ

末尾再帰している関数はループ文に簡単に変換できると言いましたが、その方法を書きます。

自分で考えています。

機械的な作業でいけますね。

例えば、こんな関数があるとしましょう。(C#)

int MSaiki (int arg) {
if (arg == 100) {return arg;}
return MSaiki(arg + 1);
}


これは、ツッコミどころ満載の変な関数ですが、それは置いておきましょう。
まず、無限ループ(for(;;)やwhile(true))を書きます。

ループを抜ける処理はbreak;でやることにします。

for (;;) {

}

続いて、仮引数(引数)の代わりとなるものを作らないといけません。
また、戻り値の代わりとなる変数も作ります。
これはループの外側に書きます。

int arg = 引数となる任意の値を代入
int result;
for (;;) {

}

そしたら、先ほどの関数内の処理を丸々コピペします。

int arg = 引数となる任意の値を代入
int result;
for (;;) {
if (arg == 100) {return arg;}
return MSaiki(arg + 1);
}

もちろんこれはエラーですから、returnのところを改造します。
そのときに

return 再帰呼び出し(arg1, arg2, ...); となっているものは
arg1変数に〇〇を代入、arg2変数に〇〇を代入…、
そして continue; というふうにします。

return 再帰呼び出しではない; となっているものは
returnで戻り値にしていたものをresultに代入、
そして break; というふうにします。

するとこうなります。

int arg = 引数となる任意の値を代入
int result;
for (;;) {
if (arg == 100) {result = arg; break;}
arg = arg + 1;
continue;
}


これでループに変換できました。

result = arg; は機械的にやればそうなるだけで、場合によってはargを戻り値としても構いません。

もちろん、これを関数化させることもできますね。

int MSaiki_Loop (int initializeArg) {
int arg = initializeArg; // これは機械的に書いた場合
int result;
for (;;) {
if (arg == 100) {result = arg; break;}
arg = arg + 1;
continue;
}
return result;
}

これで独立した関数になり、より元の姿に近づきました。


ところで、このやり方には1つ欠点があります。

末尾再帰している関数の中で

string[] strs = 〇〇 // 適当に置いてみた
for (int i = 0; i < strs.Length; i++) {
return true;
}


みたいに、ループ文の中で return をしているコードがあると正常に動きません。

あの変換方法では、ループ文が関数を意味して、 break; や continue; が return の働きをしているわけです。

ループ文のなかで return があると、それも機械的に break; などに変換されますが、
すると単にそこのループを抜けただけで、 return の働きはしてくれません。

この場合について、色んな方法を考えましたが、それでも対応できないケースがありました。

どんなケースでも対応できて、さらに一番、便利だと思ったのはGoToで外に飛ぶことですね。

できれば使いたくないのですが…。

GoToを使いたくなかったり、言語にGoToがない場合は、この変換方法じゃ無理ですね。

新たに考えないといけなさそうです。
この変換方法は完全ではないみたいですね~。


「いい変換方法がある」という方はぜひコメントしてください。

tag:

コメント

継続渡しスタイルで書けば非末尾再帰は末尾再帰に容易に変換できます

  • 2014/05/13(火) 11:27:29 |
  • URL |
  • 743 #-
  • [ 編集 ]

Re: 743

どうもです。継続渡しスタイルというのがあるんですか。
検索してみたところScheme言語と深く関わっている感じですが、手続き型の言語でも“継続渡しスタイル”で記述することは出来るのだろうか…。

関数型言語の世界は広いですね。

関数型言語はそもそもアルゴリズムを合理的に書くために開発されたのでコンパイラが賢くないと性能が出ない。が、今どきのコンパイラは賢いのでC並に速くなったりする。
そもそも関数型言語は言語仕様が論理的で数学的だからコンパイラの最適化なんて話題と相性が良い。型推論とか。
性能が同じでエレガントに書けるのならソッチの方が有利では。

  • 2014/08/13(水) 00:23:33 |
  • URL |
  • 表記なし #-
  • [ 編集 ]

Re: 表記なし

なるほど。
関数型言語というのはコードの書きやすさ重視で設計されているんですね。

まぁ、関数型言語と手続き型言語のどちらが優れているかというのは私には結論づけられませんが、
コンピュータがノイマン型アーキテクチャである以上は手続き型言語のほうがより現実に近く、関数型言語は実行時の性能について数歩遅れていると思います。

その遅れを関数型言語のコンパイラが頑張って取り戻そうとしているわけですね。

遅延評価を原則とする言語で書けば、末尾再帰でもメモリ溢れ可能

詳しくは、
無限の構造で末尾再帰はやっちゃだめ - Haskell戦記
http://shudaisho.hatenablog.com/entry/20130612/1371043099
など、"遅延評価 末尾再帰"をキーワードに検索して下さい。
たぶん、正規評価と遅延評価では、最後に処理する「末尾」の位置が異なるのだと私は思います。
関数を呼び出すとき、正規評価では引数->関数本体の順で処理が行われるのに対し、
遅延評価では逆に、関数本体->引数の順に処理が行われます。
このように処理の順番が逆なので、最適化が効く位置も遅延評価では反転します。
遅延評価で末尾再帰を使うと、正規評価と同様に無限構造のデータを扱えなくなるようです。

話は変わりますが、継続渡しスタイルは、本来はスタックに積むべき「呼び出し元への戻り方の連鎖」=「継続」を、呼び出し先へ渡す引数の中へ含めてしまうものです。
単に継続渡しスタイルに変換しただけでは、「継続」の格納場所をスタック以外の領域(ヒープとか)に移せるだけで、メモリ全体の消費量は変わりません。
大抵のOSやCPUではスタック領域や操作を特別扱いしているため、スタックの代わりにヒープを使うのは良いのですが、メモリ消費量がループ並となる末尾最適化には敵いません。

おまけの「ループ文の中でreturn」ですが、

ループ文のなかで return があると、それも機械的に break; などに変換されますが、
すると単にそこのループを抜けただけで、 return の働きはしてくれません。

多重ループの脱出。 - trinoの走り書き
http://d.hatena.ne.jp/n-trino/20090604/p1
が参考になるでしょう。

  • 2015/09/14(月) 21:41:35 |
  • URL |
  • A-11 #-
  • [ 編集 ]

Re: 遅延評価を原則とする言語で書けば、末尾再帰でもメモリ溢れ可能

遅延評価という仕組みがあるんですね。
1件目のリンク見ましたが、何言ってるのかよく分かりませんでした…。

遅延評価の仕組みがどうなっているのか、よく分かりませんが、
たとえば遅延評価言語でreturn Saiki(x)という再帰をしたとして、それはSaikiに再び入るわけですが、xはまだ評価されていないので保持し続けないといけませんよね。

となると、C#でいえばラムダ式からラムダ式の外のローカル変数を参照できる仕組みがありますけど、あれの実装みたいな複雑な実装が必要なんですかね。
関数型言語ではちょっと違うのでしょうか。

また、保持する場所がスタック領域だとすれば、遅延評価の言語では末尾再帰でさえ、少なくとも評価されるまではスタックを積む必要があるということは想像がつきます(見当違いかもしれませんが)。

あと継続渡しスタイルというのがあるのですか。
こちらもよく分かりませんが、まあ関数型というのはいろいろあるということですね…。

最後の、多重ループのbreak、これは面倒くさい問題ですよね。
言語でそういう機能をサポートしてくれたらいいんですが、無いという。
gotoでやるのは、gotoは自由度が高すぎるので、もっと制限を設けた構文を付けてほしいですね。

素朴な実装では、遅延評価はC#と同じくクロージャを使います

>となると、C#でいえばラムダ式からラムダ式の外のローカル変数を参照できる仕組みがありますけど、あれの実装みたいな複雑な実装が必要なんですかね。
>関数型言語ではちょっと違うのでしょうか。
大体同じで、最適化コンパイルを試みない真面目な実装なら
クロージャ - Wikipedia
http://ja.wikipedia.org/wiki/%E3%82%AF%E3%83%AD%E3%83%BC%E3%82%B8%E3%83%A3
を使う必要があるでしょう。
ただし、C#をはじめ現在主流の言語の多くは、真面目な実装なんてしません。
C++などで仮想関数の仕組みを実装する真面目な方法は
仮想関数テーブル - Wikipedia
http://ja.wikipedia.org/wiki/%E4%BB%AE%E6%83%B3%E9%96%A2%E6%95%B0%E3%83%86%E3%83%BC%E3%83%96%E3%83%AB
を使うものです。
しかし上記リンクで述べられているように、C#やJavaなどでは実行時コンパイルで仮想関数テーブルを使わないコードに書き換えてしまいます。
クロージャについても、下記のリンクで述べられているように、コンパイラが強力であるほど、不真面目な=効率的な実装に置き換えられます。
プログラミング言語の進化を追え: 第4回 大人のためのブラックボックス読解講座
http://www.ibm.com/developerworks/jp/opensource/library/itm-progevo4/index.html

>最後の、多重ループのbreak、これは面倒くさい問題ですよね。
>言語でそういう機能をサポートしてくれたらいいんですが、無いという。
どこでみたか忘れたけど、C言語などで複数の文を一まとめに扱う{}に、名前を付ける言語をみた覚えがあります。
while(1)"outer_loop"{
while(1)"inner_loop"{
if(something) break "outer_loop"; //"outer_loop"{}の内側の{}は無視してジャンプ。
}
}
みたいな感じ。

  • 2015/09/21(月) 20:24:18 |
  • URL |
  • A-11 #-
  • [ 編集 ]

Re: 素朴な実装では、遅延評価はC#と同じくクロージャを使います

クロージャというのは、見てみたところ、よくわかりませんが、
オブジェクトとしての関数と、それを生成した環境において、その関数が参照する変数のスナップショット(関数オブジェクトを生成した関数内で有効なローカル変数)をセットにして包むみたいなことでしょうか。

日本語が複雑すぎてどこがどこを修飾してるのか伝わってないかもしれませんが。
C#でラムダ式を使って書いたデリゲートは、クロージャですね。

遅延評価言語での再帰は、上述のC#でのクロージャの定義とは若干異なるクロージャかもしれませんが、
与える引数をクロージャで包んでしまって、再帰呼び出しは自分自身のクロージャを生成してそのクロージャを呼ぶ…みたいな感じですか。

もちろん、C言語系の言語にはあてはまらない仕様ですが、言語によってはいけそうですね。


仮想関数テーブルのWikipedia見てみましたが、C#でも仮想関数テーブル使ってるみたいじゃないですか?
他の言語では、メソッド名の文字列で判断している場合もあるようですね。

多重ループを抜ける言語機能、いいですね。
多くの言語でなんでこういう機能がないのか、不思議です。

コメントの投稿

トラックバック

トラックバック URL
http://cyberboy6.blog.fc2.com/tb.php/277-86463f80
この記事にトラックバックする(FC2ブログユーザー)

当ブログをご利用(閲覧等)になる場合は必ず「当ブログの利用規定」をお守りください。