Jump to content

Talk:Man or boy test

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Amazing how most wikipedia articles regarding algorithms quickly evolve into pissing contest between programming language implementations. Is the algorithm really so hard or are programmers so stupid that they can't possibly read it unless it's written in their favorite language? I'm sure there's also a lot of propaganda going on -- I mean, is it really necessary implementations for 2 versions of C#?! -- 201.47.188.2 (talk) 18:30, 8 September 2008 (UTC)[reply]

(nevermind) but, just how many levels of recursion is this supposed to have before anything returns? --Random832 03:06, 12 May 2007 (UTC)[reply]

PROC
name 		Max depth of
recursions 		Total
calls
a 512 722
b 511 721
  • Need a C0FFEE now?

I too am curious to know how/where/why Donald Knuth derived this strange algorithium. NevilleDNZ 09:32, 12 May 2007 (UTC) Well, that explains it. mozilla craps out after 1000 (i tried to implement it in javascript). --Random832 02:09, 18 May 2007 (UTC)[reply]

anyway, if anyone cares. C implementation 

#include <stdio.h>
typedef struct s {
    int k;
    struct s *x1, *x2, *x3, *x4;
    int(*f)(struct s* ref);
} *ps;

int B(ps ref) {
    (ref->k)--;
    return A(ref->k,ref,ref->x1,ref->x2,ref->x3,ref->x4);
}

int A(int k, ps x1,ps x2,ps x3,ps x4,ps x5) {
    struct s x;
    x.x1=x1; x.x2=x2; x.x3=x3; x.x4=x4;
    x.k=k; x.f=B;
    if(x.k <= 0)
        return x4->f(x4) + x5->f(x5);
    else
        return B(&x);
}

int x(ps ref) {
    return ref->k;
}

int main() {
    struct s p; p.k= +1; p.f=x;
    struct s m; m.k= -1; m.f=x;
    struct s z; z.k=  0; z.f=x;
    int val = A(10,&p,&m,&m,&p,&z);
    printf("value is %d\n",val);
    return 0;
}

--Random832 02:09, 18 May 2007 (UTC).[reply]

Pending code snippet transplant/removal?

[edit]

http://www.rosettacode.org/rosettacode/w/index.php?title=Talk:Man_or_boy_test —Preceding unsigned comment added by NevilleDNZ (talk • contribs) 00:32, 19 December 2007 (UTC)[reply]

Scheme

[edit]

I turned the Common Lisp example into Scheme. Would it be useful to add that, given that there's already CL? Golwengaud (talk) 16:35, 24 December 2007 (UTC)[reply]

Yes, I believe it would. 70.111.126.237 (talk) 16:16, 3 January 2008 (UTC)[reply]
Done. Golwengaud (talk) 14:57, 6 January 2008 (UTC)[reply]

Common Lisp

[edit]

There is a bug in the Common Lisp implementation: even with LET*, the scope of a local variable does not include its own initialization form, so the proposed solution does not in fact work (B is unbound). I intend to replace it shortly. 70.111.126.237 (talk) 16:16, 3 January 2008 (UTC)[reply]

Scala

[edit]

Added a Scala implementation. This is without the object wrapper because you can run Scala programs directly as scripts. 128.214.11.51 (talk) 08:26, 17 March 2008 (UTC)[reply]

Change C implementation

[edit]

The C program in the article is rather confusing. In particular, ARG is both a type and a macro: 

 /* 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 f_1 (ARG* _) { return -1; }
 int f0  (ARG* _) { return  0; }
 int f1  (ARG* _) { return  1; }
 
 // --- helper
 int eval(ARG* a) { return a->fn(a); }
 #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)) ));
 }

The C program from the talk page (at top, by Random832) looks much clearer, and avoids advanced features such as __VA_ARGS__: 

#include <stdio.h>
typedef struct s {
    int k;
    struct s *x1, *x2, *x3, *x4;
    int(*f)(struct s* ref);
} *ps;

int B(ps ref) {
    (ref->k)--;
    return A(ref->k,ref,ref->x1,ref->x2,ref->x3,ref->x4);
}

int A(int k, ps x1,ps x2,ps x3,ps x4,ps x5) {
    struct s x;
    x.x1=x1; x.x2=x2; x.x3=x3; x.x4=x4;
    x.k=k; x.f=B;
    if(x.k <= 0)
        return x4->f(x4) + x5->f(x5);
    else
        return B(&x);
}

int x(ps ref) {
    return ref->k;
}

int main() {
    struct s p; p.k= +1; p.f=x;
    struct s m; m.k= -1; m.f=x;
    struct s z; z.k=  0; z.f=x;
    int val = A(10,&p,&m,&m,&p,&z);
    printf("value is %d\n",val);
    return 0;
}

So, why not use the latter instead? 81.231.33.217 (talk) 08:56, 24 June 2008 (UTC)[reply]

This article has clearly lost its focus!

[edit]

Folks, it seems like this article has gotten lost in outer space. Judging from the title, this article should detail the routine which Knuth wrote in order to evaluate the correctness of various implementations of Algol 60 compilers. And that's all. What on earth is the significance or use of implementing this routine in any other language, let alone over a dozen? As such, I would propose eliminating all of the other language examples. 65.183.135.231 (talk) 19:14, 6 November 2008 (UTC)[reply]

I went ahead and did it. I do feel bad, since people have apparently put a lot of work into coding them. However, while interesting, the alternate language examples are not at all relevant to the article. 65.183.135.231 (talk) 19:20, 6 November 2008 (UTC)[reply]
There's a reference to a D version that isn't visible anymore. I think that keeping articles on focus is important, but it's also important to keep Wikipedia a playful place (and implementing such small program is clearly fun for many programmers, and it also teaches many things about several languages) because if there's no play and fun, then it starts to smell as of job or as death. As a compromise a linked sub page can be created, like 'Man_or_boy_test_implementations', where to move the implementations. —Preceding unsigned comment added by 79.32.203.42 (talk) 04:38, 16 November 2008 (UTC)[reply]
Wikipedia is an Encyclopedia, not a playground. It's not an introduction to programming, either--see the Wikibooks project, instead. 65.183.135.231 (talk) 02:53, 20 November 2008 (UTC)[reply]
You can't believe how much people contribute to open source projects because it's a fun thing to do. They don't do it for money, for fame, and sometimes they even don't do it because they need the final product a lot. They often do it because it's a way to learn, to have fun, to show their capabilities to other people, to gain respect from people like them, etc. Removing all the fun out of contributing to Wikipedia just because it's an 'Encyclopedia, not a playground' is a very gray thing to do. —Preceding unsigned comment added by 79.43.199.47 (talk) 15:31, 21 November 2008 (UTC)[reply]
Please see: http://en.wikipedia.org/wiki/Wikipedia:Not. I find copy-editing quite good fun. Others find writing articles fun. Still others find checking sources and adding sources fun. Some, as you point out, find adding non-encyclopedic errata fun. However, unlike the other examples, this last activity is neither acceptable nor helpful towards Wikipedia becoming what it was created to be, and largely is: an encyclopedia. We can have plenty of fun and still make a fairly serious product. Don't tell me that silliness and unrelated nonsense should be included in an article just because it's "fun" and otherwise, somehow, everyone will leave and stop contributing. 65.183.135.231 (talk) 04:39, 23 November 2008 (UTC)[reply]
The various implementations weren't "silliness and unrelated nonsense", but I presume they are off-topic here, and they are too much original content even in a dedicated page (I think most of the code present in Wikipedia is original content). The original purpose of Knuth was to design a little test to tell adult languages apart from more primitive ones, but showing a list of actual adult languages (and why they are adult) seems off-topic here. The implementations are now moved (by someone else) here (www.rosettacode.org/wiki/Man_or_boy_test ), a wiki that has right the purpose of showing alternative implementations of the same code. —Preceding unsigned comment added by 79.36.206.215 (talk) 11:11, 26 November 2008 (UTC)[reply]
What is with people not getting this? It's not "a little test to tell adult languages apart from more primitive ones." Read the freaking letter to the editor; it's in the "References" section. It's barely a page long. Knuth makes it QUITE clear that the test is to tell CONFORMING COMPILERS from NON-CONFORMING COMPILERS, specifically for the ALGOL60 standard's recursion and non-local references features. Please see below, where I provide a quote to this effect (look for bold text). .65.183.135.231 (talk) 18:30, 30 November 2008 (UTC)[reply]
And Wikipedia's policy is against original research, not original content--indeed, this latter is clearly encouraged. 65.183.135.231 (talk) 23:16, 2 December 2008 (UTC)[reply]
Added here, it's not original research, just a copy-paste: http://en.wikipedia.org/wiki/Wikipedia_talk:Articles_for_creation/Submissions/Man_or_boy_test_implementations —Preceding unsigned comment added by 79.35.23.216 (talk) 09:23, 19 November 2008 (UTC)[reply]
I think you're confused. It's most certainly original research because the source of all of these algorithms (or most of them) is just random Wikipedians donating their own unpublished implementations. 65.183.135.231 (talk) 02:53, 20 November 2008 (UTC)[reply]
And for that matter, what on earth is the use of implementing this algorithm in D? The sole use of the algorithm was for testing standards compliance of Algol 60 compilers! There is a major logical disconnect in presenting implementations in other languages--I hardly even know how to respond. 65.183.135.231 (talk) 02:55, 20 November 2008 (UTC)[reply]
The feature being tested in Algol 60 is present in most modern programming languages, so it's perfectly valid to write it in these languages. It's not an Algol 60-specific test at all. Not that they all need to be on the wiki page, necessarily... —Preceding unsigned comment added by 65.94.11.245 (talk) 19:59, 26 November 2008 (UTC)[reply]
"Not an Algol 60-specific test"?!! Dude, did you actually read Knuth's letter to the editor, which describes the test? It's in the "References" section. Here's most of it:
There are quite a few ALGOL60 compilers in existence which have been designed to handle recursion and non-local references properly, and I thought perhaps a little test-program may be of value. Hence I have written the following simple routine, which may separate the "man-compilers" from the "boy-compilers"
How could this not be understood as an "Algol 60-specific test"? It's as plain as day: The ALGOL60 standard defined some difficult-to-implement features, such as recursion and non-local references, yet Knuth noticed that many so-called ALGOL60 compilers did not properly implement this standard. As such, he made a non-trivial routine which utilized those features, to present a test for standards-adherence. It's just for ALGOL60. Sure, you can express this routine in other languages, but that's not the point. The point is to say, "Given that I've coded this routine in ALGOL60, does the compiler properly translate it?" 65.183.135.231 (talk) 18:27, 30 November 2008 (UTC)[reply]
I apologize if I'm coming off as a bit of a bastard--I'm actually a bit frustrated from far sillier arguments I had today with other people. In any case, in order to be more clear, here is an example of an article where I think adding alternative implementations makes more sense and is appropriate for Wikipedia: http://en.wikipedia.org/wiki/Trabb_Pardo-Knuth_algorithm. Best, 65.183.135.231 (talk) 07:46, 20 November 2008 (UTC)[reply]
I just came across this dialogue, after posting my own unrelated contribution in "Code formatting" below. THANK YOU so much for refuting every stupid argument this dude kept coming back at you with. This was strictly about Algol 60 compilers, and, like you also noted, Wikipedia is not a playground.
BTW, one of my professors in both my undergraduate program and in my Masters program was Dr. Peter R King, one of the more prominent Algol 60/68/W authorities in the world. HWSager (talk) 03:49, 11 September 2023 (UTC)[reply]


What is the problem to be solved? It's unclear for me from the article. --Wikyvema (talk) 00:18, 19 February 2018 (UTC)[reply]

Code formatting

[edit]

The current formatting of the code really obscures its structure. For example, it suggests that outreal is part of the declaration of A. The original (below) is much clearer. The current version was introduced to match the original publication, but the obscure formatting may have been due to a copy editor rather than reflecting Knuth's intent. Either way, I think clarity is more important than pedantry in this instance. So I'll change it back if no-one objects. 

begin
  real procedure A(k, x1, x2, x3, x4, x5);
  value k; integer k;
  real x1, x2, x3, x4, x5;
  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(1, A(10, 1, -1, -1, 1, 0))
end

Nobody complained so I've gone ahead and done this. — Preceding unsigned comment added by 2.27.171.228 (talk) 21:32, 21 August 2023 (UTC)[reply]

Formatting matters aside, shouldn't the "end" before the "outreal" be followed by a semi-colon? That "end" ends the begin-end block that comprises the body of procedure A (following the parameter declarations within procedure A), and thus ends the whole definition of procedure A. This whole definition of procedure A, in turn, needs a semi-colon separator from the "outreal" statement (which is itself a procedure invocation, and is the only executable statement in the program (outermost begin-end block)).
Hartmut W Sager, an old Algol 60 nerd. HWSager (talk) 03:25, 11 September 2023 (UTC)[reply]
Yes, the original had a semicolon there. I've added it back in. — Preceding unsigned comment added by 91.110.3.64 (talk) 20:35, 10 March 2024 (UTC)[reply]
Retrieved from "https://en.wikipedia.org/w/index.php?title=Talk:Man_or_boy_test&oldid=1213037807"