再帰関数のインライン展開

質問

再帰関数のインライン展開は出来るのでしょうか？
もし、出来るようならアセンブラではどのように表現されているんですか？
C以外の言語でも、再帰関数のインライン展開が出来るプログラム言語があれば教えてください。

回答No.7

jacta · ベストアンサー

> というのは、最適化をせずに、明示的にインライン指定をしなくても自動でインライン展開（可能な限り）をしてくれるということですね。
> 逆にCでは最適化をするかインライン指定をしないとインライン展開（可能な限り）をしてくれないということですか？

ちょっと違います。
確かに、明示的にinlineを付けなくても、最適化でインライン展開されることはありますが、ここで取り上げているのはinlineというキーワードの意味についてです。
C++ではinlineを付けた関数はインライン展開を目指すのに対して、Cではinlineを付けた関数は高速呼び出し（実現方法は任意）を目指すというわけです。

> > プロセッサ依存の関数ベクタ
> よく分からないので勉強します

通常、関数を呼び出すには16～64ビット程度のアドレスを指定する必要があります。それを、関数ベクタ（関数のアドレスを集めたテーブル）に予め登録しておき、何番目の関数というように（ハード的に）指定すれば、もっと効率よく関数を呼び出せます。

他には、絶対アドレスではなく、相対アドレスで指定すれば、関数呼び出しを効率化できる可能性があります。

お礼

私自身プログラミングは上位アプリケーションしか作ったことがなく、インライン展開も「オプティマイザで出来ればインラインしとこう」くらいでした。
分からないキーワードがたくさん出てきたのでもっと勉強します。
とても参考になりました。ありがとうございました。

回答No.6

Quant

#3です。
私がアセンブラを組んでいたときは、OSがプロセスに割り当てたメモリの下位番地がスタックに割り当てられるので、特別スタックをプログラマが意識する必要はなかったように思います。今は変わっているんですかね。
ただ自動的に割り当てられたスタックには限りがありますので、再帰の階層が深くなりすぎると、スタックオーバーフローのエラーが出ますので、そのときは、プログラムをリンクする段階でスタック領域を確保できるようにたいていのコンパイラはなっていました。

回答No.5

jacta

末尾再帰の場合にはループに展開できる可能性があることは既に回答が出ている通りです。

他に、再帰関数の引数の一部が定数であれば、関数の定義次第ではインライン展開できる可能性があります。
もし、引数の全部が定数であれば、単なる右辺値になったり、関数内での副作用の部分だけが直接インライン展開される可能も、「原理的には」考えられます。

> C以外の言語でも、再帰関数のインライン展開が出来るプログラム言語があれば教えてください。

C++とか（多分期待している答えは違うんでしょうね）。
C言語もC99でinlineが標準でサポートされるようになりましたが、C++のinlineとは微妙に仕様がことなります。
C++では文字通り（可能な限り）インライン展開させるための機能ですが、C99では（可能であれば）通常より高速に呼び出す方法を採用させるための機能です。それはインライン展開でもよいですし、プロセッサ依存の関数ベクタを使ったり、ハード的な機能を利用したり、関数の定義によって方式を選択したりしても構わないわけです。

お礼

C言語とC++とではインライン展開の仕様が違うんですか。
> C++では文字通り（可能な限り）インライン展開させるための機能
というのは、最適化をせずに、明示的にインライン指定をしなくても自動でインライン展開（可能な限り）をしてくれるということですね。
逆にCでは最適化をするかインライン指定をしないとインライン展開（可能な限り）をしてくれないということですか？

> プロセッサ依存の関数ベクタ
よく分からないので勉強します

ありがとうございました。

回答No.4

BLUEPIXY

普通はできないです。
引数の受け渡しによる値の保持をするスタックを自前で作ればいいのかもしれませんが、なにやってんだかわかんないですよね。
それに、もしインライン展開できるとしても、インライン指定した関数がコンパイラによってインライン展開されるかどうかはわかりません。
もともとできるかぎりインラインにしてねという指定だからです。
大抵の場合、再帰関数はループに置き換えできると思うので、初めからループとしてコーディングした方がいいと思います。

お礼

自前でスタックを作るのは訳が分からなくなりそうですね。関数コールのオーバーヘッドが気になるようなら素直にループ構造に置き換えたほうがいいですね。

回答No.3

Quant

長い間アセンブラでプログラムを組んでいないので、自信ありませんが、再帰関数の場合、スタックで引数のやり取りをするぐらいで、他の処理は普通の関数と同じだったと思います。

回答No.2

xcrOSgS2wY

一般論として、再帰関数は次のような方法によるインライン展開が可能です。

(1) あらかじめ決めた数段分だけ展開する

例えば「f()がf()を呼ぶ」かわりに、f()のコピーを2つ作成しておき「f()がf2()を、f2()がf3()を、f3()がf3()を呼ぶ」ように展開します。（常にこのような展開が可能なわけではありません。）

すると、f()→f2()とf2()→f3()の各呼び出しは再帰ではない普通の関数呼出になるので、f()とf2()は通常の関数と同様のインライン展開が可能になります。

このような形にすることで、ループアンロールと同様のメリットがあります。

(2) 「終端再帰関数」を単純ループに置き換えて展開する

終端再帰関数とは、関数実行の最後で再帰呼出を行う再帰関数のことです。このような形の関数の場合、これを再帰ではなく単純ループの形に書き換えることが可能です。（常に可能なのか、あるいは正確にはどのようにして「終端再帰」を見分けるのか、という厳密な定義は知りません。）

ですので、再帰関数が終端再帰関数であれば、単純ループに置き換えた上で通常の関数と同様のインライン展開が可能になります。

お礼

(1)では階乗計算などで実現できそうですね。

(2)ではインラインで出来ない再帰構造は「終端再帰」に変えた方がいいということですね。（オーバーヘッド軽減のため）
「終端再帰」というのがよく分からないので勉強してみます。

ありがとうございました。

回答No.1

rabbit_cat

普通はできないです。

ただし、いわゆる末尾再帰は、ループに展開できます。
Lisp，Schemeなどの関数型言語では、ほぼ必須の機能です。
C++等では、実現している処理系と思いますが。

末尾再帰でないループは、スタックを自前で作ることでループに展開できますが、これを自動的にやってくれる最適化機能は、多分ないと思います。

お礼

> いわゆる末尾再帰は、ループに展開できます。
末尾再帰がよく分からないので勉強します。

末尾再帰に修正したい場合は自力で修正しないといけないんですね。
関数設計時に末尾再帰を頭に入れておかないといけないですね。

ありがとうございました。