编译器递归测试

编译器递归测试,是一种由电脑科学家高德纳提出,用来评价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 的引用,只有像x4x5 一样出现在语句A:=x4+x5中时才会真正调用B 。与前述迥异,这在C语言中是非常容易实现的,但在多个Pascal的实现版本中是不可能完成的(尽管ISO 7185标准已经支持函数作为参数)。其实只需要将引用的函数集在前文中声明(此例中只有B),就可以变相实现了。
  3. 常数/函数的二元论 :A中的X1-X5 可能是数值常量或函数 B 的引用,为此,表达式 X4 + X5必须能够处理这两种情况,犹如x4X5的 被实际参数所取代一样。( 按名调用 )。相比起动态类型语言,对于静态类型语言而言这可能是更棘手的问题。标准的解决办法是对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).