Algoritmy pro CSP (pokračování) Prohledávání + konzistence -• Splňování podmínek prohledáváním prostoru řešení -• podmínky jsou užívány pasivně jako test M 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, 18. května 2009 2 Algoritmy pro CSP Prohledávání + konzistence -• Splňování podmínek prohledáváním prostoru řešení -• podmínky jsou užívány pasivně jako test M 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 M ú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, 18. května 2009 2 Algoritmy pro CSP Prohledávání + konzistence -• Splňování podmínek prohledáváním prostoru řešení -• podmínky jsou užívány pasivně jako test M 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 M úplná metoda (nalezneme řešení nebo dokážeme jeho neexistenci) M 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 3 neúplná metoda (v doméně zůstanou ještě nekonzistentní hodnoty) 3 relativně rychlé (polynomiální) Hana Rudová, Logické programování I, 18. května 2009 2 Algoritmy pro CSP Prohledávání + konzistence -• Splňování podmínek prohledáváním prostoru řešení -• podmínky jsou užívány pasivně jako test M 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 M úplná metoda (nalezneme řešení nebo dokážeme jeho neexistenci) M 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 S 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, 18. května 2009 2 Algoritmy pro CSP Prohledávání do hloubky -• 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 -• dopredná 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, 18. května 2009 3 Algoritmy pro CSP Prohledávání do hloubky -• 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 -• dopredná 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ě 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 M budoucí - proměnné, které budou vybrány v budoucnosti Hana Rudová, Logické programování I, 18. května 2009 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 labeling(G,l) proceduře labeling(G,a) if a > |uzly(G)| then return uzly(G) for y x g Da do if consistent(G,a) then % consistent(G,a) je nahrazeno FC(G,a), LA(G,a), R := labeling(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í -• Procedury consistent uvedeme pouze pro binární podmínky Hana Rudová, Logické programování I, 18. května 2009 4 Algoritmy pro CSP Backtracking (BT) -• Backtracking overuje v každém kroku konzistenci podmínek vedoucích z minulých proměnných do aktuální proměnné 3 Backtracking tedy zajišťuje konzistenci podmínek M na všech minulých proměnných -• na podmínkách mezi minulými proměnnými a aktuální proměnnou Hana Rudová, Logické programování I, 18. května 2009 5 Algoritmy pro CSP Backtracking (BT) -• Backtracking overuje v každém kroku konzistenci podmínek vedoucích z minulých proměnných do aktuální proměnné 3 Backtracking tedy zajišťuje konzistenci podmínek M na všech minulých proměnných -• na podmínkách mezi minulými proměnnými a aktuální proměnnou -• 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 (Vk,Vm) z Q Consistent := not revise^,Vm) % pokud vyřadíme prvek, bude doména prázdná return Consistent end BT Hana Rudová, Logické programování I, 18. května 2009 5 Algoritmy pro CSP Příklad: backtracking Omezení: Vi, V2, V3 in 1... 3, Vi# = 3 x V3 Stavový prostor 3 červené čtverečky: chybný pokus o instanciaci, řešení neexistuje M 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, 1 8. května 2009 6 Algoritmy pro CSP Kontrola dopředu (FC - forward checking) M FC je rozšíření backtrackingu M 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, 18. května 2009 7 Algoritmy pro CSP Kontrola dopředu (FC - forward checking) M FC je rozšíření backtrackingu M 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 procedure FC(G,a) Q;={(Yi, V a) e 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 (Vk,Vm) z Q if revise((Vfc,Vm)) then Consistent := (|Dfcl>0) % vyprázdnění domény znamená nekonzistenci return Consistent end FC M Hrany z minulých proměnných do aktuální proměnné není nutno testovat Hana Rudová, Logické programování I, 18. května 2009 7 Algoritmy pro CSP Príklad: kontrola dopředu Omezení: Vi,V2, V3 in 1 ...3, c : Vi# = 3 x V3 Stavový prostor: V 1 c => fail c => fail V- V, Hana Rudová, Logické programování I, 18. května 2009 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) e hrany(G), í > a] % začínáme s hranami do a Consistent := true while Q není prázdná a Consistent do vyber a smaž libovolnou hranu (Vk,Vm) z Q if revise((Vfc,ym)) then Q := Q u {(Vi,Vk)\(Vi,Vk) g hrany(G), i ŕ k,i ŕ m,i> a} Consistent := (|Dfcl>0) return Consistent end LA Hana Rudová, Logické programování I, 18. května 2009 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 M procedure LA(G,a) Q := {(Vi,Va) 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 (Vk,Vm) z Q if revise((Vfc,ym)) then Q := Q u {(Vi,Vk)\(Vi,Vk) e hrany(G), i ŕ k,i ŕ m,i> a} Consistent := (|Dfcl>0) return Consistent end LA -• 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 -• 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, 18. května 2009 9 Algoritmy pro CSP Příklad: pohled dopředu (pomocí AC-3) Omezení: Ví, V2, V3 in 1... 4, c\ : Vi# > V2, c2:V2#=3x V3 Stavový prostor (spouští se iniciální konzistence se před startem prohledávání) i , d => V1 in 2..4 V2in 1..3 c2=>V2=3 V3=1 d => V1= 4 1 4< » 2 3. ► 3 1c S Hana Rudová, Logické programování I, 18. května 2009 10 Algoritmy pro CSP Príklad: pohled dopředu pomocí AC-1 Omezení: Vi,V2,V3 in 1...4, cl:Vi#>V2, c2:V2#=3xV3 Stavový prostor, pokud bychom použili místo AC-3 algoritmus AC-1 M iniciální konzistence se před startem prohledávání nespouští -• algorimus AC-1 opakuje revize všech hran, dokud se změnila doména alespoň jedné proměnné => AC-1 vynutí hranovou konzistenci, jakmile je přiřazena hodnota aktuální proměnné V- c1 = V, > fail c1 => V2=1 c1 c2 => fail c2 :>V2=1..2 :> fail 4 d c2 :>V2=1..3 :>V2=3 V3=1 V. Hana Rudová, Logické programování I, 18. května 2009 Ó 11 Algoritmy pro CSP Přehled algoritmů Backtracking (BT) kontroluje v kroku a podmínky c(Vi,Va),...,c(Va_i,Va) z minulých proměnných do aktuální proměnné proměnné C N ^ CD aktuálni ? CD Š-"š o =^ C Q) O N ^ CD CD Hana Rudová, Logické programování I, 18. května 2009 12 Algoritmy pro CSP Přehled algoritmů Backtracking (BT) kontroluje v kroku a podmínky c(Vi,Va),...,c(Va_i,Va) z minulých proměnných do aktuální proměnné BT Kontrola dopředu (FC) kontroluje v kroku a podmínky c(Va+i,Va),---,c(Vn,Va) z budoucích proměnných do aktuální proměnné proměnné C N Ä =3 ^ CD aktuálni £" CD Š-"š o =v C Q) O N C^ CD CD Hana Rudová, Logické programování I, 18. května 2009 12 Algoritmy pro CSP Přehled algoritmů Backtracking (BT) kontroluje v kroku a podmínky c(Vi,Va),...,c(Va_i,Va) z minulých proměnných do aktuální proměnné BT Kontrola dopředu (FC) kontroluje v kroku a podmínky c(Va+i,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 10. 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, 18. května 2009 14 Algoritmy pro CSP Implementace Prologu Literatura: M Matýska L., Toman D.: Implementační techniky Prologu , Informační systémy, (1 990), 21-59. http: //www. i es. muni . cz/peopl e/matyska/vyuka/1 p/l p. html Opakování: základní pojmy M Konečná množina klauzulí Hlava :- Tělo tvoří program P. -• Hlava je literal M Tělo je (eventuálně prázdná) konjunkce literálů Ti,...Ta, a> 0 M Literal je tvořen m-árním predikátovým symbolem (m/p) a m termy (argumenty) -• Term je konstanta, proměnná nebo složený term. -• Složený term a n termy na místě argumentů -• Dotaz (cíl) je neprázdná množina literálů. Hana Rudová, Logické programování I, 18. května 2009 16 Implementace Prologu Interpretace Deklarativní sémantika: Hlava platí, platí-li jednotlivé literály těla. Hana Rudová, Logické programování I, 18. května 2009 17 Implementace Prologu Interpretace Deklarativní sémantika: Hlava platí, platí-li jednotlivé literalytela. Procedurální (imperativní) sémantika: Entry: Hlava:: { call Ti ■ ■ ■ call Ta } Volání procedury s názvem Hl ava uspěje, pokud uspěje volání všech procedur (literálů) v těle. Hana Rudová, Logické programování I, 18. května 2009 17 Implementace Prologu Interpretace Deklarativní sémantika: Hlava platí, platí-li jednotlivé literalytela. Procedurální (imperativní) sémantika: Entry: Hlava:: { call Ti ■ ■ ■ call Ta } Volání procedury s názvem Hl ava 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, 18. května 2009 17 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 3a : A 0) z programu P takovou, že 3a : A 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, 18. května 2009 24 Implementace Prologu Príklad a(b(X),c(X,Y),d) Kopírování struktur FUNCT a/3 REF REF CONST d FUNCT c/2 REF FREE Y FUNCT b/1 FREEX Hana Rudová, Logické programování I, 18. května 2009 25 Implementace Prologu Kopírování struktur II -• Term F s aritou A reprezentován A+l slovy: M funktor a arita v prvním slově M 2. slovo nese první argument (resp. odkaz na jeho hodnotu) i M A+l slovo nese hodnotu A-tého argumentu -• Reprezentace vychází z orientovaných acyklických grafů: a/3 d t 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, 18. května 2009 26 Implementace Prologu Sdílení struktur M 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 M rámec je vektor aktuálních hodnot těchto proměnných A í-tá položka nese hodnotu í-té proměnné v původním termu Hana Rudová, Logické programování I, 18. května 2009 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. Hana Rudová, Logické programování I, 18. května 2009 28 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, 18. května 2009 28 Implementace Prologu Srovnání: příklad -• Naivní srovnání: sdílení paměťově méně náročné Hana Rudová, Logické programování I, 18. května 2009 29 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 Hana Rudová, Logické programování I, 18. května 2009 29 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 M Postupná tvorba termů: A = a(K,L,M), K = b(X), L = c(X,Y), M = d 3 Sdílení termů: A kostra_a A 1/ kostra_b i\ L - M:d —►■ kostra_c Hana Rudová, Logické programování I, 18. května 2009 29 I Srovnání: příklad - pokračování -• 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/l -- FREE X Hana Rudová, Logické programování I, 18. května 2009 30 Implementace Prologu Srovnání: příklad - pokračování -• 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/l -- FREE X tj. identické jako přímé vytvoření termu a(b(X) ,c(X,Y) ,d) Hana Rudová, Logické programování I, 18. května 2009 30 Implementace Prologu Srovnání II -• Složitost algoritmů pro přístup k jednotlivým argumentům 3 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, 18. května 2009 31 Implementace Prologu Srovnání II -• Složitost algoritmů pro přístup k jednotlivým argumentům 3 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 -• Lokalita přístupů do paměti -• sdílení struktur: přístupy rozptýleny po paměti -• 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, 18. května 2009 31 Implementace Prologu Srovnání II -• Složitost algoritmů pro přístup k jednotlivým argumentům 3 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 -• Lokalita přístupů do paměti -• sdílení struktur: přístupy rozptýleny po paměti -• 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 3 Z praktického hlediska neexistuje mezi těmito přístupy zásadní rozdíl Hana Rudová, Logické programování I, 18. května 2009 31 Implementace Prologu Řízení výpočtu -• Dopřed ný výpočet -• po úspěchu (úspěšná redukce) -i* jednotlivá volání procedur skončí úspěchem •• klasické volání rekurzivních procedur Hana Rudová, Logické programování I, 18. května 2009 32 Implementace Prologu Řízení výpočtu -• Dopřed ný výpočet -• po úspěchu (úspěšná redukce) -i* jednotlivá volání procedur skončí úspěchem •• klasické volání rekurzivních procedur -• Zpětný výpočet (backtracking) M po neúspěchu vyhodnocení literalu (neúspěšná redukce) A nepodaří se unifikace aktuálních a formálních parametrů hlavy •• návrat do bodu, kde zůstala nevyzkoušená alternativa výpočtu St je nutná obnova původních hodnot jednotlivých proměnných po nalezení místa s dosud nevyzkoušenou klauzulí pokračuje dále dopředný výpočet Hana Rudová, Logické programování I, 18. května 2009 32 Implementace Prologu Aktivační záznam -• Volání (=aktivace) procedury -• 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 Hana Rudová, Logické programování I, 18. května 2009 33 Implementace Prologu Aktivační záznam -• Volání (=aktivace) procedury -• 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ředný výpočet 3 stav výpočtu v okamžiku volání procedury 3 aktuální parametry 3 lokální proměnné 3 pomocné proměnné ('a la registry) Hana Rudová, Logické programování I, 18. května 2009 33 Implementace Prologu Aktivační záznam -• Volání (=aktivace) procedury -• 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ředný výpočet 3 stav výpočtu v okamžiku volání procedury 3 aktuální parametry 3 lokální proměnné 3 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, 18. května 2009 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). Hana Rudová, Logické programování I, 18. května 2009 34 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, 18. května 2009 34 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) -• Při návratu je třeba obnovit (roll-back) původní hodnoty proměnných -• Využijeme vlastností logických proměnných 3 instanciovat lze pouze volnou proměnnou M 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, 18. května 2009 34 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) -• Při návratu je třeba obnovit (roll-back) původní hodnoty proměnných -• Využijeme vlastností logických proměnných 3 instanciovat lze pouze volnou proměnnou M 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 * 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, 18. května 2009 34 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) -• Při návratu je třeba obnovit (roll-back) původní hodnoty proměnných -• Využijeme vlastností logických proměnných 3 instanciovat lze pouze volnou proměnnou M 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 * 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á" -• Globální zásobník: pro uložení složených termů M 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, 18. května 2009 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 Hana Rudová, Logické programování I, 18. května 2009 35 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 -• samostatně provázány (odkaz na předchozí okolí resp. bod volby) Hana Rudová, Logické programování I, 18. května 2009 35 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 -• samostatně provázány (odkaz na předchozí okolí resp. bod volby) Důsledky: -• samostatná práce s každou částí aktivačního záznamu (optimalizace) Hana Rudová, Logické programování I, 18. května 2009 35 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 -• samostatně provázány (odkaz na předchozí okolí resp. bod volby) Důsledky: -• 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, 18. května 2009 35 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 -• samostatně provázány (odkaz na předchozí okolí resp. bod volby) Důsledky: -• samostatná práce s každou částí aktivačního záznamu (optimalizace) -• alokace pouze okolí pro deterministické procedury -• 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, 18. května 2009 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). cd). c(2). Hana Rudová, Logické programování I, 18. května 2009 36 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). cd). c(2). M Ř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 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 Hana Rudová, Logické programování I, 18. května 2009 36 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). cd). c(2). M Ř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 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, 18. května 2009 36 Implementace Prologu