6

私は Scheme インタプリタを書こうとしていますが、TCO の実装が難しいと感じています。TCO が機能するために関数にどのようなプロパティが必要かはわかりません。

1) 定義の最後に自己再帰呼び出しがある関数:

(define (sum-list list accum)
  (if (null list) accum
      (sum-list (cdr list) (+ accum 1))))

2) 定義の最後にない自己再帰呼び出しを持つ関数:

(define (sum-list list accum)
  (cond ((not (null list))
         (sum-list (cdr list) (+ accum 1)))
        (else accum)))

3) 再帰呼び出しを変数に格納してから返す関数:

(define (sum-list list accum)
  (let ((sum
         (if (null list)
             accum
             (sum-list (cdr list (+ accum 1))))))
    sum))

4) 相互再帰関数:

(define (sum-list list accum)
  (if (null list)
      accum
      (other-function (cdr list) (+ accum 1))))

(define (other-function list accum)
  (sum-list list accum))

5) 関数定義の最後で別の無関係な関数を単純に呼び出す:

(define (foo)
  (bar))

6) 私が考えることができる最もトリッキーなケースは閉鎖です。スコープ内の変数への参照を保持するとどうなりますか?

(define (sum-list list accum ignored)
  (let ((local-var 12345))
    (if (null list)
        accum
        (sum-list
         (cdr list)
         (+ accum 1)
         (lambda () local-var)))))

7) 引数として自己再帰呼び出しを使用して、関数定義の最後で別の関数を呼び出す:

(define (sum-list list)
  (if (null list)
      0
      (+ 1 (sum-list (cdr list)))))

私が理解しているように、TCO 実装 (Scheme と Common Lisp の両方) は TCO に適した関数を書き換えるため、TCO に適した関数を静的に検出できなければなりません。

私が知りたいのは：

  • これらの関数のうち、TCO によって書き直されるのはどれですか? また、なぜそれらだけを書き直すのでしょうか?
  • TCO の書き換えが発生する状況 (例: 7) ではありますが、関数は引き続きメモリを線形に消費しますか?
4

2 に答える 2

7

Scheme 仕様を見てください。考えられるすべてのテール コンテキストがそこで定義されています。特に、R6RS (現在承認されている標準) では、セクション§11.20 テール コールとテール コンテキストを確認する必要があります。

テールコールは、テール コンテキストで発生するプロシージャ コールです。末尾のコンテキストは帰納的に定義されます。末尾のコンテキストは、特定のラムダ式に関して常に決定されることに注意してください。

  • 以下で <tail expression> として示されている、ラムダ式の本体内の最後の式は、末尾のコンテキストで発生します。

    (lambda <formals>
  <definition>* 
  <expression>* <tail expression>)

  • 次の式のいずれかが末尾のコンテキストにある場合、<末尾の式> として示されている部分式は末尾のコンテキストにあります。これらは、<expression> の一部を <tail expression> に置き換えることにより、この章で説明するフォームの構文の仕様から派生したものです。テール コンテキストを含むルールのみがここに表示されます。

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

(cond <cond clause>+)
(cond <cond clause>* (else <tail sequence>))

(case <expression>
  <case clause>+)
(case <expression>
  <case clause>*
  (else <tail sequence>))

(and <expression>* <tail expression>)
(or <expression>* <tail expression>)

(let <bindings> <tail body>)
(let <variable> <bindings> <tail body>)
(let* <bindings> <tail body>)
(letrec* <bindings> <tail body>)
(letrec <bindings> <tail body>)
(let-values <mv-bindings> <tail body>)
(let*-values <mv-bindings> <tail body>)

(let-syntax <bindings> <tail body>)
(letrec-syntax <bindings> <tail body>)

(begin <tail sequence>)

    <cond 節> は(<test> <tail sequence>)、<case 節> は((<datum>*) <tail sequence>)、<テール ボディ> は<definition>* <tail sequence>、<テール シーケンス> は<expression>* <tail expression>です。

  • cond式が末尾のコンテキストにあり、次の形式の節がある場合、 <expression 2 >の評価の結果として生じるプロシージャへの (暗黙の) 呼び出しは、末尾のコンテキストにあります。<式2 >自体は末尾のコンテキストではありません。(<expression1> => <expression2>)

于 2013-09-15T22:28:16.253 に答える
7

これがSchemeを解釈するランタイムまたは言語について言及していないため、この答えは少しずれている可能性があります。

末尾呼び出しの最適化と get call/cc を同時に実装する確実な方法は、CPS 変換を行うことです。CPS では、すべての呼び出しは末尾呼び出しであり、末尾以外の再帰コードはネストされた継続を取得します。

テールコールを適用する前にスタックをポップしたときに得られる TCO。CPS ではすべてのコールがテール コールであるため、何をすべきかがわかります。

3 と 7 を除いて、すべての手順がこの恩恵を受けるでしょう。

編集パイソン:

Python には TCO がないため、ホスト言語を使用して直接呼び出しを行うことはできません。ただし、トランポリンを使用することもできます。

于 2013-09-15T22:38:45.173 に答える