如何检测可以应用尾调用优化的函数？

Question

我正在尝试编写一个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),但该函数仍然线性消耗内存？

Answer 1

看看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 clause>是(<test> <tail sequence>),<case子句>是((<datum>*) <tail sequence>),<tail body>是<definition>* <tail sequence>,<tail sequence>是<expression>* <tail expression>.

• 如果cond表达式在尾部上下文中,并且具有该表单的子句,则对<expression ₂ > 的求值产生的过程的(隐含的)调用在尾部上下文中.<表达式₂ >本身不在尾部上下文中.(<expression1> => <expression2>)

Answer 2

你还没有提到它将解释Scheme的运行时或语言,所以可能这个答案有点偏.

实现尾部呼叫优化和同时获得呼叫/ cc的简单方法是进行CPS转换.使用CPS,每个调用都是尾调用,非尾递归代码获得嵌套延续.

在应用尾调用之前弹出堆栈时你会得到TCO.由于每次通话都是CPS的尾部通话,因此您知道该怎么做.

除了3和7之外,你的每个程序都会从​​中受益.当递归调用返回时,这些程序还有一个继续.

编辑Python:

Python没有TCO,因此您无法使用宿主语言直接进行调用.但是,你可以用蹦床来做.