编译器递归测试

编译器递归测试，是一种由计算机科学家高德纳提出，用来评价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])
• 男人或男孩测试 （页面存档备份，存于互联网档案馆） 多种编程语言的例子