Algoritmy pro CSP (pokračování)
Prohledávání + konzistence
JS> Splňování podmínek prohledáváním prostoru řešení
podmínky jsou užívány pasivné jako test A přiřazuji hodnoty proměnných a zkouším co se stane
-4» vestavený prohledávací algoritmus Prologu: backtracking, triviální: generuj & testuj
Hana Rudová, Logické programování I, 7. kvetna 2010
2
Algoritmy pro CSP
Prohledávání + konzistence
JS> Splňování podmínek prohledáváním prostoru řešení
podmínky jsou užívány pasivné jako test A přiřazuji hodnoty proměnných a zkouším co se stane
-4» vestavený prohledávací algoritmus Prologu: backtracking, triviální: generuj & testuj
A úplná metoda (nalezneme rešení nebo dokážeme jeho neexistenci)
i> zbytecne pomalé (exponenciální): procházím i „evidentne" špatná ohodnocení
Hana Rudová, Logické programování I, 7. kvetna 2010
2
Algoritmy pro CSP
Prohledávání + konzistence
JS> Splňování podmínek prohledáváním prostoru řešení
podmínky jsou užívány pasivné jako test A přiřazuji hodnoty proměnných a zkouším co se stane
-4» vestavený prohledávací algoritmus Prologu: backtracking, triviální: generuj & testuj
A úplná metoda (nalezneme rešení nebo dokážeme jeho neexistenci)
i> zbytecne pomalé (exponenciální): procházím i „evidentne" špatná ohodnocení
-i* KonzistenCní (propagaCní) techniky
-fc umožnují odstranení nekonzistentních hodnot z domény promenných -i* neúplná metoda (v doméne zustanou ješte nekonzistentní hodnoty) A relativne rychlé (polynomiální)
Hana Rudová, Logické programování I, 7. kvetna 2010
2
Algoritmy pro CSP
Prohledávání + konzistence
JS> Splňování podmínek prohledáváním prostoru řešení
podmínky jsou užívány pasivné jako test A přiřazuji hodnoty proměnných a zkouším co se stane
-4» vestavený prohledávací algoritmus Prologu: backtracking, triviální: generuj & testuj
A úplná metoda (nalezneme rešení nebo dokážeme jeho neexistenci)
i> zbytecne pomalé (exponenciální): procházím i „evidentne" špatná ohodnocení
-i* KonzistenCní (propagaCní) techniky
-fc umožnují odstranení nekonzistentních hodnot z domény promenných -i* neúplná metoda (v doméne zůstanou ješte nekonzistentní hodnoty) A relativne rychlé (polynomiální)
& Používá se kombinace obou metod
postupné prirazování hodnot promenným i* po prirazení hodnoty odstranení nekonzistentních hodnot konzistencními technikami
Hana Rudová, Logické programování I, 7. kvetna 2010 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)
& Dve fáze prohledávání s navracením
& dopredná fáze: proměnné jsou postupne vybírány, rozširuje se CásteCné rešení prirazením konzistení hodnoty (pokud existuje) další promenné
po vybrání hodnoty testujeme konzistenci
a zpetná fáze: pokud neexistuje konzistentní hodnota pro aktuální proměnnou, algoritmus se vrací k předchozí prirazené hodnote
Hana Rudová, Logické programování I, 7. kvetna 2010
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)
& Dve fáze prohledávání s navracením
& dopredná fáze: proměnné jsou postupne vybírány, rozširuje se CásteCné rešení prirazením konzistení hodnoty (pokud existuje) další promenné
po vybrání hodnoty testujeme konzistenci
a zpetná fáze: pokud neexistuje konzistentní hodnota pro aktuální proměnnou, algoritmus se vrací k předchozí prirazené hodnote
& Promenné delíme na
& minulé - promenné, které už byly vybrány (a mají prirazenu hodnotu) * aktuální - promenná, která je práve vybrána a je jí prirazována hodnota s budoucí - promenné, které budou vybrány v budoucnosti
Hana Rudová, Logické programování I, 7. kvetna 2010 3 Algoritmy pro CSP
Základní algoritmus prohledávání do hloubky
Pro jednoduchost proměnné očíslujeme a ohodnocujeme je v daném pořadí Na začátku voláno jako labeling(G,1)
procedure labeling(G,a)
if a > |uzly(G)| then return uzly(G)
for Vx 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 promenných vrátíme jejich ohodnocení Procedury consistent uvedeme pouze pro binární podmínky
Hana Rudová, Logické programování I, 7. května 2010
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í promenné
Backtracking tedy zajišťuje konzistenci podmínek A na všech minulých promenných
-fc na podmínkách mezi minulými promennými a aktuální promennou
Hana Rudová, Logické programování I, 7. kvetna 2010
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í promenné
Backtracking tedy zajišťuje konzistenci podmínek A na všech minulých promenných
-fc na podmínkách mezi minulými promennými a aktuální promennou procedure BT(G,a)
Q:={(Vi, va) g hrany(G), i < a} % hrany vedoucí z minulých promenných do aktuální
Consistent := true
while Q není prázdná a Consistent do
vyber a smaž libovolnou hranu (Vk,Vm) z Q
Consistent := not revise(Vk,Vm)      % pokud vyradíme prvek, bude doména prázdná return Consistent end BT
Hana Rudová, Logické programování I, 7. kvetna 2010
5
Algoritmy pro CSP
Příklad: backtracking
C Omezení: Vi,V2, V3 in 1... 3, Vi# = 3 x V3 & Stavový prostor: í
S* cervené ctverecky: chybný pokus o instanciaci, r ešení neexistuje i* nevyplnená kolecka: nalezeno r ešení
Jť cerná kolecka: vnit r ní uzel, máme pouze cástecné p r i razení
Hana Rudová, Logické programování I, 7. kvetna 2010 6
Kontrola dopředu (FC - forward checking)
FC je rozšírení backtrackingu
FC navíc zajišťuje konzistenci mezi aktuální proměnnou a budoucími proměnnými, které jsou s ní spojeny dosud nesplnenými podmínkami
Hana Rudová, Logické programování I, 7. kvetna 2010
7
Algoritmy pro CSP
Kontrola dopředu (FC - forward checking)
FC je rozšírení backtrackingu
FC navíc zajišťuje konzistenci mezi aktuální proměnnou a budoucími proměnnými, které jsou s ní spojeny dosud nesplnenými podmínkami
procedure FC(G,a)
Q:={(Vi, va) g hrany(G), i> a} % přidání hran z budoucích do aktuální promenné
Consistent := true
while Q není prázdná a Consistent do
vyber a smaž libovolnou hranu (Vk,Vm) z Q
if revise((Vk,Vm)) then
Consistent := (\Dk\ > 0) % vyprázdnení domény znamená nekonzistenci
return Consistent end FC
Hrany z minulých promenných do aktuální promenné není nutno testovat
Hana Rudová, Logické programování I, 7. kvetna 2010
7
Algoritmy pro CSP
Príklad: kontrola dopredu
C Omezení: V1,V2,V3 in 1... 3,   c : Vi# = 3 x V3 & Stavový prostor:
Hana Rudová, Logické programování I, 7. kvetna 2010 8 Algoritmy pro CSP
Pohled dopredu (LA - looking ahead)
LAjě rozšírení FC, navíc ověrujě konzistenci hran mezi budoucími proměnnými
procedure LA(G,a)
Q := {(Vi,Va)  g hrany(G), i> a} % zaCí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((Vk,Vm)) then
Q := Q u {(Vi,Vk)\(Vi,Vk)  g hrany(G), i = k, i = m,i> a} Consistent := (\Dk\ > 0) return Consistent end LA
Hana Rudová, Logické programování I, 7. května 2010
9
Algoritmy pro CSP
Pohled dopředu (LA - looking ahead)
LA je rozšírení FC, navíc overuje konzistenci hran mezi budoucími promennými
procedure LA(G,a)
Q := {(Vi,Va)  g hrany(G), i> 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((Vk,Vm)) then
Q := Q u {(Vi,Vk)\(Vi,Vk)  g hrany(G), i = k, i = m,i> a} Consistent := (\Dk\ > 0) return Consistent end LA
A Hrany z minulých proměnných do aktuální promenné opet netestujeme -i- Tato LA procedura je založena na AC-3, lze použít i jiné AC algoritmy
JS> 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šte pred startem prohledávání
Hana Rudová, Logické programování I, 7. kvetna 2010 9 Algoritmy pro CSP
Příklad: pohled dopředu (pomocí AC-3)
Omezení: V1.V2.V3 in 1...4, c 1: Vi# > V2, c2: V?# = 3 x V3 Stavový prostor
(spouští se iniciální konzistence se pred startem prohledávání)
q cl => V in 2..4 V2 in 1..3
c2 => V2 = 3
V3 = 1
V1
4
cl => V1= 4
V2 31
V3 4
Hana Rudová, Logické programování I, 7. kvetna 2010
10
Algoritmy pro CSP
Přehled algoritmů
Backtracking (BT) kontroluje v kroku a podmínky
C(Vi ,Va),...,C(Va-l,Va)
z minulých promenných do aktuální promenné
BT
FC
LA
promenne
aktuálni
Hana Rudová, Logické programování I, 7. kvetna 2010
11
Algoritmy pro CSP
Přehled algoritmů
Backtracking (BT) kontroluje v kroku a podmínky
C(Vi ,Va),...,c(Va-1,Va)
z minulých proměnných do aktuální proměnné Kontrola dopředu (FC) kontroluje v kroku a podmínky
c(Va+1,Va),...,c(Vn,Va)
z budoucích proměnných do aktuální proměnné
BT
a
FC
LA
n
promenne
aktuální
Hana Rudová, Logické programování I, 7. května 2010
11
Algoritmy pro CSP
Přehled algoritmů
BT
Backtracking (BT) kontroluje v kroku a podmínky
,Va),...,c(Va-1,Va)
z minulých proměnných do aktuální proměnné Kontrola dopředu (FC) kontroluje v kroku a podmínky
c(Va+1,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
Vl(a < l < n), \/k(a < k < n),k = l: c(Vk,Vi) z budoucích proměnných do aktuální proměnné LA a mězi budoucími proměnnými
a
FC
n
promenne
aktuální
Hana Rudová, Logické programování I, 7. května 2010
11
Algoritmy pro CSP
CviCení
1. Jak vypadá stavový prostor rešení pro následující omezení A in 1..4, B in 3..4, C in 3..4, B #< C, A #= C
p r i použití kontroly dop redu a uspo rádání promenných A,B,C? Popište, jaký typ propagace probehne v jednotlivých uzlech.
2. Jak vypadá stavový prostor rešení pro následující omezení A in 1..4, B in 3..4, C in 3..4, B #< C, A#= C
p r i použití pohledu dop r edu a uspo rádání promenných A,B,C? Popište, jaký typ propagace probehne v jednotlivých uzlech.
3. Jak vypadá stavový prostor rešení pro následující omezení domain([A,B,C],0,1), A#= B-1, C #= A*A
p r i použití backtrackingu a pohledu dop r edu a uspo rádání promenných A,B,C? Popište, jaký typ propagace probehne v jednotlivých uzlech.
Hana Rudová, Logické programování I, 7. kvetna 2010 12 Algoritmy pro CSP
Cvicení
1. Jaká jsou pravidla pro konzistenci mezí u omezení X#= Y+5? Jaké typy propagací pak probehnou v následujícím príklade pri použití konzistence mezí?
X in 1..20, Y in 1..20, X #= Y+ 5, Y#> 10.
2. Ukažte, jak je dosaženo hranové konzistence v následujícím príkladu:
domain([X,Y,Z],1,5]), X #< Y, Z#= Y+1 .
Hana Rudová, Logické programování I, 7. kvetna 2010
13
Algoritmy pro CSP
Implementace Prologu
Literatura:
& Matyska L., Toman D.: Implementacní techniky Prologu, Informacní systémy, (1990), 21-59.
http://www.ics.muni.cz/people/matyska/vyuka/lp/lp.html
Opakování: základní pojmy
-í* Konečná množina klauzulí Hlava :- Tělo tvorí program P. JS> Hlava je literál
& Tělo je (eventuálne prázdná) konjunkce literálU Ti,...Ta, a > 0 & Literál
je tvořen m-árním predikátovým symbolem (m/p) a m termy (argumenty) JS> Term je konstanta, promenná nebo složený term.
-í* Složený term
s n termy na míste argumentu
& Dotaz (cíl) je neprázdná množina literálu.
Hana Rudová, Logické programování I, 7. kvetna 2010
15
Implementace Prologu
Interpretace
Deklarativní sémantika:
Hlava platí, platí-li jednotlivé literály tela.
Hana Rudová, Logické programování I, 7. kvetna 2010
16
Implementace Prologu
Interpretace
Deklarativní sémantika:
Hlava platí, platí-li jednotlivé literály tela.
Procedurální (imperativní) sémantika:
Entry: Hlava:: {
call Ti
■
■
■
call Ta
}
Volání procedury s názvem Hlava uspeje, pokud uspeje volání všech procedur (literálu) v tele.
Hana Rudová, Logické programování I, 7. kvetna 2010
16
Implementace Prologu
Interpretace
Deklarativní sémantika:
Hlava platí, platí-li jednotlivé literály tela.
Procedurální (imperativní) sémantika:
Entry: Hlava:: {
call Ti
■
■
■
call Ta
}
Volání procedury s názvem Hlava uspeje, pokud uspeje volání všech procedur (literálU) v tele.
Procedurální sémantika = podklad pro implementaci
Hana Rudová, Logické programování I, 7. kvetna 2010 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':-Bl ,...,Bn   (n > 0) z programu P takovou, že 3a : Aer = A' a; a je nejobecnejší unifikátor.
Pokud neexistuje A' nebo a, ukona cyklus.
Hana Rudová, Logické programování I, 7. kvetna 2010
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 : Aer = A' a; a je nejobecnejší unifikátor.
Pokud neexistuje A' nebo a, ukonc cyklus.
4. Nahrad' A v S cíli B1 až Bn.
5. Aplikuj a na G a S.
6. end while
7. Pokud S==empty, pak výpocet úspešne skoncil a výstupem je G se všemi aplikovanými substitucemi.
Pokud S!=empty, výpocet koná neúspechem.
Hana Rudová, Logické programování I, 7. kvetna 2010 17 Implementace Prologu
Abstraktní interpret - pokraCování
Kroky (3) až (5) predstavují redukci (logickou inferenci) cíle A. Pocet redukcí za sekundu (LIPS) == indikátor výkonu implementace
Hana Rudová, Logické programování I, 7. kvetna 2010
18
Implementace Prologu
Abstraktní interpret - pokřaCování
Kroky (3) až (5) představují redukci (logickou inferenci) cíle A. PoCet redukcí za sekundu (LIPS) == indikátor výkonu implementace
veta
Existuje-li instance C dotazu G, odvoditelná z programu P v konecném poctu kroků, pak bude tímto interpretem nalezena.
Hana Rudová, Logické programování I, 7. kvetna 2010
18
Implementace Prologu
Nedeterminismus interpetu
1. SelekCní pravidlo: výber cíle A z množiny cílu S JÍ neovlivnuje výrazne výsledek chování interpretu
2. Způsob prohledávání stromu výpoCtu: výber klauzule A' z programu P
JG* je velmi duležitý, všechny klauzule totiž nevedou k úspešnému rešení
Hana Rudová, Logické programování I, 7. kvetna 2010
19
Implementace Prologu
Nedeterminismus interpetu
1. SelekCní pravidlo: výber cíle A z množiny cílu S M neovlivnuje výrazne výsledek chování interpretu
2. Způsob prohledávání stromu výpoCtu: výber klauzule A' z programu P
JG* je velmi duležitý, všechny klauzule totiž nevedou k úspešnému rešení
Vztah k úplnosti:
1. Selekcní pravidlo neovlivnuje úplnost
& možno zvolit libovolné v rámci SLD rezoluce
2. Prohledávání stromu výpoctu do šírky nebo do hloubky
Hana Rudová, Logické programování I, 7. kvetna 2010
19
Implementace Prologu
Nedeterminismus interpetu
1. SelekCní pravidlo: výber cíle A z množiny cílu S JÍ neovlivnuje výrazne výsledek chování interpretu
2. Způsob prohledávání stromu výpoCtu: výber klauzule A' z programu P
JG* je velmi duležitý, všechny klauzule totiž nevedou k úspešnému r ešení
Vztah k úplnosti:
1. Selekcní pravidlo neovlivnuje úplnost
& možno zvolit libovolné v rámci SLD rezoluce
2. Prohledávání stromu výpoctu do šírky nebo do hloubky
„Prozrení" - automatický výber správné klauzule
& vlastnost abstraktního interpretu, kterou ale reálné interprety nemají
Hana Rudová, Logické programování I, 7. kvetna 2010 19 Implementace Prologu
Prohledávání do šírky
1. Vybereme všechny klauzule A-, které je možno unifikovat s literálem A M necht'je techto klauzulí q
2. Vytvoríme q kopií množiny S
3. V každé kopii redukujeme A jednou z klauzulí A-. M aplikujeme príslušný nejobecnejší unifikátor
Hana Rudová, Logické programování I, 7. kvetna 2010
20
Implementace Prologu
Prohledávání do šírky
1. Vybereme všechny klauzule A-, které je možno unifikovat s literálem A M necht'je techto klauzulí q
2. Vytvo ríme q kopií množiny S
3. V každé kopii redukujeme A jednou z klauzulí AÍ. M aplikujeme p ríslušný nejobecnejší unifikátor
4. V následujících krocích redukujeme všechny množiny Si soucasne.
Hana Rudová, Logické programování I, 7. kvetna 2010
20
Implementace Prologu
Prohledávání do šírky
1. Vybereme všechny klauzule     které je možno unifikovat s literálem A M necht'je techto klauzulí q
2. Vytvoríme q kopií množiny S
3. V každé kopii redukujeme A jednou z klauzulí A-. M aplikujeme príslušný nejobecnejší unifikátor
4. V následujících krocích redukujeme všechny množiny Si soucasne.
5. Výpocet ukoncíme úspechem, pokud se alespon jedna z množin Si stane prázdnou.
Hana Rudová, Logické programování I, 7. kvetna 2010
20
Implementace Prologu
Prohledávání do šířky
1. Vybereme všechny klauzule A-, které je možno unifikovat s literálem A M necht'je techto klauzulí q
2. Vytvoríme q kopií množiny S
3. V každé kopii redukujeme A jednou z klauzulí A-. M aplikujeme príslušný nejobecnejší unifikátor
4. V následujících krocích redukujeme všechny množiny Si soucasne.
5. Výpocet ukoncíme úspechem, pokud se alespon jedna z množin Si stane prázdnou.
-í* Ekvivalence s abstraktnímu interpretem
A pokud jeden interpret neuspeje, pak neuspeje i druhý i> pokud jeden interpret uspeje, pak uspeje i druhý
Hana Rudová, Logické programování I, 7. kvetna 2010 20 Implementace Prologu
Prohledávání do hloubky
1. Vybereme všechny klauzule A'i, které je možno unifikovat s literálem A.
2. Všechny tyto klauzule zapíšeme na zásobník.
3. Redukci provedeme s klauzulí na vrcholu zásobníku.
Hana Rudová, Logické programování I, 7. kvetna 2010
21
Implementace Prologu
Prohledávání do hloubky
1. Vybereme všechny klauzule A'i, které je možno unifikovat s literálem A.
2. Všechny tyto klauzule zapíšeme na zásobník.
3. Redukci provedeme s klauzulí na vrcholu zásobníku.
4. Pokud v nejakém kroku nenajdeme vhodnou klauzuli A', vrátíme se
k predchozímu stavu (tedy anulujeme aplikace posledního unifikátoru a) a vybereme ze zásobníku další klauzuli.
Hana Rudová, Logické programování I, 7. kvetna 2010
21
Implementace Prologu
Prohledávání do hloubky
1. Vybereme všechny klauzule A'i, které je možno unifikovat s literálem A.
2. Všechny tyto klauzule zapíšeme na zásobník.
3. Redukci provedeme s klauzulí na vrcholu zásobníku.
4. Pokud v nejakém kroku nenajdeme vhodnou klauzuli A', vrátíme se
k předchozímu stavu (tedy anulujeme aplikace posledního unifikátoru a) a vybereme ze zásobníku další klauzuli.
5. Pokud je zásobník prázdný, koncívýpocet neúspechem.
6. Pokud naopak zredukujeme všechny literály v S, výpocet koncí úspechem.
Hana Rudová, Logické programování I, 7. kvetna 2010
21
Implementace Prologu
Prohledávání do hloubky
1. Vybereme všechny klauzule A'i, které je možno unifikovat s literálem A.
2. Všechny tyto klauzule zapíšeme na zásobník.
3. Redukci provedeme s klauzulí na vrcholu zásobníku.
4. Pokud v nejakém kroku nenajdeme vhodnou klauzuli A', vrátíme se
k predchozímu stavu (tedy anulujeme aplikace posledního unifikátoru a) a vybereme ze zásobníku další klauzuli.
5. Pokud je zásobník prázdný, koncívýpocet neúspechem.
6. Pokud naopak zredukujeme všechny literály v S, výpocet koncí úspechem.
-» Není úplné, tj. nemusí najít všechna rešení
Nižší pametová nárocnost než prohledáváni do širky & Používá se v Prologu
Hana Rudová, Logické programování I, 7. kvetna 2010 21 Implementace Prologu
Reprezentace objektů
J& Beztypový jazyk
ü> Kontrola „typů" za běhu výpočtu
JS> Informace o strukture součástí objektů
Hana Rudová, Logické programování I, 7. kvetna 2010
22
Implementace Prologu
Reprezentace objektů
J& Beztypový jazyk
ii> Kontrola „typů" za behu výpoctu
JS> Informace o strukture soucástí objektu
Typy objektů
M Primitivní objekty:
konstanta císlo
-i. volná promenná -i- odkaz (reference)
Hana Rudová, Logické programování I, 7. kvetna 2010
22
Implementace Prologu
Reprezentace objektů
J& Beztypový jazyk
ü> Kontrola „typů" za behu výpočtu
JS> Informace o strukture součástí objektu
Typy objektů
M Primitivní objekty:
konstanta císlo
-i. volná promenná -i- odkaz (reference)
& Složené (strukturované) objekty:
± struktura A seznam
Hana Rudová, Logické programování I, 7. kvetna 2010 22 Implementace Prologu
Reprezentace objektů II
P ríznaky (tags):
Objekt	Príznak
volná promenná	FREE
konstanta	CONST
celé císlo	INT
odkaz	REF
složený term	FUNCT
Hana Rudová, Logické programování I, ľ. kvetna 2GlG
23
Implementace Prologu
Reprezentace objektů II
P ríznaky (tags):
Objekt	Príznak
volná promenná	FREE
konstanta	CONST
celé císlo	INT
odkaz	REF
složený term	FUNCT
Obsah adresovatelného slova: hodnota a príznak.
Hana Rudová, Logické programování I, ľ. kvetna 2GlG
23
Implementace Prologu
Reprezentace objektů II
Príznaky (tags):
Objekt	Príznak
volná promenná	FREE
konstanta	CONST
celé císlo	INT
odkaz	REF
složený term	FUNCT
Obsah adresovatelného slova: hodnota a príznak. Primitivní objekty uloženy prímo ve slove
Hana Rudová, Logické programování I, 7. kvetna 2010
ZS
Implementace Prologu
Reprezentace objektů II
Příznaky (tags):
Objekt	Příznak
volná promenná	FREE
konstanta	CONST
celé císlo	INT
odkaz	REF
složený term	FUNCT
Obsah adresovatelného slova: hodnota a príznak. Primitivní objekty uloženy prímo ve slove Složené objekty
Ä jsou instance termu ve zdrojovém textu, tzv. zdrojového termu
& zdrojový term bez promenných => každá instanciace ekvivalentní zdrojovému termu
zdrojový term s promennými => dve instance se mohou lišit aktuálními hodnotami promenných, jedinecnost zajišťuje kopírování struktur nebo sdílení struktur
Hana Rudová, Logické programování I, 7. kvetna 2010
2B
Implementace Prologu
Kopírování struktur
P ríklad:
a(b(X),c(X,Y),d),
FUNCT a/3
REF
REF
CONSTd
FUNCT c/2
REF
FREE Y
FUNCT b/1 -
FREE X
Hana Rudová, Logické programování I, ľ. kvetna 2GlG
24
Implementace Prologu
Kopírování struktur II
Term F s aritou A reprezentován A+1 slovy: A funktor a arita v prvním slove
J* 2. slovo nese první argument (resp. odkaz na jeho hodnotu) . A A+1 slovo nese hodnotu A-tého argumentu
Reprezentace vychází z orientovaných acyklických grafu
a/3	i	_		d
				
c/2
Y
b/l 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, 7. kvetna 2010
25
Implementace Prologu
Sdílení struktur
Vychází z myšlenky, že pri reprezentaci je treba rešit prítomnost promenných JS> Instance termu
< kostra_termu; rámec >
M kostra_termu je zdrojový term s ocíslovanými promennými & rámec je vektor aktuálních hodnot techto promenných
í-tá položka nese hodnotu í-té promenné v původním termu
Hana Rudová, Logické programování I, 7. kvetna 2010
26
Implementace Prologu
Sdílení struktur II
Príklad:
a(b(X),c(X,Y),d) reprezentuje
< a(b($1),c($1,$2),d)  ;  [FREE, FREE] > kde symbolem $i oznacujeme í-tou promennou.
Hana Rudová, Logické programování I, 7. kvetna 2010
27
Implementace Prologu
Sdílení struktur II
Príklad:
a(b(X),c(X,Y),d) reprezentuje
< a(b($1),c($1,$2),d) ;  [FREE, FREE] > kde symbolem $i oznacujeme í-tou promennou.
Implementace:
< &kostra_termu; &rámec > (& vrací adresu objektu) Všechny instance sdílí spolecnou kostru_termu => sdílení struktur
Hana Rudová, Logické programování I, 7. kvetna 2010
27
Implementace Prologu
Srovnání: príklad
Naivní srovnání: sdílení pamet'ove méne nárocné
Hana Rudová, Logické programování I, 7. kvetna 2010
28
Implementace Prologu
Srovnání: příklad
Naivní srovnání: sdílení pamet'ove méne nárocné
Platí ale pouze pro rozsáhlé termy prítomné ve zdrojovém kódu
Hana Rudová, Logické programování I, 7. kvetna 2010
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 prítomné ve zdrojovém kódu
Postupná tvorba termU:
A = a(K,L,M), K = b(X), L = c(X,Y), M = d
Sdílení termů
A
- kostra_a
- K
L
M:d
- kostra_b
kostra_č
- X
Y
Hana Rudová, Logické programování I, 7. kvetna 2010
28
Implementace Prologu
Srovnání: príklad - pokračování
C 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, ľ. kvetna 2GlG
29
Implementace Prologu
Srovnání: príklad - pokračování
C 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 prímé vytvorení termu a(b(X),c(X,Y),d)
Hana Rudová, Logické programování I, 7. kvetna 2010 29 Implementace Prologu
Srovnání II
Složitost algoritmů pro přístup k jednotlivým argumentům
s sdílení struktur: nutná víceúrovnová neprímá adresace & kopírování struktur: bez problémů
jednodušší algoritmy usnadnují i optimalizace
Hana Rudová, Logické programování I, 7. kvetna 2010
30
Implementace Prologu
Srovnání II
Složitost algoritmů pro přístup k jednotlivým argumentům
s sdílení struktur: nutná víceúrovnová neprímá adresace & kopírování struktur: bez problému
jednodušší algoritmy usnadnují i optimalizace
Lokalita prístupu do pameti
s sdílení struktur: prístupy rozptýleny po pameti & kopírování struktur: lokalizované prístupy
pri stránkování pameti - rozptýlení vyžaduje prístup k více stránkám
Hana Rudová, Logické programování I, 7. kvetna 2010
30
Implementace Prologu
Srovnání II
Složitost algoritmů pro prístup k jednotlivým argumentům
s sdílení struktur: nutná víceúrovnová neprímá adresace & kopírování struktur: bez problému
jednodušší algoritmy usnadnují i optimalizace
Lokalita přístupů do pameti
s sdílení struktur: prístupy rozptýleny po pameti & kopírování struktur: lokalizované prístupy
pri stránkování pameti - rozptýlení vyžaduje prístup k více stránkám
Z praktického hlediska neexistuje mezi temito prístupy zásadní rozdíl
Hana Rudová, Logické programování I, 7. kvetna 2010
30
Implementace Prologu
Řízení výpočtu
JS> Dopredný výpočet
a po úspechu (úspešná redukce)
jednotlivá volání procedur skona úspechem
a klasické volání rekurzivních procedur
Hana Rudová, Logické programování I, 7. kvetna 2010
31
Implementace Prologu
Řízení výpoCtu
JS> Dopredný výpoCet
a po úspechu (úspešná redukce)
jednotlivá volání procedur skoncí úspechem
a klasické volání rekurzivních procedur
JS> Zpetný výpoCet (backtracking)
a po neúspechu vyhodnocení literálu (neúspešná redukce) nepodarí se unifikace aktuálních a formálních parametrů hlavy
a návrat do bodu, kde zústala nevyzkoušená alternativa výpoctu je nutná obnova původních hodnot jednotlivých promenných
po nalezení místa s dosud nevyzkoušenou klauzulí pokracuje dále dopredný výpocet
Hana Rudová, Logické programování I, 7. kvetna 2010
31
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 & Aktivacní záznam uložen na lokálním zásobníku
Hana Rudová, Logické programování I, 7. kvetna 2010
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
& Aktivacní záznam uložen na lokálním zásobníku
JS> Dopredný výpocet
i> stav výpoctu v okamžiku volání procedury
A aktuální parametry
iľ lokální promenné
& pomocné promenné ('a la registry)
Hana Rudová, Logické programování I, 7. kvetna 2010
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
JS> Aktivacní záznam uložen na lokálním zásobníku
JS> Dopredný výpocet
i> stav výpoctu v okamžiku volání procedury A aktuální parametry iľ lokální promenné
pomocné promenné ('a la registry)
J& Zpetný výpocet (backtracking)
-i- hodnoty parametrů v okamžiku zavolání procedury -fc následující klauzule pro zpracování pri neúspechu
Hana Rudová, Logické programování I, 7. kvetna 2010
32
Implementace Prologu
Aktivační záznam a roll-back
Neúspěšná klauzule mohla nainstanciovat nelokální proměnné
a(X) :- X = b(c,Y), Y = d. ?- W = b(Z,e), a(W).
Hana Rudová, Logické programování I, 7. května 2010
33
Implementace Prologu
Aktivační záznam a roll-back
Neúspěšná klauzule mohla nainstanciovat nelokální proměnné
a(X) : - X = b(c,Y), Y = d. ?- W = b(Z,e), a(W).        (viz instanciace Z)
Hana Rudová, Logické programování I, 7. kvetna 2010
33
Implementace Prologu
Aktivační záznam a roll-back
Neúspěšná klauzule mohla nainstanciovat nelokální proměnné
a(X) : - X = b(c,Y), Y = d. ?- W = b(Z,e), a(W).        (viz instanciace Z)
£ Pri návratu je treba obnovit (roll-back) pUvodní hodnoty promenných
Využijeme vlastností logických promenných
Jť instanciovat lze pouze volnou promennou
iť jakmile promenná získá hodnotu, nelze ji zmenit jinak než návratem výpočtu => puvodní hodnoty všech promenných odpovídají volné promenné
Hana Rudová, Logické programování I, 7. kvetna 2010
33
Implementace Prologu
Aktivační záznam a roll-back
Neúspešná klauzule mohla nainstanciovat nelokální promenné
a(X) : - X = b(c,Y), Y = d. ?- W = b(Z,e), a(W).        (viz instanciace Z)
-í* Pri návratu je treba obnovit (roll-back) puvodní hodnoty promenných
Využijeme vlastností logických promenných
Jť instanciovat lze pouze volnou promennou
iť jakmile promenná získá hodnotu, nelze ji zmenit jinak než návratem výpočtu => původní hodnoty všech promenných odpovídají volné promenné
& Stopa (trail): zásobník s adresami instanciovaných promenných
A ukazatel na aktuální vrchol zásobníku uchováván v aktivacním záznamu
pri neúspechu jsou hodnoty promenných na stope v úseku mezi aktuálním a uloženým vrcholem zásobníku zmeneny na „volná"
Hana Rudová, Logické programování I, 7. kvetna 2010
33
Implementace Prologu
Aktivační záznam a roll-back
Neúspešná klauzule mohla nainstanciovat nelokální promenné
a(X) : - X = b(c,Y), Y = d. ?- W = b(Z,e), a(W).        (viz instanciace Z)
-í* Pri návratu je treba obnovit (roll-back) puvodní hodnoty promenných
Využijeme vlastností logických promenných
Jť instanciovat lze pouze volnou promennou
iť jakmile promenná získá hodnotu, nelze ji zmenit jinak než návratem výpočtu => puvodní hodnoty všech promenných odpovídají volné promenné
& Stopa (trail): zásobník s adresami instanciovaných promenných
A ukazatel na aktuální vrchol zásobníku uchováván v aktivacním záznamu
pri neúspechu jsou hodnoty promenných na stope v úseku mezi aktuálním a uloženým vrcholem zásobníku zmeneny na „volná"
& Globální zásobník: pro uložení složených termu
S> ukazatel na aktuální vrchol zásobníku uchováván v aktivacním záznamu
-i- pri neúspechu vrchol zásobníku snížen podle uschované hodnoty v aktivacním záznamu
Hana Rudová, Logické programování I, 7. kvetna 2010 33 Implementace Prologu
Okolí a bod volby
Aktivační záznam úspešne ukončené procedury nelze odstranit z lokálního zásobníku => rozdelení aktivačního záznamu:
JS> okolí (environment) - informace nutné pro dopredný beh programu
-í* bod volby (choice point) - informace nezbytné pro zotavení po neúspechu
Hana Rudová, Logické programování I, 7. kvetna 2010
34
Implementace Prologu
Okolí a bod volby
Aktivacní záznam úspešne ukoncené procedury nelze odstranit z lokálního zásobníku => rozdelení aktivačního záznamu:
JS> okolí (environment) - informace nutné pro dopredný beh programu
M bod volby (choice point) - informace nezbytné pro zotavení po neúspechu
& ukládány na lokální zásobník
-i* samostatne provázány (odkaz na predchozí okolí resp. bod volby)
Hana Rudová, Logické programování I, 7. kvetna 2010
34
Implementace Prologu
Okolí a bod volby
Aktivacní záznam úspešne ukoncené procedury nelze odstranit z lokálního zásobníku => rozdelení aktivaCního záznamu:
JS> okolí (environment) - informace nutné pro dopredný beh programu
-í* bod volby (choice point) - informace nezbytné pro zotavení po neúspechu
& ukládány na lokální zásobník
-i* samostatne provázány (odkaz na predchozí okolí resp. bod volby) Důsledky:
& samostatná práce s každou cástí aktivacního záznamu (optimalizace)
Hana Rudová, Logické programování I, 7. kvetna 2010
34
Implementace Prologu
Okolí a bod volby
Aktivacní záznam úspešne ukoncené procedury nelze odstranit z lokálního zásobníku => rozdelení aktivačního záznamu:
JS> okolí (environment) - informace nutné pro dopredný beh programu
M bod volby (choice point) - informace nezbytné pro zotavení po neúspechu
& ukládány na lokální zásobník
-i* samostatne provázány (odkaz na predchozí okolí resp. bod volby) Důsledky:
& samostatná práce s každou cástí aktivacního záznamu (optimalizace) -í* alokace pouze okolí pro deterministické procedury
Hana Rudová, Logické programování I, 7. kvetna 2010
34
Implementace Prologu
Okolí a bod volby
Aktivacní záznam úspešne ukoncené procedury nelze odstranit z lokálního zásobníku => rozdelení aktivačního záznamu:
JS> okolí (environment) - informace nutné pro dopredný beh programu
-í* bod volby (choice point) - informace nezbytné pro zotavení po neúspechu
& ukládány na lokální zásobník
-i* samostatne provázány (odkaz na predchozí okolí resp. bod volby) Důsledky:
& samostatná práce s každou cástí aktivacního záznamu (optimalizace)
-í* alokace pouze okolí pro deterministické procedury
& možnost odstranení okolí po úspešném vykonání (i nedeterministické) procedury (pokud okolí následuje po bodu volby dané procedury)
pokud je okolí na vrcholu zásobníku
Hana Rudová, Logické programování I, 7. kvetna 2010 34 Implementace Prologu
Řez
JS> Prostředek pro ovlivnení behu výpoctu programátorem
a(X) :- b(X),  !, c(X). a(3). b(1). b(2). c(1). c(2).
Hana Rudová, Logické programování I, 7. kvetna 2010
35
Implementace Prologu
Řez
JS> Prostředek pro ovlivnění běhu výpočtu programátorem
a(X) :- b(X),  !, c(X). a(3). b(1). b(2). c(1). c(2).
-í* Řez: neovlivňuje dopredný výpočet, má vliv pouze na zpětný výpočet
-i* Odstranení alternativních vetví výpočtu
=> odstranení odpovídajících bodů volby
A tj. odstranení bodu volby mezi současným vrcholem zásobníku a bodem volby procedury, která rez vyvolala (včetne bodu volby procedury s rezem)
=> zmena ukazatele na „nejmladší" bod volby
Hana Řudová, Logické programování I, 7. kvetna 2010
35
Implementace Prologu
Řez
JS> Prostředek pro ovlivnení behu výpoctu programátorem
a(X) :- b(X),  !, c(X). a(3). b(1). b(2). c(1). c(2).
-í* Rez: neovlivnuje dopredný výpocet, má vliv pouze na zpetný výpocet
& Odstranení alternativních vetví výpoctu
^ odstranení odpovídajících bodů volby
A tj. odstranení bodu volby mezi soucasným vrcholem zásobníku a bodem volby procedury, která rez vyvolala (vcetne bodu volby procedury s rezem)
=> zmena ukazatele na „nejmladší" bod volby
^ Vytvárení deterministických procedur => Optimalizace využití zásobníku
Hana Rudová, Logické programování I, 7. kvetna 2010 35
Implementace Prologu