编译器递归测试

编译器递归测试，是一種由计算机科学家高德纳提出，用來评价ALGOL 60编程语言实现的手段。该测试的目的是识别出能够正确实现“递归和非本地引用”的编译器。 

（目前只有少数的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值，即使是现代计算机也会很快用完所有堆栈空间。

说明

在这个程序中，有三个ALGOL特性是编译器中比较难正确实现的：
嵌套函数定义  ：由于B 是在A 的函数体中实现，B 的函数体就有权限访问A 的局部变量——例如最明显的k 值，以及x1,x2,x3,x4,x5 。这对于ALGOL的后继语言Pascal来说是非常简单的，但在其他主要的ALGOL后继语言是不可能实现的，例如C语言（但C语言具有取地址操作符&，可以向任意函数传递局部变量的地址，所以这是可以换种方式实现的）
函数引用  ：在递归函数调用A(k,B,x1,x2,x3,x4)中的B 不是对B的调用，而是对B 的引用，只有像x4 或x5 一样出现在语句A:=x4+x5中时才会真正调用B 。与前述迥异，这在C语言中是非常容易实现的，但在多个Pascal的實作版本中是不可能完成的（尽管ISO 7185标准已经支持函数作为参数）。其实只需要将引用的函数集在前文中声明（此例中只有B），就可以变相实现了。
常数/函数的二元论  ：A中的X1-X5 可能是数值常量或函数  B  的引用，为此，表达式 X4 + X5必须能够处理这两种情况，犹如x4 和X5的 被实际参数所取代一样。（ 按名调用 ）。相比起动态类型语言，对于静态类型语言而言这可能是更棘手的问题。标准的解决办法是对A 函数的主调用重新解释 常数1，0，-1，把它们看作是返回1、0、-1的不带参数的函数 。

所有这些都不是该测试的主要意义，他们仅仅是测试的先决条件。该测试的真正意义在于能否将对B函数的另一个引用定位到正确的B的实例上去——另一个同样能够同样访问到本地的A的引用。一个所谓的“男孩”编译器，（可能）会使得B总是访问最顶层的A调用帧。

参见
Jensen's Device

外部链接
 The Man or Boy Test as published in the ALGOL Bulletin 17, p7 (available at [2])
男人或男孩测试  多种编程语言的例子

参考文献（略）

带有ALGOL 60代码示例的条目
编译器理论
高德纳