C++: Man Or Boy Test

Background: The man or boy test was proposed by computer scientist Donald Knuth as a means of evaluating implementations of the ALGOL 60 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

Task: Imitate Knuth’s example in Algol 60 in another language, as far as possible.

Details: Local variables of routines are often kept in activation records (also call frames). In many languages, these records are kept on a call stack. In Algol (and e.g. in Smalltalk), they are allocated on a heap instead. Hence it is possible to pass references to routines that still can use and update variables from their call environment, even if the routine where those variables are declared already returned. This difference in implementations is sometimes called the Funarg Problem.

In Knuth’s example, each call to A allocates an activation record for the variable A. When B is called from A, any access to k now refers to this activation record. Now B in turn calls A, but passes itself as an argument. This argument remains bound to the activation record. This call to A also “shifts” the variables x_i by one place, so eventually the argument B (still bound to its particular activation record) will appear as x4 or x5 in a call to A. If this happens when the expression x4 + x5 is evaluated, then this will again call B, which in turn will update k in the activation record it was originally bound to. As this activation record is shared with other instances of calls to A and B, it will influence the whole computation.

So all the example does is to set up a convoluted calling structure, where updates to k can influence the behavior in completely different parts of the call tree.

Knuth used this to test the correctness of the compiler, but one can of course also use it to test that other languages can emulate the Algol behavior correctly. If the handling of activation records is correct, the computed value will be −67.

Performance and Memory: Man or Boy is intense and can be pushed to challenge any machine. Memory (both stack and heap) not CPU time is the constraining resource as the recursion creates a proliferation activation records which will quickly exhaust memory and present itself through a stack error. Each language may have ways of adjusting the amount of memory or increasing the recursion depth. Optionally, show how you would make such adjustments.

works with GCC

Uses “shared_ptr” smart pointers from Boost / TR1 to automatically deallocate objects. Since we have an object which needs to pass a pointer to itself to another function, we need to use “enable_shared_from_this”.

#include <iostream>
#include <tr1/memory>
using std::tr1::shared_ptr;
using std::tr1::enable_shared_from_this;

struct Arg {
	virtual int run() = 0;
	virtual ~Arg() { };
};

int A(int, shared_ptr<Arg>, shared_ptr<Arg>, shared_ptr<Arg>,
shared_ptr<Arg>, shared_ptr<Arg>);

class B : public Arg, public enable_shared_from_this<B> {
private:
	int k;
	const shared_ptr<Arg> x1, x2, x3, x4;

public:
	B(int _k, shared_ptr<Arg> _x1, shared_ptr<Arg> _x2, shared_ptr<Arg> _x3,
	shared_ptr<Arg> _x4)
	: k(_k), x1(_x1), x2(_x2), x3(_x3), x4(_x4) { }
	int run() {
		return A(--k, shared_from_this(), x1, x2, x3, x4);
	}
};

class Const : public Arg {
private:
	const int x;
public:
	Const(int _x) : x(_x) { }
	int run () { return x; }
};

int A(int k, shared_ptr<Arg> x1, shared_ptr<Arg> x2, shared_ptr<Arg> x3,
shared_ptr<Arg> x4, shared_ptr<Arg> x5) {
	if (k <= 0)
	return x4->run() + x5->run();
	else {
		shared_ptr<Arg> b(new B(k, x1, x2, x3, x4));
		return b->run();
	}
}

int main() {
	std::cout << A(10, shared_ptr<Arg>(new Const(1)),
	shared_ptr<Arg>(new Const(-1)),
	shared_ptr<Arg>(new Const(-1)),
	shared_ptr<Arg>(new Const(1)),
	shared_ptr<Arg>(new Const(0))) << std::endl;
	return 0;
}

Works with: C++11

uses anonymous functions. Tested with g++ version 4.5 and Visual C++ version 16 (Windows SDK 7.1):

#include <functional>
#include <iostream>

typedef std::function<int()> F;

static int A(int k, const F &x1, const F &x2, const F &x3, const F &x4, const F &x5)
{
	F B = [=, &k, &B]
	{
		return A(--k, B, x1, x2, x3, x4);
	};

	return k <= 0 ? x4() + x5() : B();
}

static F L(int n)
{
	return [n] { return n; };
}

int main()
{
	std::cout << A(10, L(1), L(-1), L(-1), L(1), L(0)) << std::endl;
	return 0;
}

Works with: TR1

uses TR1 without C++11.

#include <tr1/functional>
#include <iostream>

typedef std::tr1::function<int()> F;

static int A(int k, const F &x1, const F &x2, const F &x3, const F &x4, const F &x5);

struct B_class {
	int &k;
	const F x1, x2, x3, x4;
	B_class(int &_k, const F &_x1, const F &_x2, const F &_x3, const F &_x4) :
	k(_k), x1(_x1), x2(_x2), x3(_x3), x4(_x4) { }
	int operator()() const { return A(--k, *this, x1, x2, x3, x4); }
};

static int A(int k, const F &x1, const F &x2, const F &x3, const F &x4, const F &x5)
{
	F B = B_class(k, x1, x2, x3, x4);
	return k <= 0 ? x4() + x5() : B();
}

struct L {
	const int n;
	L(int _n) : n(_n) { }
	int operator()() const { return n; }
};

int main()
{
	std::cout << A(10, L(1), L(-1), L(-1), L(1), L(0)) << std::endl;
	return 0;
}