2016-08-05 13 views
3

講義中、私はテールコールの定義をテールコンテキストで発生するコール式として指定しました。私はThe Revised Report on the Algorithmic Language Schemeで尾のコンテキストの定義を見上げ:関数のテールコンテキストとは何ですか?

末尾呼び出し尾文脈で発生するプロシージャコールです。テールのコンテキストは誘導的に定義されます。テール・コンテキストは、特定のラムダ式に関して常に決定されることに留意されたい。

私はこれが実際に尾の文脈が何であるかを明確にしているとは思わないが、誰かが初心者にとって理解しやすい説明を与えることができるだろうか?

答えて

1

テールは 動物 機能の最後です。直観的には、関数が呼び出し元に評価の結果を返す以外に何もしなければ、テールコンテキストで評価が行われます。

テールコンテキストに関する重要な点は、コールフレーム内でテールコンテキストで実行されるコールによってコールフレームが再利用されることを可能にするものは何もないことです(コール元への参照を除く)。そうすることで、不完全なパーティショニングを行うquicksortのようなアルゴリズムの場合、いくつかの再帰アルゴリズムのスペース要件をO(N)からO(1)、またはO(log N)に変更できます。

プログラムフロー分析では、コールフレームをリサイクルする他の可能性を特定できますが、多くの言語では、単純な構文解析でテールコンテキストを認識できます。 Schemeの場合、プロシージャーは元のポストにリンクされた言語文書で指定されます。スキームでは、このようにテールコールを識別できる場合、テールコールを最適化する必要があります。

他の多くの言語では、テールコールの最適化は不要であり、場合によっては可能でもありません。たとえば、C++では、最後の呼び出しの後で戻り値の前に実行する必要のある暗黙のデストラクタが存在することがあります。また、返される値を別の型に変換する必要があるかもしれません。コールフレームがイントロスペクション(たとえばJavascript)に使用できる言語では、コールフレームリサイクルは、観察可能なプログラムの動作を変更します。

関連する問題