跳至內容

編譯器遞迴測試

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

編譯器遞迴測試,是一種由電腦科學家高德納提出,用來評價ALGOL 60程式語言實現的手段。該測試的目的是辨識出能夠正確實現「遞迴和非本地參照」的編譯器。

There are quite a few ALGOL60 translators in existence which have been designed to handle recursion and non-local references properly, and I thought perhaps a little test-program may be of value. Hence I have written the following simple routine, which may separate the "man-compilers" from the "boy-compilers" - 高德納[1].

(目前只有少數的ALGOL 60直譯器能夠正確處理遞迴和非本地參照,所以我認為設計一段小程式去測試編譯器的遞迴功能是有價值的。因此我寫了這段簡單的代碼,以便區分「年幼的」編譯器和「成熟的」編譯器。)

Knuth的例子

[編輯]
begin
real procedure A (k, x1, x2, x3, x4, x5);
value k; integer k;
    begin
        real procedure B;
        begin k:= k - 1;
        B:= A := A (k, B, x1, x2, x3, x4);
    end;
    if k <= 0 then A:= x4 + x5 else B;
end;
outreal (A (10, 1, -1, -1, 1, 0));
end;

這將形成一棵由B呼叫訊框組成的呼叫樹,包含了每一B呼叫訊框和巢狀的A呼叫訊框,每一訊框均含有相應B呼叫產生時的k值副本。試圖在紙上演算出最後結果可能是徒勞的,在原文中高德納推測答案是-121,但正確的結果是-67, 附錄里有一篇由查爾斯H林賽審校的論文,其中包含一個帶有不同初始值的表格。 對於較大的[來源請求]k[來源請求]值,即使是現代電腦也會很快用完所有堆疊空間。

(k) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
A 1 0 -2 0 1 0 1 -1 -10 -30 -67 -138 -291 -642 -1446 -3250 -7244 -16065 -35601 -78985 -175416 -389695 -865609 -1922362 -4268854 -9479595

說明

[編輯]

在這個程式中,有三個ALGOL特性是編譯器中比較難正確實現的:

  1. 巢狀函式定義 :由於B 是在A 的函式體中實現,B 的函式體就有權限訪問A 的局部變數——例如最明顯的k 值,以及x1,x2,x3,x4,x5 。這對於ALGOL的後繼語言Pascal來說是非常簡單的,但在其他主要的ALGOL後繼語言是不可能實現的,例如C語言(但C語言具有取位址運算子&,可以向任意函式傳遞局部變數的位址,所以這是可以換種方式實現的)
  2. 函式參照 :在遞迴函式呼叫A(k,B,x1,x2,x3,x4)中的B 不是對B的呼叫,而是對B 的參照,只有像x4x5 一樣出現在語句A:=x4+x5中時才會真正呼叫B 。與前述迥異,這在C語言中是非常容易實現的,但在多個Pascal的實作版本中是不可能完成的(儘管ISO 7185標準已經支援函式作為參數)。其實只需要將參照的函式集在前文中聲明(此例中只有B),就可以變相實現了。
  3. 常數/函式的二元論 :A中的X1-X5 可能是數值常數或函式 B 的參照,為此,表達式 X4 + X5必須能夠處理這兩種情況,猶如x4X5的 被實際參數所取代一樣。( 按名呼叫 )。相比起動態型別語言,對於靜態型別語言而言這可能是更棘手的問題。標準的解決辦法是對A 函式的主呼叫重新解釋 常數1,0,-1,把它們看作是返回1、0、-1的不帶參數的函式 。

所有這些都不是該測試的主要意義,他們僅僅是測試的先決條件。該測試的真正意義在於能否將對B函式的另一個參照定位到正確的B的實例上去——另一個同樣能夠同樣訪問到本地的A的參照。一個所謂的「男孩」編譯器,(可能)會使得B總是訪問最頂層的A呼叫訊框。

參見

[編輯]

外部連結

[編輯]

參考文獻(略)

[編輯]
  1. ^ Donald Knuth. Man or boy?. July 1964 [Dec 25, 2009]. (原始內容存檔於2021-02-23).