plementace Prologu (pokračování)
Interpret Prologu
Základní principy:
M 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í
M triviální zřetězení
Hana Rudová, Logické programování I, 16. května 201 2
2
Implementace Prologu
Interpret Prologu
Základní principy:
M 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í
M triviální zřetězení
Vyhodnocení dotazu: volání procedur řízené unifikací
Hana Rudová, Logické programování I, 16. května 201 2
2
Implementace Prologu
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)
Hana Rudová, Logické programování I, 16. května 201 2
3
Implementace Prologu
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.
Hana Rudová, Logické programování I, 16. května 201 2
3
Implementace Prologu
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í 1,16. května 201 2 3 Implementace Prologu
Interpret - vlastnosti
3 Lokální i globální zásobník
M 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 deterministické procedury.
dopředném úspěšném výpočtu
Hana Rudová, Logické programování I, 16. května 201 2
4
Implementace Prologu
Interpret - vlastnosti
3 Lokální i globální zásobník
M 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, 16. května 201 2
4
Implementace Prologu
Interpret - vlastnosti
3 Lokální i globální zásobník
M 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.
M „Interpret":
interpret(Query, Vars) :- call(Query), success(Query, Vars). interpret(_,_) :- failure.
3 dotaz vsazen do kontextu této speciální nedeterministické procedury
M tato procedura odpovídá za korektní reakci systému v případě úspěchu i neúspěchu
Hana Rudová, Logické programování 1,16. května 2012 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) tj., indexace procedur
Hash tabulka pro vyhledání první klauzule M Možno rozhodnout (parciálně) determinismus procedury
Hana Rudová, Logické programování I, 16. května 201 2
5
Implementace Prologu
Indexace argumentů
a(l) :- q(l). a(a) :- b(X). a([A|T]) :- c(A,T).
M Obecně nedeterministická
M 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, 16. května 201 2
6
Implementace Prologu
Indexace argumentů
a(l) :- q(l). a(a) :- b(X). a([A|T]) :- c(A,T).
M Obecně nedeterministická
M Při volání s alespoň částečně instanciovaným argumentem vždy deterministická (pouze jedna klauzule může uspět)
-0 Indexace podle prvního argumentu
Základní typy zřetězení:
M podle pořadí klauzulí (aktuální argument je volná proměnná) 3 dle konstant (aktuální je argument konstanta) M formální argument je seznam (aktuální argument je seznam) M dle struktur (aktuální argument je struktura)
Hana Rudová, Logické programování 1,16. května 2012 6 Implementace Prologu
Indexace argumentů II
Složitější indexační techniky
3 podle všech argumentů M podle nejvíce diskriminujícího argumentu M kombinace argumentů (indexové techniky z databází) J> zejména pro přístup k faktům
Hana Rudová, Logické programování 1,16. května 201 2
7
Implementace Prologu
Tail Recursion Optimization, TRO
Iterace prováděna pomocí rekurze => lineární paměťová náročnost cyklů
Hana Rudová, Logické programování I, 16. května 201 2
8
Implementace Prologu
Tail Recursion Optimization, TRO
Iterace prováděna pomocí rekurze => lineární paměťová náročnost cyklů
Optimalizace koncové rekurze (Ta H 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:
M v případě úspěchu se rovnou pokračuje
M 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, 16. května 201 2
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).
Hana Rudová, Logické programování I, 16. května 201 2
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
M 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í 1,16. května 201 2
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, 16. května 201 2
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í 1,16. května 201 2
10
Implementace Prologu
Optimalizace posledního volání
TRO pouze speciální případ
obecné optimalizace posledního volání (Last Ca\\ 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ů
3 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, 16. května 201 2
10
Implementace Prologu
Optimalizace posledního volání
TRO pouze speciální případ
obecné optimalizace posledního volání (Last Ca\\ 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ů
3 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 M pouze pro neinstanciované proměnné
Hana Rudová, Logické programování 1,16. května 2012 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, 16. května 201 2
12
Překlad
M Motivace:
dosažení vyšší míry optimalizace M kompaktní kód
3 částečná nezávislost na hardware
3 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, 16. května 201 2
12
Preklad
Překlad
Motivace:
M dosažení vyšší míry optimalizace M kompaktní kód
3 částečná nezávislost na hardware
M 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)
M 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, 16. května 201 2
12
Preklad
Překlad
3 Motivace:
3 dosažení vyšší míry optimalizace M kompaktní kód
částečná nezávislost na hardware
3 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
3 Výhody:
«• snazší přenos jazyka (nutno přepsat jen druhou část)
M kód abstraktního počítače možno navrhnout s ohledem na jednoduchost překladu prostor pro strojově nezávislou optimalizaci
M 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í 1,16. května 2012 12
Parciální vyhodnocení
M 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
3 příklad: vyhodnocení aritmetických výrazů nad konstantami
Hana Rudová, Logické programování I, 16. května 201 2
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).
Hana Rudová, Logické programování I, 16. května 201 2
14
ní 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, 16. května 201 2
14
ní 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, 16. května 201 2
14
Preklad
Parciální vyhodnocení II
Konstrukce překladače: parciálním vyhodnocením interpretu Problémy:
M příliš složitá operace
M vyhodnocení se musí provést vždy znovu pro každý nový program
M výsledný program příliš rozsáhlý M nedostatečná dekompozice
M zejména při použití zdrojového jazyka jako implementačního jazyka interpretu
Hana Rudová, Logické programování I, 16. května 201 2
Preklad
Parciální vyhodnocení II
Konstrukce překladače: parciálním vyhodnocením interpretu Problémy:
M příliš složitá operace
M vyhodnocení se musí provést vždy znovu pro každý nový program
M výsledný program příliš rozsáhlý M nedostatečná dekompozice
M 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í 1,16. května 2012 15 Preklad
Parciální vyhodnocení Prologu
Cílová operace: unifikace. Důvod:
3 ří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, 16. května 201 2
16
Preklad
Parciální vyhodnocení Prologu
Cílová operace: unifikace. Důvod:
3 řízení výpočtu poměrně podrobné i v interpretu 3 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ů ...)
3 většina unifikací nevyžaduje obecnou unifikaci a lze je nahradit jednoduššími operacemi
Zviditelnění unifikace: transformací zdrojového programu
3 termy reprezentujeme kopírováním struktur na globálním zásobníku
3 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
3 formálním parametrem procedury jsou pouze volné proměnné, které se v hlavě vyskytují pouze jednou
3 všechny unifikace jsou explicitně zachyceny voláním predikátu unify/2
Hana Rudová, Logické programování 1,16. května 2012 16 Překlad
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, 16. května 2012
17
Preklad
Explicitní unifikace
Příklad: append/3 s explicitní unifikací:
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).
append([],L,L).
append([A|X],L,[A|Y]
append(X,L,Y).
Hana Rudová, Logické programování I, 16. května 201 2
Explicitní unifikace
Příklad: append/3 s explicitní unifikací:
append(Al, A2, A3) :- unify(Al,[]), | append([],L,L).
unify(A2,L), |
unify(A3,L). |
append(Al, A2, A3) :- unify(Al,[A|X]), | append([A|X],L,[A|Y] :-
unify(A2,L), |
unify(A3,[A|Y]), |
put(X,Bl), | append(X,L,Y).
put(L,B2), |
put(Y,B3), |
append(Bl,B2,B3). |
Cíl: parciálně vyhodnotit predikáty unify/2 a put/2
Hana Rudová, Logické programování I, 16. května 201 2
Preklad
Pomocné termy a predikáty
M 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, 16. května 201 2
18
Preklad
Pomocné termy a predikáty
M 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 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é.
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, 16. května 201 2
18
Preklad
Pomocné termy a predikáty
M 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 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é.
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
M 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í 1,16. května 2012 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)
;   true ),
T := $addr$(A).
Hana Rudová, Logické programování I, 16. května 201 2
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),
C var(A), create_var(A)
;    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),
uni fy_var(A,T).
kde unify_var/2 vloží do T odkaz nebo založí novou proměnnou.
Hana Rudová, Logické programování I, 16. května 201 2
19
Preklad
unify pro konstantu
2) T je konstanta: výsledkem je test nebo přiřazení
unify(A,T) :-atomi c(T),
C ( var(A), create_var(A), instantiate_const(A,T) ) ; ( 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.
Hana Rudová, Logické programování I, 16. května 201 2
20
Preklad
unify pro konstantu
2) T je konstanta: výsledkem je test nebo přiřazení
unify(A,T) :-atomi c(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 i nstanti ate_const/2 uloží do slova s adresou A hodnotu T. Opět možno přepsat do kompaktního tvaru
unify(A,T) :-atomi c(T), uni fy_const(A,T).
kde unify_const/2 provede příslušný test nebo přiřazení.
Hana Rudová, Logické programování 1,16. května 201 2
20
Preklad
uni fy 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 uni fy_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, 16. května 201 2
21
Preklad
uni fy 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 uni fy_struct/3 je analogický výše použitým predikátům unify_var/2 a unify_const/2.
Druhá fáze: uni f y_args ([],_) .
unify_args([T|Tl], A) :-unify(A,T), unify_args(Tl,A+1).
Hana Rudová, Logické programování I, 16. května 201 2 21
unify pro odkaz
4) T je odkazem: nutno použít obecnou unifikaci (není žádná informace pro parciální vyhodnocení)
unify(A,T) :-
i s_addr(T,P), unification (A, P) .
Hana Rudová, Logické programování I, 16. května 201 2
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) :-
i s_addr (T, B) . %Tjeodkaz put(T,B) :-
var(T), % T je proměnná
create_var(B),
T := $addr$(B). put(T,B) :-
atomic(T), % T je konstanta
create_const(B,T). put(T,B) :-
struct(T), % T je struktura
create_struct(B,T).
Hana Rudová, Logické programování I, 16. května 201 2
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, 16. května 201 2
24
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, 16. května 201 2
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ěnnout T
=> stačí provést unification(A2 ,A3)
Hana Rudová, Logické programování I, 16. května 201 2
24
Preklad
Výsledný tvar append/3
append(Al, A2, A3) :-uni fy_const(Al,[]), um'fication(A2 ,A3) .
append(Al, A2, A3) :-
uni fy_struct('.',2,Al), unify_var(A,Al+1), unify_var(X,Al+2), uni fy_var(L,A2), uni fy_struct('.',2,A3), uni fi cation(Al+l,A3+1), 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í 1,16. května 201 2
25
Preklad
Jiný příklad
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:
proceduře a(X,Y,Z,A) is i f ( x == 'c' &&
( is_struct(Y,'s',1) &&
first_arg(Y) == 'f ) && Z == 'ď )
then
call g(A)
el se
a(AI, A2, A3, A4) :-unify_const(c,Al), uni fy_struct(s,1,A2), uni fy_const(f,A2+1), unify_const(d,A3), unify_var(A,A4), g(A4).
cal 1 f ai 1
end proceduře tj. posloupnost testů jako v procedurálním jazyce
Hana Rudová, Logické programování I, 16. května 201 2
26
Preklad
Jiný příklad
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:
proceduře a(X,Y,Z,A) is i f ( x == 'c' &&
( is_struct(Y,'s',1) &&
first_arg(Y) == 'f ) && Z == 'ď )
then
call g(A)
el se
a(AI, A2, A3, A4) :-unify_const(c,Al), uni fy_struct(s,1,A2), uni fy_const(f,A2+1), unify_const(d,A3), unify_var(A,A4), g(A4).
cal 1 f ai 1
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, 16. května 201 2
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:
M Oblast kódu (programová databáze)
3 separátní oblasti pro uživatelský kód (modifikovatelný) a vestavěné predikáty (nemění se) M obsahuje rovněž všechny statické objekty (texty atomů a funktorů apod.)
3 Lokální zásobník (Stack)
M Stopa (Trail)
M Globální zásobník n. ha\da(Heap)
3 Pomocný zásobník (Push Down List, PDL)
M pracovní paměť abstraktního počítače
M použitý v unifikaci, syntaktické analýze apod.
Hana Rudová, Logické programování I, 16. května 201 2
27
Preklad
Rozmístění datových oblastí
Příklad konfigurace
Halda \ / Stopa	f
Zásobník N PDL	
Oblast kódu	
M Halda i lokální zásobník musí růst stejným směrem
3 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, 16. května 201 2
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
Argumentové registry: A1,A2 , . . .       (při předávání parametrů n. pracovní registry)
Registry pro lokální proměnné: Y1,Y2, . . .
3 abstraktní znázornění lok. proměnných na zásobníku
Hana Rudová, Logické programování 1,16. května 201 2 29 Preklad
Typy instrukcí WAMu
M put instrukce - příprava argumentů před voláním podcíle
M žádná z těchto instrukcí nevolá obecný unifikační algoritmus M get instrukce - unifikace aktuálních a formálních parametrů
M vykonávají činnost analogickou instrukcím uni fy u pare. vyhodnocení 3 obecná unifikace pouze při get_value
M uni fy instrukce - zpracování složených termů
M jednoargumentové instrukce, používají registr S jako druhý argument
M počáteční hodnota S je odkaz na 1. argument
M volání instrukce uni fy zvětší hodnotu S o jedničku
* obecná unifikace pouze při unify_value a unify_local_val ue
M Indexační instrukce - indexace klauzulí a manipulace s body volby
M Instrukce řízení běhu - předávání řízení a explicitní manipulace s okolím
Hana Rudová, Logické programování 1,16. května 201 2 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_value	A2,A5
put_value	A3,A6
put_value	A4,A7
execute	b/4
Hana Rudová, Logické programování I, 16. května 201 2
31
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í 1,16. května 201 2
32
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.
3 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	I 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í 1,16. května 201 2 32
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_nil Ai
put_struct Ai,F/N
put_list Ai
unify instrukce
unify_var Y
unify_value Y
unify_local_val ue Y
unify_const C uni fy_ni1
unify_void N
instrukce řízení allocate deal locate call Proc/N,A execute Proc/N proceed
indexační instrukce
try_me_else Next retry_me_el se 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
, 16. května 201 2
33
Preklad
WAM - indexace
M Provázání klauzulí: instrukce XX_me_el se:
3 první klauzule: try_me_else; založí bod volby
M poslední klauzule: trust_me_el se; zruší nejmladší bod volby
M ostatní klauzule: retry_me_el se; znovu použije nejmladší bod volby po neúspěchu
Hana Rudová, Logické programování I, 16. května 201 2
34
Preklad
WAM - indexace
M Provázání klauzulí: instrukce XX_me_el se:
3 první klauzule: try_me_else; založí bod volby
M poslední klauzule: trust_me_el se; zruší nejmladší bod volby
M ostatní klauzule: retry_me_el se; znovu použije nejmladší bod volby po neúspěchu
M Provázání podmnožiny klauzulí (podle argumentu):
try 3 retry M trust
Hana Rudová, Logické programování I, 16. května 201 2
34
Preklad
WAM - indexace
M Provázání klauzulí: instrukce XX_me_el se:
3 první klauzule: try_me_else; založí bod volby
M poslední klauzule: trust_me_el se; zruší nejmladší bod volby
M ostatní klauzule: retry_me_el se; znovu použije nejmladší bod volby po neúspěchu
M Provázání podmnožiny klauzulí (podle argumentu):
try 3 retry M trust
„Rozskokové" instrukce (dle typu a hodnoty argumentu):
3 switch_on_term Var, Const, List, Struct
výpočet následuje uvedeným návěstím podle typu prvního argumentu
M swi tch_on_YY: hashovací tabulka pro konkrétní typ (konstanta, struktura)
Hana Rudová, Logické programování I, 16. května 201 2
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: L2
L3:
L4:
LI: Lla
switch_on_term LI, L2, L3, L4
switch_on_const atom
1
2
L7a L8a
try trust
switch_on_struct s/l
f/1
try_me_el se L5 bodyl
Lla L5a L6a
L9a LlOa
L5:     retry_me_else L6
Hana Rudová, Logické programování I, 16. května 201 2
L5a: body2
L6: retry_me_else L7
L6a: body3
L7: retry_me_else L8
L7a: body4
L8: retry_me_else L9
L8a: body 5
L9: retry_me_else L10
L9a: body6
L10: trust_me_else fail
LlOa: body7
35
WAM - řízení výpočtu
M execute Proč: ekvivalentní příkazu goto
Hana Rudová, Logické programování I, 16. května 201 2
36
Preklad
WAM - řízení výpočtu
M execute Proč: ekvivalentní příkazu goto M proceed: zpracování faktů
Hana Rudová, Logické programování I, 16. května 201 2
36
Preklad
WAM - řízení výpočtu
A execute Proč: ekvivalentní příkazu goto M proceed: zpracování faktů
M allocate: alokuje okolí (pro některé klauzule netřeba, proto explicitně generováno)
Hana Rudová, Logické programování I, 16. května 201 2
36
Preklad
WAM - řízení výpočtu
M execute Proč: ekvivalentní příkazu goto M proceed: zpracování faktů
allocate: alokuje okolí (pro některé klauzule netřeba, proto explicitně generováno) M deallocate: uvolní okolí (je-li to možné, tedy leží-li na vrcholu zásobníku) M call Proc,N: zavolá Proč, N udává počet lok. proměnných (odpovídá velikosti zásobníku)
Hana Rudová, Logické programování I, 16. května 201 2
36
Preklad
WAM - řízení výpočtu
M execute Proč: ekvivalentní příkazu goto
M proceed: zpracování faktů
M allocate: alokuje okolí (pro některé klauzule netřeba, proto explicitně generováno)
M deallocate: 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í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í 1,16. května 201 2 36 Preklad