Knuth Test Championship

Introduction

Back in 1964, the famous specialist Donald Knuth proposed a simple test [1], which he called "Man or boy?" (loosely translated "adult or child?") to check the translators from the Algol-60 language.





The test looked like this:





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 B;
     if k<=0 then A:=x4+x5 else B;
   end A;
 outreal(A(10,1,-1,-1,1,0);
end;
      
      



A B, , ( -67 , 10) . N 2(N-1).





, , , [2], 10.





, 32- . .

PL/1, [2]. , : OS PL/I V2.3.0, Enterprise PL/I V3R9M0 PL/I for Windows V8.0, 15, 23 26 .





PL/1-KT [3] , - , .. «» .





Β« Β» :





) «» . , PL/1 , , , . , «» , «». - , , «» .





) . -, , -, , () .





:





1. «», . SONY Intel Solo 1,33 1 . Windows Vista Business. , .





2. , . , kernel32.dll, ( - ) .





. , , .





, , , ( PL/1) .





PL/1 :





1. . . , – .





2. B.





3 , .. 6 11 .





, . «» . .





4+4 , 4 , 44 - 44 ( ). 44 . "" 27 226 2,952,790,016 . , 32- Windows 3 , 27 .





/3GB BOOT.INI Windows XP, bcdedit /set increaseuserva 3221225471 32- Windows Vista Windows-7, 3 , , EXE- IMAGE_FILE_LARGE_ADDRESS_AWARE.





, kernel32.dll user32.dll , , . , , , .





, – PL/1 (.. ALLOCATE FREE) «» «» . «» PL/1 , : , , , .





, , , Win-32 API VirtualAlloc. VirtualAlloc. , 50% , – VirtualFree, 50% . ( 1 ). , , «» .





PL/1 PL/1-. «» 3200 .





226 36 , .. 2416 , 2140 , – 1073 . ALLOCATE :





1. ALLOCATE 8226 . PL/1-KT [3], ESP.





2. PL/1-KT MAXWDS ALLOCATE . , , 1.5 .





3. MAXWDS . , «» .





«» ( «» ), 27.





PL/1 «» , «» , , . . - , . 1: X1 «» , - P1 , A1. X2 , - P3, P2 . A2 P3, .





Figure:  1. Referring to array elements X1 and X2 in two non-adjacent areas
. 1. X1 X2

, - . , .





PL/1-KT

. , , . , . X4+X5 . X5 , X4 ( X5, X4, ). X5 X4, X5 X4. X4, Z. X4 X5, X5 . 12 .





─────────────────────────────────────────────────────────────────────────────
//  "'"              "  "
//  ???  ???    COHTE:                 K PL/1-KT
─────────────────────────────────────────────────────────────────────────────
// MO MORB             BEPC 1.0            ATA COAH     13.5.2012
// COEME MATEPA: HTTP://EN.WIKIPEDIA.ORG/WIKI/MAN_OR_BOY_TEST
─────────────────────────────────────────────────────────────────────────────
//  :
─────────────────────────────────────────────────────────────────────────────
//     
//   =27   WINDOWS-XP C  /3GB
//  BOOT.INI    BCDEDIT /SET INCREASEUSERVA=3221225471 
// WINDOWS-VISTA  WINDOWS-7
────────────────────────────────────────────────────────────────────────────
MORB: PROC() MAIN;
DECLARE
//----       (  ) ----

            CHAR(*) VAR,

//----    PL/1-KT ----

?MEMORY         FIXED(31) EXT INIT(-1), //   
?MEM_ALL        FIXED (7) EXT INIT(1),  //   

//----   PL/1-KT ----

MAXWDS          RETURNS(FIXED(31)), //   

//----      ----

1  (1:2) BASED(_()),  //  1:2 
 2 KK           FIXED(31),          //    
 2 (XX1,                            // 
    XX2,
    XX3,
    XX4)        ENTRY(FIXED(31)) RETURNS(FIXED(31)),
 2 (NN1,
    NN2,                            // 
    NN3,
    NN4)        FIXED(31),

//---- ,  1  ----

P1              PTR,        //   1 
1            FIXED(31),  //  1    

//---- ,  2  ----

P2              PTR,        //   2 
F2              FIXED(31) DEF(P2), //       
2            FIXED(31),  //  2    
P2_         PTR,        //    2 
F2_         FIXED(31) DEF(P2_), //    
             FIXED(31),  //      

//----    A ----

N               FIXED(31),  //  
          FIXED(31),  //    

//----     ----
 
P4              PTR,        //     
F4              FIXED(31) DEF(P4), //       
?ESP            FIXED(31),  //     ESP  PL/1-KT
_       FIXED(31),  //  

//----     ----

I               FIXED(31),  //    
L               FIXED(31),  //   
Z               FIXED(31),  //   A
J               FIXED(31);  //     
─────────────────────────────────────────────────────────────────────────────
//----   ----

PUT SKIP(2) LIST('^I^I "MAN OR BOY", ',?DATE);

//----       ----

IF LENGTH()>0 THEN I=;

//-----------------      ---------------------

PUT SKIP(2) EDIT(TOTWDS,'   , :')
                (P'ZZZ,999,999,999',A);
PUT SKIP;

//----      ----

_=2**26*8+1024*1024; //   27
ALLOCATE(_) SET(P4); //    
?ESP=F4+_;           //  -    ESP

//----   (1 )    ----

1=MAXWDS*2;               //    
ALLOCATE(1) SET (P1);     //    1 
1=1/36;                //     1 

PUT SKIP EDIT(1,'   1 ')(P'ZZZ,ZZZ,999,999',A);

//----   (2 )    ----

2=MAXWDS*2;               //    
ALLOCATE(2) SET(P2);      //    2 
2=2/36;                //     2 

PUT SKIP EDIT(2,'   2 ')(P'ZZZ,ZZZ,999,999',A);

//----      ----

=1+2;               //      
F2_=F2-1*36;          //   2 

PUT SKIP(2) LIST('-'(40),'^M');

//-------------------------    ----------------------------

DO I=I TO 27;      //       

   //----   ----

   PUT SKIP EDIT(TIME,'     =',I)(A,A,F(2));
   PUT SKIP;

   //----   (    ) ----

   L=A((I), X1,0, X2,0, X3,0, X4,0, X5,0);

   //----   ----

   PUT LIST(' '(20),'^M');
   PUT SKIP EDIT(TIME,' = ', I,L)(A(8),X(1),A,P'z9b',P'---,---,---,--9');
   PUT SKIP LIST('-'(40),'^M');
END I;

//-------------------     --------------------

A:PROC(K,X1,N1,X2,N2,X3,N3,X4,N4,X5,N5) RETURNS(FIXED(31));

DECLARE

K                 FIXED(31),    //  
(X1,X2,X3,X4,X5)  ENTRY(FIXED(31)) RETURNS(FIXED(31)), // 
(N1,N2,N3,N4,N5)  FIXED(31);    //   

//----    A ----

N+=1;

//----      ----

IF N> THEN PUT SKIP LIST('',STOP);

//----       ----

J+=1;
IF J>8191 THEN //      
  {;
    J=0;
    PUT EDIT(TIME,'  ',N,'^M')(A,A,P'ZZZ,999,999',A);
  };

//--------------------     -------------------

//----      A ----

=N;  //    1/2 
XX1(N)=X1; //  
XX2(N)=X2;
XX3(N)=X3;
XX4(N)=X4;
NN1(N)=N1; //   
NN2(N)=N2;
NN3(N)=N3;
NN4(N)=N4;
KK (N)=K;  //    

IF K<=0 THEN     //    X4  X5
  {;
    XX4(N)=X5;   // \  
    NN4(N)=N5;   // /   #5
    Z=X4(N4);    //   #4   #4
    =N;    //    1/2 
    NN4(N)<=>Z;  //   #4    #5
    Z=XX4(N)(Z); //   #5   #5
    =N;    //    1/2 
    Z+=NN4(N);   //  X4+X5
  };
        ELSE Z=B((N)); //      B

//----   A ----

N-=1;

//----    ----

RETURN(Z);

//--------------------     -------------------

B:PROC(Y) RETURNS(FIXED(31));

DCL Y FIXED(31); //   

=Y;        //    1/2 
KK(Y)-=1;        //     

//----     ----

RETURN(A(KK(Y),B,Y,XX1(Y),NN1(Y),XX2(Y),NN2(Y),XX3(Y),NN3(Y),XX4(Y),NN4(Y)));
END B;
END A;

//------------    1  2   --------------

_:PROC RETURNS(PTR);

//----    1   ----

IF <=1 THEN RETURN(P1); //    1 

//----    2   ----

RETURN(P2_);                 //    2 

END _;

//----------------------    --------------------------

X1:PROC(Y) RETURNS(FIXED(31)); DCL Y FIXED(31); RETURN( 1); END X1;
X2:PROC(Y) RETURNS(FIXED(31)); DCL Y FIXED(31); RETURN(-1); END X2;
X3:PROC(Y) RETURNS(FIXED(31)); DCL Y FIXED(31); RETURN(-1); END X3;
X4:PROC(Y) RETURNS(FIXED(31)); DCL Y FIXED(31); RETURN( 1); END X4;
X5:PROC(Y) RETURNS(FIXED(31)); DCL Y FIXED(31); RETURN( 0); END X5;
END MORB;

      
      



. 2. 27 , 9 , -46750171 67 , 292 . 1 , , .





Figure:  2. Result of test execution with initial number 27
. 2. 27

, , «» - , . ( ), , , «» PL/1 (, , 32- ). 26 64- Windows-8 16 . 27, 32- , , «» , , .





. 64- . .

. Β«Man or boy?Β» [2] , . , Β« Β» – () . , . – . - (, , - ). , – , .. , . , 2n.





, , [3], , , . , . , - Windows-XP, 3 . . (. 1) , 27, Β« Β» , [2].





, , , , , Win64 . , , Haskell, 30. , , «-». , c 32- Windows, AMD Opteron 6282SE c 384 «».





c Intel Core i5-3210M, c 4 Windows 7 Win64. , , , . PL/1, , – Win64 8 , .. BINARY FIXED(63), ( PL/1 . 1) , BINARY FIXED(31). , - , (- ), ESP RSP. , .





, , Win32, Win64. , NTDLL.DLL KERNEL32.DLL Windows 7 «» , , «» 1 .





«» . Win32 , 8 . , «640 »? , 30 (, ) 16*229=4294967296 . ! , , , 232. Win32 Win64, . ESP RSP, . Win64.





«» « », Windows 7 31.





«», . .. Win64 Win32 ( ) 16 ! ( , ) 4 8 , ( ) Win32 32 .





, - . , 32, 250 ( 200 ). , . , , .





: ? «» ? , . , ( ), , ( 1).





, «» , , . .





. «» . , , , .





P.S. , , , , , , . , , , . – , , .. . (, , , ) [4].





1.       Donald Knuth (July 1964). Β«Man or boy?Β». http://www.chilton-computing.org.uk/acl/applications/algol/p006.htm. Retrieved Dec 25,2009





2.       http://rosettacode.org/wiki/Man_or_boy_test





3. D.Yu.Karavaev "To the question of improving the programming language" RSDN Magazine # 4 2011





 4.https: //keldysh.ru/papers/2013/prep2013_29.pdf





 








All Articles