編譯器遞歸測試

男人抑或男孩測試，由電腦科學家高德納在1964年提出，是用來評價ALGOL 60程式語言實現的一個手段。該測試的目的是區分出編譯器能否正確實現「遞歸和非局部變量」。

## ALGOL語言表述

Donald Knuth在1964年發表的算法語言ALGOL 60代碼：

```pascal
begin
    real procedure A(k, x1, x2, x3, x4, x5);
    value k; integer k;
    real x1, x2, x3, x4, x5;
    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(1, A(10, 1, -1, -1, 1, 0))
end
```

執行這程序所創建的調用棧由函數`A`和它所包含的函數`B`互遞歸調用產生的二者的調用幀構成，每個函數`B`的調用幀都非局部變量一個函數`A`調用幀，每個函數`A`的調用幀都在傳遞給它的實際參數列表中，接受`0`至`5`個函數參數問題`B`，並且都含有自己的局部變量`k`，它在非局部引用這個函數`A`的函數`B`每次被調用時變更。

Charles H. Lindsey在1988年將這個測試改寫為ALGOL 68代碼：

```bash
BEGIN 
    PROC a = (INT k, PROC INT x1, x2, x3, x4, x5) INT:
    BEGIN
        LOC INT kk := k;
        PROC b = INT:
        BEGIN
            kk -:= 1;
            a(kk, b, x1, x2, x3, x4)
        END;
        IF kk <= 0 THEN x4 + x5 ELSE b FI
    END;
    print((whole(a(10, INT:1, INT:-1, INT:-1, INT:1, INT:0), 0), newline))
END
```

Lindsey採用了W. H. Burge在1964年虛構的「ALGOL Men」，將這個測試描述為：過程`b`的眾多化身被創建於在眾多的環境中，每個化身都能夠遞減創建它的那個環境中的特定`kk`。

## 解說

在這個程序中用到的三個ALGOL 60特徵是編譯器中早年間比較難以正確實現的：

- 嵌套函數定義：函數`B`被嵌套定義於函數`A`的局部上下文之中，故而函數`B`可稱為嵌套函數，它的函數主體能夠訪問非局部變量的函數`A`的局部變量，例如最明顯的傳值形式參數`k`，以及傳名形式參數`x1`、`x2`、`x3`、`x4`和`x5`。嵌套函數定義對於Pascal來說是直截了當的，而對於C語言是不可能的，但是C語言可以通過取地址運算符`&`而在函數之間傳遞局部變量的地址。
- 函數參數：在函數`B`中的互遞歸調用`A(k, B, x1, x2, x3, x4)`的實際參數列表中的`B`，不是對函數`B`的調用，而是函數參數問題`B`，即頭等函數`B`的名字。接受了函數參數`B`的函數`A`通常被稱為高階函數，它會在自己的局部變量`k`大於等於`0`之時調用函數`B`。函數參數在支持過程參數的標準Pascal（ISO 7185）中是直截了當的，在C語言中可以採用函數指針對函數加以引用。
- 常量與函數的聯合：向函數`A`中的形式參數`x1`至`x5`傳遞的實際參數，是常量數值與函數參數`B`的聯合，函數`A`中的表達式`x4 + x5`必須能夠處理這兩種情況，直到此時函數`A`的形式參數`x4`和`x5`才會被替代為常量數值或者調用函數`B`的結果值。相比起動態類型語言，對於靜態類型語言而言這可能是更大的問題，標準的解決辦法比如前面ALGOL 68實現所採用的，是將對函數`A`的最頂層調用中的常量`1`、`0`和`-1`重新表述為返回這些值的Thunk。

所有這些都不是該測試的主要意義，它們只是測試的先決條件。該測試的真正意義在於，能否將不同的函數參數`B`定位到正確的函數`B`的實例，就是說執行一個函數參數`B`要與給定這個參數的函數`B`，訪問相同的函數`A`的局部符號。比如說一個「男孩」編譯器，會使得函數`B`總是訪問最頂層的函數`A`調用幀。

試圖在紙上演算出最後結果可能是徒勞的，高德納在最初文章中推測答案是`-121`，但正確的結果是`-67`。下面的援引OEIS A132343的表格，列出不同`k`值的結果及其遞推關係：

k｜0｜1｜2｜3｜4｜5｜6｜7｜8｜9｜10｜11｜n (n≥10)

A(k)｜1｜0｜-2｜0｜1｜0｜1｜-1｜-10｜-30｜-67｜1-6×(-1)+11×(-10)-10×(-30)+5×(-67) = -138｜A(n-5)-6×A(n-4)+11×A(n-3)-10×A(n-2)+5×A(n-1)

## Scheme語言表述

下面是用函數式程式語言Scheme實現這個測試的代碼：

```Scheme
(define (A k x1 x2 x3 x4 x5)
  (define (B)
    (set! k (- k 1))
    (A k B x1 x2 x3 x4))
  (if (<= k 0)
    (+ (x4) (x5))
    (B)))

(A 10 (lambda () 1) (lambda () -1) (lambda () -1) (lambda () 1) (lambda () 0))
```

Scheme支持詞法作用域和嵌套函數定義，並且支持頭等函數，不需要對傳遞給函數`A`的實際參數列表中的函數參數問題`B`加以LISP式函數引述`#'`。這裡將對函數`A`的頂層調用中的常量`1`、`0`和`-1`表示為返回這些值的沒有參數的匿名函數、和，從而使得傳遞給函數`A`中的形式參數`x1`到`x5`都是函數即匿名函數或頭等函數`B`，並且將ALGOL中`x4`與`x5`的加法，直接寫為這裡的函數調用`(x4)`與`(x5)`的加法。

## 變體

Donald Knuth在1964年對這個測試應有結果進行了更正，並提出了一個變體：`A(k, x<sub>1</sub>, x<sub>2</sub>, x<sub>3</sub>, x<sub>4</sub>, x<sub>5</sub>) = c<sub>1</sub>×x<sub>1</sub> + c<sub>2</sub>×x<sub>2</sub> + c<sub>3</sub>×x<sub>3</sub> + c<sub>4</sub>×x<sub>4</sub> + c<sub>5</sub>×x<sub>5</sub>`，下表列出了其中的係數：

k｜c1(k)｜c2(k)｜c3(k)｜c4(k)｜c5(k)

0｜0｜0｜0｜1｜1

1｜0｜0｜1｜1｜0

2｜0｜1｜1｜0｜0

3｜1｜1｜0｜0｜0

4｜2｜1｜0｜0｜0

5｜3｜2｜1｜0｜0

6｜5｜3｜3｜2｜0

7｜8｜6｜9｜6｜0

8｜14｜15｜22｜13｜0

9｜29｜37｜48｜26｜0

10｜66｜85｜102｜54｜0

對於`k >= 6`有著：

- `c<sub>1</sub>(k) = c<sub>1</sub>(k-1) + c<sub>2</sub>(k-1)`
- `c<sub>2</sub>(k) = c<sub>2</sub>(k-1) + c<sub>3</sub>(k-1)`
- `c<sub>3</sub>(k) = c<sub>3</sub>(k-1) + c<sub>4</sub>(k-1) + c<sub>1</sub>(k-1) - 1`
- `c<sub>4</sub>(k) = c<sub>4</sub>(k-1) + c<sub>1</sub>(k-1) - 1`
- `c<sub>5</sub>(k) = 0`

下面將這個變體表述為ALGOL 68代碼：

```bash
BEGIN
    PROC a = (INT k, PROC VOID x1, x2, x3, x4, x5) VOID:
    BEGIN
        INT kk := k;
        PROC b = VOID:
        BEGIN
            kk -:= 1;
            a(kk, b, x1, x2, x3, x4)
        END;
        IF kk <= 0 THEN x4; x5 ELSE b FI
    END;
    [1:5] INT c := (0, 0, 0, 0, 0);
    PROC d = (INT i) VOID: c[i] +:= 1;
    a(10, VOID:d(1), VOID:d(2), VOID:d(3), VOID:d(4), VOID:d(5));
    print((whole(c[1] - c[2] - c[3] + c[4], 0), newline))
END
```

這裡的`VOID:d(1)`至`VOID:d(5)`都是過程`d`的部份應用後形成的Thunk。