再帰関数のサポートについて

質問

http://ja.phptherightway.com/pages/Functional-Programming.html
上記ページにありますようにPHPは再帰関数をサポートとあります。

関数プログラミングなるものはこの再帰関数を使ってループをつくったりすると
ききました。
たとえば
function roop($i){
print($i);
$n = $i + 1;
if($n < 100){
roop($n);
}
}
roop(1);

というようなコードでしょうか。
これは１～99までのループですよね。

これはPHPがインタープリターといえど、一度　PHP専用のバイトコードに変換して
からPHPエンジンがバイトコードを実行するため再帰が可能という解釈でもんだいないですかね？

もしほんとうに逐次解釈なインタープリターなら解釈途中に、その関数自体の定義をインタープリターが認識？
し終わる前に未定義状態の関数が出現してしまうってことですよね？
undefined な関数があるといようなエラーがでてくのでしょうか？

生Cのソースみればわかるのでしょうけれども、私はCがわからないので・・・。

概要でよいのでご教授ください。

回答No.4

wormhole · ベストアンサー

＞ということは、再帰関数などは、自身の関数定義が宣言し終わる前に
＞自身の関数内で自分自身を呼び出してしまっているので、この場合において
＞バイトコードをはかないインタープリターは再帰関数を実装というかサポートできないという解釈でいいのかなということです。

仮にそういうインタプリターがあったとしても、その再帰関数を一番最初に呼び出すところでひっかかるんじゃないでしょうか。
再帰関数の定義より前に、その再帰関数を呼び出していれば未定義で実行されないでしょうし、定義より後に呼び出しがあれば再帰関数の定義は読み込み済みなので呼び出せるし再帰関数自身も当然呼び出せる。

補足

＞仮にそういうインタプリターがあったとしても、その再帰関数を一番最初に呼び出すところでひっかかるんじゃないでしょうか。

なるほど、・・・ちょっと考えると、そう考えるのがふつうですね・・・。

回答No.5

ki073

逐次実行される場合でも、
関数を書いてある部分はあくまでも定義であって、読み込み中に実行されるわけではありません。
function roop($i){
では$1の値が確定していませんので、実行しようが無いのです。
最後の
roop(1);
で引数が確定するので、ここで初めて実行されます。

No.3で書かれているように、ローカル変数が使えないと再帰関数は難しいでしょうねえ。
やっぱり変数のスコープが需要なのでしょう。

いろいろなスクリプト言語で逐次実行環境があるはずですが、Rubyにはirbというのがあります。
一行入力すると結果が出力されます。
関数を入れると当然ですが読み込むだけです。その関数を呼び出したときに初めて答えがでます。
逐次実行のようすがよくわかります。
ループや条件分岐などもおもしろい動作をしますし、クラス定義などほぼ全ての機能が使えます。

回答No.3

mpro-gram

インタープリターといえど、ソースファイル読み込みは最初に終わらせるんじゃないですかね。実行終了までファイル開きっぱなしで、逐次読み込みって時間的にも無駄が多い様な？
phpは、開始スクリプトファイルは、最初に全部読み込んでいるし、その時点でメモリに展開してるわけで、この時点で、バイトコードじゃないのかな？テキスト文字列のまま保持するとは思えない。
コンパイラはそのバイトコードをファイルに出力するが、インタープリターは、展開し終わったら即実行開始なだけでしょう。バイトコードに解釈できなければ、文法エラーで終了するし。
インタープリターの「展開しては実行」は、プログラムファイルが複数になったときよく解る。コンパイラ型言語では、全部のファイルをコンパイル（バイトコード変換）できないと実行用ファイルにならないが、インタープリター型言語では、一個目のファイルの実行を開始して、include文の行までいかないと２個目のプログラムファイル読み込みも文法チェックも行われない。

で、phpマニュアルによれば、
http://jp.php.net/manual/ja/functions.user-defined.php
「PHP では、関数は参照される前に定義されている必要はありません」

→　つまり、同じファイル内に、条件に関係なく定義されていれば、後方に定義があってもよいということ。
最初に文法チェックでファイル全体を読み込むから、この時点で関数の存在は解ってるので（シンボルテーブルに登録済み）、その定義文のところへ飛ぶ（関数の内容が前方に記述されてる必要はない、というか前方に関数定義が記述されていても、呼び出されない限り関数内の実行時エラーは出ないし）
→　しかし、条件分岐内や、include先の別ファイルにあるときは、その条件文やinclude文が実行されてからでないと、関数定義の存在がシンボルテーブルに登録されないので、実行順として、その条件分岐や、include文が先に記述されている必要がある。
→　でも、再帰関数は、一回目に呼ばれた時点で、存在は自明なので、次の呼び出しも問題ない。最後まで実行されてる必要はない。

あと、disk basic だって、「subroutine 行番号」記述で後方に記述された関数呼び出しみたいなことはやれた。変数が全部global なので、同じ名前だと、呼び出しごとに別の物とはならなかったので再帰出来なかっただけで、perlとかphpとかのように局所変数が使えれば、再帰関数も可能となる。
perlとかJavaScriptはちゃんとlocal用の宣言しないと、local scopeの変数にならないので、再帰関数内でうっかりglobal変数を使うと、無限ループに陥ったり、結果が狂ったりする。
なので、再帰関数を作れるかには、変数のスコープという概念が重要。

他言語でこんな記述も見つけた。
http://d.hatena.ne.jp/adsaria/20080730/1217399820

お礼

なるほど・・・。
インタプリターの実行方法うぬんで考えるのはナンセンスというわけですか・・・。
もう言語仕様レベルで再帰が可能かどうかという話ですね・・・。

回答No.2

SherlockHolmes2

バイトコード（中間コード）を吐かない言語であっても、スクリプトの実行前にソースコードを一旦舐める物もあります。（どこまで舐めるかは言語の実装によって異なると思います）

そこで文法エラー等を引っ掛けたり、どのような関数があるか、等の情報を採取し、それから実際に実行に移ります。

ですので、質問内容にあるような再帰関数も実行可能なのです。

回答No.1

wormhole

＞もしほんとうに逐次解釈なインタープリターなら解釈途中に、その関数自体の定義をインタープリターが認識？

この場合の「逐次解釈なインタープリター」というのはプログラムソースを先頭から読みながら順番に実行するという意味ではありません。
プログラムソースを解析した中間コードを順番に実行するという意味です。

補足

あー、質問のしかたがわるかったですね。

知りたいのは、もしバイトコードなどをはかないインタープリター　の場合
（現存するスクリプトでそのようなインタプリタがあるかどうかはわかりませんが）
事前に関数の定義など知りようがないですよね？

ということは、再帰関数などは、自身の関数定義が宣言し終わる前に
自身の関数内で自分自身を呼び出してしまっているので、この場合において
バイトコードをはかないインタープリターは再帰関数を実装というかサポートできないという解釈でいいのかなということです。