Man or boy test

From wiki.visual-prolog.com

Jump to: navigation, search

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.

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

Task: Imitate Knuth's example in Algol 60 in another language, as far as possible.

Visual Prolog (like any other Prolog) does not allow variables to be changed. But behavior can easily be mimicked by using a varM (modifiable variable), which is actually an object containing a value of the relevant type in a modifiable entity (a so called fact variable). Secondly, anonymous function (lambda-expression) cannot be recursive, but this is mimicked by using another varM to hold the function.

implement main
    open core
 
clauses
    run():-
        console::init(),
        stdio::write(a(10, {() = 1}, {() = -1}, {() = -1}, {() = 1}, {() = 0})).
 
class predicates
    a : (integer K, function{integer} X1, function{integer} X2, function{integer} X3, 
            function{integer} X4, function{integer} X5) -> integer Result.
clauses
    a(K, X1, X2, X3, X4, X5) = R :-
        KM = varM::new(K),
        BM = varM{function{integer}}::new({() = 0}),
        BM:value :=
            { () = BR :-
                KM:value := KM:value-1,
                BR = a(KM:value, BM:value, X1, X2, X3, X4)
            },
        R = if KM:value <= 0 then X4() + X5() else BM:value() end if.
 
end implement main

The implementation gives the expected result (which is -67).

Personal tools