Implementace Prologu (pokračování)
Interpret Prologu
Základní principy:
klauzule uloženy jako termy
JS> programová databáze
.i* pro uložení klauzulí a má charakter haldy
umožňuje modifikovatelnost prologovských programu za behu (assert)
JS> klauzule zřetězeny podle poradí naCtení iľ triviální zretezení
Hana Rudová, Logické programování I, 7. kvetna 2010
2
Implementace Prologu
Interpret Prologu
Základní principy:
klauzule uloženy jako termy
JS> programová databáze
.i* pro uložení klauzulí a má charakter haldy
umožňuje modifikovatelnost prologovských programu za behu (assert)
JS> klauzule zřetězeny podle poradí naCtení iľ triviální zretezení
Vyhodnocení dotazu: volání procedur rízené unifikací
Hana Rudová, Logické programování I, 7. kvetna 2010
2
Implementace Prologu
Interpret - Základní princip
1. Vyber redukovaný literál („první", tj. nejlevejší literál cíle)
2. Lineárním průchodem od zaCátku databáze najdi klauzuli, jejíž hlava má stejný funktor a stejný poCet argumentu jako redukovaný literál
3. V prípade nalezení klauzule založ bod volby procedury
4. Založ dále okolí první klauzule (velikost odvozena od poCtu lokálních promenných v klauzuli)
Hana Rudová, Logické programování I, 7. kvetna 2010
3
Implementace Prologu
Interpret - Základní princip
1. Vyber redukovaný literál („první", tj. nejlevejší literál cíle)
2. Lineárním prUchodem od zaCátku databáze najdi klauzuli, jejíž hlava má stejný funktor a stejný poCet argumentů jako redukovaný literál
3. V prípade nalezení klauzule založ bod volby procedury
4. Založ dále okolí první klauzule (velikost odvozena od poCtu lokálních promenných v klauzuli)
5. Proved' unifikaci literálu a hlavy klauzule
6. Úspech == pridej všechny literály klauzule k cíli („doleva", tj. na místo redukovaného literálu). Telo prázdné == výpocet se s úspechem vrací do klauzule, jejíž adresa je v aktuálním okolí.
7. Neúspech unifikace == z bodu volby se obnoví stav a pokracuje se v hledání další vhodné klauzule v databázi.
Hana Rudová, Logické programování I, 7. kvetna 2010
3
Implementace Prologu
Interpret - Základní princip
1. Vyber redukovaný literál („první", tj. nejlevejší literál cíle)
2. Lineárním průchodem od zaCátku databáze najdi klauzuli, jejíž hlava má stejný funktor a stejný poCet argumentů jako redukovaný literál
3. V prípade nalezení klauzule založ bod volby procedury
4. Založ dále okolí první klauzule (velikost odvozena od poCtu lokálních promenných v klauzuli)
5. Proved' unifikaci literálu a hlavy klauzule
6. Úspech == pridej všechny literály klauzule k cíli („doleva", tj. na místo redukovaného literálu). Telo prázdné == výpocet se s úspechem vrací do klauzule, jejíž adresa je v aktuálním okolí.
7. Neúspech unifikace == z bodu volby se obnoví stav a pokracuje se v hledání další vhodné klauzule v databázi.
8. Pokud není nalezena odpovídající klauzule, výpocet se vrací na predchozí bod volby (krátí se lokální i globální zásobník).
9. Výpocet koncí neúspechem: neexistuje již bod volby, k nemuž by se výpocet mohl vrátit. 10. Výpocet koncí úspechem, jsou-li úspešne redukovány všechny literály v cíli.
Hana Rudová, Logické programování I, 7. kvetna 2010 3 Implementace Prologu
Interpret - vlastnosti
-í* Lokální i globální zásobník
pri dopredném výpočtu roste a pri zpetném výpočtu se zmenšuje
Lokální zásobník se může zmenšit pri dopredném úspešném výpočtu deterministické procedury.
Hana Rudová, Logické programování I, 7. kvetna 2010
4
Implementace Prologu
Interpret - vlastnosti
Lokální i globální zásobník
pri dopředném výpočtu roste a 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 úspešném výpočtu deterministické procedury.
Unifikace argumentů hlavy - obecný unifikační algoritmus Současne poznačí adresy instanciovaných promenných na stopu.
Hana Rudová, Logické programování I, 7. kvetna 2010
4
Implementace Prologu
Interpret - vlastnosti
-í* Lokální i globální zásobník
pri dopredném výpoctu roste a pri zpetném výpoctu se zmenšuje
Lokální zásobník se může zmenšit pri dopredném úspešném výpoctu deterministické procedury.
-í* Unifikace argumentů hlavy - obecný unifikacní algoritmus
Soucasne poznací adresy instanciovaných promenných na stopu.
-í* „Interpret":
interpretCQuery, Vars) :- call(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 prípade úspechu i neúspechu
Hana Rudová, Logické programování I, 7. kvetna 2010 4 Implementace Prologu
Optimalizace: Indexace
Zretezení klauzulí podle poradí nactení velmi neefektivní & Provázání klauzulí se stejným funktorem a aritou hlavy (tvorí jednu proceduru)
a tj., indexace procedur -í* Hash tabulka pro vyhledání první klauzule & Možno rozhodnout (parciálne) determinismus procedury
Hana Rudová, Logické programování I, 7. kvetna 2010
5
Implementace Prologu
Indexace argumentů
a(l) :- q(1). a(a) :- b(X). a([A|T]) :- c(A,T).
& Obecně nedeterministická
-í* Pri volání s alespoň CásteCne instanciovaným argumentem vždy deterministická (pouze jedna klauzule může uspet)
Hana Rudová, Logické programování I, 7. kvetna 2010
6
Implementace Prologu
Indexace argumentů
a(1) :- q(1). a(a) :- b(X). a([A|T]) :- c(A,T).
& Obecne nedeterministická
-í* Pri volání s alespon částečne instanciovaným argumentem vždy deterministická (pouze jedna klauzule může uspet)
Indexace podle prvního argumentu
Základní typy zretezení:
-i- podle poradí klauzulí (aktuální argument je volná promenná) A dle konstant (aktuální je argument konstanta) -i- formální argument je seznam (aktuální argument je seznam) dle struktur (aktuální argument je struktura)
Hana Rudová, Logické programování I, 7. kvetna 2010 6 Implementace Prologu
Indexace argumentů II
C Složitejší indexační techniky
a podle všech argumentů
a podle nejvíce diskriminujícího argumentu
kombinace argumentu (indexové techniky z databází) zejména pro prístup k faktům
Hana Rudová, Logické programování I, 7. kvetna 2010
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, 7. května 2010
8
Implementace Prologu
Tail Recursion Optimization, TRO
Iterace provádena pomocí rekurze => lineární pameťová nárocnost cyklů
Optimalizace koncové rekurze (Tail Recursion Optimisation), TRO:
Okolí se odstraní pred rekurzivním voláním posledního literálu klauzule, pokud je klauzule resp. její volání deterministické.
Rízení se nemusí vracet:
& v případe úspechu se rovnou pokracuje
JS> v prípade neúspechu se vrací na predchozí bod volby („nad" aktuální klauzulí) aktuální klauzule nemá dle predpokladu bod volby
Rekurzivne volaná klauzule může být volána prímo z kontextu volající klauzule.
Hana Rudová, Logické programování I, 7. kvetna 2010
8
Implementace Prologu
TRO - prí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, 7. kvetna 2010
9
Implementace Prologu
TRO - prí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 rekurzivne 4krát
£ bez TRO: 4 okolí, lineární pamet'ová nárocnost & s TRO: 1 okolí, konstatní pamet'ová nárocnost
Hana Rudová, Logické programování I, 7. kvetna 2010
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, 7. května 2010
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, 7. kvetna 2010
10
Implementace Prologu
Optimalizace posledního volání
TRO pouze speciální prípad
obecné optimalizace posledního volání (Last Call Optimization), LCO
Okolí (pred redukcí posledního literálu)
odstranováno vždy, když leží na vrcholu zásobníku.
Nutné úpravy interpretu
JS> disciplina smerování ukazatelu
-fc vždy „mladší" ukazuje na „starší" („mladší" budou odstraneny dríve) -i- z lokálního do globálního zásobníku
vyhneme se vzniku „visících odkazu" pri predcasném odstranení okolí
Hana Rudová, Logické programování I, 7. kvetna 2010
10
Implementace Prologu
Optimalizace posledního volání
TRO pouze speciální prípad
obecné optimalizace posledního volání (Last Call Optimization), LCO
Okolí (pred redukcí posledního literálu)
odstraňováno vždy, když leží na vrcholu zásobníku.
Nutné úpravy interpretu
JS> disciplina směrování ukazatelu
-fc vždy „mladší" ukazuje na „starší" („mladší" budou odstraneny dríve) -i- z lokálního do globálního zásobníku
vyhneme se vzniku „visících odkazu" pri predcasném odstranení okolí
„globalizace" lokálních proměnných: lokální promenné posledního literálu
A nutno presunout na globální zásobník i> pouze pro neinstanciované promenné
Hana Rudová, Logické programování I, 7. kvetna 2010 10 Implementace Prologu
Preklad
Preklad
Motivace:
dosažení vyšší míry optimalizace i* kompaktní kód
Jť cástecná nezávislost na hardware
Hana Rudová, Logické programování I, 7. kvetna 2010 12 Preklad
Preklad
-í* Motivace:
dosažení vyšší míry optimalizace i* kompaktní kód
Jť cástecná nezávislost na hardware Etapy prekladu:
1. zdrojový text == kód abstraktního pocítace
2. kód abstraktního pocítace == kód (instrukce) cílového pocítace
Hana Rudová, Logické programování I, 7. kvetna 2010
12
Preklad
Preklad
-í* Motivace:
dosažení vyšší míry optimalizace i* kompaktní kód
Jť částečná nezávislost na hardware
JS> Etapy prekladu:
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:
-i- snazší prenos jazyka (nutno prepsat jen druhou část)
S> kód abstraktního počítače možno navrhnout s ohledem na jednoduchost prekladu; prostor pro strojove nezávislou optimalizaci
Hana Rudová, Logické programování I, 7. kvetna 2010
12
Preklad
Preklad
-í* Motivace:
dosažení vyšší míry optimalizace i* kompaktní kód
Jť cástecná nezávislost na hardware Etapy prekladu:
1. zdrojový text == kód abstraktního pocítace
2. kód abstraktního pocítace == kód (instrukce) cílového pocítace
& Výhody:
-i- snazší prenos jazyka (nutno prepsat jen druhou cást)
S> kód abstraktního pocítace možno navrhnout s ohledem na jednoduchost prekladu; prostor pro strojove nezávislou optimalizaci
C Preklad Prologu založen na principu existence abstraktního pocítace V dalším se venujeme jeho odvození a vlastnostem
Hana Rudová, Logické programování I, 7. kvetna 2010 12 Preklad
Parciální vyhodnocení
& Jak navrhnout Warrenův abstraktní pocítac?
prostřednictvím parciálního vyhodnocení
Parciální vyhodnocení
a forma zpracování programu,
tzv. transformace na úrovni zdrojového kódu
a dosazení známých hodnot vstupních parametru a vyhodnocení všech operací nad nimi
príklad: vyhodnocení aritmetických výrazu nad konstantami
Hana Rudová, Logické programování I, 7. kvetna 2010
13
Preklad
Parciální vyhodnocení - príklad
a(X,Y) :- b(X), c(X,Y).          a(X,Y) :- b(Y), c(Y,X). b(1).     b(2).     b(3). b(4).
c(1,2). c(1,3). c(1,4). c(2,3). c(2,4). c(3,4). Dotaz ?- a(2,Z).
Hana Rudová, Logické programování I, 7. kvetna 2010
14
Preklad
Parciální vyhodnocení - príklad
a(X,Y) :- b(X), c(X,Y). a(X,Y) :- b(Y), c(Y,X).
b(1).     b(2).     b(3). b(4).
c(1,2).     c(1,3).     c(1,4).     c(2,3).     c(2,4). c(3,4). Dotaz ?- a(2,Z).
lze společne s uvedeným programem parciálne vyhodnotit na nový program a'(3).    a'(4). a'(1). a nový dotaz ?- a'(Z).
Hana Rudová, Logické programování I, 7. kvetna 2010
14
Preklad
Parciálni vyhodnocení - príklad
a(X,Y) :- b(X), c(X,Y). a(X,Y) :- b(Y), c(Y,X).
b(1).     b(2).     b(3). b(4).
c(1,2).     c(1,3).     c(1,4).     c(2,3).     c(2,4). c(3,4). Dotaz ?- a(2,Z).
lze spolecne s uvedeným programem parciálne vyhodnotit na nový program a'(3).    a'(4). a'(1). a nový dotaz ?- a'(Z).
Je evidentní, že dotaz nad parciálne vyhodnoceným programem bude zpracován mnohem rychleji (efektivneji) než v prípade původního programu.
Hana Rudová, Logické programování I, 7. kvetna 2010
14
Preklad
Parciální vyhodnocení II
Konstrukce prekladače: parciálním vyhodnocením interpretu Problémy:
& príliš složitá operace
A vyhodnocení se musí provést vždy znovu pro každý nový program
JS> výsledný program príliš rozsáhlý JS> nedostatecná dekompozice
-fc zejména pri použití zdrojového jazyka jako implementacního jazyka interpretu
Hana Rudová, Logické programování I, 7. kvetna 2010
15
Preklad
Parciální vyhodnocení II
Konstrukce prekladace: parciálním vyhodnocením interpretu Problémy:
& príliš složitá operace
A vyhodnocení se musí provést vždy znovu pro každý nový program
JS> výsledný program príliš rozsáhlý JS> nedostatecná dekompozice
-fc zejména pri použití zdrojového jazyka jako implementacního jazyka interpretu Vhodnejší:
JS> využití („rucního") parciálního vyhodnocení pro návrh abstraktního pocítace
1. nalezení operací zdrojového jazyka, které lze dekomponovat do jednodušších operací
2. dekomponujeme tak dlouho, až jsou výsledné operace dostatecne jednoduché nebo již neexistují informace pro parciální vyhodnocení
Hana Rudová, Logické programování I, 7. kvetna 2010 15 Preklad
Parciální vyhodnocení Prologu
Cílová operace: unifikace. Duvod:
rízení výpoctu pomerne podrobné i v interpretu £ unifikace v interpretu atomickou operací
& unifikace v interpretu nahrazuje radu podstatne jednodušších operací (testy, prirazení, predání a prevzetí parametrů ...)
& vetšina unifikací nevyžaduje obecnou unifikaci a lze je nahradit jednoduššími operacemi
Hana Rudová, Logické programování I, 7. kvetna 2010
16
Preklad
Parciální vyhodnocení Prologu
Cílová operace: unifikace. Duvod:
rízení výpoctu pomerne podrobné i v interpretu £ unifikace v interpretu atomickou operací
& unifikace v interpretu nahrazuje radu podstatne jednodušších operací (testy, prirazení, předání a převzetí parametrů ...)
& vetš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ísteny na globální zásobník (predikátem put/2) a predávány jsou pouze adresy
& formálním parametrem procedury jsou pouze volné promenné, které se v hlave vyskytují pouze jednou
& všechny unifikace jsou explicitne zachyceny voláním predikátu unify/2
Hana Rudová, Logické programování I, 7. kvetna 2010 16 Preklad
Explicitní unifikace
Príklad: append/3 s explicitní unifikací:
append(A1, A2, A3) :- unify(A1,[]), | append([],L,L).
unify(A2,L), | unify(A3,L).
Hana Rudová, Logické programování I, 7. kvetna 2010
17
Preklad
Explicitní unifikace
Príklad: append/3 s explicitní unifikací:
append(A1, A2, A3)
append(A1, A2, A3)
:- unify(A1,[]),
unify(A2,L),
unify(A3,L). :- unify(A1,[A|X]),
unify(A2,L),
unify(A3,[A|Y]),
put(X,B1),
put(L,B2),
put(Y,B3),
append(B1,B2,B3).
| append([],L,L).
| append([A|X],L,[A|Y] :-
append(X,L,Y).
Hana Rudová, Logické programování I, 7. kvetna 2010
17
Preklad
Explicitní unifikace
Príklad: append/3 s explicitní unifikací:
append(A1, A2, A3)
append(A1, A2, A3)
:- unify(A1,[]),
unify(A2,L),
unify(A3,L). :- unify(A1,[A|X]),
unify(A2,L),
unify(A3,[A|Y]),
put(X,B1),
put(L,B2),
put(Y,B3),
append(B1,B2,B3).
| append([],L,L).
| append([A|X],L,[A|Y] :-
append(X,L,Y).
Cíl: parciálne vyhodnotit predikáty unify/2 a put/2
Hana Rudová, Logické programování I, 7. kvetna 2010
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é promenné X term T;
X musí být volná promenná.
Hana Rudová, Logické programování I, 7. kvetna 2010
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é promenné X term T;
X musí být volná promenná.
predikát repres(A,Tag,V) - uloží do promenné Tag príznak a do
promenné 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é promenné.
príznak: informace o strukture soucástí objektu
volná promenná FREE, konstanta CONST, celé císlo INT, odkaz REF, složený term FUNCT
Hana Rudová, Logické programování I, 7. kvetna 2010
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)
JS> predikát : = (X,T) - priradí volné promenné X term T;
X musí být volná promenná.
predikát repres(A,Tag,V) - uloží do promenné Tag príznak a do
promenné 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é promenné.
príznak: informace o strukture součástí objektu
volná promenná 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, 7. kvetna 2010 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 prípady:
1) T je volná promenná: výsledkem je instanciace
unify(A,T) :- var(T),
( var(A), create_var(A)
;   true ),
T := $addr$(A).
Hana Rudová, Logické programování I, 7. kvetna 2010
19
Preklad
unify pro volnou promennou
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 prípady:
1) T je volná promenná: výsledkem je instanciace
unify(A,T) :- var(T),
( 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 pri parc. prekladu. Lze proto prepsat na
unify(A,T) :- var(T),
unify_var(A,T).
kde unify_var/2 vloží do T odkaz nebo založí novou promennou.
Hana Rudová, Logické programování I, 7. kvetna 2010
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, 7. kvetna 2010
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. Opet 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é přogřamování I, 7. kvetna 2010 20 Překlad
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 =.. [_|Tl], unify_args(Tl,A+1).
Predikát unify_struct/3 je analogický výše použitým predikátum unify_var/2 a unify_const/2.
Hana Rudová, Logické programování I, 7. kvetna 2010
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 argumentu
unify(A,T)
struct(T),
functor(T,F,N),
unify_struct(F,N,A),
T =.. UTl], unify_args(Tl,A+1).
Predikát unify_struct/3 je analogický výše použitým predikátum unify_var/2 a unify_const/2.
Druhá fáze: unify_args([],_).
unify_args([T|Tl], A) unify(A,T), unify_args(Tl,A+1).
Hana Rudová, Logické programování I, 7. kvetna 2010 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, 7. kvetna 2010
22
Preklad
put
Parametry procedur jsou vždy umísteny 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 nepotrebuje unifikaci)
put(T,B) :-
is_addr(T,B). %Tje odkaz
put(T,B) :-
var(T), %Tje promenná
create_var(B),
T := $addr$(B). put(T,B) :-
atomic(T), %T je konstanta
create_const(B,T). put(T,B) :-
struct(T), %Tje struktura
create_struct(B,T).
Hana Rudová, Logické programování I, 7. kvetna 2010
23
Preklad
První klauzule append/3
Parciální vyhodnocení první klauzule programu append/3
append(A1, A2, A3) :- unify(A1,[]), | append([],L,L).
unify(A2,L), | unify(A3,L). |
upraví
unify(A1,[]) na unify_const(A1,[])
unify(A2,L)    na L:=$addr$(A2)
unify(A3,L)   na is_addr(L,T), unification(T,A3)
Hana Rudová, Logické programování I, 7. kvetna 2010
24
Preklad
První klauzule append/3
Parciální vyhodnocení první klauzule programu append/3
append(A1, A2, A3) :- unify(A1,[]), | append([],L,L).
unify(A2,L), | unify(A3,L). |
upraví
unify(A1,[]) na unify_const(A1,[])
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á prejmenování T na A2
Hana Rudová, Logické programování I, 7. kvetna 2010
24
Preklad
První klauzule append/3
Parciální vyhodnocení první klauzule programu append/3
append(A1, A2, A3)       unify(A1,[]), | append([],L,L).
unify(A2,L), | unify(A3,L). |
upraví
unify(A1,[]) na unify_const(A1,[])
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á prejmenování T na A2
=> není nutné vytváret novou promennout T
=> stací provést unification(A2,A3)
Hana Rudová, Logické programování I, 7. kvetna 2010
24
Preklad
Výsledný tvar append/3
append(A1, A2, A3) :-
unify_const(A1,[]),
unification(A2,A3). append(A1, A2, A3) :-
unify_struct('.',2,A1),
unify_var(A,A1+1),
unify_var(X,A1+2),
unify_var(L,A2),
unify_struct('.',2,A3),
unification(A1+1,A3+1),
unify_var(Y,A3+2),
append(A1+2,A2,A3+2).
Vetšina původních unifikací prevedena unifikace v posledním kroku je nezbytná
append(A1, A2, A3) :-
unify(A1,[]),
unify(A2,L), unify(A3,L). append(A1, A2, A3) :-
unify(A1,[A|X]),
unify(A2,L), unify(A3,[A|Y]),
put(X,B1), put(L,B2), put(Y,B3), append(B1,B2,B3).
jednodušší operace; (dusledkem dvojího výskytu promenné)
Hana Rudová, Logické programování I, 7. kvetna 2010
25
Preklad
Jiný prí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 |
if ( X == 'c' && | ( is_struct(Y,'s',1) && |
first_arg(Y) == f ) && |
Z == 'ď   ) |
then |
call g(A) |
else |
a(A1, A2, A3, A4) :-unify_const(c,A1), unify_struct(s,1,A2), unify_const(f,A2+1), unify_const(d,A3), unify_var(A,A4), g(A4).
call fail | end procedure tj. posloupnost testů jako v procedurálním jazyce
Hana Rudová, Logické programování I, 7. kvetna 2010
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:
procedure 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(A1, A2, A3, A4) :-unify_const(c,A1), unify_struct(s,1,A2), unify_const(f,A2+1), unify_const(d,A3), unify_var(A,A4), g(A4).
call fail I end procedure tj. posloupnost testů jako v procedurálním jazyce
Vyzkoušejte si: delete(X,  [YjT],  [Y|T1]) :- delete(X, T, T1).
Hana Rudová, Logické programování I, 7. kvetna 2010
26
Preklad
Warrenův abstraktní pocítac, WAM I.
Navržen D.H.D. Warrenem v roce 1983, modifikace do druhé poloviny 80. let Datové oblasti:
& Oblast kódu (programová databáze)
separátní oblasti pro uživatelský kód (modifikovatelný) a vestavené predikátý (nemení se) -i- obsahuje rovnež všechny statické objekty (texty atomu a funktoru apod.)
JS> Lokální zásobník (Stack)
& Stopa (Trail)
JS> Globální zásobník n. halda(Heap)
JS> Pomocný zásobník (Push Down List, PDL)
pracovní pamet' abstraktního pocítace -i- použitý v unifikaci, syntaktické analýze apod.
Hana Rudová, Logické programování I, 7. kvetna 2010
27
Preklad
Rozmístení datových oblastí
Príklad konfigurace
Halda
Stopa
Zásobník
PDL
Oblast kodu
Ý A
Halda i lokální zásobník musí mst stejným smerem
-i- lze jednoduše porovnat stárí dvou promenných srovnáním adres využívá se pri zabránení vzniku visících odkazu
Hana Rudová, Logické programování I, 7. kvetna 2010
28
Preklad
Registry WAMu
JS> Stavové registry:
P čítač 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ý pri analýze složených termu (Structure pointer)
CUT ukazatel na bod volby, na který se rezem zařízne zásobník
Argumentové registry: A1,A2,...       (pri predávaní parametru n. pracovní registry)
Registry pro lokální proměnné: Y1,Y2,...
-fc abstraktní znázornení lok. promenných na zásobníku
Hana Rudová, Logické programování I, 7. kvetna 2010 29 Preklad
Typy instrukcí WAMu
& put instrukce - príprava argumentů pred voláním podcíle A žádná z techto instrukcí nevolá obecný unifikacní algoritmus
& get instrukce - unifikace aktuálních a formálních parametrů
-i- vykonávají cinnost analogickou instrukcím unify u parc. vyhodnocení -fc obecná unifikace pouze pri get_value
& unify instrukce - zpracování složených termu
jednoargumentové instrukce, používají registr S jako druhý argument
pocátecní hodnota S je odkaz na 1. argument J* volání instrukce unify zvetší hodnotu S o jednicku 3 obecná unifikace pouze pri unify_value a unify_local_value
Indexacní instrukce - indexace klauzulí a manipulace s body volby & Instrukce rízení behu - predávání rízení a explicitní manipulace s okolím
Hana Rudová, Logické programování I, 7. kvetna 2010 30 Preklad
Instrukce put a get: príklad
Príklad: a(X,Y,Z) b(f,X,Y,Z).	
get_var	A1,A5
get_var	A2,A6
get_var	A3,A7
put_const	A1,f
put_value	A2,A5
put_value	A3,A6
put_value	A4,A7
execute	b/4
Hana Rudová, Logické programování I, 7. kvetna 2010
31
Preklad
Instrukce WAMu
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_nil	Ai	unify_nil	
get_list	Ai	put_struct	Ai,F/N	unify_void	N
		put_list	Ai		
instrukce rízení
allocate
deallocate
call Proc/N,A
execute Proc/N
proceed
indexacní instrukce
try_me_else Next retry_me_else Next trust_me_else fail
try Next retry Next trust fail
cut_last save_cut Y load_cut Y
switch_on_term Var,Const,List,Struct switch_on_const Table switch_on_struct Table
Hana Rudová, Logické programování I, ľ. kvetna 2GlG
32
Preklad
Instrukce unify, get, put
Vetší pocet typů objektů
& rozlišeny atomy, císla, nil = prázdný seznam, seznam speciální drůh složeního termů
unify_void ůmožní preskoCit anonymních promenné ve složených termech & put_unsafe_value pro optimalizaci práce s lokálními promennými pri TRO
a(X) :- b(X,Y),  !, a(Y).
pri TRO nesmí být lokální promenné posledního literálů (Y) na lokálním zásobníků
J* kompilátor může všechny nebezpeCné (unsafe) výskyty lok. promenných detekovat pri prekladů (jsoů to poslední výskyty lok. promenných) a generuje složitejší instrůkce put_unsafe_value, které provádejí test ůmístení
Hana Růdová, Logické programování I, 7. kvetna 2010
33
Preklad
Instrukce unify, get, put
Vetší pocet typů objektů
J* rozlišeny atomy, císla, nil = prázdný seznam, seznam speciální drůh složeního termů
unify_void ůmožní preskoCit anonymních promenné ve složených termech & put_unsafe_value pro optimalizaci práce s lokálními promennými pri TRO
a(X)       b(X,Y),  !, a(Y).
pri TRO nesmí být lokální promenné posledního literálů (Y) na lokálním zásobníků
J* kompilátor může všechny nebezpeCné (unsafe) výskyty lok. promenných detekovat pri prekladů (jsoů to poslední výskyty lok. promenných) a generuje složitejší instrůkce put_unsafe_value, které provádejí test ůmístení
unify_local_value kvůliTROjako put_unsafe_value
-i- a(X)      d(X), b(s(Y),X).    objekt prístůpný pres Y opet nesmí být na lok. zásobníků doba života s/1 může být delší než doba života okolí na než se Y odkazůje
Jť unify_local_value testůjí ůmístení a pokůd nůtné presoůvají objekty na haldů
Hana Růdová, Logické programování I, 7. kvetna 2010 33 Preklad
WAM - indexace
Provázání klauzulí: instrukce XX_me_e1se:
M první klauzule: try_me_e1se; založí bod volby
i> poslední klauzule: trust_me_e1se; zruší nejmladší bod volby
a ostatní klauzule: retry_me_e1se; znovu použije nejmladší bod volby po neúspechu
Hana Rudová, Logické programování I, 7. kvetna 2010
34
Preklad
WAM - indexace
Provázání klauzulí: instrukce XX_me_e1se:
M první klauzule: try_me_e1se; založí bod volby
i> poslední klauzule: trust_me_e1se; zruší nejmladší bod volby
a ostatní klauzule: retry_me_e1se; znovu použije nejmladší bod volby po neúspechu
ii> Provázání podmnožiny klauzulí (podle argumentu):
S try
retry -i- trust
Hana Rudová, Logické programování I, 7. kvetna 2010
34
Preklad
WAM - indexace
Provázání klauzulí: instrukce XX_me_else:
M první klauzule: try_me_else; založí bod volby
i> poslední klauzule: trust_me_else; zruší nejmladší bod volby
a ostatní klauzule: retry_me_else; znovu použije nejmladší bod volby po neúspechu
ii> Provázání podmnožiny klauzulí (podle argumentu):
S try -k retry -i- trust
-í* „Rozskokové" instrukce (dle typu a hodnoty argumentu):
switch_on_term Var, Const, List, Struct
výpocet následuje uvedeným návestím podle typu prvního argumentu
switch_on_YY: hashovací tabulka pro konkrétní typ (konstanta, struktura)
Hana Rudová, Logické programování I, 7. kvetna 2010
34
Preklad
Príklad indexace instrukcí
Procedu re a(atom) :- body1. a(1) :- body2. a(2) :- body3.
a([X|Y]) :- body4. a([X|Y]) :- body5. a(s(N)) :- body6. a(f(N)) :- bodyľ.
odpovídají instrukce
a: switch_on_term L1, L2, L3, L4 L2:     switch_on_const   atom :L1a
1 :L5a
2 :L6a L3:     try L7a
trust L8a L4:     switch_on_struct s/1 :L9a
f/1 :L10a
L1:    try_me_else L5 L1a: body1
L5:     retry_me_else L6
Hana Rudová, Logické programování I, 7. května 2010
L5a:	body2	
L6:	retry_me_e1se	L7
L6a:	body3	
L7:	retry_me_e1se	L8
L7a:	body4	
L8:	retry_me_e1se	L9
L8a:	body5	
L9:	retry_me_e1se	L10
L9a:	body6	
L10:	trust_me_e1se	fail
L10a:	body7	
35 Preklad
WAM - rízení výpoctu
& execute Proc: ekvivalentní príkazu goto
Hana Rudová, Logické programování I, 7. kvetna 2010
36
Preklad
WAM - rízení výpočtu
& execute Proc: ekvivalentní príkazu goto J5> proceed: zpracování faktů
Hana Rudová, Logické programování I, 7. kvetna 2010
36
Preklad
WAM - rízění výpočtu
& execute Proc: ekvivalentní príkazu goto J5> proceed: zpracování faktu
M allocate: alokuje okolí (pro nekteré klauzule netreba, proto explicitne generováno)
Hana Rudová, Logické programování I, 7. kvetna 2010
36
Preklad
WAM - rízení výpočtu
& execute Proc: ekvivalentní príkazu goto
J5> proceed: zpracování faktU
M allocate: alokuje okolí (pro některé klauzule netreba, proto explicitne generováno)
& deallocate: uvolní okolí (je-li to možné, tedy leží-li na vrcholu zásobníku)
& call Proc,N: zavolá Proc, N udává poCet lok. proměnných (odpovídá velikosti zásobníku)
Hana Rudová, Logické programování I, 7. kvetna 2010
36
Preklad
WAM - řízení výpočtu
& execute Proc: ekvivalentní príkazu goto
J5> proceed: zpracování faktU
M allocate: alokuje okolí (pro některé klauzule netreba, proto explicitne generováno)
& deallocate: uvolní okolí (je-li to možné, tedy leží-li na vrcholu zásobníku)
& call Proc,N: zavolá Proc, N udává poCet lok. promenných (odpovídá velikosti zásobníku) Možná optimalizace:   vhodným usporádáním promenný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, 7. kvetna 2010 36 Preklad
WAM - rez
Implementace rezu (opakování): odstranení bodů volby mezi soucasným vrcholem zásobníku a bodem volby procedury, která r ez vyvolala (vcetne bodu volby procedury s rezem)
Indexacní instrukce znemožnují v dobe p r ekladu rozhodnout, zda bude alokován bod volby M príklad: ?- a(X). může být nedeterministické, ale ?- a(1). muže být deterministické
Hana Rudová, Logické programování I, 7. kvetna 2010
37
Preklad
WAM - rez
Implementace rezů (opakování): odstranení bodů volby mezi soůcasným vrcholem zásobníků a bodem volby procedůry, která rez vyvolala (vcetne bodů volby procedůry s rezem)
Indexacní instrůkce znemožnůjí v dobe prekladů rozhodnoůt, zda bůde alokován bod volby M príklad: ?- a(X). může být nedeterministické, ale ?- a(1). může být deterministické
cut_last:     B := CUT save_cut Y:    Y := CUT load_cut Y:     B := Y
Hana Růdová, Logické programování I, 7. kvetna 2010
37
Preklad
WAM - rez
Implementace rezu (opakování): odstranení bodu volby mezi soucasným vrcholem zásobníku a bodem volby procedury, která rez vyvolala (vcetne bodu volby procedury s rezem)
Indexacní instrukce znemožnují v dobe prekladu rozhodnout, zda bude alokován bod volby M príklad: ?- a(X). muže být nedeterministické, ale ?- a(1). muže být deterministické
cut_1ast:     B := CUT save_cut Y:    Y := CUT 1oad_cut Y:     B := Y
Hodnota registru B je uchovávána v registru CUT instrukcemi call a execute.
Je-li rez prvním predikátem klauzule, použije se rovnou cut_1ast. V opacném prípade se použije
jako první instrukce save_cut Y a v míste skutecného volání rezu se použije 1oad_cut Y.
Hana Rudová, Logické programování I, 7. kvetna 2010
37
Preklad
WAM - rez
Implementace rezu (opakování): odstranení bodu volby mezi současným vrcholem zásobníku a bodem volby procedury, která rez vyvolala (včetne bodu volby procedury s rezem)
Indexační instrukce znemožnují v dobe prekladu rozhodnout, zda bude alokován bod volby M príklad: ?- a(X). muže být nedeterministické, ale ?- a(1). muž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 call a execute.
Je-li rez prvním predikátem klauzule, použije se rovnou cut_last. V opačném prípade se použije
jako první instrukce save_cut Y a v míste skutečného volání rezu se použije load_cut Y.
Prí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 A1,2; cut_last; put A2,A1; execute c/1 execute d/2
Hana Rudová, Logické programování I, 7. kvetna 2010 37 Preklad
WAM - optimalizace
1. Indexace klauzulí
2. Generování optimální posloupnosti instrukcí WAMu
3. Odstranění redundancí pri generování cílového kódu.
Hana Rudová, Logické programování I, 7. kvetna 2010
38
Preklad
WAM - optimalizace
1. Indexace klauzulí
2. Generování optimální posloupnosti instrukcí WAMu
3. Odstranení redundancí pri generování cílového kódu.
& Príklad: a(X,Y,Z) b(f,X,Y,Z).
naivní kód (vytvorí kompilátor pracující striktne zleva doprava) vs.
optimalizovaný kód (pocet registrů a tedy i pocet instrukcí/presunů v pameti 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	A1,f	| put_const	A1,f
put_value	A2,A5	| execute	b/4
put_value	A3,A6		
put_value	A4,A7		
execute	b/4		
Hana Rudová, Logické programování I, 7. kvetna 2010 38 Preklad