Friday 7 August 2009

Man or Boy Test

I have written the following simple routine, which may separate the 'man-compilers' from the 'boy-compilers'
— Donald Knuth

The Man or Boy Test was created to beat Algol 60 compilers into submission as at the time there were apparently few compilers which implemented recursion and non-local references properly.

Translating the code into Clojure proved pretty challenging!

This can be compared against the Lisp version on Rosetta Code. Implementing this required finding letfn which allows you do declare local functions that can refer to themselves (e.g. recursive).

The local function b refers to itself. This torturous structure means that b will appear as all the positions of x1 to x5 arguments during evaluation. b can only be evaluated when it is in position x4 or x5. At this point, the evaluation of b changes the variable k which should be reflected in the recursive call that follows AND any further evaluation within that call frame.

For this reason, k needs to be mutable, hence it's an atom. The first 16 values are shown below.

user> (map man-or-boy (range 16))
  (1 0 -2 0 1 0 1 -1 -10 -30 -67 -138 -291 -642 -1446 -3250)

Now for the 17th value the stack overflows. I can't quite work out how to avoid that (yet).