程式語言介紹/尾呼叫成本模型

我們從回顧一下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