編譯器遞迴測試
![本頁使用了標題或全文手工轉換](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
此條目翻譯品質不佳。 (2017年3月25日) |
編譯器遞迴測試,是一種由電腦科學家高德納提出,用來評價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特性是編譯器中比較難正確實現的:
- 巢狀函式定義 :由於B 是在A 的函式體中實現,B 的函式體就有權限訪問A 的局部變數——例如最明顯的k 值,以及x1,x2,x3,x4,x5 。這對於ALGOL的後繼語言Pascal來說是非常簡單的,但在其他主要的ALGOL後繼語言是不可能實現的,例如C語言(但C語言具有取位址運算子&,可以向任意函式傳遞局部變數的位址,所以這是可以換種方式實現的)
- 函式參照 :在遞迴函式呼叫A(k,B,x1,x2,x3,x4)中的B 不是對B的呼叫,而是對B 的參照,只有像x4 或x5 一樣出現在語句A:=x4+x5中時才會真正呼叫B 。與前述迥異,這在C語言中是非常容易實現的,但在多個Pascal的實作版本中是不可能完成的(儘管ISO 7185標準已經支援函式作為參數)。其實只需要將參照的函式集在前文中聲明(此例中只有B),就可以變相實現了。
- 常數/函式的二元論 :A中的X1-X5 可能是數值常數或函式 B 的參照,為此,表達式 X4 + X5必須能夠處理這兩種情況,猶如x4 和X5的 被實際參數所取代一樣。( 按名呼叫 )。相比起動態型別語言,對於靜態型別語言而言這可能是更棘手的問題。標準的解決辦法是對A 函式的主呼叫重新解釋 常數1,0,-1,把它們看作是返回1、0、-1的不帶參數的函式 。
所有這些都不是該測試的主要意義,他們僅僅是測試的先決條件。該測試的真正意義在於能否將對B函式的另一個參照定位到正確的B的實例上去——另一個同樣能夠同樣訪問到本地的A的參照。一個所謂的「男孩」編譯器,(可能)會使得B總是訪問最頂層的A呼叫訊框。
參見
[編輯]外部連結
[編輯]- [1] (頁面存檔備份,存於網際網路檔案館)The Man or Boy Test as published in the ALGOL Bulletin 17, p7 (available at [2])
- 男人或男孩測試 (頁面存檔備份,存於網際網路檔案館) 多種程式語言的例子
參考文獻(略)
[編輯]- ^ Donald Knuth. Man or boy?. July 1964 [Dec 25, 2009]. (原始內容存檔於2021-02-23).
|
|