维基百科

编译器递归测试

编译器递归测试，是一种由计算机科学家高德纳提出，用来评价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" - 高德纳[1].

（目前只有少数的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调用帧。

参见

外部链接

参考文献（略）

  1. ^ Donald Knuth. Man or boy?. July 1964 [Dec 25, 2009]. （原始内容存档于2021-02-23）. 
检索自“https://zh.wikipedia.org/w/index.php?title=编译器递归测试&oldid=81777273”