Implementace Prologu (pokračování) Interpret Prologu Základní principy: M klauzule uloženy jako termy -• programová databáze M pro uložení klauzulí M má charakter haldy v umožňuje modifikovatelnost prologovských programů za běhu (assert) -• klauzule zřetězeny podle pořadí načtení 3 triviální zřetězení Hana Rudová, Logické programování I, 20. května 2009 2 Implementace Prologu Interpret Prologu Základní principy: M klauzule uloženy jako termy -• programová databáze M pro uložení klauzulí M má charakter haldy v umožňuje modifikovatelnost prologovských programů za běhu (assert) -• klauzule zřetězeny podle pořadí načtení 3 triviální zřetězení Vyhodnocení dotazu: volání procedur řízené unifikací Hana Rudová, Logické programování I, 20. května 2009 2 Implementace Prologu Interpret - Základní princip 1. Vyber redukovaný literal („první", tj. nejlevější literal 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ý literal 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) Hana Rudová, Logické programování I, 20. května 2009 3 Implementace Prologu Interpret - Základní princip 1. Vyber redukovaný literal („první", tj. nejlevější literal 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ý literal 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 literalu a hlavy klauzule 6. Úspěch => přidej všechny literaly klauzule k cíli („doleva", tj. na místo redukovaného literalu). 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. Hana Rudová, Logické programování I, 20. května 2009 3 Implementace Prologu 03 Interpret - Základní princip 1. Vyber redukovaný literal („první", tj. nejlevější literal 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ý literal 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 literalu a hlavy klauzule 6. Úspěch => přidej všechny literaly klauzule k cíli („doleva", tj. na místo redukovaného literalu). 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 literaly v cíli. Hana Rudová, Logické programování I, 20. května 2009 3 Implementace Prologu 03 Interpret - vlastnosti -• Lokální i globální zásobník -• při dopředném výpočtu roste M 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. Hana Rudová, Logické programování I, 20. května 2009 4 Implementace Prologu Interpret - vlastnosti -• Lokální i globální zásobník -• při dopředném výpočtu roste M 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. Hana Rudová, Logické programování I, 20. května 2009 4 Implementace Prologu Interpret - vlastnosti -• Lokální i globální zásobník -• při dopředném výpočtu roste M 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 instanciovanych proměnných na stopu. -• „Interpret": interpret(Query, Vars) :- call(Query), success(Query, Vars). interpret(_,_) :- failure. 3 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, 20. května 2009 4 Implementace Prologu Optimalizace: Indexace M 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) 3 tj., indexace procedur -• Hash tabulka pro vyhledání první klauzule -• Možno rozhodnout (parciálně) determinismus procedury Hana Rudová, Logické programování I, 20. května 2009 5 Implementace Prologu Indexace argumentů a(l) :- q(l). 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) Hana Rudová, Logické programování I, 20. května 2009 6 Implementace Prologu Indexace argumentů a(l) :- q(l). 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í: M podle pořadí klauzulí (aktuální argument je volná proměnná) -• dle konstant (aktuální je argument konstanta) M formální argument je seznam (aktuální argument je seznam) «• dle struktur (aktuální argument je struktura) Hana Rudová, Logické programování I, 20. května 2009 6 Implementace Prologu Indexace argumentů II -• Složitější indexační techniky M podle všech argumentů 3 podle nejvíce diskriminujícího argumentu M kombinace argumentů (indexové techniky z databází) -i* zejména pro přístup k faktům Hana Rudová, Logické programování I, 20. května 2009 7 Tail Recursion Optimization, TRO Iterace prováděna pomocí rekurze => lineární paměťová náročnost cyklů Hana Rudová, Logické programování I, 20. května 2009 8 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í) M 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, 20. května 2009 8 Implementace Prologu 63 TRO - příklad Program: append([], L, L). append([A|X], L, [A|Y]) :- append(X, L, Y). Dotaz: ?- append([a,b,c], [x], L). Hana Rudová, Logické programování I, 20. května 2009 9 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 M s TRO: 1 okolí, konstatní paměťová náročnost Hana Rudová, Logické programování I, 20. května 2009 9 Implementace Prologu Optimalizace posledního volání TRO pouze speciální případ obecné optimalizace posledního volání (Last Call Optimization), LCO Hana Rudová, Logické programování I, 20. května 2009 10 Implementace Prologu 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. Hana Rudová, Logické programování I, 20. května 2009 10 Implementace Prologu 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ů M vždy „mladší" ukazuje na „starší" („mladší" budou odstraněny dříve) M 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í Hana Rudová, Logické programování I, 20. května 2009 10 Implementace Prologu 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ů M vždy „mladší" ukazuje na „starší" („mladší" budou odstraněny dříve) M 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í M „globalizace" lokálních proměnných: lokální proměnné posledního literálu M nutno přesunout na globální zásobník -• pouze pro neinstanciované proměnné Hana Rudová, Logické programování I, 20. května 2009 10 Implementace Prologu Překlad Překlad -• Motivace: 3 dosažení vyšší míry optimalizace 3 kompaktní kód 3 částečná nezávislost na hardware Hana Rudová, Logické programování I, 20. května 2009 12 Překlad -• Motivace: 3 dosažení vyšší míry optimalizace 3 kompaktní kód 3 čá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 Hana Rudová, Logické programování I, 20. května 2009 12 Překlad -• Motivace: 3 dosažení vyšší míry optimalizace 3 kompaktní kód 3 čá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: 3 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 Hana Rudová, Logické programování I, 20. května 2009 12 Preklad Překlad -• Motivace: 3 dosažení vyšší míry optimalizace 3 kompaktní kód 3 čá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: 3 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, 20. května 2009 12 Preklad Parciální vyhodnocení -• Jak navrhnout Warrenův abstraktní počítač? M prostřednictvím parciálního vyhodnocení -• Parciální vyhodnocení -• forma zpracování programu, tzv. transformace na úrovni zdrojového kódu M dosazení známých hodnot vstupních parametrů a vyhodnocení všech operací nad nimi -i* příklad: vyhodnocení aritmetických výrazů nad konstantami Hana Rudová, Logické programování I, 20. května 2009 13 Parciální vyhodnocení - příklad 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). Hana Rudová, Logické programování I, 20. května 2009 14 Preklad Parciální vyhodnocení - příklad 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'(l). a nový dotaz ?- a'(Z). Hana Rudová, Logické programování I, 20. května 2009 14 Preklad Parciální vyhodnocení - příklad 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'(l). 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, 20. května 2009 14 Preklad Parciální vyhodnocení II Konstrukce překladače: parciálním vyhodnocením interpretu Problémy: -• příliš složitá operace M 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 jazyka jako implementačního jazyka interpretu Hana Rudová, Logické programování I, 20. května 2009 15 Preklad Parciální vyhodnocení II Konstrukce překladače: parciálním vyhodnocením interpretu Problémy: -• příliš složitá operace M 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 jazyka jako 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, 20. května 2009 15 Preklad Parciální vyhodnocení Prologu Cílová operace: unifikace. Důvod: M řízení výpočtu poměrně podrobné i v interpretu M unifikace v interpretu atomickou operací M unifikace v interpretu nahrazuje řadu podstatně jednodušších operací (testy, přiřazení, předání a převzetí parametrů ...) M většina unifikací nevyžaduje obecnou unifikaci a lze je nahradit jednoduššími operacemi Hana Rudová, Logické programování I, 20. května 2009 16 Preklad Parciální vyhodnocení Prologu Cílová operace: unifikace. Důvod: M řízení výpočtu poměrně podrobné i v interpretu M unifikace v interpretu atomickou operací M unifikace v interpretu nahrazuje řadu podstatně jednodušších operací (testy, přiřazení, předání a převzetí parametrů ...) M většina unifikací nevyžaduje obecnou unifikaci a lze je nahradit jednoduššími operacemi Zviditelnění unifikace: transformací zdrojového programu M termy reprezentujeme kopírováním struktur na globálním zásobníku M 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 M formálním parametrem proceduryjsou pouze volné proměnné, které se v hlavě vyskytují pouze jednou M všechny unifikace jsou explicitně zachyceny voláním predikátu unify/2 Hana Rudová, Logické programování I, 20. května 2009 16 Preklad Explicitní unifikace Příklad: append/3 s explicitní unifikací: append(Al, A2, A3) :- unify(Al,[]), | append([],L,L). unify(A2,L), | unify(A3,L). Hana Rudová, Logické programování I, 20. května 2009 17 Preklad Explicitní unifikace Příklad: append/3 s explicitní unifikací: append(Al, A2, A3) append(Al, A2, A3) - unify(Al,[]), unify(A2,L) , unify (A3, L) . - unify(Al,[A|X]), unify(A2,L), unify(A3,[A|Y]), put(X,BI), put(L,B2), put(Y,B3), append(Bl,B2,B3) append([],L,L). append([A|X],L,[A|Y] append(X,L,Y). Hana Rudová, Logické programování I, 20. května 2009 17 Preklad Explicitní unifikace Příklad: append/3 s explicitní unifikací: append(Al, A2, A3) append(Al, A2, A3) - unify(Al,[]), unify(A2,L) , unify (A3, L) . - unify(Al,[A|X]), unify(A2,L), unify(A3,[A|Y]), put(X,BI), 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, 20. května 2009 17 Preklad Pomocné termy a predikáty -• term $addr$(A) - odkaz na objekt s adresou A -• 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) -• predikát : = (X,T) - priradí volné proměnné X term T; X musí být volná proměnná. Hana Rudová, Logické programování I, 20. května 2009 18 Preklad Pomocné termy a predikáty -• term $addr$(A) - odkaz na objekt s adresou A -• 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) -• predikát : = (X,T) - priradí volné proměnné X term T; X musí být volná proměnná. M predikát repres(A,Tag,V) - uloží do proměnné Tag prí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é. 3 příznak: informace o struktuře součástí objektu volná proměnná FREE, konstanta CONST, celé číslo INT, odkaz REF, složený term FUNCT Hana Rudová, Logické programování I, 20. května 2009 18 Preklad Pomocné termy a predikáty -• term $addr$(A) - odkaz na objekt s adresou A -• 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) -• predikát : = (X,T) - priradí volné proměnné X term T; X musí být volná proměnná. M predikát repres(A,Tag,V) - uloží do proměnné Tag prí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é. 3 příznak: informace o struktuře součástí objektu volná proměnná FREE, konstanta CONST, celé číslo INT, odkaz REF, složený term FUNCT -• 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, 20. května 2009 18 Preklad 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), ( var(A), create_var(A) I true ), T := $addr$(A). Hana Rudová, Logické programování I, 20. května 2009 19 Preklad 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), ( var(A), create_var(A) I true ), T := $addr$(A). Disjunkce garantuje, že A je 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), unify_var(A,T). kde unify_var/2 vloží do T odkaz nebo založí novou proměnnou. Hana Rudová, Logické programování I, 20. května 2009 19 Preklad unify pro konstantu 2) T je konstanta: výsledkem je test nebo přiřazení unify(A,T) :-atomic(T), ( ( var(A), create_var(A), instantiate_const(A,T) ) ; ( repres(A,Tag,Value), Tag == 'FREE', instantiate_const(A,T) ; Tag == 'CONST', Value == T ) )■ kde instantiate_const/2 uloží do slova s adresou A hodnotu T. Hana Rudová, Logické programování I, 20. května 2009 20 Preklad unify pro konstantu 2) T je konstanta: výsledkem je test nebo přiřazení unify(A,T) :-atomic(T), ( ( var(A), create_var(A), instantiate_const(A,T) ) ; ( repres(A,Tag,Value), Tag == 'FREE', instantiate_const(A,T) ; Tag == 'CONST', Value == T ) )■ kde instantiate_const/2 uloží do slova s adresou A hodnotu T. Opět možno přepsat do kompaktního tvaru unify(A,T) :-atomic(T), unify_const(A,T). kde unify_const/2 provede příslušný test nebo přiřazení. Hana Rudová, Logické programování I, 20. května 2009 20 Preklad unify pro složený term 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), functor(T,F,N), unify_struct(F,N,A), T =.. [_|T1], unify_args(Tl,A+1). Predikát unify_struct/3 je analogický výše použitým predikátům unify_var/2 a unify_const/2. Hana Rudová, Logické programování I, 20. května 2009 21 Preklad unify pro složený term 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), functor(T,F,N), unify_struct(F,N,A), T =.. [_|T1], unify_args(Tl,A+1). Predikát unify_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|Tl], A) :-urvi f y (A ,T), unify_args(Tl,A+1). Hana Rudová, Logické programování I, 20. května 2009 21 Preklad unify pro odkaz 4) T je 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, 20. května 2009 22 Preklad 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). %Tjeodkaz 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, 20. května 2009 23 Preklad První klauzule append/3 Parciální vyhodnocení první klauzule programu append/3 append(Al, A2, A3) :- unify(Al,[]), | append([],L,L). unify(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) Hana Rudová, Logické programování I, 20. května 2009 24 Preklad První klauzule append/3 Parciální vyhodnocení první klauzule programu append/3 append(Al, A2, A3) :- unify(Al,[]), | append([],L,L). unify(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 Hana Rudová, Logické programování I, 20. května 2009 24 Preklad První klauzule append/3 Parciální vyhodnocení první klauzule programu append/3 append(Al, A2, A3) :- unify(Al,[]), | append([],L,L). unify(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ěnnoutT => stačí provést unification(A2 ,A3) Hana Rudová, Logické programování I, 20. května 2009 24 Preklad Výsledný tvar append/3 append(Al, A2, A3) :-unify_const(Al,[]), unification(A2 ,A3) . append(Al, A2, A3) :- unify_struct('.',2,Al), unify_var(A,Al+l), unify_var(X,Al+2), unify_var(L,A2), unify_struct('.',2,A3), unification(Al+l,A3+l) , unify_var(Y,A3+2), append(Al+2,A2,A3+2). append(Al, A2, A3) :- unify(Al,[]), unify(A2,L), unify(A3,L) append(Al, A2, A3) :- unify(Al,[A|X]), unify(A2,L), unify (A3, [A | Y]), put(X,Bl), put(L,B2), put(Y,B3), append(Bl,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, 20. května 2009 25 Preklad Jiný příklad a(c,s(f),d,X) :- g(X). Procedurální pseudokod (testy a přiřazení) a kód abstraktního počítače: 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) else a(Al, 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). cal 1 f ai 1 end procedure tj. posloupnost testů jako v procedurálním jazyce Hana Rudová, Logické programování I, 20. května 2009 26 Preklad Jiný příklad a(c,s(f),d,X) :- g(X). Procedurální pseudokod (testy a přiřazení) a kód abstraktního počítače: 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) else a(Al, 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). cal 1 f ai 1 end procedure 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, 20. května 2009 26 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) 3 obsahuje rovněž všechny statické objekty (texty atomů a funktorů apod.) -• Lokální zásobník (Stack) M Stopa (Trail) M Globální zásobník n. ha\da(Heap) M Pomocný zásobník (Push Down List, POL) M pracovní paměť abstraktního počítače M použitý v unifikaci, syntaktické analýze apod. Hana Rudová, Logické programování I, 20. května 2009 27 Preklad Rozmístění datových oblastí Příklad konfigurace Halda v A Stopa Zásobník v A PDL Oblast kódu 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, 20. května 2009 28 Preklad Registry 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 M Argumentové registry: A1,A2 , . . . (při předávání parametrů n. pracovní registry) -• Registry pro lokální proměnné: Yl, Y2, . . . M abstraktní znázornění lok. proměnných na zásobníku Hana Rudová, Logické programování I, 20. května 2009 29 Preklad Typy instrukcí WAMu -• put instrukce - příprava argumentů před voláním podcíle -• žádná z těchto instrukcí nevolá obecný unifikační algoritmus M get instrukce - unifikace aktuálních a formálních parametrů 3 vykonávají činnost analogickou instrukcím unify u pare. vyhodnocení -• obecná unifikace pouze při get_value M 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 M volání instrukce unify zvětší hodnotu S o jedničku M obecná unifikace pouze při unify_value a unify_local_value M Indexační instrukce - indexace klauzulí a manipulace s body volby -• Instrukce řízení běhu - předávání řízení a explicitní manipulace s okolí Hana Rudová, Logické programování I, 20. května 2009 30 Instrukce pu 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 Al,f put_value A2,A5 put_value A3,A6 put_value A4,A7 execute b/4 Hana Rudová, Logické programování I, 20. května 2009 t a get: příklad 31 Preklad Instrukce WAMu get instrukce get_var Ai,Y get_value Ai,Y get_const Ai,C get_ni1 Ai get_struct Ai,F/N get_list Ai put instrukce put_var Ai,Y put_value Ai,Y put_unsafe_value Ai ,Y put_const Ai,C put_ni1 Ai put_struct Ai,F/N put_list Ai unify instrukce unify_var Y unify_value Y unify_local_value Y unify_const C unify_nil unify_void N instrukce řízení allocate deallocate call Proc/N,A execute Proc/N proceed indexační instrukce try_me_else Next retry_me_else Next trust_me_else fail try Next retry Next trust fail 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, 20. května 2009 32 Preklad Instrukce unify, get, put -• Větší počet typů objektů -• rozlišeny atomy, čísla, ni 1 = prázdný seznam, seznam speciální druh složeního termu M 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 3 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 3 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í Hana Rudová, Logické programování I, 20. května 2009 33 Preklad Instrukce unify, get, put -• Větší počet typů objektů -• rozlišeny atomy, čísla, ni 1 = prázdný seznam, seznam speciální druh složeního termu M 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 3 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 3 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í -• unify_local_value kvůli TRO jako put_unsafe_value 3 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 M unify_local_value testují umístění a pokud nutné přesouvají objekty na haldu Hana Rudová, Logické programování I, 20. května 2009 33 Preklad WAM - indexace -• Provázání klauzulí: instrukce XX_me_else: M první klauzule: try_me_else; založí bod volby 3 poslední klauzule: trust_me_else; zruší nejmladší bod volby -• ostatní klauzule: retry_me_else; znovu použije nejmladší bod volby po neúspěchu Hana Rudová, Logické programování I, 20. května 2009 34 Preklad WAM - indexace -• Provázání klauzulí: instrukce XX_me_else: M první klauzule: try_me_else; založí bod volby 3 poslední klauzule: trust_me_else; zruší nejmladší bod volby -• ostatní klauzule: retry_me_else; znovu použije nejmladší bod volby po neúspěchu -• Provázání podmnožiny klauzulí (podle argumentu): «• try M retry .# trust Hana Rudová, Logické programování I, 20. května 2009 34 Preklad WAM - indexace -• Provázání klauzulí: instrukce XX_me_else: M první klauzule: try_me_else; založí bod volby 3 poslední klauzule: trust_me_else; zruší nejmladší bod volby -• ostatní klauzule: retry_me_else; znovu použije nejmladší bod volby po neúspěchu -• Provázání podmnožiny klauzulí (podle argumentu): «• try M retry .# trust M „Rozskokové" instrukce (dle typu a hodnoty argumentu): M switch_on_term Var, Const, List, Struct výpočet následuje uvedeným návěstím podle typu prvního argumentu M switch_on_YY: hashovací tabulka pro konkrétní typ (konstanta, struktura) Hana Rudová, Logické programování I, 20. května 2009 34 Preklad Příklad indexace instrukcí Proceduře a(atom) :- bodyl. a(l) :- body2. a(2) :- body3. a([X|Y]) a([X|Y]) a(s(N)) a(f(N)) - body4 - body5 body6. bodyľ. odpovídají instrukce a: switch. _on_term L 1, LZ, Li, L2: switch. _on_const atom 1 2 Lla L5a L6a L3: try trust L7a L8a L4: switch. _on_struct s/1 f/1 L9a LlOa LI: try_me_ .else L5 Lla: bodyl L5: retry_me_else L6 Hana Rudová, Logické programování I, 20. května 2009 35 L5a: body2 L6: retry_me_ .else L7 L6a: body3 L7: retry_me_ .else L8 L7a: body4 L8: retry_me_ .else L9 L8a: body5 L9: retry_me_ .else L10 L9a: body6 L10: trust_me_ .else fail LlOa: bodyľ Preklad WAM - řízení M execute Proč: ekvivalentní příkazu goto Hana Rudová, Logické programování I, 20. května 2009 36 výpočtu Preklad WAM - řízení M execute Proč: ekvivalentní příkazu goto & proceed: zpracování faktů Hana Rudová, Logické programování I, 20. května 2009 36 výpočtu Preklad WAM - řízení výpočtu M execute Proč: ekvivalentní příkazu goto & proceed: zpracování faktů M allocate: alokuje okolí (pro některé klauzule netřeba, proto explicitně generováno) Hana Rudová, Logické programování I, 20. května 2009 36 Preklad WAM - řízení výpočtu M execute Proč: ekvivalentní příkazu goto & proceed: zpracování faktů M allocate: alokuje okolí (pro některé klauzule netřeba, proto explicitně generováno) M deal 1 ocate: uvolní okolí (je-li to možné, tedy leží-li na vrcholu zásobníku) M call Proč,N: zavolá Proč, N udává počet lok. proměnných (odpovídá velikosti zásobní Hana Rudová, Logické programování I, 20. května 2009 36 WAM - řízení výpočtu M execute Proč: ekvivalentní příkazu goto & proceed: zpracování faktů M allocate: alokuje okolí (pro některé klauzule netřeba, proto explicitně generováno) M deal 1 ocate: uvolní okolí (je-li to možné, tedy leží-li na vrcholu zásobníku) M call Proč,N: zavolá Proč, N udává počet lok. proměnných (odpovídá velikosti zásobní 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, 20. května 2009 36 WAM - řez 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 M příklad: ?- a(X) . může být nedeterministické, ale ?- a(l) . může být deterministické Hana Rudová, Logické programování I, 20. května 2009 37 Preklad WAM - řez 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 M 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 load_cut Y: B := Y Hana Rudová, Logické programování I, 20. května 2009 37 Preklad WAM - řez 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 M 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 load_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 load_cut Y. Hana Rudová, Logické programování I, 20. května 2009 37 Preklad WAM - řez 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 M 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 load_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 load_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; load_cut Y2; put Y1.A1; execute c/1 get_const AI,2; cut_last; put A2,A1; execute c/1 execute d/2 Hana Rudová, Logické programování I, 20. května 2009 37 Preklad 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. Hana Rudová, Logické programování I, 20. května 2009 38 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 A1,A5 get_var A2,A6 get_var A3,A7 put_const Al,f put_value A2,A5 put_value A3,A6 put_value A4,A7 execute b/4 get_var A3, A4 get_var A2,A3 get_var A1,A2 put_const Al,f execute b/4 Hana Rudová, Logické programování I, 20. května 2009 38 Preklad