编译器递归测试

男人抑或男孩测试，由计算机科学家高德纳在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。