Algoritmy pro CSP (pokračování) Prohledávání + konzistence m Splňování podmínek prohledáváním prostoru řešení M podmínky jsou užívány pasivně jako test 3 přiřazuji hodnoty proměnných a zkouším co se stane M vestavěný prohledávací algoritmus Prologu: backtracking, triviální: generuj & testuj Hana Rudová, Logické programování I, 9. května 201 2 2 Algoritmy pro CSP Prohledávání + konzistence Splňování podmínek prohledáváním prostoru řešení M podmínky jsou užívány pasivně jako test 3 přiřazuji hodnoty proměnných a zkouším co se stane M vestavěný prohledávací algoritmus Prologu: backtracking, triviální: generuj & testuj & úplná metoda (nalezneme řešení nebo dokážeme jeho neexistenci) M zbytečně pomalé (exponenciální): procházím i „evidentně" špatná ohodnocení Hana Rudová, Logické programování I, 9. května 201 2 2 Algoritmy pro CSP Prohledávání + konzistence Splňování podmínek prohledáváním prostoru řešení M podmínky jsou užívány pasivně jako test 3 přiřazuji hodnoty proměnných a zkouším co se stane M vestavěný prohledávací algoritmus Prologu: backtracking, triviální: generuj & testuj 3 úplná metoda (nalezneme řešení nebo dokážeme jeho neexistenci) 3 zbytečně pomalé (exponenciální): procházím i „evidentně" špatná ohodnocení Konzistenční (propagační) techniky M umožňují odstranění nekonzistentních hodnot z domény proměnných M neúplná metoda (v doméně zůstanou ještě nekonzistentní hodnoty) 3 relativně rychlé (polynomiální) Hana Rudová, Logické programování I, 9. května 201 2 2 Algoritmy pro CSP Prohledávání + konzistence Splňování podmínek prohledáváním prostoru řešení M podmínky jsou užívány pasivně jako test 3 přiřazuji hodnoty proměnných a zkouším co se stane M vestavěný prohledávací algoritmus Prologu: backtracking, triviální: generuj & testuj 3 úplná metoda (nalezneme řešení nebo dokážeme jeho neexistenci) 3 zbytečně pomalé (exponenciální): procházím i „evidentně" špatná ohodnocení Konzistenční (propagační) techniky M umožňují odstranění nekonzistentních hodnot z domény proměnných M neúplná metoda (v doméně zůstanou ještě nekonzistentní hodnoty) 3 relativně rychlé (polynomiální) Používá se kombinace obou metod 3 postupné přiřazování hodnot proměnným M po přiřazení hodnoty odstranění nekonzistentních hodnot konzistenčními technikami Hana Rudová, Logické programování I, 9. května 2012 2 Algoritmy pro CSP Prohledávání do hloubky m Základní prohledávací algoritmus pro problémy splňování podmínek Prohledávání stavového prostoru do hloubky (depth first search) m Dvě fáze prohledávání s navracením M dopředná fáze: proměnné jsou postupně vybírány, rozšiřuje se částečné řešení přiřazením konzistení hodnoty (pokud existuje) další proměnné & po vybrání hodnoty testujeme konzistenci M zpětná fáze: pokud neexistuje konzistentní hodnota pro aktuální proměnnou, algoritmus se vrací k předchozí přiřazené hodnotě Hana Rudová, Logické programování I, 9. května 201 2 3 Algoritmy pro CSP Prohledávání do hloubky m Základní prohledávací algoritmus pro problémy splňování podmínek Prohledávání stavového prostoru do hloubky (depth first search) m Dvě fáze prohledávání s navracením M dopředná fáze: proměnné jsou postupně vybírány, rozšiřuje se částečné řešení přiřazením konzistení hodnoty (pokud existuje) další proměnné 3 po vybrání hodnoty testujeme konzistenci M zpětná fáze: pokud neexistuje konzistentní hodnota pro aktuální proměnnou, algoritmus se vrací k předchozí přiřazené hodnotě m Proměnné dělíme na 3 minulé - proměnné, které už byly vybrány (a mají přiřazenu hodnotu) M aktuální - proměnná, která je právě vybrána a je jí přiřazována hodnota 3 budoucí - proměnné, které budou vybrány v budoucnosti Hana Rudová, Logické programování I, 9. května 2012 3 Algoritmy pro CSP Základní algoritmus prohledávání do hloubky m Pro jednoduchost proměnné očíslujeme a ohodnocujeme je v daném pořadí Na začátku voláno jako 1 abel i ng (G, 1) proceduře labeling(G,a) if a > |uzly(G)| then return uzly(G) for Vx e Da do if consistent(G,a) then % consistent(G,a) je nahrazeno FC(G,a), LA(G,a), R := label ing(G,a + 1) if R ^ fail then return R return fail end labeling Po přiřazení všech proměnných vrátíme jejich ohodnocení m Procedury consistent uvedeme pouze pro binární podmínky Hana Rudová, Logické programování I, 9. května 201 2 4 Algoritmy pro CSP Backtracking (BT) m Backtracking ověřuje v každém kroku konzistenci podmínek vedoucích z minulých proměnných do aktuální proměnné m Backtracking tedy zajišťuje konzistenci podmínek & na všech minulých proměnných M na podmínkách mezi minulými proměnnými a aktuální proměnnou Hana Rudová, Logické programování I, 9. května 201 2 5 Algoritmy pro CSP Backtracking (BT) m Backtracking ověřuje v každém kroku konzistenci podmínek vedoucích z minulých proměnných do aktuální proměnné m Backtracking tedy zajišťuje konzistenci podmínek M na všech minulých proměnných M na podmínkách mezi minulými proměnnými a aktuální proměnnou 3 procedure BT(G,a) Q-={(Ví, V a) £ hrany(G) , í < a} % hrany vedoucí z minulých proměnných do aktuální Consistent := true while Q neni prázdná a Consistent do vyber a smaž libovolnou hranu (Vfe,Vm) z Q Consistent := not revise(Vk,Vm) % pokud vyřadíme prvek, bude doména prázdná return Consistent end BT Hana Rudová, Logické programování I, 9. května 201 2 5 Algoritmy pro CSP Příklad: backtracking -» Omezení: Vi, V2, V3 in 1... 3, V1#=3xV3 M červené čtverečky: chybný pokus o instanciaci, řešení neexistuje 3 nevyplněná kolečka: nalezeno řešení M černá kolečka: vnitřní uzel, máme pouze částečné přiřazení Hana Rudová, Logické programování I, 9. května 2012 6 Algoritmy pro CSP Kontrola dopředu (FC - forward checking) m FC je rozšíření backtrackingu FC navíc zajišťuje konzistenci mezi aktuální proměnnou a budoucími proměnnými, které jsou s ní spojeny dosud nesplněnými podmínkami Hana Rudová, Logické programování I, 9. května 201 2 7 Algoritmy pro CSP Kontrola dopředu (FC - forward checking) m FC je rozšíření backtrackingu FC navíc zajišťuje konzistenci mezi aktuální proměnnou a budoucími proměnnými, které jsou s ní spojeny dosud nesplněnými podmínkami m proceduře FC(G,a) Q-={(Ví, V a) £ hrany(G) , í > a} % přidání hran z budoucích do aktuální proměnné Consistent := true while Q neni prázdná a Consistent do vyber a smaž libovolnou hranu (Vfe,Vm) z Q if revise((Vfc,Vm)) then Consistent := (\Dk\ > 0) % vyprázdnění domény znamená nekonzistenci return Consistent end FC Hrany z minulých proměnných do aktuální proměnné není nutno testovat Hana Rudová, Logické programování I, 9. května 201 2 7 Algoritmy pro CSP Příklad: kontrola dopředu Omezení: Vi, V2, V3 in 1... 3, c : Vi# = 3 x V3 Stavový prostor: Hana Rudová, Logické programování I, 9. května 201 2 8 Algoritmy pro CSP Pohled dopředu (LA - looking ahead) m LA je rozšíření FC, navíc ověřuje konzistenci hran mezi budoucími proměnnými m procedure LA(G,a) Q := {(Vi,Va) £ hrany(G), i > a} % začínáme s hranami do a Consistent := true while Q neni prázdná a Consistent do vyber a smaž libovolnou hranu (Vfc,Vm) z Q if revise((Vfc,Vm)) then Q := Q u {(Vi,Vk)\(VuVk) e hrany(G), i ± k,i ± m,í > a} Consistent := (|Dfc| > 0) return Consistent end LA Hana Rudová, Logické programování I, 9. května 201 2 9 Algoritmy pro CSP Pohled dopředu (LA - looking ahead) m LA je rozšíření FC, navíc ověřuje konzistenci hran mezi budoucími proměnnými 3 procedure LA(G,a) Q := {(VuVa) e hrany(G), í > a} % začínáme s hranami do a Consistent := true while Q neni prázdná a Consistent do vyber a smaž libovolnou hranu (Vfe,Vm) z Q if revise((Vfc,Vm)) then Q := Q u {(Ví, V*) I (Ví, Vjk) e hrany(G), i ŕ k, i ŕ m,í > a} Consistent := (|Dfc| > 0) return Consistent end LA M Hrany z minulých proměnných do aktuální proměnné opět netestujeme 3 Tato LA procedura je založena na AC-3, lze použít i jiné AC algoritmy m LA udržuje hranovou konzistenci: protože ale LA(G,a) používá AC-3, musíme zajistit iniciální konzistenci pomocí AC-3 ještě před startem prohledávání Hana Rudová, Logické programování I, 9. května 2012 9 Algoritmy pro CSP Příklad: pohled dopředu (pomocí AC-3) Omezení: V1.V2.V3 in 1...4, cl:Vi#>V2, c2 : V2# = 3 x V3 Stavový prostor (spouští se iniciální konzistence se před startem prohledávání) • c1 => V1 in 2..4 Y2in 1..3 c2 => V2=3 V3= 1 c1 => V1= 4 V< 4, V2 3, V3 1, Hana Rudová, Logické programování I, 9. května 201 2 10 Algoritmy pro CSP Přehled algoritmů Backtracking (BT) kontroluje v kroku a podmínky c(Vi,VJ,...,c(Va_i,Va) z minulých proměnných do aktuální proměnné proměnné 3"§. --~í =3 &) C N CD CD CD aktuálni ^ CD o =q- c &) o N ^ CD CD Hana Rudová, Logické programování I, 9. května 201 2 11 Algoritmy pro CSP Přehled algoritmů Backtracking (BT) kontroluje v kroku a podmínky c(Vi,VJ,...,c(Va_i,Va) z minulých proměnných do aktuální proměnné Kontrola dopředu (FC) kontroluje v kroku a podmínky C(Va+l, Va),...,C(Vn,Va) a z budoucích proměnných do aktuální proměnné FC LA n Hana Rudová, Logické programování I, 9. května 201 2 Přehled algoritmů Backtracking (BT) kontroluje v kroku a podmínky c(Vi,VJ,...,c(Va_i,Va) z minulých proměnných do aktuální proměnné Kontrola dopředu (FC) kontroluje v kroku a podmínky C(Va+l, Va),...,C(Vn,Va) z budoucích proměnných do aktuální proměnné Pohled dopředu (LA) kontroluje v kroku a podmínky Vř(a < l < n), Vfc(a < k < ri),k + l: c(Vk,Vi) z budoucích proměnných do aktuální proměnné LA a mezi budoucími proměnnými 1 j proměnné T \ 3 5. aktuálni Hana Rudová, Logické programování I, 9. května 201 2 11 Algoritmy pro CSP Cvičení 1. Jak vypadá stavový prostor řešení pro následující omezení A in 1 ..4, B in 3..4, C in 3..4, B #< C, A #= C při použití kontroly dopředu a uspořádání proměnných A,B,C? Popište, jaký typ propagace proběhne v jednotlivých uzlech. 2. Jak vypadá stavový prostor řešení pro následující omezení A in 1 ..4, B in 3..4, C in 3..4, B #< C, A #= C při použití pohledu dopředu a uspořádání proměnných A,B,C? Popište, jaký typ propagace proběhne v jednotlivých uzlech. 3. Jak vypadá stavový prostor řešení pro následující omezení domain([A,B,C],0,l), A#= B-l, C #= A*A při použití backtrackingu a pohledu dopředu a uspořádání proměnných A,B,C? Popište, jaký typ propagace proběhne v jednotlivých uzlech. Hana Rudová, Logické programování I, 9. května 2012 12 Algoritmy pro CSP Cvičení 1. Jaká jsou pravidla pro konzistenci mezí u omezení X#= Y+5? Jaké typy propagací pak proběhnou v následujícím příkladě při použití konzistence mezí? X in 1 ..20, Y in 1 ..20, X #= Y + 5, Y #> 1 0. 2. Ukažte, jak je dosaženo hranové konzistence v následujícím příkladu: domain([X,Y,Z],l ,5]), X #< Y, Z#= Y+l . Hana Rudová, Logické programování I, 9. května 2012 13 Algoritmy pro CSP 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 m Konečná množina klauzulí Hlava :- Tělo tvoří program P. Hlava je literál Tělo je (eventuálně prázdná) konjunkce literálů 7i,... Ta, a > 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. m Složený term s n termy na místě argumentů Dotaz (cíl) je neprázdná množina literálů. Hana Rudová, Logické programování I, 9. května 201 2 Implementace Prologu Interpretace Deklarativní sémantika: Hlava platí, platí-li jednotlivé literály těla. Hana Rudová, Logické programování I, 9. května 201 2 16 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, 9. května 201 2 16 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, 9. května 201 2 16 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, 9. května 201 2 23 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, 9. května 201 2 24 Implementace Prologu Kopírování struktur II Term F s aritou A reprezentován A+l slovy: 3 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, 9. května 201 2 2 5 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, 9. května 201 2 26 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, 9. května 201 2 27 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, 9. května 201 2 27 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, 9. května 201 2 28 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, 9. května 201 2 28 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, 9. května 201 2 28 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, 9. května 201 2 29 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í I, 9. května 201 2 29 Implementace Prologu Srovnání II m Složitost algoritmů pro přístup k jednotlivým argumentům 3 sdílení struktur: nutná víceúrovňová nepřímá adresace kopírování struktur: bez problémů 3 jednodušší algoritmy usnadňují i optimalizace Hana Rudová, Logické programování I, 9. května 201 2 30 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, 9. května 201 2 30 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 3 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, 9. května 201 2 30 Implementace Prologu Řízení výpočtu Dopřed ný výpočet 3 po úspěchu (úspěšná redukce) ± jednotlivá volání procedur skončí úspěchem M klasické volání rekurzivních procedur Hana Rudová, Logické programování I, 9. května 201 2 31 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, 9. května 201 2 31 Implementace Prologu Aktivační záznam 3 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, 9. května 2012 32 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 3 aktuální parametry M lokální proměnné M pomocné proměnné ('a la registry) Hana Rudová, Logické programování I, 9. května 201 2 32 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, 9. května 201 2 32 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, 9. května 201 2 33 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, 9. května 201 2 33 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, 9. května 201 2 33 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 3 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, 9. května 201 2 33 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 3 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 3 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, 9. května 2012 33 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, 9. května 201 2 34 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, 9. května 201 2 34 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, 9. května 201 2 34 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, 9. května 201 2 34 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, 9. května 2012 34 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, 9. května 201 2 35 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, 9. května 201 2 35 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 M 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, 9. května 2012 35 Implementace Prologu