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, 13. května 2011 3 Implementace Prologu Hana Rudová, Logické programování 1,13. května 2011 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í 1,13. května 2011 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, 1 3. května 2011 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í 1,13. května 2011 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, 13. května 2011 7 Implementace Prologu Hana Rudová, Logické programování I, 13. května 2011 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í 1,13. května 2011 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í 1,13. května 2011 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, 13. května 2011 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, 13. května 2011 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, 13. května 2011 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, 13. května 2011 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, 13. května 2011 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í 1,13. května 2011 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, 13. května 2011 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, 13. května 2011 19 Preklad Hana Rudová, Logické programování I, 13. května 2011 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, 1 3. května 2011 21 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í 1,13. května 2011 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í 1,13. května 2011 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, 13. května 2011 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, 13. května 201 1 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í 1,13. května 2011 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í 1,13. května 2011 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í 1,13. května 2011 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í 1,13. května 2011 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_va"lue ■ 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_va"lue a unify_1oca"l_va"lue ■ 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, 13. května 2011 30 Preklad Instrukce put a get: příklad Příklad: a(X,Y,Z) b(f,X,Y,Z). get_var A1.A5 get_var A2.A6 get_var A3.A7 put_const AI,f put_va"lue A2.A5 put_va"lue A3.A6 put_va"lue A4.A7 execute b/4 Hana Rudová, Logické programování 1,13. května 2011 WAM - optimalizace 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 get_var get_var A1.A5 A2.A6 A3.A7 put_const AI, f put_va"lue A2.A5 put_va"lue A3.A6 put_va"lue A4.A7 execute b/4 get_var get_var get_var put_const execute A3.A4 A2.A3 A1.A2 AI,f b/4 Hana Rudová, Logické programování 1,13. května 2011 Instrukce WAMu WAM - indexace get instrukce put instrukce unify instrukce get_var Ai,Y put_var Ai ,Y unify_var Y get_value Ai ,Y put_value Ai ,Y unify_value Y get_const Ai,C put_unsafe_value Ai,Y unify_local_value Y get_nil Ai put_const Ai ,C unify_const C get_struct Ai,F/N put_ni1 Ai u n i fy_n i1 get_list Ai put_struct Ai,F/N unify_void N put_li St Ai instrukce řízení indexační instrukce allocate try_me_else Next try Next deallocate retry_me_else Next retry Next call Proc/N,A trust_me_else 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í 1,13. května 2011 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, 13. května 2011 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(fCN)) : - body4. - body5. body6. bodyľ. a: switch_on_term LI, L2, L3, L4 L5a: body2 L2: switch_on_const atom :Lla L6: retry. _me_ _el se L7 1 :L5a L6a: body3 2 :L6a L7: retry. _me_ _el se L8 L3: try L7a L7a: body4 trust L8a L8: retry. _me_ _el se L9 L4: switch_on_struct s/l :L9a L8a: body5 f/1 :LlOa L9: retry. _me_ _el se L10 LI: try_me_else L5 L9a: body6 Lla: bodyl L10: trust. _me_ _el se fail L5: retry_me_else L6 LlOa bodyľ Hana Rudová, Logické programování 1,13. května 2011 35 WAM - řízení výpočtu 1 execute Proč: ekvivalentní příkazu goto 1 proceed: zpracování faktů 1 allocate: alokuje okolí (pro některé klauzule netřeba, proto explicitně generováno) 1 deallocate: uvolní okolí (je-li to možné, tedy leží-li na vrcholu zásobníku) 1 cal 1 Proč, N: zavolá Proč, N udává počet lok. proměnných (odpovídá velikosti zásobníku) Možná optimalizace: vhodným uspořádáním proměnných lze dosáhnout postupného zkracování lokálního zásobníku a(A,B,C,D) :- b(D), c(A,C), d(B), e(A), f. generujeme instrukce allocate call b/1,4 call c/2,3 call d/1,2 call e/1,1 deallocate execute f/0 Hana Rudová, Logické programování I, 13. května 2011 36 Prekl