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žnuje modifikovatelnost prologovských programu za behu (assert)
JS> klauzule zretezeny podle poradí nactení iľ triviální zretezení
Hana Rudová, Logické programování I, 13. kvetna 2011
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, 13. kvetna 2011
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 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)
Hana Rudová, Logické programování I, 13. kvetna 2011
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.
Hana Rudová, Logické programování I, 13. kvetna 2011
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, 13. kvetna 2011 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, 13. kvetna 2011
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, 13. kvetna 2011
4
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.
-í* Unifikace argumentů hlavy - obecný unifikační algoritmus
Současne poznací adresy instanciovaných proměnný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, 13. kvetna 2011 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, 13. kvetna 2011
5
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 cástecne instanciovaným argumentem vždy deterministická (pouze jedna klauzule může uspet)
Hana Rudová, Logické programování I, 13. kvetna 2011
6
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)
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, 13. kvetna 2011 6 Implementace Prologu
Indexace argumentů II
C Složitejší indexacní techniky
a podle všech argumentu %> podle nejvíce diskriminujícího argumentu Jr kombinace argumentu (indexové techniky z databází) zejména pro prístup k faktum
Hana Rudová, Logické programování I, 13. kvetna 2011
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, 13. května 2011
8
Implementace Prologu
Tail Recursion Optimization, TRO
Iterace provádena pomocí rekurze => lineární pameťová náročnost 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 prípade úspechu se rovnou pokračuje
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 muže být volána prímo z kontextu volající klauzule.
Hana Rudová, Logické programování I, 13. kvetna 2011
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, 13. kvetna 2011
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, 13. kvetna 2011
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, 13. května 2011
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, 13. kvetna 2011
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, 13. kvetna 2011
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í
„globalizace" lokálních promenný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, 13. kvetna 2011 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, 13. kvetna 2011 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, 13. kvetna 2011
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 přepsat 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
Hana Rudová, Logické programování I, 13. kvetna 2011
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
C Preklad Prologu založen na principu existence abstraktního počítače V dalším se venujeme jeho odvození a vlastnostem
Hana Rudová, Logické programování I, 13. kvetna 2011 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, 13. kvetna 2011
13
Preklad
Parciální vyhodnocení - príklad
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, 13. kvetna 2011
14
Preklad
Parciální vyhodnocení - pří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).
Hana Rudová, Logické programování I, 13. kvetna 2011
14
Preklad
Parciální vyhodnocení - príklad
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, 13. kvetna 2011
14
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
Hana Rudová, Logické programování I, 13. kvetna 2011
15
Preklad
Parciální vyhodnocení II
Konstrukce překladace: 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, 13. kvetna 2011 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, 13. kvetna 2011
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í, predání a prevzetí parametrů ...)
& vetšina unifikací nevyžaduje obecnou unifikaci a lze je nahradit jednoduššími operacemi
Zviditelnení 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, 13. kvetna 2011 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, 13. kvetna 2011
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).
mrify(A1,[A|X]),
unify(A2,L),
mrify(A3,[A|Y]),
put(X,B1),
put(L,B2),
put(Y,B3),
apperd(B1,B2,B3).
| apperd([],L,L).
| apperd([A|X],L,[A|Y]
apperd(X,L,Y).
Hana Rudová, Logické programování I, 13. kvetna 2011
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, 13. kvetna 2011
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, 13. kvetna 2011
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 součástí objektu
volná promenná FREE, konstanta CONST, celé číslo INT, odkaz REF, složený term FUNCT
Hana Rudová, Logické programování I, 13. kvetna 2011
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 soucástí objektu
volná promenná FREE, konstanta CONST, celé císlo INT, odkaz REF, složený term FUNCT
-í* je-li A adresa a i celocíselná konstanta, pak výraz A+i reprezentuje adresu o i slov vyšší (ukazatelová aritmetika)
Hana Rudová, Logické programování I, 13. kvetna 2011 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, 13. kvetna 2011
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, 13. kvetna 2011
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, 13. kvetna 2011
20
Preklad
unify pro konstantu
2) T je konstanta: výsledkem je test nebo prirazení
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 prepsat do kompaktního tvaru
unify(A,T) :-atomic(T), unify_const(A,T).
kde unify_const/2 provede príslušný test nebo prirazení.
Hana Rudová, Logické programování I, 13. kvetna 2011 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 argumentu
um'fy(A,T)
struct(T),
furctor(T,F,N),
um'fy_struct(F,N,A),
T =.. [_|TlL um'fy_args(Tl,A+1).
Predikát urify_struct/3 je analogický výše použitým predikátum urify_var/2 a urify_corst/2.
Hana Rudová, Logické programování I, 13. kvetna 2011
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 =.. [_|Tl], 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) :-unify(A,T), unify_args(Tl,A+1).
Hana Rudová, Logické programování I, 13. kvetna 2011 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, 13. kvetna 2011
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, 13. kvetna 2011
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, 13. kvetna 2011
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, 13. kvetna 2011
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
=> stačí provést unification(A2,A3)
Hana Rudová, Logické programování I, 13. kvetna 2011
24
Preklad
Výsledný tvar append/3
append(A1, A2, A3) :- append(A1, A2, A3) :-
unify_const(A1,[]), unify(A1,[]),
unification(A2,A3). unify(A2,L), unify(A3,L).
append(A1, A2, A3) :- append(A1, A2, A3) :-
unify_struct('.',2,A1), unify(A1,[A|X]), unify_var(A,A1+1), unify_var(X,A1+2),
unify_var(L,A2), unify(A2,L),
unify_struct('.',2,A3), unify(A3,[A|Y]), unification(A1+1,A3+1), unify_var(Y,A3+2),
put(X,B1), put(L,B2), put(Y,B3),
append(A1+2,A2,A3+2). append(B1,B2,B3).
Vetšina původních unifikací převedena na jednodušší operace;
unifikace v posledním kroku je nezbytná (důsledkem dvojího výskytu promenné)
Hana Rudová, Logické programování I, 13. kvetna 2011
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 |
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, 13. kvetna 2011
26
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
Vyzkoušejte si: de1ete(X,  [YjT],  [Y|T1]) :- de1ete(X, T, T1).
Hana Rudová, Logické programování I, 13. kvetna 2011
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, 13. kvetna 2011
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, 13. kvetna 2011
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í promenné: Y1,Y2,...
-fc abstraktní znázornení lok. promenných na zásobníku
Hana Rudová, Logické programování I, 13. kvetna 2011 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, 13. kvetna 2011 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, 13. kvetna 2011
31
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.
Hana Rudová, Logické programování I, 13. kvetna 2011
32
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, 13. kvetna 2011 32 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, lB. kvetna 20ll
BB
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, 13. kvetna 2011
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
retry -i- trust
Hana Rudová, Logické programování I, 13. kvetna 2011
34
Preklad
WAM - inděxacě
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 -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, 13. kvetna 2011
34
Preklad
Príklad indexace instrukcí
Procedure a(atom) :- body1. a(1) :- body2. a(2) :- body3.
a([X|Y]) :- body4. a([X|Y]) :- body5. a(s(N)) :- body6. a(f(N)) :- body7.
odpovídají instrukce
a:	switch_on_term L1, L2,		L3, L4	L5a:	body2	
L2:	switch_on_const	atom	:L1a	L6:	retry_me_else	L7
		1	:L5a	L6a:	body3	
		2	:L6a	L7:	retry_me_else	L8
L3:	try	L7a		L7a:	body4	
	trust	L8a		L8:	retry_me_else	L9
L4:	switch_on_struct	s/1	:L9a	L8a:	body5	
		f/1	:L10a	L9:	retry_me_else	L10
L1:	try_me_else L5			L9a:	body6	
L1a:	body1			L10:	trust_me_else	fail
L5:	retry_me_else L6			L10a:	body7	
Hana Rudová, Logické programování I, 13. kvetna 2011
35
Preklad
WAM - rízení výpoctu
& execute Proc: ekvivalentní príkazu goto
Hana Rudová, Logické programování I, 13. kvetna 2011
36
Preklad
WAM - rízení výpoctu
& execute Proc: ekvivalentní príkazu goto J5> proceed: zpracování faktu
Hana Rudová, Logické programování I, 13. kvetna 2011
36
Preklad
WAM - rízení výpočtu
& execute Proc: ekvivalentní pří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, 1S. kvetna 2011
S6
Preklad
WAM - ř ízení výpočtu
& execute Proc: ekvivalentní příkazu goto
J5> proceed: zpracování faktů
M allocate: alokuje okolí (pro některé klauzule netřeba, 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)
Hana Rudová, Logické programování I, 13. kvetna 2011
36
Preklad
WAM - rízení 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)
& 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, 13. kvetna 2011 36 Preklad