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 节尾调用和尾上下文：

尾调用是发生在尾上下文中的过程调用。尾上下文是归纳定义的。请注意，尾上下文始终是根据特定的 lambda 表达式确定的。

  • lambda 表达式主体中的最后一个表达式，如下面的 <tail expression> 所示，出现在尾部上下文中。

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

  • 如果以下表达式之一处于尾部上下文中，则显示为 <tail expression> 的子表达式处于尾部上下文中。这些是通过用 <tail expression> 替换某些出现的 <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>)，一个 <tail body> 是<definition>* <tail sequence>，一个 <tail sequence> 是<expression>* <tail expression>。

  • 如果一个cond表达式在尾部上下文中，并且有一个形式的子句，那么（隐含的）调用由 <expression 2 > 的求值产生的过程是在尾部上下文中。<表达式2 > 本身不在尾部上下文中。(<expression1> => <expression2>)

于 2013-09-15T22:28:16.253 回答
7

您还没有提到这将解释 Scheme 的运行时或语言，所以这个答案可能有点偏离。

同时实现尾调用优化和get call/cc的万无一失的方法是做CPS-conversion。使用 CPS，每次调用都是尾调用，并且非尾递归代码得到嵌套的延续。

在应用尾调用之前弹出堆栈时，您将获得 TCO。由于每次调用都是 CPS 中的尾调用，因此您知道该怎么做。

除了 3 和 7 之外，您的每个程序都将从中受益。当递归调用返回时，这些程序还有待执行。

编辑 Python：

Python 没有 TCO，因此您不能使用宿主语言直接进行调用。但是，您可以使用蹦床来做到这一点。

于 2013-09-15T22:38:45.173 回答