编译器递归测试

男人抑或男孩测试，由计算机科学家高德纳在1964年提出，是用來评价ALGOL 60编程语言实现的一个手段。该测试的目的是区分出编译器能否正确实现“递归和”。 

ALGOL语言表述
Donald Knuth在1964年发表的算法语言ALGOL 60代码：
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每次被调用时变更。

在1988年将这个测试改写为ALGOL 68代码：
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重新表述为返回这些值的。

所有这些都不是该测试的主要意义，它们只是测试的先决条件。该测试的真正意义在于，能否将不同的函数参数B定位到正确的函数B的实例，就是说执行一个函数参数B要与给定这个参数的函数B，访问相同的函数A的局部符号。比如说一个“男孩”编译器，会使得函数B总是访问最顶层的函数A调用帧。

试图在纸上演算出最后结果可能是徒劳的，高德纳在最初文章中推测答案是-121，但正确的结果是-67。下面的援引OEIS 的表格，列出不同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实现这个测试的代码：
(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, x1, x2, x3, x4, x5) = c1×x1 + c2×x2 + c3×x3 + c4×x4 + c5×x5，下表列出了其中的系数：

 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有着：
c1(k) = c1(k-1) + c2(k-1)
c2(k) = c2(k-1) + c3(k-1)
c3(k) = c3(k-1) + c4(k-1) + c1(k-1) - 1
c4(k) = c4(k-1) + c1(k-1) - 1
c5(k) = 0

下面将这个变体表述为ALGOL 68代码：
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的部份应用后形成的。

参见

男人抑或男孩测试的dc实现

引用

外部链接

男人抑或男孩测试  多种编程语言的例子

Category:带有ALGOL 60代码示例的条目
Category:编译原理
Category:高德纳