編譯器遞歸測試

編譯器遞歸測試，是一種由電腦科學家高德納提出，用來評價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 的參照，只有像x4 或x5 一樣出現在陳述式A:=x4+x5中時才會真正呼叫B 。與前述迥異，這在C語言中是非常容易實現的，但在多個Pascal的實作版本中是不可能完成的（儘管ISO 7185標準已經支援函數作為參數）。其實只需要將參照的函數集在前文中聲明（此例中只有B），就可以變相實現了。
3. 常數/函數的二元論 ：A中的X1-X5 可能是數值常數或函數 B 的參照，為此，表達式 X4 + X5必須能夠處理這兩種情況，猶如x4 和X5的 被實際參數所取代一樣。（ 按名呼叫 ）。相比起動態型別語言，對於靜態型別語言而言這可能是更棘手的問題。標準的解決辦法是對A 函數的主呼叫重新解釋 常數1，0，-1，把它們看作是返回1、0、-1的不帶參數的函數 。

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

參見

• Jensen's Device

外部連結

• [1] （頁面存檔備份，存於互聯網檔案館）The Man or Boy Test as published in the ALGOL Bulletin 17, p7 (available at [2])
• 男人或男孩測試 （頁面存檔備份，存於互聯網檔案館） 多種程式語言的例子

參考文獻（略）

1. Donald Knuth. Man or boy?. July 1964 [Dec 25, 2009]. （原始內容存檔於2021-02-23）.