Separating the Men from the Boys, Knuth Style

mgcadmin 08-05-2025

When I set out developing my own language I had a few milestones I had in mind. One goal I've had for quite some time, was to be able to pass Knuth's "Man or Boy test". I'm happy to say, that as of this afternoon, Owlscript can successfully execute knuths test program, arriving at the correct output! Well, the first 15 values at least, then it runs out of stack space - but thats to be expected.

To mark the occasion I figured I would write a post about some of the difficulties faced in getting my interpreter to properly run the test, and how I addressed them. But first, here is the code for Knuths man or boy test implemented in owlscript:

def C(var i) {
    return &() -> i;
}

def A(var k, var x1, var x2, var x3, var x4, var x5) {
    def B() {
        k--;
        return A(k, B, x1, x2, x3, x4);
    }
    if (k <= 0) {
        return x4()+x5();
    }
    return B();
}

def main() {
    let i := 0;
    while (i < 15) {
        print i + ": ";
        println A(i, C(1), C(-1), C(-1), C(1), C(0));
        i := i + 1;
    }
}

And the output:

max@MaxGorenLaptop:~/owlscript$ owlscript manorboy.owl
0: 1
1: 0
2: -2
3: 0
4: 1
5: 0
6: 1
7: -1
8: -10
9: -30
10: -67
11: -138
12: -291
13: -642
14: -1446

I suppose before we get too much further I should talk a little bit about the actual test, and what is supposed to accomplish.

Knuth's Man Or Boy Test

In the early 1960s, as various implementations of the Algol 60 language came into existence it became clear that some of algol's more novel features were not trivial to implement, leading to compilers of varying quality. Knuth termed those which were correctly implemented "man compilers", while dubbing those of a more dubious quality "boy compilers". It was a different time.

To quote Knuth himself:

"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." - Donald Knuth, 1964

His original implementation in Algol 60 was thus:

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

You might take a look at that snippet of code and think "huh? THAT is the code that is so hard to properly execute?" and at first glance you'd be excused for thinking so. However, hidden in that dozen lines of code is enough complexity to give any interpreter or compiler a good thrashing. 

It should be remembered that while we take things like being able to implement recursive algorithms for granted, when algol was invented it was the first high level language to support doing so. And the same can be said for nested procedures, non local references, procedure references, call by name parameters, and the list goes on. 

Challenges

Implementing an interpreter capable of computing knuths procedure requires either support for call by name, or some way of emulating its behavior. In chapter 3 of The Structure and Interpretation of Computer Programs it is disclosed that scheme's keywords delay and force used for implementing delayed evaluation, a form of call by name, is syntactic sugar for wrapping a value in a lambda which returns that value when evaluated:

(define delay (lambda (x) (lambda (x) x)))
(define force (lambda (x xs) (apply x xs)))

Owlscript doesn't have call by name, but it does have anonymous functions and closures, and so the wrapping is done explicitly:

def C(var i) {
    return &() -> i;
}

println A(i, C(1), C(-1), C(-1), C(1), C(0));

Owlscript was designed with first class functions in mind, so procedure references was less of a challenge and more an implementation detail. By supporting first class functions, nested procedures become easily implemented as well, the complicating factor being if you want to allow those procedures to outlive their enclosing procedures (closures).

This is where a particularly cool datastructure comes into play: the cactus stack.

---