编程语言介绍/尾调用成本模型

我们从回顾一下reverse的实现开始，我们之前讨论过

reverse_orig([],[]).
reverse_orig([Head|Tail],Rev) :-  reverse_orig(Tail,TailRev),  @(TailRev,[Head],Rev).

这个实现对于我们要反转的列表元素数量是二次方的。下面，我们有一个不同的实现，它对我们要反转的列表中的元素数量是线性的

reverse_opt(X,Y) :- rev(X,[],Y).
rev([],Sofar,Sofar).
rev([Head|Tail],Sofar,Rev) :-  rev(Tail,[Head|Sofar],Rev).

这个谓词使用了一个辅助函数，它有三个参数。这三个参数中的第二个充当累加器：我们将递归调用的参数的构造转移到之前我们在返回时所做的任务。在这个具体的例子中，这个任务包括将一个元素添加到当前反转列表的开头。很容易知道rev在第一个列表的元素数量上以线性时间运行。这个谓词有两个子句。第一个，基本情况，是 O(1)。第二个，归纳情况，执行一个递归调用，并且每次调用的成本是 O(1)，即它包括将一个元素添加到一个列表的开头。此外，这个谓词还有另一个优势，我们在 w:gprolog 中说明

| ?- length(L, 10000), reverse_opt(L, X).

L = [A,B ... ]

(354 ms) yes
| ?- length(L, 10000), reverse_orig(L, X).

Fatal Error: global stack overflow (size: 32768 Kb, environment variable used: GLOBALSZ)

那么，发生了什么？第一个版本的 reverse 甚至不会在大型列表上终止，而第二个版本不仅完美终止，而且运行速度非常快。这个案例中的秘密是一种叫做尾调用的优化。如果一个函数的最后一个动作是执行一个递归调用，那么这个函数的激活记录可以被重用来存储新的数据。换句话说，没有创建新的激活记录；只是在进行内存空间的重用。实际上，这种优化将递归函数转换为 C 风格的 while 循环。原则上，任何递归函数都可以用这种方式优化。例如，我们展示了两个函数，这次是在 SML 中，它们不是尾调用，并展示了相应的尾调用版本

fun sum [] = 0
  | sum (a::l) = sum l + a;

fun sum_opt thelist =
    let
      fun sum (nil, sofar) = sofar
      |   sum (head::tail, sofar) = sum (tail, sofar + head)
    in
      len (thelist, 0)
    end;

fun length nil = 0
|   length (head::tail) = 1 + length tail;

fun length_opt thelist =
    let
      fun len (nil, sofar) = sofar
      |   len (head::tail, sofar) = len (tail, sofar + 1)
    in
      len (thelist, 0)
    end;

将非尾调用函数转换为尾调用调用的技巧很简单：创建一个辅助函数，将原本在调用返回时执行的计算移动到累加器的构造过程中。例如，SML 的 foldl 实现是尾调用。折叠操作符的应用发生在新归约种子构造期间，正如我们下面看到的

fun foldl _ c nil = c
  | foldl f c (a::b) = foldl f (f(a,c)) b