recursion - Erlangの再帰関数は単なるgotoではありませんか？

Question

頭の中でまっすぐにするためだけに。Erlangコードの次の例を考えてみましょう。

 test() ->
      receive
          {From, whatever} ->
                %% do something
               test();
          {From, somethingelse} ->
               %% do something else
               test();
 end.

test（）呼び出しではなく、gotoですか？

Cで学んだので、関数呼び出しを行うと、戻り位置は常にスタックに置かれるので、これを尋ねます。スタックオーバーフローが発生するため、ここのErlangではこれが当てはまるとは想像できません。

関数を呼び出すには、gotoとgosubの2つの方法がありました。gotoはプログラムフローを別の場所に誘導し、gosubはあなたがどこから来たのかを覚えているので、戻ることができます。

この考え方を考えると、Erlangの再帰をより簡単に見ることができます。なぜなら、私がgotoとしてtest（）を読んだだけなら、まったく問題がないからです。

したがって、私の質問：：Erlangは、スタック上のリターンアドレスを記憶する代わりに、gotoを使用しているだけではありませんか？

編集：

私のポイントを明確にするために：

gotoは、いくつかの言語で使用して、あちこちをジャンプできることを知っています。ただし、someFunction（）を実行する代わりに、次のことも実行できると仮定します。最初の例では、フローが戻るsomeFunction（）に移動し、2番目の例では、フローはsomeFunctionで続行され、決して戻りません。

したがって、メソッドの開始点にジャンプできるようにするだけで、通常のGOTOの動作を制限します。

このように見える場合、Erlangの再帰関数呼び出しはgotoのように見えます。

（私の意見では、gotoは、元の場所に戻ることができない関数呼び出しです）。これはまさにErlangの例で起こっていることです。

score 14 · Accepted Answer

末尾再帰呼び出しは、ハウスキーピングが実行されるため、後藤というよりも「戻り、すぐにこの他の関数を呼び出す」という意味です。

最新のポイントへの対処：リターンポイントの記録は、関数が呼び出されたときに実行されるハウスキーピングのほんの一部です。リターンポイントはスタックフレームに格納され、ローカル変数とパラメータを含め、残りの部分は（通常の呼び出しで）割り当てられ、初期化される必要があります。末尾再帰では、新しいフレームを割り当てる必要はなく、リターンポイントを保存する必要もありません（前の値は正常に機能します）が、残りのハウスキーピングを実行する必要があります。

関数が戻ったときに実行する必要のあるハウスキーピングもあります。これには、ローカルとパラメーターの破棄（スタックフレームの一部として）や呼び出しポイントへの戻りが含まれます。末尾再帰呼び出し中に、現在の関数のローカルは新しい関数を呼び出す前に破棄されますが、戻りは発生しません。

スレッドがプロセスよりも軽量のコンテキスト切り替えを可能にする方法と同様に、末尾呼び出しは、ハウスキーピングの一部をスキップできるため、軽量の関数呼び出しを可能にします。

Perlの" goto &NAME"ステートメントは、ローカルを破棄するため、あなたが考えているものに近いですが、完全ではありません。新しく呼び出された関数のパラメーターは保持されます。

もう1つの単純な違い：末尾呼び出しは関数のエントリポイントにのみジャンプできますが、gotoはほとんどの場所にジャンプできます（一部の言語では、gotoが関数の外にジャンプできないCなどのgotoのターゲットが制限されています）。

score 8 · Accepted Answer

正解です。Erlangコンパイラはそれが末尾再帰呼び出しであることを検出し、スタック上を移動する代わりに、現在の関数のスタックスペースを再利用します。

さらに、循環末尾再帰を検出することもできます。

test() -> ..., test2().
test2() -> ..., test3().
test3() -> ..., test().

また、最適化されます。

これの「不幸な」副作用は、関数呼び出しをトレースしているときに、末尾再帰関数の各呼び出しを見ることができないということですが、入口と出口のポイントを見ることができます。

score 4 · Accepted Answer

ここに2つの質問があります。

まず、いいえ。この場合、test（）のこれらの呼び出しは両方とも末尾再帰であるため、スタックをオーバーランする危険はありません。

第二に、いいえ、関数呼び出しはgotoではなく、関数呼び出しです。:) gotoを問題にするのは、コード内の構造をバイパスすることです。ステートメントから飛び出したり、ステートメントに飛び込んだり、割り当てをバイパスしたりすることができます...あらゆる種類の厄介さ。関数呼び出しには明らかな制御フローがあるため、この問題は発生しません。

score 3 · Accepted Answer

ここでの違いは、「実際の」後藤と、場合によっては後藤のように見えるものとの違いだと思います。特殊なケースでは、コンパイラは、別の関数を呼び出す前に、現在の関数のスタックを自由にクリーンアップできることを検出できます。これは、呼び出しが関数の最後の呼び出しである場合です。違いは、もちろん、他の呼び出しと同様に、新しい関数に引数を渡すことができることです。

他の人が指摘しているように、この最適化は再帰呼び出しではなく、すべての最後の呼び出しに制限されます。これは、FSMをプログラミングする「古典的な」方法で使用されます。

score 3 · Accepted Answer

それは、それがそうである理由とgoto同じ理由です。これは（の道徳的同等物）を使用して実装されますが、プログラマーに直接の足でのシュートの可能性を完全に公開するわけではありません。ifgotowhilegotogotogoto

score 2 · Accepted Answer

2

実際、 Guy Steeleによると、これらの再帰関数は究極のGOTOです。

于 2009-09-27T12:25:18.370 に答える

score 2 · Accepted Answer

これがより一般的な答えです。これは、コールスタックに基づく以前の答えに優先します。以前の回答が受け入れられたので、テキストを置き換えません。

プロローグ

一部のアーキテクチャには、「呼び出される」「関数」と呼ばれるものはありませんが、類似したものがあります（メッセージングでは「メソッド」または「メッセージハンドラ」と呼ばれる場合があります。イベントベースのアーキテクチャには「イベントハンドラ」または単に「ハンドラ」があります）。）。一般的なケースでは「コードブロック」と「呼び出し」という用語を使用しますが、（厳密に言えば）「コードブロック」には完全に機能しないものが含まれる場合があります。いくつかの場所で私がそうするかもしれないように、あなたは「呼び出し」または「呼び出す」の代わりに適切に活用された形の「呼び出し」を使うことができます。呼び出しを記述するアーキテクチャの機能は、「継続渡しスタイル」（CPS）のように「スタイル」と呼ばれることもありますが、これは以前は正式な用語ではありませんでした。物事が抽象化しすぎないようにするために、コールスタック、継続渡し、メッセージング（àlaOOP）、およびイベント処理の呼び出しスタイルを調べます。これらのスタイルに使用しているモデルを指定する必要がありますが、スペースの都合上、それらは省略しています。

呼び出し機能

または、Cは継続、調整、コンテキストのためのものであり、それで十分です

Hohpeは、コールスタックスタイルの3つの頭韻的な呼び出し機能を識別します。継続、調整、コンテキスト（これらはすべて、他の単語の使用法と区別するために大文字になっています）。

継続は、コードブロックが終了したときに実行を継続する場所を決定します。「継続」機能は「ファーストクラスの継続」（私を含めて単に「継続」と呼ばれることが多い）に関連しており、継続によって継続機能がプログラムレベルで表示および操作可能になります。
調整とは、必要なデータの準備ができるまでコードが実行されないことを意味します。呼び出された関数が終了するまでプログラムカウンターは関数に戻らないため、単一の呼び出しスタック内で、無料でCoordinationを取得できます。協調は、（たとえば）並行およびイベント駆動型プログラミングで問題になります。前者はデータプロデューサーがデータコンシューマーに遅れをとる可能性があるため、後者はハンドラーがイベントを発生させたときにハンドラーが応答を待たずにすぐに続行するためです。
コンテキストとは、コードブロック内の名前を解決するために使用される環境を指します。これには、ローカル変数、パラメーター、および戻り値の割り当てと初期化が含まれます。パラメータの受け渡しも呼び出し規約でカバーされています（頭韻を維持します）。一般的なケースでは、コンテキストをローカルをカバーする機能に分割できます。1つはパラメーターをカバーし、もう1つは戻り値をカバーします。CPSの場合、戻り値はパラメーターの受け渡しでカバーされます。

3つの機能は必ずしも独立しているわけではありません。呼び出しスタイルは、それらの相互関係を決定します。たとえば、調整は、コールスタックスタイルで継続に関連付けられています。戻り値は継続に関係するため、継続とコンテキストは一般的に接続されています。

Hohpeのリストは必ずしも網羅的ではありませんが、末尾呼び出しとgotoを区別するのに十分です。警告：Hohpeの機能に基づいて呼び出しスペースを探索するなど、接線をたどる可能性がありますが、自分自身を封じ込めようとします。

呼び出し機能タスク

各呼び出し機能には、コードブロックを呼び出すときに完了するタスクが含まれます。継続の場合、呼び出されたコードブロックは、呼び出しコードのチェーンによって自然に関連付けられます。コードブロックが呼び出されると、現在の呼び出しチェーン（または「呼び出しチェーン」）は、チェーンの最後に呼び出しコードへの参照（「呼び出し参照」）を配置することによって拡張されます（このプロセスについては、以下で詳しく説明します）。。呼び出しを考慮に入れると、名前をコードブロックとパラメーターにバインドすることも含まれます。ボンデージや規律のない言語でも、同じように楽しむことができます。

末尾呼び出し

または、答え

または、残りは基本的に不要です

末尾呼び出しは、継続を最適化することであり、メインの継続タスク（呼び出し参照の記録）をいつスキップできるかを認識することです。他の機能タスクはそれ自体で成り立っています。「goto」は、継続とコンテキストのためにタスクを最適化することを表します。これが、末尾呼び出しが単純な「後藤」ではない理由です。以下は、さまざまな呼び出しスタイルで末尾呼び出しがどのように見えるかを具体化します。

特定の呼び出しスタイルでの末尾呼び出し

さまざまなスタイルで、呼び出しチェーンがさまざまな構造に配置されます。これを「もつれ」と呼びます。これは、より適切な言葉がないためです。スパゲッティコードから離れたのはいいことではありませんか？

コールスタックでは、もつれの中に呼び出しチェーンは1つだけです。チェーンを延長するということは、プログラムカウンターを押すことを意味します。末尾呼び出しは、プログラムカウンタープッシュがないことを意味します。
CPSの下では、もつれは現存する継続で構成され、逆有向木（すべてのエッジが中央ノードに向かう有向木）を形成します。ここで、中央に戻る各パスは呼び出しチェーンです（注：プログラムのエントリポイントが「ヌル」の継続を通過すると、もつれは逆有向木の森全体になる可能性があります）。1つの特定のチェーンはデフォルトであり、呼び出し中に呼び出し参照が追加されます。末尾呼び出しは、デフォルトの呼び出しチェーンに呼び出し参照を追加しません。ここでの「呼び出しチェーン」は、「ファーストクラスの継続」という意味で、基本的に「継続」と同義であることに注意してください。
メッセージパッシングでは、呼び出しチェーンはブロックされたメソッドのチェーンであり、それぞれがチェーン内のメソッドの前にメソッドからの応答を待機します。別のメソッドを呼び出すメソッドは「クライアント」です。呼び出されたメソッドは「サプライヤ」です（「サプライヤ」はそれほど優れていませんが、意図的に「サービス」を使用していません）。メッセージングタングルは、接続されていない呼び出しチェーンのセットです。このもつれ構造は、複数のスレッドまたはプロセススタックを持つようなものです。メソッドが単に別のメソッドの応答をそれ自体としてエコーする場合、そのメソッドは、クライアントがそれ自体ではなくサプライヤを待機するようにすることができます。これにより、調整と継続の最適化を含む、もう少し一般的な最適化が得られることに注意してください。メソッドの最後の部分が応答に依存しない場合（および応答が応答に依存しない場合）最後の部分で処理されたデータに依存します）、メソッドは、クライアントの待機依存関係をサプライヤに渡した後も続行できます。これは、メソッドの最後の部分がスレッドのメイン関数になり、その後にコールスタックスタイルの末尾呼び出しが続く、新しいスレッドの起動に似ています。

イベント処理スタイルはどうですか？

イベント処理では、呼び出しには応答がなく、ハンドラーは待機しないため、「呼び出しチェーン」（上記で使用）は有用な概念ではありません。もつれの代わりに、チャネルが所有するイベントの優先キューと、リスナーとハンドラーのペアのリストであるサブスクリプションがあります。一部のイベント駆動型アーキテクチャでは、チャネルはリスナーのプロパティです。すべてのリスナーは正確に1つのチャネルを所有するため、チャネルはリスナーと同義になります。呼び出しとは、チャネルでイベントを発生させることを意味します。これにより、サブスクライブされているすべてのリスナーハンドラーが呼び出されます。パラメータは、イベントのプロパティとして渡されます。別のスタイルの応答に依存するコードは、イベント処理の下で、関連するイベントとともに別個のハンドラーになります。末尾呼び出しは、別のチャネルでイベントを発生させ、その後は何もしないハンドラーになります。末尾呼び出しの最適化には、2番目のチャネルから最初のチャネルへのイベントのリスナーの再サブスクライブが含まれるか、場合によっては、最初のチャネルでイベントを発生させたハンドラーが代わりに2番目のチャネルで発生するようにします（コンパイラーではなくプログラマーによる最適化） /通訳者）。最適化されていないバージョンから始めて、以前の最適化は次のようになります。

リスナーのアリスは、ハンドラー「パーティー」を使用して、BBCニュースのイベント「発足」を購読します
アリスがチャンネルBBCニュースでイベント「選挙」を発砲
ボブはBBCニュースで「選挙」を聞いているので、ボブの「openPolls」ハンドラーが呼び出されます
ボブは、チャンネルCNNのイベント「就任式」に登録しています。
ボブはチャンネルCNNでイベント「投票」を開始します
その他のイベントは発生して処理されます。最終的に、そのうちの1つ（たとえば「win」）がCNNでイベント「inauguration」を起動します。
ボブの禁止されたハンドラーがBBCニュースで「就任式」を発砲
アリスの就任ハンドラーが呼び出されます。

そして最適化されたバージョン：

リスナーのアリスがBBCニュースのイベント「就任式」を購読します
アリスがチャンネルBBCニュースでイベント「選挙」を発砲
ボブはBBCニュースで「選挙」を聞いているので、ボブの「openPolls」ハンドラーが呼び出されます
ボブは、BBCニュースで「就任式」を聞いている人をCNN*の就任式イベントに登録します。
ボブはチャンネルCNNでイベント「投票」を開始します
その他のイベントは発生して処理されます。最終的に、そのうちの1つがCNNでイベント「発足」を開始します。
アリスの就任ハンドラーは、CNNの就任イベントのために呼び出されます。

末尾呼び出しは、サブスクリプションを考慮に入れる必要があるため、イベント処理では扱いにくい（使用できない？）ことに注意してください。アリスが後でBBCニュースの「就任式」の購読を解除した場合、CNNの就任式の購読もキャンセルする必要があります。さらに、システムは、リスナーに対してハンドラーを不適切に複数回呼び出さないようにする必要があります。上記の最適化された例では、BBCニュースで「就任式」を起動するCNNの「就任式」の別のハンドラーがある場合はどうなりますか？アリスの「パーティー」イベントは2回解雇されるため、仕事で問題が発生する可能性があります。1つの解決策は、ステップ4で* BobがBBCニュースの「就任式」からすべてのリスナーの購読を解除することですが、その後、アリスがCNN経由ではない就任式イベントを見逃すという別のバグを導入します。たぶん彼女はアメリカとイギリスの両方の就任式を祝いたいと思っています。これらの問題は、おそらくサブスクリプションのタイプに基づいて、モデルで区別していないために発生します。たとえば、特別な種類のワンショットサブスクリプションがあるかもしれません（System-Vシグナルハンドラー）または一部のハンドラーはサブスクライブを解除し、末尾呼び出しの最適化はこれらの場合にのみ適用されます。

次は何ですか？

呼び出し機能のタスクをさらに完全に指定することができます。そこから、どのような最適化が可能で、いつ使用できるかを理解できます。おそらく、他の呼び出し機能を識別できます。また、呼び出しスタイルの例をさらに考えることもできます。また、呼び出し機能間の依存関係を調べることもできます。たとえば、同期および非同期の呼び出しには、継続と調整を明示的に結合または分離することが含まれます。それは決して終わらない。

それを全部手に入れますか？私はまだそれを自分で消化しようとしています。

参照：

Hohpe、Gregor; 「イベント駆動型アーキテクチャ」
スガルスキー、ダン; 「CPSと末尾呼び出し-一緒に素晴らしい味がする2つの素晴らしい味」

score 1 · Accepted Answer

この場合、追加の作業を行ったり、ローカル変数を使用したりする必要がないため、末尾呼び出しの最適化を行うことができます。したがって、コンパイラはこれをループに変換します。

score 0 · Accepted Answer

（私の意見では、gotoは、元の場所に戻ることができない関数呼び出しです）。これはまさにerlangの例で起こっていることです。

それはErlangで起こっていることではありません、あなたはあなたが来たところに戻ることができます。

呼び出しは末尾再帰です。つまり、gotoの「一種」です。コードを理解または記述しようとする前に、末尾再帰とは何かを理解していることを確認してください。Erlangを初めて使用する場合は、JoeArmstrongの本を読むことはおそらく悪い考えではありません。

概念的には、test（）を使用して自分自身を呼び出す場合、渡したパラメーター（この例ではなし）を使用して関数の先頭が呼び出されますが、スタックには何も追加されません。したがって、すべての変数が破棄され、関数が新しく開始されますが、新しい戻りポインターをスタックにプッシュしませんでした。つまり、CやJavaの場合のように、gotoと従来の命令型言語スタイルの関数呼び出しのハイブリッドのようなものです。ただし、呼び出し元の関数からの最初の呼び出しから、スタックにはまだ1つのエントリがあります。したがって、別のtest（）を実行するのではなく、最終的に値を返すことによって終了すると、その戻り位置がスタックからポップされ、呼び出し元の関数で実行が再開されます。