>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.
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???
> >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.
> 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???
This is hard to tell for people like me that are not familiar with ALGOL calling conventions.
> 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. Here is Lisp, but it uses setq. I figure in Haskell you'd use a State monad, but there are probably other ways.
Ingo Wechsung <quetzalc...@consultant.com> wrote: > 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 :)
Paolo Bonzini <bonz...@gnu.org> wrote: >>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.
> 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.
On 9 Nov., 11:33, Paul Rubin <http://phr...@NOSPAM.invalid> wrote:
> Ingo Wechsung <quetzalc...@consultant.com> writes: > > > 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.
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?
> > 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.
> 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.
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...
Ingo Wechsung <quetzalc...@consultant.com> writes: > 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.
|
