Interpret Prologu Implementace Prologu (pokračování) Základní principy: ■ klauzule uloženy jako termy ■ programová databáze ■ pro uložení klauzulí ■ má charakter haldy ■ umožňuje modifikovatelnost prologovských programů za běhu (assert) ■ klauzule zřetězeny podle pořadí načtení ■ triviální zřetězení Vyhodnocení dotazu: volání procedur řízené unifikací Interpret - Základní princip 1. Vyber redukovaný literál („první", tj. nejlevější literál cíle) 2. Lineárním průchodem od začátku databáze najdi klauzuli, jejíž hlava má stejný funktor a stejný počet argumentů jako redukovaný literál 3. V případě nalezení klauzule založ bod volby procedury 4. Založ dále okolí první klauzule (velikost odvozena od počtu lokálních proměnných v klauzuli) 5. Proveď unifikaci literálu a hlavy klauzule 6. Úspěch => přidej všechny literály klauzule k cíli („doleva", tj. na místo redukovaného literálu). Tělo prázdné => výpočet se s úspěchem vrací do klauzule, jejíž adresa je v aktuálním okolí. 7. Neúspěch unifikace => z bodu volby se obnoví stav a pokračuje se v hledání další vhodné klauzule v databázi. 8. Pokud není nalezena odpovídající klauzule, výpočet se vrací na předchozí bod volby (krátí se lokální i globální zásobník). 9. Výpočet končí neúspěchem: neexistuje již bod volby, k němuž by se výpočet mohl vrátit. 1 0. Výpočet končí úspěchem, jsou-li úspěšně redukovány všechny literály v cíli. Hana Rudová, Logické programování I, 7. května 2010 3 Implementace Prologu Hana Rudová, Logické programování I, 7. května 2010 2 Implementace Prologu Interpret - vlastnosti ■ Lokální i globální zásobník ■ při dopředném výpočtu roste ■ při zpětném výpočtu se zmenšuje Lokální zásobník se může zmenšit při dopředném úspěšném výpočtu deterministické procedury. ■ Unifikace argumentů hlavy - obecný unifikační algoritmus Současně poznačí adresy instanciovaných proměnných na stopu. ■ „Interpret": interpret(Query, Vars) :- ca"l"l(Query), success(Query, Vars). interpret(_,_) :- failure. ■ dotaz vsazen do kontextu této speciální nedeterministické procedury ■ tato procedura odpovídá za korektní reakci systému v případě úspěchu i neúspěchu Hana Rudová, Logické programování I, 7. května 2010 4 Implementace Prologu Optimalizace: Indexace Zřetězení klauzulí podle pořadí načtení velmi neefektivní Provázání klauzulí se stejným funktorem a aritou hlavy (tvoří jednu proceduru) ■ tj., indexace procedur Hash tabulka pro vyhledání první klauzule Možno rozhodnout (parciálně) determinismus procedury Hana Rudová, Logické programování I, 7. května 2010 Implementace Prologu Indexace argumentů II Složitější indexační techniky ■ podle všech argumentů ■ podle nejvíce diskriminujícího argumentu ■ kombinace argumentů (indexové techniky z databází) ■ zejména pro přístup k faktům Indexace argumentů a(l) :- q Cl). a(a) :- b(X). a([A|T]) :- c(A,T). ■ Obecně nedeterministická ■ Při volání s alespoň částečně instanciovaným argumentem vždy deterministická (pouze jedna klauzule může uspět) ■ Indexace podle prvního argumentu Základní typy zřetězení: ■ podle pořadí klauzulí (aktuální argument je volná proměnná) ■ dle konstant (aktuální je argument konstanta) ■ formální argument je seznam (aktuální argument je seznam) ■ dle struktur (aktuální argument je struktura) Hana Rudová, Logické programování I, 7. května 2010 Implementace Prologu Tail Recursion Optimization, TRO Iterace prováděna pomocí rekurze => lineární paměťová náročnost cyklů Optimalizace koncové rekurze (Tail Recursion Optimisation), TRO: Okolí se odstraní před rekurzivním voláním posledního literálu klauzule, pokud je klauzule resp. její volání deterministické. Řízení se nemusí vracet: ■ v případě úspěchu se rovnou pokračuje ■ v případě neúspěchu se vrací na předchozí bod volby („nad" aktuální klauzulí) ■ aktuální klauzule nemá dle předpokladu bod volby Rekurzivně volaná klauzule může být volána přímo z kontextu volající klauzule. Hana Rudová, Logické programování I, 7. května 2010 7 Implementace Prologu Hana Rudová, Logické programování I, 7. května 2010 8 Implementace Prologu TRO - příklad Program: append([], L, L). append([A|X], L, [A|Y]) :- append(X, L, Y). Dotaz: ?- append([a,b,c], [x], L). append volán rekurzivně 4krát ■ bez TRO: 4 okolí, lineární paměťová náročnost ■ s TRO: 1 okolí, konstatní paměťová náročnost Hana Rudová, Logické programování I, 7. května 2010 9 Implementace Prologu Překlad Optimalizace posledního volání TRO pouze speciální případ obecné optimalizace posledního volání (Last Call Optimization), LCO Okolí (před redukcí posledního literálu) odstraňováno vždy, když leží na vrcholu zásobníku. Nutné úpravy interpretu ■ disciplina směrování ukazatelů ■ vždy „mladší" ukazuje na „starší" („mladší" budou odstraněny dříve) ■ z lokálního do globálního zásobníku vyhneme se vzniku „visících odkazů" při předčasném odstranění okolí ■ „globalizace" lokálních proměnných: lokální proměnné posledního literálu ■ nutno přesunout na globální zásobník ■ pouze pro neinstanciované proměnné Hana Rudová, Logické programování I, 7. května 2010 10 Implementace Prologu Překlad ■ Motivace: ■ dosažení vyšší míry optimalizace ■ kompaktní kód ■ částečná nezávislost na hardware ■ Etapy překladu: 1. zdrojový text => kód abstraktního počítače 2. kód abstraktního počítače => kód (instrukce) cílového počítače ■ Výhody: ■ snazší přenos jazyka (nutno přepsat jen druhou část) ■ kód abstraktního počítače možno navrhnout s ohledem na jednoduchost překladu; prostor pro strojově nezávislou optimalizaci ■ Překlad Prologu založen na principu existence abstraktního počítače V dalším se věnujeme jeho odvození a vlastnostem Hana Rudová, Logické programování I, 7. května 2010 12 Preklad Parciální vyhodnocení Parciální vyhodnocení - příklad ■ Jak navrhnout Warrenův abstraktní počítač? ■ prostřednictvím parciálního vyhodnocení ■ Parciální vyhodnocení ■ forma zpracování programu, tzv. transformace na úrovni zdrojového kódu ■ dosazení známých hodnot vstupních parametrů a vyhodnocení všech operací nad nimi ■ příklad: vyhodnocení aritmetických výrazů nad konstantami Hana Rudová, Logické programování I, 7. května 2010 13 Preklad Parciální vyhodnocení II Konstrukce překladače: parciálním vyhodnocením interpretu Problémy: ■ příliš složitá operace ■ vyhodnocení se musí provést vždy znovu pro každý nový program ■ výsledný program příliš rozsáhlý ■ nedostatečná dekompozice ■ zejména při použití zdrojového jazykajako implementačního jazyka interpretu Vhodnější: ■ využití („ručního") parciálního vyhodnocení pro návrh abstraktního počítače 1. nalezení operací zdrojového jazyka, které lze dekomponovat do jednodušších operací 2. dekomponujeme tak dlouho, až jsou výsledné operace dostatečně jednoduché nebo již neexistují informace pro parciální vyhodnocení Hana Rudová, Logické programování I, 7. května 2010 15 Preklad a(X,Y) :- b(X), c(X,Y). a(X,Y) :- b(Y), c(Y,X). b(l). b(2). b(3). b(4). c(l,2). c(l,3). c(l,4). c(2,3). c(2,4). c(3,4). Dotaz ?- a(2 ,Z) . lze společně s uvedeným programem parciálně vyhodnotit na nový program a'(3). a'(4). a'Cl), a nový dotaz ?- a'(Z). Je evidentní, že dotaz nad parciálně vyhodnoceným programem bude zpracován mnohem rychleji (efektivněji) než v případě původního programu. Hana Rudová, Logické programování I, 7. května 2010 14 Preklad Parciální vyhodnocení Prologu Cílová operace: unifikace. Důvod: ■ řízení výpočtu poměrně podrobné i v interpretu ■ unifikace v interpretu atomickou operací ■ unifikace v interpretu nahrazuje řadu podstatně jednodušších operací (testy, přiřazení, předání a převzetí parametrů ...) ■ většina unifikací nevyžaduje obecnou unifikaci a lze je nahradit jednoduššími operacemi Zviditelnění unifikace: transformací zdrojového programu ■ termy reprezentujeme kopírováním struktur na globálním zásobníku ■ parametry procedur jsou vždy umístěny na globální zásobník (predikátem put/2) a předávány jsou pouze adresy ■ formálním parametrem procedury jsou pouze volné proměnné, které se v hlavě vyskytují pouze jednou ■ všechny unifikace jsou explicitně zachyceny voláním predikátu unify/2 Hana Rudová, Logické programování I, 7. května 2010 16 Preklad Explicitní unifikace Pomocné termy a predikáty Příklad: append/3 s explicitní unifikací: append(AI, A2, A3) append(AI, A2, A3) unify(AI,[]), unify(A2,L), unify(A3,L). unify(AI,[A|X]), unify(A2,L), unify(A3,[A|Y]), put(X,Bl), put(L,B2), put(Y,B3), append(Bl,B2,B3). append([],L,L). append([A|X],L,[A|Y] append(X,L,Y). Cíl: parciálně vyhodnotit predikáty unify/2 a put/2 Hana Rudová, Logické programování I, 7. května 2010 1 term $addr$(A) - odkaz na objekt s adresou A 1 predikát is_addr(P,V) - je-li P ve tvaru $addr$(A), pak V se unifikuje s hodnotou slova na adrese A (jinak predikát selže) 1 predikát : = (X,T) - přiřadí volné proměnné X term T; X musí být volná proměnná. 1 predikát repres(A,Tag, V) - uloží do proměnné Tag příznak a do proměnné V hodnotu slova na adrese A. A musí být adresa na globálním zásobníku, Tag i V musí být volné proměnné. ■ příznak: informace o struktuře součástí objektu volná proměnná FREE, konstanta CONST, celé číslo INT, odkaz REF, složený term FUNCT 1 je-li A adresa a i celočíselná konstanta, pak výraz A+i reprezentuje adresu o i slov vyšší (ukazatelová aritmetika) Hana Rudová, Logické programování I, 7. května 2010 18 Prekla unify pro volnou proměnnou unify(A,T) unifikuje term na adrese A (aktuální parametr) s termem T (formální parametr). Podle hodnoty T mohou nastat následující 4 případy: 1) T je volná proměnná: výsledkem je instanciace unify(A.T) :- var(T), C var(A), create_var(A) ; true ), T := $addr$(A). Disjunkce garantuje, že Aje korektní adresa na globálním zásobníku: nutný run-time test, tedy nelze využít při pare. překladu. Lze proto přepsat na unify(A.T) :- var(T), uni fy_var(A,T). kde unify_var/2 vloží do T odkaz nebo založí novou proměnnou. unify pro konstantu 2) T je konstanta: výsledkem je test nebo přiřazení unify(A.T) :-atomic(T), C C var(A), create_var(A), instantiate_const(A,T) ) ; C repres(A,Tag,Value), Tag == 'FREE', instantiate_const(A,T) ; Tag == 'CONST', Value == T ) ). kde i nstanti ate_const/2 uloží do slova s adresou A hodnotu T. Opět možno přepsat do kompaktního tvaru unifyCA.T) :-atomic(T), unify_const(A,T)■ kde uni fy_const/2 provede příslušný test nebo přiřazení. Hana Rudová, Logické programování I, 7. května 2010 19 Preklad Hana Rudová, Logické programování I, 7. května 2010 20 unify pro složený term u ni fy pro odkaz 3) T je složený term: dvoufázové zpracování, v první fázi test nebo založení funktoru, v druhé rekurzivní unifikace argumentů unify(A.T) :-struct(T), f unctor(T,F,N), um'fy_struct(F,N,A), T =.. [_|T1], unify_args(Tl,A+1). Predikát uni fy_struct/3 je analogický výše použitým predikátům unify_var/2 a unify_const/2. Druhá fáze: unify_args([] ,_) . unify_args([T|T"l], A) :-um'fy(A,T) , unify_args(Tl,A+1). Hana Rudová, Logické programování I, 7. května 2010 4) Tje odkazem: nutno použít obecnou unifikaci (není žádná informace pro parciální vyhodnocení) unify(A,T) :- is_addr(T,P), unification(A,P). Hana Rudová, Logické programování I, 7. května 2010 put Parametry procedur jsou vždy umístěny na globální zásobník predikátem put/2 a předávány jsou pouze adresy. Predikát put/2 je jednodušší (nikdy nepotřebuje unifikaci) put(T,B) :- is_addr(T,B). % Tje odkaz put(T.B) :- var(T), % Tje proměnná create_var(B), T := $addr$(B). put(T.B) :- atomic(T), % Tje konstanta create_const(B,T). put(T.B) :- struct(T), % Tje struktura create_struct(B,T). Hana Rudová, Logické programování I, 7. května 2010 23 Preklad První klauzule append/3 Parciální vyhodnocení první klauzule programu append/3 append(Al, A2, A3) :- unify(AI,[]), | append([],L,L). unÍfy(A2,L), | unify(A3,L). | upraví unify(Al,[]) na unify_const(Al,[]) unify(A2,L) na L:=$addr$(A2) unify(A3,L) na is_addr(L,T), unification(T,A3) posloupnost L:=$addr$(A2) , is_addr(L,T) odpovídá přejmenování T na A2 => není nutné vytvářet novou proměnnout T => stačí provést unifi cation(A2 ,A3) Hana Rudová, Logické programování I, 7. května 2010 24 Preklad Výsledný tvar append/3 Jiný příklad appendCAl, A2, A3) :-unify_const(Al,[]), unification(A2,A3). appendCAl, A2, A3) :- fy_struct('.',2,A1), fy_var(A,Al+l), fy_var(X,Al+2), fy_var(L,A2), fy_struct('.',2,A3), fication(Al+l,A3+l), unify_var(Y,A3+2), append(Al+2,A2,A3+2). appendCAl, A2, A3) :- um'fyCAl, []) , um'fy(A2,L) , um'fy(A3,L). appendCAl, A2, A3) :- um'fyCAl, [A|X]) , um'fyCA2,L) , um'fyCA3, [A| Y]) , putCX.Bl), putCL,B2), putCY,B3), appendCBl,B2,B3). Většina původních unifikací převedena na jednodušší operace; unifikace v posledním kroku je nezbytná (důsledkem dvojího výskytu proměnné) Hana Rudová, Logické programování I, 7. května 2010 25 Preklad Warrenův abstraktní počítač, WAM I. Navržen D.H.D. Warrenem v roce 1 983, modifikace do druhé poloviny 80. let Datové oblasti: ■ Oblast kódu (programová databáze) ■ separátní oblasti pro uživatelský kód (modifikovatelný) a vestavěné predikáty (nemění se) ■ obsahuje rovněž všechny statické objekty (texty atomů a funktorú apod.) ■ Lokální zásobník (Stack) ■ Stopa (Trail) ■ Globální zásobník n. ba\da(Heap) ■ Pomocný zásobník (Push Down List, PDL) ■ pracovní paměť abstraktního počítače ■ použitý v unifikaci, syntaktické analýze apod. Hana Rudová, Logické programování I, 7. května 2010 a(c,s(f),d,X) :- g(X). Procedurální pseudokód (testy a přiřazení) a kód abstraktního počítače: a(AI, A2, A3, A4) :-unify_const(c,Al), unify_struct(s,l,A2), unify_const(f,A2+1), unify_const(d,A3), unify_var(A,A4), g(A4). proceduře a(X,Y,Z,A) is if ( x == 'c' && ( is_struct(Y,'s',1) && first_arg(Y) == 'f ) && Z == 'ď ) then call g(A) el se call fa-M end proceduře tj. posloupnost testů jako v procedurálním jazyce Vyzkoušejte si: delete(X, [Y|T], [Y|T1]) :- delete(X, T, TI). Hana Rudová, Logické programování I, 7. května 2010 26 Překlad Rozmístění datových oblastí Příklad konfigurace Halda Stopa T Zásobník PDL 1 Oblast kodu Halda i lokální zásobník musí růst stejným směrem ■ lze jednoduše porovnat stáří dvou proměnných srovnáním adres využívá se při zabránění vzniku visících odkazů Hana Rudová, Logické programování I, 7. května 2010 Registry WAMu Typy instrukcí WAMu ■ Stavové registry: P čitač adres (Program counter) CP adresa návratu (Continuation Pointer) E ukazatel na nejmladší okolí (Environment) B ukazatel na nejmladší bod volby (Backtrack point) TR vrchol stopy (TRail) H vrchol haldy (Heap) HB vrchol haldy v okamžiku založení posledního bodu volby (Heap on Backtrack point) S ukazatel, používaný při analýze složených termů (Structure pointer) CUT ukazatel na bod volby, na který se řezem zařízne zásobník ■ Argumentové registry: A1,A2 , . . . (při předávání parametrů n. pracovní registry) ■ Registry pro lokální proměnné: Y1.Y2, . . . ■ abstraktní znázornění lok. proměnných na zásobníku Hana Rudová, Logické programování I, 7. května 2010 29 Preklad ■ put instrukce - příprava argumentů před voláním podcíle ■ žádná z těchto instrukcí nevolá obecný unifikační algoritmus ■ get instrukce - unifikace aktuálních a formálních parametrů ■ vykonávají činnost analogickou instrukcím unify u pare. vyhodnocení ■ obecná unifikace pouze při get_value ■ unify instrukce - zpracování složených termů ■ jednoargumentové instrukce, používají registr S jako druhý argument ■ počáteční hodnota S je odkaz na 1. argument ■ volání instrukce unify zvětší hodnotu S o jedničku ■ obecná unifikace pouze při unify_value a unify_local_value ■ Indexační instrukce - indexace klauzulí a manipulace s body volby ■ Instrukce řízení běhu - předávání řízení a explicitní manipulace s okolím Hana Rudová, Logické programování I, 7. května 2010 30 Preklad Instrukce put a get: příklad Instrukce WAMu Příklad: a(X,Y,Z) :- b(f,X,Y,Z). get instrukce get_var Ai,Y put instrukce put_var Ai,Y unify instrukce unify_var Y get_var A1.A5 get_value Ai ,Y put_value Ai ,Y unify_value Y get_var A2.A6 get_const Ai,C put_unsafe_value Ai,Y unify_local_value Y get_var A3.A7 get_nil Ai put_const Ai ,C unify_const C put_const Al,f get_struct Ai,F/N put_ni1 Ai unify_nil put_value A2.A5 get_list Ai put_struct Ai,F/N unify_void N put_value A3.A6 put_li St Ai put_value A4.A7 instrukce řízení indexační instrukce execute b/4 allocate try_me_else Next try Next deallocate retry_me_el se Next retry Next call Proc/N,A trust_me_el se fail trust fail execute Proc/N proceed cut_last switch_on_ term Var,Const,List.Struct save_cut Y switch_on_ const Table load_cut Y switch_on_ struct Table Hana Rudová, Logické programování I, 7. května 2010 Hana Rudová, Logické programování I, 7. května 2010 Instrukce unify, get, put WAM - indexace ■ Větší počet typů objektů ■ rozlišeny atomy, čísla, ni 1 = prázdný seznam, seznam speciální druh složeního termu ■ unify_void umožní přeskočit anonymních proměnné ve složených termech ■ put_unsafe_val ue pro optimalizaci práce s lokálními proměnnými při TRO ■ a(X) :- b(X,Y), !, a(Y) . při TRO nesmí být lokální proměnné posledního literálu (Y) na lokálním zásobníku ■ kompilátor může všechny nebezpečné (unsafe) výskyty lok. proměnných detekovat při překladu (jsou to poslední výskyty lok. proměnných) a generuje složitější instrukce put_unsafe_value, které provádějí test umístění ■ um'fy_"loca"l_va"lue kvůli TRO jako put_unsafe_value ■ a(X) :- d(X), b(s(Y),X). objekt přístupný přes Y opět nesmí být na lok. zásobníku doba života s/l může být delší než doba života okolí na něž se Y odkazuje ■ unify_local_value testují umístění a pokud nutné přesouvají objekty na haldu Hana Rudová, Logické programování I, 7. května 2010 33 Preklad ■ Provázání klauzulí: instrukce XX_me_el se: ■ první klauzule: try_me_else; založí bod volby ■ poslední klauzule: trust_me_else; zruší nejmladší bod volby ■ ostatní klauzule: retry_me_el se; znovu použije nejmladší bod volby po neúspěchu ■ Provázání podmnožiny klauzulí (podle argumentu): ■ try ■ retry ■ trust ■ „Rozskokové" instrukce (dle typu a hodnoty argumentu): ■ switch_on_term Var, Const, List, Struct výpočet následuje uvedeným návěstím podle typu prvního argumentu ■ switch_on_YY: hashovací tabulka pro konkrétní typ (konstanta, struktura) Hana Rudová, Logické programování I, 7. května 2010 34 Preklad Příklad indexace instrukcí Proceduře a(atom) :- bodyl. a(l) :- body2. a(2) :- body3. odpovídají instrukce a([X|Y]) a([X|Y]) aCs(N)) : a(f(N)) : - body4. - body5. body6. bodyľ. WAM - řízení výpočtu execute Proč: ekvivalentní příkazu goto proceed: zpracování faktů aTlocate: alokuje okolí (pro některé klauzule netřeba, proto explicitně generováno) deallocate: uvolní okolí (je-li to možné, tedy leží-li na vrcholu zásobníku) cal 1 Proč, N: zavolá Proč, N udává počet lok. proměnných (odpovídá velikosti zásobníku) a: switch_on_term LI, L2, L3, L4 L5a: body2 Možná optimalizace: vhodným uspořádáním proměnných L2: switch_on_const atom 1 :Lla :L5a L6: L6a: retry. body3 _me_ _el se L7 lze dosáhnout postupného zkracováni a(A,B,C,D) :- b(D), c(A,C), d(B), e(A), f. 2 :L6a L7: retry. _me_ _el se L8 generujeme instrukce allocate L3: try L7a L7a: body4 call b/1,4 trust L8a L8: retry. _me_ _el se L9 call c/2,3 L4: switch_on_struct s/l :L9a L8a: body5 call d/1,2 f/1 :L10a L9: retry. _me_ _el se L10 call e/1,1 LI: try_me_else L5 L9a: body6 deallocate Lla: bodyl L10: trust. _me_ _el se fail execute f/0 L5: Hana retry_me_else L6 Rudová, Logické programování 1, 7. května 2010 LlOa: 35 bodyľ Preklad Hana Rudová, Logické programování 1, 7. května 2010 36 WAM - řez WAM - optimalizace Implementace řezu (opakování): odstranění bodů volby mezi současným vrcholem zásobníku a bodem volby procedury, která řez vyvolala (včetně bodu volby procedury s řezem) Indexační instrukce znemožňují v době překladu rozhodnout, zda bude alokován bod volby ■ příklad: ?- a(X) . může být nedeterministické, ale ?- a(l) . může být deterministické cut_last: B := CUT save_cut Y: Y := CUT 1oad_cut Y: B := Y Hodnota registru B je uchovávána v registru CUT instrukcemi cal 1 a execute. Je-li řez prvním predikátem klauzule, použije se rovnou cut_last. V opačném případě se použije jako první instrukce save_cut Y a v místě skutečného volání řezu se použije 1oad_cut Y. Příklad: a(X,Z) :- b(X), !, c(Z). a(2,Z) :- !, c(Z). a(X,Z) :- d(X,Z). odpovídá save_cut Y2; get A2.Y1; call b/1,2; 1oad_cut Y2; put Yl.Al; execute c/1 get_const AI,2; cut_last; put A2.A1; execute c/1 execute d/2 Hana Rudová, Logické programování I, 7. května 2010 37 Překlad 1. Indexace klauzulí 2. Generování optimální posloupnosti instrukcí WAMu 3. Odstranění redundancí při generování cílového kódu. ■ Příklad: a(X,Y,Z) :- b(f,X,Y,Z). naivní kód (vytvoří kompilátor pracující striktně zleva doprava) vs. optimalizovaný kód (počet registrů a tedy i počet instrukcí/přesunů v paměti snížen): get_var A1.A5 | get_var A3.A4 get_var A2.A6 | get_var A2.A3 get_var A3.A7 | get_var A1.A2 put_const AI,f | put_const AI,f put_value A2.A5 | execute b/4 put_value A3.A6 1 put_value A4.A7 1 execute b/4 | Hana Rudová, Logické programování I, 7. května 2010 38