末尾再帰は、新しいスタック フレームを作成する代わりに同じスタック フレームを再利用するため、より効率的ですが、スキームのすべてにこれが必要なのはなぜですか?
3 に答える
3
Scheme には がないgotoため、すべてのループは最終的に末尾再帰を使用して行われます。適切な末尾再帰の保証がなければ、Scheme でループを提供する信頼できる方法はありません。
更新:「最終的に末尾再帰を使用する」とはどういう意味かを説明したいと思います。do@newacct が言及したので、マクロを見てみましょう。例えば：
(do ((i 1 (+ i 1)))
((> i 10))
(display i)
(newline))
前述したように、Scheme には がないgotoため、どこかからループを取得する必要があります。実際には、次のように (次のように) マクロ展開されます。
(let loop ((i 1))
(unless (> i 10)
(display i)
(newline)
(loop (+ i 1))))
loophere はキーワードでも組み込み関数でもないことに注意してください。これは名前付きの †</sup> によって作成され、フォームletの下部で (末尾再帰を介して) 呼び出される名前付き関数です。unless
実際、Scheme の標準的なループ形式はすべて末尾再帰を使用します。そこから逃れることはできません。
† 名前付きlet(大まかに言えば‡</sup>) のマクロ展開は次のとおりです。
(letrec ((loop (lambda (i)
(unless (> i 10)
(display i)
(newline)
(loop (+ i 1))))))
(loop 1))
‡ 厳密に言えば、次のようにマクロに展開します。
((letrec ((loop (lambda (i)
(unless (> i 10)
(display i)
(newline)
(loop (+ i 1))))))
loop)
1)
于 2013-02-18T21:13:25.943 に答える
2
末尾再帰は、言語の仕様によって義務付けられています。R6RS のセクション5.11からの引用:
Scheme の実装は適切に末尾再帰でなければなりません。テール コンテキストと呼ばれる特定の構文コンテキストで発生するプロシージャ コールは、テール コールです。無制限の数のアクティブ末尾呼び出しをサポートする場合、Scheme 実装は適切に末尾再帰的です。呼び出されたプロシージャがまだ戻る可能性がある場合、呼び出しはアクティブです。これには、通常のリターンだけでなく、後で呼び出される call-with-current-continuation によって以前に取得された継続によるリターンも含まれることに注意してください。キャプチャされた継続がない場合、呼び出しは最大 1 回返される可能性があり、アクティブな呼び出しはまだ返されていないものになります。適切な末尾再帰の正式な定義は、Clinger の論文 [5] に記載されています。(rnrs base (6)) ライブラリーからの構築物で末尾呼び出しを識別する規則は、セクション 11.20 で説明されています。
これの実際的な理由は、末尾再帰により、再帰を使用した効率的なループの実装が可能になるためです。
于 2013-02-18T21:21:08.143 に答える
0
Without TR guarantee call/cc would be unusable. Looping in itself could be achieved via do which is a part of the language.
edit: this turned out to be not correct. See comments by John Clements at the question. A language can have non-TR function call mechanism but have a special separate mechanism for calling the continuations.
于 2013-02-19T17:24:01.963 に答える