Implementace Prologu Literatura: M Matýska L, Toman D.: Implementační techniky Prologu, Informační systémy, (1990), 21-59. http://www.i cs.muni.cz/people/matyska/vyuka/1p/1p.html Opakování: základní pojmy 3 Konečná množina klauzulí Hlava :- Tělo tvoří program P. M Hlava je literál Tělo je (eventuálně prázdná) konjunkce literálů 7i,... Ta, a > 0 -0 Literál je tvořen m-árním predikátovým symbolem (m/p) a m termy (argumenty) M Term je konstanta, proměnná nebo složený term. 3 Složený term s n termy na místě argumentů M Dotaz (cíl) je neprázdná množina literálů. Hana Rudová, Logické programování I, 14. května 201 3 2 Implementace Prologu Interpretace Deklarativní sémantika: Hlava platí, platí-li jednotlivé literály těla. Hana Rudová, Logické programování I, 14. května 201 3 3 Implementace Prologu Interpretace Deklarativní sémantika: Hlava platí, platí-li jednotlivé literály těla. Procedurální (imperativní) sémantika: Entry: Hlava:: { call Ti ■ ■ ■ call Ta } Volání procedury s názvem Hlava uspěje, pokud uspěje volání všech procedur (literálů) v těle. Hana Rudová, Logické programování I, 14. května 201 3 3 Implementace Prologu Interpretace Deklarativní sémantika: Hlava platí, platí-li jednotlivé literály těla. Procedurální (imperativní) sémantika: Entry: Hlava:: { call Ti ■ ■ ■ call Ta } Volání procedury s názvem Hlava uspěje, pokud uspěje volání všech procedur (literálů) v těle. Procedurální sémantika = podklad pro implementaci Hana Rudová, Logické programování I, 14. května 201 3 3 Implementace Prologu Abstraktní interpret Vstup: Logický program P a dotaz G. 1. Inicializuj množinu cílů S literály z dotazu G; S: =G 2. while ( S != empty ) do 3. Vyber AeS a dále vyber klauzuli A' : -Bi, . . . , Bn (n > 0) z programu P takovou, že 3 0) z programu P takovou, že 3 každá instanciace ekvivalentní zdrojovému termu M zdrojový term s proměnnými => dvě instance se mohou lišit aktuálními hodnotami proměnných, jedinečnost zajišťuje kopírování struktur nebo sdílení struktur Hana Rudová, Logické programování I, 14. května 201 3 10 Implementace Prologu Kopírování struktur Příklad: a(b(X),c(X,Y),d), FUNCT a/3 REF -REF -CONST d FUNCT c/2 - REF FREE Y FUNCT b/1 FREE X Hana Rudová, Logické programování I, 14. května 201 3 Implementace Prologu Kopírování struktur II Term F s aritou A reprezentován A+l slovy: S funktor a arita v prvním slově 3 2. slovo nese první argument (resp. odkaz na jeho hodnotu) i 3 A+l slovo nese hodnotu A-tého argumentu 3 Reprezentace vychází z orientovaných acyklických grafů: a/3 d i c/2 Y b/1 X Vykopírována každá instance => kopírování struktur Termy ukládány na globální zásobník Hana Rudová, Logické programování I, 14. května 201 3 1 2 Implementace Prologu Sdílení struktur Vychází z myšlenky, že při reprezentaci je třeba řešit přítomnost proměnných Instance termu < kostra_termu; rámec > kostra_termu je zdrojový term s očíslovanými proměnnými rámec je vektor aktuálních hodnot těchto proměnných S í-tá položka nese hodnotu í-té proměnné v původním termu Hana Rudová, Logické programování I, 14. května 2013 13 Implementace Prologu Sdílení struktur II Příklad: a(b(X),c(X,Y),d) reprezentuje < a(b($l),c($l,$2),d) ; [FREE, FREE] > kde symbolem $i označujeme í-tou proměnnou. Hana Rudová, Logické programování I, 14. května 201 3 14 Implementace Prologu Sdílení struktur II Příklad: a(b(X),c(X,Y),d) reprezentuje < a(b($l),c($l,$2),d) ; [FREE, FREE] > kde symbolem $i označujeme í-tou proměnnou. Implementace: < &kostra_termu; &rámec > (& vrací adresu objektu) Všechny instance sdílí společnou kostru_termu => sdílení struktur Hana Rudová, Logické programování I, 14. května 201 3 14 Implementace Prologu Srovnání: příklad M Naivní srovnání: sdílení paměťově méně náročné Hana Rudová, Logické programování I, 14. května 201 3 Implementace Prologu Srovnání: příklad M Naivní srovnání: sdílení paměťově méně náročné M Platí ale pouze pro rozsáhlé termy přítomné ve zdrojovém kódu Hana Rudová, Logické programování I, 14. května 201 3 Implementace Prologu Srovnání: příklad Naivní srovnání: sdílení paměťově méně náročné Platí ale pouze pro rozsáhlé termy přítomné ve zdrojovém kódu Postupná tvorba termů: A = a(K,L,M), K = b(X), L = c(X,Y), M = d Sdílení termů kostra.a K M:d kostra.b kostrac X Hana Rudová, Logické programování I, 14. května 201 3 1 5 Implementace Prologu Srovnání: příklad - pokračování M Kopírování struktur: A = a(K,L,M),K = b(X), L = c(X,Y), M = d FUNCT a/3 REF -REF -CONST d FUNCT c/2 - REF FREE Y FUNCT b/1 FREE X Hana Rudová, Logické programování I, 14. května 201 3 16 Implementace Prologu Srovnání: příklad - pokračování M Kopírování struktur: A = a(K,L,M),K = b(X), L = c(X,Y), M = d FUNCT a/3 REF -REF -CONST d FUNCT c/2 - REF FREE Y FUNCT b/1 FREE X tj. identické jako přímé vytvoření termu a(b(X) , c(X, Y) , d) Hana Rudová, Logické programování 1,14. května 2013 16 Implementace Prologu Srovnání II M Složitost algoritmů pro přístup k jednotlivým argumentům sdílení struktur: nutná víceúrovňová nepřímá adresace M kopírování struktur: bez problémů 3 jednodušší algoritmy usnadňují i optimalizace Hana Rudová, Logické programování I, 14. května 201 3 Implementace Prologu Srovnání M Složitost algoritmů pro přístup k jednotlivým argumentům sdílení struktur: nutná víceúrovňová nepřímá adresace M kopírování struktur: bez problémů 3 jednodušší algoritmy usnadňují i optimalizace M Lokalita přístupů do paměti M sdílení struktur: přístupy rozptýleny po paměti M kopírování struktur: lokalizované přístupy 3 při stránkování paměti - rozptýlení vyžaduje přístup k více stránkám Hana Rudová, Logické programování I, 14. května 201 3 Implementace Prologu Srovnání M Složitost algoritmů pro přístup k jednotlivým argumentům sdílení struktur: nutná víceúrovňová nepřímá adresace M kopírování struktur: bez problémů 3 jednodušší algoritmy usnadňují i optimalizace M Lokalita přístupů do paměti M sdílení struktur: přístupy rozptýleny po paměti M kopírování struktur: lokalizované přístupy 3 při stránkování paměti - rozptýlení vyžaduje přístup k více stránkám M Z praktického hlediska neexistuje mezi těmito přístupy zásadní rozdíl Hana Rudová, Logické programování I, 14. května 201 3 Implementace Prologu Řízení výpočtu M Dopřed ný výpočet M po úspěchu (úspěšná redukce) St jednotlivá volání procedur skončí úspěchem 3 klasické volání rekurzivních procedur Hana Rudová, Logické programování I, 14. května 201 3 18 Implementace Prologu Řízení výpočtu Dopřed ný výpočet M po úspěchu (úspěšná redukce) 3 jednotlivá volání procedur skončí úspěchem 3 klasické volání rekurzivních procedur M Zpětný výpočet (backtracking) po neúspěchu vyhodnocení literálu (neúspěšná redukce) 3 nepodaří se unifikace aktuálních a formálních parametrů hlavy 3 návrat do bodu, kde zůstala nevyzkoušená alternativa výpočtu je nutná obnova původních hodnot jednotlivých proměnných 3 po nalezení místa s dosud nevyzkoušenou klauzulí pokračuje dále dopředný výpočet Hana Rudová, Logické programování I, 14. května 201 3 18 Implementace Prologu Aktivační záznam M Volání (=aktivace) procedury Aktivace sdílí společný kód, liší se obsahem aktivačního záznamu M Aktivační záznam uložen na lokálním zásobníku Hana Rudová, Logické programování I, 14. května 201 3 19 Implementace Prologu Aktivační záznam Volání (=aktivace) procedury M Aktivace sdílí společný kód, liší se obsahem aktivačního záznamu Aktivační záznam uložen na lokálním zásobníku Dopřed ný výpočet M stav výpočtu v okamžiku volání procedury M aktuální parametry M lokální proměnné M pomocné proměnné ('a la registry) Hana Rudová, Logické programování I, 14. května 201 3 19 Implementace Prologu Aktivační záznam Volání (=aktivace) procedury M Aktivace sdílí společný kód, liší se obsahem aktivačního záznamu Aktivační záznam uložen na lokálním zásobníku Dopřed ný výpočet M stav výpočtu v okamžiku volání procedury M aktuální parametry M lokální proměnné M pomocné proměnné ('a la registry) M Zpětný výpočet (backtracking) M hodnoty parametrů v okamžiku zavolání procedury M následující klauzule pro zpracování při neúspěchu Hana Rudová, Logické programování I, 14. května 201 3 19 Implementace Prologu Aktivační záznam a roll-back 3 Neúspěšná klauzule mohla nainstanciovat nelokální proměnné 3 a(X) :- X = b(c,Y), Y = d. ?- W = b(Z,e), a(W). Hana Rudová, Logické programování I, 14. května 201 3 20 Implementace Prologu Aktivační záznam a roll-back Neúspěšná klauzule mohla nainstanciovat nelokální proměnné M a(X) :- X = b(c,Y), Y = d. ?- W = b(Z,e), a(W) . (viz instanciace Z) Hana Rudová, Logické programování I, 14. května 201 3 20 Implementace Prologu Aktivační záznam a roll-back M Neúspěšná klauzule mohla nainstanciovat nelokální proměnné 3 a(X) :- X = b(c,Y), Y = d. ?- W = b(Z,e), a(W) . (viz instanciace Z) Při návratu je třeba obnovit (roll-back) původní hodnoty proměnných M Využijeme vlastností logických proměnných 3 instanciovat lze pouze volnou proměnnou 3 jakmile proměnná získá hodnotu, nelze ji změnit jinak než návratem výpočtu => původní hodnoty všech proměnných odpovídají volné proměnné Hana Rudová, Logické programování I, 14. května 201 3 20 Implementace Prologu Aktivační záznam a roll-back M Neúspěšná klauzule mohla nainstanciovat nelokální proměnné 3 a(X) :- X = b(c,Y), Y = d. ?- W = b(Z,e), a(W) . (viz instanciace Z) Při návratu je třeba obnovit (roll-back) původní hodnoty proměnných M Využijeme vlastností logických proměnných 3 instanciovat lze pouze volnou proměnnou 3 jakmile proměnná získá hodnotu, nelze ji změnit jinak než návratem výpočtu => původní hodnoty všech proměnných odpovídají volné proměnné Stopa (trail): zásobník s adresami instanciovaných proměnných 3 ukazatel na aktuální vrchol zásobníku uchováván v aktivačním záznamu M při neúspěchu jsou hodnoty proměnných na stopě v úseku mezi aktuálním a uloženým vrcholem zásobníku změněny na „volná" Hana Rudová, Logické programování I, 14. května 201 3 20 Implementace Prologu Aktivační záznam a roll-back M Neúspěšná klauzule mohla nainstanciovat nelokální proměnné 3 a(X) :- X = b(c,Y), Y = d. ?- W = b(Z,e), a(W) . (viz instanciace Z) Při návratu je třeba obnovit (roll-back) původní hodnoty proměnných M Využijeme vlastností logických proměnných 3 instanciovat lze pouze volnou proměnnou 3 jakmile proměnná získá hodnotu, nelze ji změnit jinak než návratem výpočtu => původní hodnoty všech proměnných odpovídají volné proměnné Stopa (trail): zásobník s adresami instanciovaných proměnných 3 ukazatel na aktuální vrchol zásobníku uchováván v aktivačním záznamu M při neúspěchu jsou hodnoty proměnných na stopě v úseku mezi aktuálním a uloženým vrcholem zásobníku změněny na „volná" M Globální zásobník: pro uložení složených termů 3 ukazatel na aktuální vrchol zásobníku uchováván v aktivačním záznamu M při neúspěchu vrchol zásobníku snížen podle uschované hodnoty v aktivačním záznamu Hana Rudová, Logické programování I, 14. května 201 3 20 Implementace Prologu Okolí a bod volby Aktivační záznam úspěšně ukončené procedury nelze odstranit z lokálního zásobníku => rozdělení aktivačního záznamu: okolí (environment) - informace nutné pro dopředný běh programu M bod volby (choice point) - informace nezbytné pro zotavení po neúspěchu Hana Rudová, Logické programování I, 14. května 201 3 21 Implementace Prologu Okolí a bod volby Aktivační záznam úspěšně ukončené procedury nelze odstranit z lokálního zásobníku => rozdělení aktivačního záznamu: okolí (environment) - informace nutné pro dopředný běh programu M bod volby (choice point) - informace nezbytné pro zotavení po neúspěchu ukládány na lokální zásobník M samostatně provázány (odkaz na předchozí okolí resp. bod volby) Hana Rudová, Logické programování I, 14. května 201 3 21 Implementace Prologu Okolí a bod volby Aktivační záznam úspěšně ukončené procedury nelze odstranit z lokálního zásobníku => rozdělení aktivačního záznamu: okolí (environment) - informace nutné pro dopředný běh programu M bod volby (choice point) - informace nezbytné pro zotavení po neúspěchu ukládány na lokální zásobník M samostatně provázány (odkaz na předchozí okolí resp. bod volby) Důsledky: M samostatná práce s každou částí aktivačního záznamu (optimalizace) Hana Rudová, Logické programování I, 14. května 201 3 21 Implementace Prologu Okolí a bod volby Aktivační záznam úspěšně ukončené procedury nelze odstranit z lokálního zásobníku => rozdělení aktivačního záznamu: okolí (environment) - informace nutné pro dopředný běh programu M bod volby (choice point) - informace nezbytné pro zotavení po neúspěchu ukládány na lokální zásobník M samostatně provázány (odkaz na předchozí okolí resp. bod volby) Důsledky: M samostatná práce s každou částí aktivačního záznamu (optimalizace) alokace pouze okolí pro deterministické procedury Hana Rudová, Logické programování I, 14. května 201 3 21 Implementace Prologu Okolí a bod volby Aktivační záznam úspěšně ukončené procedury nelze odstranit z lokálního zásobníku => rozdělení aktivačního záznamu: okolí (environment) - informace nutné pro dopředný běh programu M bod volby (choice point) - informace nezbytné pro zotavení po neúspěchu ukládány na lokální zásobník M samostatně provázány (odkaz na předchozí okolí resp. bod volby) Důsledky: M samostatná práce s každou částí aktivačního záznamu (optimalizace) alokace pouze okolí pro deterministické procedury M možnost odstranění okolí po úspěšném vykonání (i nedeterministické) procedury (pokud okolí následuje po bodu volby dané procedury) M pokud je okolí na vrcholu zásobníku Hana Rudová, Logické programování I, 14. května 201 3 21 Implementace Prologu Řez Prostředek pro ovlivnění běhu výpočtu programátorem M a(X) :- b(X), !, c(X). a(3). b(l). b(2). c(l). c(2). Hana Rudová, Logické programování I, 14. května 201 3 22 Implementace Prologu Řez Prostředek pro ovlivnění běhu výpočtu programátorem * a(X) :- b(X), !, c(X). a(3). b(l). b(2). c(l). c(2). Řez: neovlivňuje dopředný výpočet, má vliv pouze na zpětný výpočet M Odstranění alternativních větví výpočtu => odstranění odpovídajících bodů volby 3 tj. odstranění bodů volby mezi současným vrcholem zásobníku a bodem volby procedury, která řez vyvolala (včetně bodu volby procedury s řezem) => změna ukazatele na „nejmladší" bod volby Hana Rudová, Logické programování I, 14. května 201 3 22 Implementace Prologu Řez M Prostředek pro ovlivnění běhu výpočtu programátorem 3 a(X) :- b(X), !, c(X). a(3). b(l). b(2). c(l). c(2). Řez: neovlivňuje dopředný výpočet, má vliv pouze na zpětný výpočet Odstranění alternativních větví výpočtu => odstranění odpovídajících bodů volby 3 tj. odstranění bodů volby mezi současným vrcholem zásobníku a bodem volby procedury, která řez vyvolala (včetně bodu volby procedury s řezem) => změna ukazatele na „nejmladší" bod volby => Vytváření deterministických procedur => Optimalizace využití zásobníku Hana Rudová, Logické programování I, 14. května 201 3 22 Implementace Prologu Interpret Prologu Základní principy: M klauzule uloženy jako termy programová databáze pro uložení klauzulí má charakter haldy St umožňuje modifikovatelnost prologovských programů za běhu (assert) M klauzule zřetězeny podle pořadí načtení M triviální zřetězení Hana Rudová, Logické programování I, 14. května 201 3 23 Implementace Prologu Interpret Prologu Základní principy: M klauzule uloženy jako termy programová databáze pro uložení klauzulí má charakter haldy St umožňuje modifikovatelnost prologovských programů za běhu (assert) M 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, 14. května 201 3 23 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, 14. května 201 3 24 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, 14. května 201 3 24 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í I, 14. května 201 3 24 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, 14. května 201 3 25 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, 14. května 201 3 25 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í I, 14. května 201 3 2 5 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, 14. května 201 3 26 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, 14. května 201 3 27 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í: 3 podle pořadí klauzulí (aktuální argument je volná proměnná) 3 dle konstant (aktuální je argument konstanta) 3 formální argument je seznam (aktuální argument je seznam) 3 dle struktur (aktuální argument je struktura) Hana Rudová, Logické programování I, 14. května 201 3 27 Implementace Prologu Indexace argumentů II M Složitější indexační techniky 3 podle všech argumentů M podle nejvíce diskriminujícího argumentu 3 kombinace argumentů (indexové techniky z databází) zejména pro přístup k faktům Hana Rudová, Logické programování I, 14. května 201 3 28 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, 14. května 201 3 29 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, 14. května 201 3 29 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, 14. května 201 3 30 Implementace Prologu TRO - příklad Program: append([], L, L). append([A|X], L, [A|Y]) :- append(X, L, Y). Dotaz: ?- append([a,b,c], [x], L). append volán rekurzivně 4krát bez TRO: 4 okolí, lineární paměťová náročnost M s TRO: 1 okolí, konstatní paměťová náročnost Hana Rudová, Logické programování I, 14. května 201 3 30 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, 14. května 201 3 31 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, 14. května 201 3 31 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) 3 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, 14. května 201 3 31 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í I, 14. května 201 3 31 Implementace Prologu 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) 3 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, 14. května 201 3 32 Implementace Prologu 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, 14. května 201 3 33 Implementace Prologu 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í I, 14. května 201 3 34 Implementace Prologu 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 unify 3 obecná unifikace pouze při get_value M unify 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 unify 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í I, 14. května 201 3 3 5 Implementace Prologu 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, 14. května 201 3 36 Implementace Prologu WAM - optimalizace 1. Indexace klauzulí 2. Generování optimální posloupnosti instrukcí WAMu 3. Odstranění redundancí při generování cílového kódu. Hana Rudová, Logické programování I, 14. května 201 3 37 Implementace Prologu WAM - optimalizace 1. Indexace klauzulí 2. Generování optimální posloupnosti instrukcí WAMu 3. Odstranění redundancí při generování cílového kódu. Příklad: a(X,Y,Z) :- b(f,X,Y,Z). naivní kód (vytvoří kompilátor pracující striktně zleva doprava) vs. optimalizovaný kód (počet registrů a tedy i počet instrukcí/přesunů v paměti snížen): get_var A1,A5 | get_var 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í I, 14. května 201 3 37 Implementace Prologu 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, 14. května 201 3 38 Implementace Prologu 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, 14. května 201 3 39 Implementace Prologu WAM - indexace M Provázání klauzulí: instrukce XX_me_el se: 3 první klauzule: try_me_else; založí bod volby 3 poslední klauzule: trust_me_el se; zruší nejmladší bod volby 3 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 3 trust Hana Rudová, Logické programování I, 14. května 201 3 39 Implementace Prologu 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, 14. května 201 3 39 Implementace Prologu 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, 14. května 201 3 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 40 Implementace Prologu WAM - řízení výpočtu M execute Proč: ekvivalentní příkazu goto Hana Rudová, Logické programování I, 14. května 201 3 41 Implementace Prologu WAM - řízení výpočtu M execute Proč: ekvivalentní příkazu goto M proceed: zpracování faktů Hana Rudová, Logické programování I, 14. května 201 3 41 Implementace Prologu WAM - řízení výpočtu A execute Proc: ekvivalentní příkazu goto M proceed: zpracování faktů & allocate: alokuje okolí (pro některé klauzule netřeba, proto explicitně generováno) Hana Rudová, Logické programování I, 14. května 201 3 41 Implementace Prologu 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, 14. května 201 3 41 Implementace Prologu 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í I, 14. května 201 3 41 Implementace Prologu WAM - řez Implementace řezu (opakování): odstranění bodů volby mezi současným vrcholem zásobníku a bodem volby procedury, která řez vyvolala (včetně bodu volby procedury s řezem) Indexační instrukce znemožňují v době překladu rozhodnout, zda bude alokován bod volby M příklad:?- a(X) . může být nedeterministické, ale ?- a(l) . může být deterministické Hana Rudová, Logické programování I, 14. května 201 3 42 Implementace Prologu WAM - řez Implementace řezu (opakování): odstranění bodů volby mezi současným vrcholem zásobníku a bodem volby procedury, která řez vyvolala (včetně bodu volby procedury s řezem) Indexační instrukce znemožňují v době překladu rozhodnout, zda bude alokován bod volby M příklad:?- a(X) . může být nedeterministické, ale ?- a(l) . může být deterministické cut_last: B := CUT save_cut Y: Y := CUT load_cut Y: B := Y Hana Rudová, Logické programování I, 14. května 201 3 42 Implementace Prologu WAM - řez Implementace řezu (opakování): odstranění bodů volby mezi současným vrcholem zásobníku a bodem volby procedury, která řez vyvolala (včetně bodu volby procedury s řezem) Indexační instrukce znemožňují v době překladu rozhodnout, zda bude alokován bod volby M příklad:?- a(X) . může být nedeterministické, ale ?- a(l) . může být deterministické cut_last: B := CUT save_cut Y: Y := CUT load_cut Y: B := Y Hodnota registru B je uchovávána v registru CUT instrukcemi cal 1 a execute. Je-li řez prvním predikátem klauzule, použije se rovnou cut_last. V opačném případě se použije jako první instrukce save_cut Y a v místě skutečného volání řezu se použije load_cut Y. Hana Rudová, Logické programování I, 14. května 201 3 42 Implementace Prologu WAM - řez Implementace řezu (opakování): odstranění bodů volby mezi současným vrcholem zásobníku a bodem volby procedury, která řez vyvolala (včetně bodu volby procedury s řezem) Indexační instrukce znemožňují v době překladu rozhodnout, zda bude alokován bod volby M příklad:?- a(X) . může být nedeterministické, ale ?- a(l) . může být deterministické cut_last: B := CUT save_cut Y: Y := CUT load_cut Y: B := Y Hodnota registru B je uchovávána v registru CUT instrukcemi cal 1 a execute. Je-li řez prvním predikátem klauzule, použije se rovnou cut_last. V opačném případě se použije jako první instrukce save_cut Y a v místě skutečného volání řezu se použije load_cut Y. Příklad: a(X,Z) :- b(X), ! , c(Z). a(2,Z) :- !, c(Z). a(X,Z) :- d(X,Z). odpovídá save_cut Y2; get A2,Y1; call b/1,2; load_cut Y2; put Y1,A1; execute c/1 get_const AI,2; cut_last; put A2,A1; execute c/1 execute d/2 Hana Rudová, Logické programování I, 14. května 201 3 42 Implementace Prologu