编译器递归测试

此條目翻譯品質不佳。 (2017年3月25日) 翻譯者可能不熟悉中文或原文語言，也可能使用了機器翻譯。請協助翻譯本條目或重新編寫，并注意避免翻译腔的问题。明顯拙劣的翻譯請改掛{{d|G13}}提交刪除。

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

目前只有少数的ALGOL 60解释器能够正确处理递归和非本地引用，所以我认为設計一段小程序去测试编译器的递归功能是有价值的。因此我写了這段简单的代码，以便区分“年幼的”编译器和“成熟的”编译器。 - 高德纳^[1]

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

这将形成一棵由B调用帧组成的调用树，包含了每一B调用帧和嵌套的A调用帧，每一帧均含有相应B调用产生时的k值副本。试图在纸上演算出最后结果可能是徒劳的，在原文中高德纳推测答案是-121，但正确的结果是-67， 附录里有一篇由查尔斯H林赛审校的论文，其中包含一个带有不同初始值的表格。 对于较大的^{[來源請求]}k^{[來源請求]}值，即使是现代计算机也会很快用完所有堆栈空间。

在这个程序中，有三个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])
• 男人或男孩测试 （页面存档备份，存于互联网档案馆） 多种编程语言的例子

1. ^ Donald Knuth. Man or boy?. July 1964 [Dec 25, 2009]. （原始内容存档于2021-02-23）. 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".