Man or boy test
The man or boy test was proposed by computer scientist Donald Knuth as a means of evaluating implementations of the programming language. The aim of the test was to distinguish compilers that correctly implemented "recursion and non-local references" from those that did not.
"I have written the following simple routine, which may separate the "man-compilers" from the "boy-compilers" - Donald Knuth"
ALGOL 60 - Knuth's example
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;
This creates a tree of B call frames that refer to each other and to the containing A call frames, each of which has its own copy of k that changes every time the associated B is called. Trying to work it through on paper is probably fruitless, but the correct answer is −67, despite the fact that in the original paper Knuth postulated it to be −121.
ALGOL 68
Charles H. Lindsey implemented the algorithm in ALGOL 68, and - as call by name is not necessary - the same algorithm can be implemented in many languages including Pascal and PL/I Ruby.
BEGIN
PROC a = (REAL in k, PROC REAL xl, x2, x3, x4, x5) REAL:
BEGIN
REAL k := in k;
PROC b = REAL:
BEGIN k := k - 1;
a(k, b, xl, x2, x3, x4)
END;
IF k<=0 THEN x4 + x5 ELSE b FI
END;
printf(($+2d.8d$, a(10, REAL:1, REAL:-1, REAL:-1, REAL:1, REAL:0)))
END
C
Even if closures are not available in a language, their effect can be simulated. This is what happens in the following C implementation:
/* man-or-boy.c */
#include <stdio.h>
#include <stdlib.h>
// --- thunks
typedef struct arg {
int (*fn)(struct arg*);
int *k;
struct arg *x1, *x2, *x3, *x4, *x5;
} ARG;
// --- lambdas
int f_1 (ARG* _) { return -1; }
int f0 (ARG* _) { return 0; }
int f1 (ARG* _) { return 1; }
// --- helper
int eval(ARG* a) { return a->fn(a); }
#define ARG(...) (&(ARG){ __VA_ARGS__ })
#define FUN(...) ARG(B,&k,__VA_ARGS__)
// --- functions
int B(ARG* a) {
int A(ARG*);
int k = *a->k -= 1;
return A( FUN(a,a->x1,a->x2,a->x3,a->x4) );
}
int A(ARG* a) {
return *a->k <= 0 ? eval(a->x4)+eval(a->x5) : B(a);
}
int main(int argc, char **argv) {
int k = argc == 2 ? strtol(argv[1],0,0) : 10;
printf("%d\n", A( FUN(ARG(f1),ARG(f_1),ARG(f_1),ARG(f1),ARG(f0)) ));
}
Haskell
Haskell is a pure language, so the impure effects of updating k must be wrapped in a state monad.
import Control.Monad.ST
import Data.STRef
type S s = ST s Integer
a :: Integer -> S s -> S s -> S s -> S s -> S s -> S s
a k x1 x2 x3 x4 x5 = a' where
a' | k <= 0 = do { x4' <- x4; x5' <- x5; return (x4' + x5') }
| otherwise = do { kr <- newSTRef k; b kr }
b kr = do
k <- readSTRef kr
let k' = k - 1
writeSTRef kr k'
a k' (b kr) x1 x2 x3 x4
run k =
runST (a k (return 1) (return (-1)) (return (-1)) (return 1) (return 0))
Lisp
Since Lisp does not have a full range of monads as in Haskell, the Lisp implementation uses setq; a purely functional implementation would be much more complicated:
(defun manOrBoy (x)
(manOrBoy-func x (lambda () 1) (lambda () -1)
(lambda () -1) (lambda () 1)
(lambda () 0)))
(defun manOrBoy-func (k-param x1 x2 x3 x4 x5)
(let*
((k k-param)
(b
(lambda ()
(progn
(setq k (- k 1))
(manOrBoy-func k b x1 x2 x3 x4)))))
(if (<= k 0)
(+ (funcall x4) (funcall x5))
(funcall b))))
Mathematica
This Mathematica code was derived from the Ruby example appearing below.
$RecursionLimit = 1665; (* anything less fails for k0 = 10 *)
a[k0_, x1_, x2_, x3_, x4_, x5_] := Module[{k, b },
k = k0;
b = (k--; a[k, b, x1, x2, x3, x4]) &;
If[k <= 0, x4[] + x5[], b[]]]
a[10, 1 &, -1 &, -1 &, 1 &, 0 &] (* => -67 *)
PL/I
morb: proc options (main) reorder;
dcl sysprint file;
put skip list(a((10), lambda1, lambda2, lambda3, lambda4, lambda5));
a: proc(k, x1, x2, x3, x4, x5) returns(fixed bin (31)) recursive;
dcl k fixed bin (31);
dcl (x1, x2, x3, x4, x5) entry returns(fixed bin (31));
b: proc returns(fixed bin(31)) recursive;
k = k - 1;
return(a((k), b, x1, x2, x3, x4));
end b;
if k <= 0 then
return(x4 + x5);
else
return(b);
end a;
lambda1: proc returns(fixed bin (31)); return(1); end lambda1;
lambda2: proc returns(fixed bin (31)); return(-1); end lambda2;
lambda3: proc returns(fixed bin (31)); return(-1); end lambda3;
lambda4: proc returns(fixed bin (31)); return(1); end lambda4;
lambda5: proc returns(fixed bin (31)); return(0); end lambda5;
end morb;
Ruby
Note: the lambda call can be replaced with Proc.new and still work.
def a(k, x1, x2, x3, x4, x5)
b = lambda { k -= 1; a(k, b, x1, x2, x3, x4) }
k <= 0 ? x4[] + x5[] : b[]
end
puts a(10, lambda {1}, lambda {-1}, lambda {-1}, lambda {1}, lambda {0})
Smalltalk
Number>>x1: x1 x2: x2 x3: x3 x4: x4 x5: x5
| b k |
k := self.
b := [ k := k - 1. k x1: b x2: x1 x3: x2 x4: x3 x5: x4 ].
^k <= 0 ifTrue: [ x4 value + x5 value ] ifFalse: b
10 x1: [1] x2: [-1] x3: [-1] x4: [1] x5: [0]