編譯器遞歸測試

編譯器遞歸測試，是一種由計算機科學家高德納提出，用來評價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" - 高德納.

（目前只有少數的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])
• 男人或男孩測試 （頁面存檔備份，存於網際網路檔案館） 多種編程語言的例子