Problem Statement

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. 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 xi 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. The table below shows the result, call depths, and total calls for a range of k:

Let's start with the solution:

def a(k, x1, x2, x3, x4, x5)
  b = uninitialized -> typeof(k)
  b = ->() { k -= 1; a(k, b, x1, x2, x3, x4) }
  k <= 0 ? x4.call + x5.call : b.call
end

puts a(10, -> {1}, -> {-1}, -> {-1}, -> {1}, -> {0})