男人抑或男孩测试，由计算机科学家高德纳在1964年提出，是用來评价ALGOL 60编程语言实现的一个手段。该测试的目的是区分出编译器能否正确实现“递归和”。
ALGOL语言表述
Donald Knuth在1964年发表的算法语言ALGOL 60代码：
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
执行这程序所创建的调用栈由函数A和它所包含的函数B互递归调用产生的二者的调用帧构成，每个函数B的调用帧都一个函数A调用帧，每个函数A的调用帧都在传递给它的实际参数列表中，接受0至5个B，并且都含有自己的局部变量k，它在非局部引用这个函数A的函数B每次被调用时变更。
在1988年将这个测试改写为ALGOL 68代码：
BEGIN
PROC a = (INT k, PROC INT x1, x2, x3, x4, x5) INT:
BEGIN
LOC INT kk := k;
PROC b = INT:
BEGIN
kk -:= 1;
a(kk, b, x1, x2, x3, x4)
END;
IF kk
Lindsey采用了W. H. Burge在1964年虚构的“ALGOL Men”，将这个测试描述为：过程b的众多化身被创建于在众多的环境中，每个化身都能够递减创建它的那个环境中的特定kk。
解说
在这个程序中用到的三个ALGOL 60特征是编译器中早年间比较难以正确实现的：
#嵌套函数定义：函数B被嵌套定义于函数A的局部上下文之中，故而函数B可称为，它的函数主体能够访问的函数A的局部变量，例如最明显的传值形式参数k，以及传名形式参数x1、x2、x3、x4和x5。嵌套函数定义对于Pascal来说是直截了当的，而对于C语言是不可能的，但是C语言可以通过取地址运算符&而在函数之间传递局部变量的地址。
#函数参数：在函数B中的互递归调用A(k, B, x1, x2, x3, x4)的实际参数列表中的B，不是对函数B的调用，而是B，即头等函数B的名字。接受了函数参数B的函数A通常被称为高阶函数，它会在自己的局部变量k大于等于0之时调用函数B。函数参数在支持的标准Pascal（ISO 7185）中是直截了当的，在C语言中可以采用函数指针对函数加以引用。
#常量与函数的联合：向函数A中的形式参数x1至x5传递的实际参数，是常量数值与函数参数B的联合，函数A中的表达式x4 + x5必须能够处理这两种情况，直到此时函数A的形式参数x4和x5才会被替代为常量数值或者调用函数B的结果值。相比起动态类型语言，对于静态类型语言而言这可能是更大的问题，标准的解决办法比如前面ALGOL 68实现所采用的，是将对函数A的最顶层调用中的常量1、0和-1重新表述为返回这些值的。
所有这些都不是该测试的主要意义，它们只是测试的先决条件。该测试的真正意义在于，能否将不同的函数参数B定位到正确的函数B的实例，就是说执行一个函数参数B要与给定这个参数的函数B，访问相同的函数A的局部符号。比如说一个“男孩”编译器，会使得函数B总是访问最顶层的函数A调用帧。
试图在纸上演算出最后结果可能是徒劳的，高德纳在最初文章中推测答案是-121，但正确的结果是-67。下面的援引OEIS 的表格，列出不同k值的结果及其递推关系：
Scheme语言表述
下面是用函数式编程语言Scheme实现这个测试的代码：
(define (A k x1 x2 x3 x4 x5)
(define (B)
(set! k (- k 1))
(A k B x1 x2 x3 x4))
(if (
Scheme支持词法作用域和定义，并且支持头等函数，不需要对传递给函数A的实际参数列表中的B加以LISP式函数引述#'。这里将对函数A的顶层调用中的常量1、0和-1表示为返回这些值的没有参数的匿名函数、和，从而使得传递给函数A中的形式参数x1到x5都是函数即匿名函数或头等函数B，并且将ALGOL中x4与x5的加法，直接写为这里的函数调用(x4)与(x5)的加法。
变体
Donald Knuth在1964年对这个测试应有结果进行了更正，并提出了一个变体：A(k, x1, x2, x3, x4, x5) = c1×x1 + c2×x2 + c3×x3 + c4×x4 + c5×x5，下表列出了其中的系数：
*c1(k) = c1(k-1) + c2(k-1)
*c2(k) = c2(k-1) + c3(k-1)
*c3(k) = c3(k-1) + c4(k-1) + c1(k-1) - 1
*c4(k) = c4(k-1) + c1(k-1) - 1
*c5(k) = 0
下面将这个变体表述为ALGOL 68代码：
BEGIN
PROC a = (INT k, PROC VOID x1, x2, x3, x4, x5) VOID:
BEGIN
INT kk := k;
PROC b = VOID:
BEGIN
kk -:= 1;
a(kk, b, x1, x2, x3, x4)
END;
IF kk
这里的VOID:d(1)至VOID:d(5)都是过程d的部份应用后形成的。
参见
*
*男人抑或男孩测试的dc实现
引用
外部链接
*
*[http://rosettacode.org/wiki/Man_or_boy_test 男人抑或男孩测试] 多种编程语言的例子
评论 (0)