"Man or boy" test
Paolo Bonzini
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.
Here is the original ALGOL 60 program by Knuth:
begin
real procedure A (k, x1, x2, x3, x4, x5);
value k; integer k;
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 (A (10, 1, -1, -1, 1, 0));
end;
Here is a possibly more readable Smalltalk program (the only language
I know well that has all the requested features):
Integer>>manOrBoy
"Smalltalk primer: [1] is a lambda, in Haskell it would be a ()-
>Number"
^self x1: [1] x2: [-1] x3: [-1] x4: [1] x5: [0]
Integer>>x1: x1 x2: x2 x3: x3 x4: x4 x5: x5
| b k |
k := self.
"b is a closure, so it uses and modifies the value of k from the
enclosing environment"
b := [ k := k - 1. k x1: b x2: x1 x3: x2 x4: x3 x5: x4 ].
^k <= 0 ifTrue: [ x4 value + x5 value ] ifFalse: b
"Example: '10 manOrBoy' returns -67"
What could be an Haskell implementation of this thing???
Thanks in advance,
Paolo
Ingo Wechsung
This is hard to tell for people like me that are not familiar with
ALGOL calling conventions.
Paolo Bonzini
> ALGOL calling conventions.
That's why I also posted the Smalltalk version. Here is Lisp,
but it uses setq. I figure in Haskell you'd use a State monad,
but there are probably other ways.
(defun manOrBoy (x)
(manOrBoy-func x (lambda () 1) (lambda () -1)
(lambda () -1) (lambda () 1)
(lambda () 0)))
(defun manOrBoy-func (k-param x1 x2 x3 x4 x5)
(let*
((k k-param)
(b
(lambda (f)
(lambda ()
(progn
(setq k (- k 1))
(manOrBoy-func k (funcall b b) x1 x2 x3 x4))))))
(if (<= k 0)
(+ (funcall x4) (funcall x5))
(funcall (funcall b b)))))
Ingo Wechsung
> > This is hard to tell for people like me that are not familiar with
> > ALGOL calling conventions.
>
> That's why I also posted the Smalltalk version.
This is like you first wrote chinese and now that I tell you I
understand chinese only partly, you post japanese.
> Here is Lisp,
And now you continue with Klingon :)
> I figure in Haskell you'd use a State monad,
Seems like overkill.
Let me try.
fA k x1 x2 x3 x4 x5 = let
fB = let
k' = k-1
in fA k' fB x1 x2 x3 x4
in if k < 0 then x4 + x5 else fB
Untested.
Vesa Karvonen
> On 9 Nov., 10:53, Paolo Bonzini <bonz...@gnu.org> wrote:
> > > This is hard to tell for people like me that are not familiar with
> > > ALGOL calling conventions.
> >
> > That's why I also posted the Smalltalk version.
> This is like you first wrote chinese and now that I tell you I
> understand chinese only partly, you post japanese.
> > Here is Lisp,
> And now you continue with Klingon :)
See the link for my SML translations:
http://lambda-the-ultimate.org/node/1309#comment-14814
> > I figure in Haskell you'd use a State monad,
> Seems like overkill.
I'm afraid you will need mutable refs to properly encode the Man or
Boy Test.
-Vesa Karvonen
Paul Rubin
> > I figure in Haskell you'd use a State monad,
> Seems like overkill.
> Let me try.
I don't think you can do it like that, without mutation. Algol 60
uses call-by-name and the test is of whether mutating the parameters
works properly.
Dirk Thierbach
>>From Wikipedia: 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.
For the appropriate values of "correctly" and that time.
> Here is the original ALGOL 60 program by Knuth:
>
> begin
> real procedure A (k, x1, x2, x3, x4, x5);
> value k; integer k;
> 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 (A (10, 1, -1, -1, 1, 0));
> end;
> What could be an Haskell implementation of this thing???
Haskell is a pure language, so the impure effects of updating k must
be wrapped in a state monad.
import Control.Monad.ST
import Data.STRef
type S s = ST s Integer
a :: Integer -> S s -> S s -> S s -> S s -> S s -> S s
a k x1 x2 x3 x4 x5 = a' where
a' | k <= 0 = do { x4' <- x4; x5' <- x5; return (x4' + x5') }
| otherwise = do { kr <- newSTRef k; b kr }
b kr = do
k <- readSTRef kr
let k' = k - 1
writeSTRef kr k'
a k' (b kr) x1 x2 x3 x4
run k =
runST (a k (return 1) (return (-1)) (return (-1)) (return 1) (return 0))
Note that in the presence of side effects, the ambigous expression "x4 + x5"
must be given explicit evaluation order (left argument first, or right
argument first). In this case, it makes no difference; in general, it can.
Result:
*Main> run 10
-67
*Main> run 9
-30
> Here is a possibly more readable Smalltalk program (the only language
> I know well that has all the requested features):
Any language should be able to simulate the "requested features"
(closures and side-effects), even if they are not primary language
constructs. (Yes, I'm getting really tired of language wars).
I could write the above program even in C.
OTOH, if Wikipedia is right and Knuth himself wasn't able to calculate
the correct answer, I think this shows clearly that ugly nested
side-effects like these can easily lead to confusion, and not to
clearly readable and correct programs.
- Dirk
Vesa Karvonen
[...]
> OTOH, if Wikipedia is right and Knuth himself wasn't able to calculate
> the correct answer, I think this shows clearly that ugly nested
> side-effects like these can easily lead to confusion, and not to
> clearly readable and correct programs.
Errare Humanum Est.
I think that the biggest obstacle to "understanding" the Man or Boy
Test is the arbitrary and artificial nature of the program. It is
easy to write much more convoluted programs without using any
side-effects. In either case, pure or impure, calculating the correct
answer is a mechanical exercise.
-Vesa Karvonen
Ingo Wechsung
I see. Works of the devil :)
The trick seems to be that every mention of B should decrease *the
same* k.
But if this is so, the declaration as "value" is clearly a misnomer,
isn't it?
Paolo Bonzini
> > Here is a possibly more readable Smalltalk program (the only language
> > I know well that has all the requested features):
>
> Any language should be able to simulate the "requested features"
> (closures and side-effects), even if they are not primary language
> constructs. (Yes, I'm getting really tired of language wars).
> I could write the above program even in C.
Sure, I should have written "the only language I know well where
I do not need to simulate the requested features". Also notice
that I wrote "the only language I know *well*", not "the only
language on Earth". It was not meant to be a language war.
That said, thanks for the answer.
Paolo
Laurent Deniau
wrote:
Now that I see it in Haskell, I can write it in C ;-)
> time man-or-boy 10
-67
0.000s
> time man-or-boy 9
-30
0.000s
> time man-or-boy 24
-4268854
1.760s
Looks like it uses an exponential amount of memory...
a+, ld.
/* man-or-boy.c */
#include <stdio.h>
#include <stdlib.h>
// --- thunks
typedef struct arg {
int (*fn)(struct arg*);
int *k;
struct arg *x1, *x2, *x3, *x4, *x5;
} ARG;
// --- lambdas
int eval(ARG* a) { return a->fn(a); }
int f_1 (ARG* _) { return -1; }
int f0 (ARG* _) { return 0; }
int f1 (ARG* _) { return 1; }
// --- helper
#define ARG(...) (&(ARG){ __VA_ARGS__ })
#define FUN(...) ARG(B,&k,__VA_ARGS__)
// --- functions
int B(ARG* a) {
int A(ARG*);
int k = *a->k -= 1;
return A( FUN(a,a->x1,a->x2,a->x3,a->x4) );
}
int A(ARG* a) {
return *a->k <= 0 ? eval(a->x4)+eval(a->x5) : B(a);
}
int main(int argc, char **argv) {
int k = argc == 2 ? strtol(argv[1],0,0) : 10;
printf("%d\n", A( FUN(ARG(f1),ARG(f_1),ARG(f_1),ARG(f1),ARG(f0)) ));
}
Jed Davis
> I see. Works of the devil :)
> The trick seems to be that every mention of B should decrease *the
> same* k.
> But if this is so, the declaration as "value" is clearly a misnomer,
> isn't it?
No, every activation of B will decrease the k in the activation of A
that created it. The recursive call to A passes k by value, so any
B-ing done by the new A won't affect the old A's value.
Some of the mentions of B won't decrement anything at all, as their
thunks won't make it up to x4 or x5 to be forced before the
corresponding k runs out.
--
(let ((C call-with-current-continuation)) (apply (lambda (x y) (x y)) (map
((lambda (r) ((C C) (lambda (s) (r (lambda l (apply (s s) l)))))) (lambda
(f) (lambda (l) (if (null? l) C (lambda (k) (display (car l)) ((f (cdr l))
(C k))))))) '((#\J #\d #\D #\v #\s) (#\e #\space #\a #\i #\newline)))))