2

次の関数の両方が構文的に末尾再帰関数であることがわかりますが、racketでは、どちらが実際に末尾再帰として扱われるか、またはその両方ですか? つまり、インタプリタによって末尾再帰として最適化されているかどうかです。

;;1
(define (foo i m s)
    (if (< i m)
        (foo (+ i 1) m (+ i s))
        s))

;;2
(define (foo i m s)
    (if (= i m)
        s
        (foo (+ i 1) m (+ i s))))

他の Lisp には別の答えがありますか?

4

4 に答える 4

4

再帰呼び出しが末尾の位置で行われるという事実により、どちらも末尾再帰です。つまり、再帰を呼び出すときに最後に行われることです。if示されている手順で、式の結果部分と代替部分の順序が逆になってもまったく問題ありません。

また、Scheme の仕様により、構文的に言えば、コード内のどこに出現するかに関係なく、すべての末尾再帰を最適化して除去する必要があります。

Scheme の実装は適切に末尾再帰でなければなりません。テール コンテキストと呼ばれる特定の構文コンテキストで発生するプロシージャ コールは、テール コールです。無制限の数のアクティブ末尾呼び出しをサポートする場合、Scheme 実装は適切に末尾再帰的です。呼び出されたプロシージャがまだ戻る可能性がある場合、呼び出しはアクティブです。これには、通常のリターンだけでなく、後で呼び出される call-with-current-continuation によって以前に取得された継続によるリターンも含まれることに注意してください。キャプチャされた継続がない場合、呼び出しは最大 1 回返される可能性があり、アクティブな呼び出しはまだ返されていないものになります。適切な末尾再帰の正式な定義は、Clinger の論文 [5] に記載されています。(rnrs base (6)) ライブラリーからの構築物で末尾呼び出しを識別する規則は、セクション 11.20 で説明されています。

于 2013-03-17T15:59:41.397 に答える
3

私たちがSchemeについて話している限り、いいえ。末尾呼び出しを検出し、適切な最適化を行うには、適合するすべての実装が必要です。これにより、一定のスタック スペースのみが必要になります。あなたの例では、どちらも完全に有効な tail-callsであり、適合する実装によってそのように認識される必要があります。

一方、「Lisp 全般」について話している場合は、事情が異なります。たとえば、ANSI Common Lisp では、末尾呼び出しを特別に処理するために適合する実装を必要としません。最新の実装のほとんどはテール コールを認識しますが (宣言の適切な組み合わせがあれば最適化して取り除きます)、言語自体にはこの動作を保証するものは何もありません。

于 2013-03-17T15:57:54.513 に答える
3

スキーム R7RS ドラフト 8の 11 ページのセクション 3.5 では、構文形式に基づいてすべての末尾再帰要件を特定しています。if要件は次のとおりです。

(if expression <tail expression> <tail expression>)
(if expression <tail expression>)

したがって、コード例に基づいて、Racket が Scheme に忠実であると仮定すると、どちらも末尾再帰です。他の Lisp に関しては、Common Lisp が末尾再帰の最適化を必要とするとは思わない。

于 2013-03-17T16:36:12.510 に答える
0

emacs lisp は末尾再帰を最適化しません:

(defun fact (n &optional result)
  (unless result (setq result 1))  ; use 1 if not given
  (if (zerop n) result
     (fact (1- n) (* n result))))
(fact 12)
479001600
(fact 1000)
Lisp nesting exceeds max-lisp-eval-depth

(値は固定整数であるため、1000 の正確な値を返すことはできません!とにかく -(fact 30)動作しますが、間違った値を返します。)

以前の特派員が言ったことに加えて、実装は、より高いoptimizationレベルおよび/またはより低いレベルで末尾再帰を自由に最適化できますsafety。疑わしい場合は、別の値を(disassemble 'foo) 試してみ(trace foo)てください。末尾再帰が最適化されていない場合は、呼び出し時にすべての呼び出しが表示されます。最適化されている場合は、「トップ」呼び出しのみが表示されます。

于 2013-03-22T14:07:52.783 に答える