Muž nebo chlapec test - Man or boy test

The muž nebo chlapec test navrhl počítačový vědec Donald Knuth jako prostředek k hodnocení implementace ALGOL 60 programovací jazyk. Cílem testu bylo rozlišit překladače že správně implementováno "rekurze a nelokální odkazy „od těch, kteří ne.

Existuje poměrně málo překladačů ALGOL60, které byly navrženy tak, aby správně zpracovávaly rekurzi a nelokální odkazy, a myslel jsem si, že možná bude mít malý testovací program hodnotu. Proto jsem napsal následující jednoduchou rutinu, která může oddělit man-kompilátory od boy-kompilátorů.

— Donald Knuth^[1]

Knuthov příklad

v ALGOL 60:

začít  nemovitý postup A(k, x1, x2, x3, x4, x5);  hodnota k; celé číslo k;  nemovitý x1, x2, x3, x4, x5;  začít    nemovitý postup B;    začít k := k - 1;          B := A := A(k, B, x1, x2, x3, x4)    konec;    -li k ≤ 0 pak A := x4 + x5 jiný B  konec  neskutečný(1,A(10, 1, -1, -1, 1, 0))konec

Tím se vytvoří strom B rámce volání, které odkazují na sebe navzájem a na obsažené A rámce volání, z nichž každý má svou vlastní kopii k který se mění pokaždé, když je přidružen B je nazýván. Pokusit se to propracovat na papíře je pravděpodobně marné, ale pro k= 10, správná odpověď je −67, a to navzdory skutečnosti, že v původním článku Knuth předpokládal, že je −121. Průzkumový papír od Charles H. Lindsey zmíněný v referencích obsahuje tabulku pro různé počáteční hodnoty. Dokonce i moderní stroje rychle dojdou zásobník prostor pro větší hodnoty k, které jsou uvedeny v tabulce níže (OEIS: A132343).^[2]

k	${ displaystyle A (k, 1, -1, -1,1,0)}$
0	1
1	0
2	−2
3	0
4	1
5	0
6	1
7	−1
8	−10
9	−30
10	−67
11	−138
12	−291
13	−642
14	−1,446
15	−3,250
16	−7,244
17	−16,065
18	−35,601
19	−78,985
20	−175,416
21	−389,695
22	−865,609
23	−1,922,362
24	−4,268,854
25	−9,479,595
26	−21,051,458

Vysvětlení

V tomto programu jsou použity tři funkce Algol, které mohou být obtížné správně implementovat v kompilátoru:

1. Vnořená funkce definice: Od té doby B je definován v místním kontextu A, tělo B má přístup k místním symbolům A - zejména k které upravuje, ale také x1, x2, x3, x4, a x5. U potomka Algolu je to přímé Pascal, ale u druhého významného algolského potomka to není možné C (bez ruční simulace mechanismu pomocí operátoru adresy C, předávání ukazatelů na místní proměnné mezi funkcemi).
2. Odkazy na funkce: B v rekurzivním volání A (k, B, x1, x2, x3, x4) není hovor na B, ale odkaz na B, který bude volán, až když k je větší než nula. To je ve standardním Pascalu jednoduché (ISO 7185 ) a také v C. Některé varianty Pascal (např. starší verze Turbo Pascal ) nepodporují odkazy na procedury, ale když je předem známá sada funkcí, na které lze odkazovat (v tomto programu je to pouze B), toto lze obejít.
3. Konstantní / funkční dualismus: x1 přes x5 parametry A mohou to být číselné konstanty nebo odkazy na funkci B - x4 + x5 výraz musí být připraven zvládnout oba případy, jako by formální parametry x4 a x5 byl nahrazen odpovídajícím skutečným parametrem (volat podle jména ). To je pravděpodobně větší problém v staticky napsané než v dynamicky zadávaných jazycích, ale standardním řešením je reinterpretace konstant 1, 0 a −1 v hlavním volání A jako funkce bez argumentů, které vracejí tyto hodnoty.

O těchto testech však nejde; jsou pouze nezbytným předpokladem toho, aby byl test vůbec smysluplný. Jaký je test o je, zda různé odkazy na B odhodlání k opravit instance B - ten, který má přístup ke stejnému A- místní symboly jako B který vytvořil odkaz. Překladač „boy“ může například místo toho kompilovat program tak, aby B vždy přistupuje k nejvyšším A rámec volání.

Viz také

• Funargův problém
• Jensenovo zařízení

Reference

externí odkazy

• „Muž nebo chlapec“, Bulletin ALGOL 17, str. 7 (k dispozici na chilton-computing.org )
• Muž nebo chlapec test příklady v mnoha programovacích jazycích