### Tue, 17 Nov 2009

#### DDC : Man or Boy?

Computer scientist Donald Knuth came up with something he called the Man or Boy Test as a way of evaluating implementations of the ALGOL60 language (standardized in 1963) to distinguish compilers that correctly implemented "recursion and non-local references" from those that did not. Knuth said:

"I have written the following simple routine, which may separate the 'man-compilers' from the 'boy-compilers'."

My first attempt at solving this problem in Disciple resulted in me raising bug #148 in the DDC bug tracker with the following code:

```
-- Compiler needs a little help inferring the types.
a :: Int -> a -> a -> a -> a -> a -> Int
a k x1 x2 x3 x4 x5
= do    b () = do { k := k - 1 ; a k b x1 x2 x3 x4 }
if k <= 0 then x4 () + x5 () else b ()

fn n = \() -> n

main ()  -- Function 'a' should return -67
= do    out = a 10 (fn 1) (fn -1) (fn -1) (fn 1) (fn 0)
if out /= -67
then println \$ "Output was " % show out % ". Should have been -67."
else println "Passed!"

```

Fiddling around with the problem a bit, I suddenly realised that the Disciple language has call-by-reference semantics by default (by way of contrast, the C programming language has default call-by-value semantics with optional call-by-reference semantics using pointers).

While chatting with Ben on IRC he suggested using a copy to create a local copy of the function parameter that gets mutated so that mutation doesn't change the value outside call frame.

Here are two correct solutions to the Man or Boy problem:

```
a0 :: Int -> a -> a -> a -> a -> a -> Int
a0 k x1 x2 x3 x4 x5
= do   b () = do { k := k - 1 ; a0 (copy k) b x1 x2 x3 x4 }
if k <= 0 then x4 () + x5 () else b ()

a1 :: Int -> a -> a -> a -> a -> a -> Int
a1 k x1 x2 x3 x4 x5
= do   m = copy k
b () = do { m := m - 1 ; a1 m b x1 x2 x3 x4 }
if k <= 0 then x4 () + x5 () else b ()

fn n = \() -> n

main ()
= do   out0 = a0 10 (fn 1) (fn -1) (fn -1) (fn 1) (fn 0)
out1 = a1 10 (fn 1) (fn -1) (fn -1) (fn 1) (fn 0)

println "All outputs below should be equal to -67."
println \$ "Output 0 : " % show out0
println \$ "Output 1 : " % show out1

```

Both of these Disciple solutions are significantly less complex than the equivalent Haskell solution.

While I have no problem with function parameters being passed by reference, I don't think its a good idea to have those parameters being mutable by default (ie with the values also changing in the calling function).

I need to play with this some more.

Posted at: 22:03 | Category: CodeHacking/DDC | Permalink