Opakování: základní pojmy Implementace Prologu Literatura: ■ 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 ■ 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ů T\,.. .Ta, a > 0 ■ Literál 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 s n termy na místě argumentů ■ Dotaz (cíl) je neprázdná množina literálů. Interpretace Deklarativní sémantika: Hlava platí, platí-1i 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 2013 3 Implementace Prologu Hana Rudová, Logické programování I, 14. května 2013 2 Implementace Prologu Abstraktní interpret Vstup: Logický program P a dotaz C. 1. Inicializuj množinu cílů S literály z dotazu C; S:=C 2. while ( S != empty ) do 3. Vyber AeS a dále vyber klauzuli A' : -Bi, . . . , B„ (n > 0) z programu P takovou, že 3a : Aer = A' cr; cr je nejobecnější unifikátor. Pokud neexistuje A' nebo cr, ukonči cyklus. 4. Nahraď A v S cíli Bi až B„. 5. Aplikuj a na C a S. 6. end while 7. Pokud S==empty, pak výpočet úspěšně skončil a výstupem je C se všemi aplikovanými substitucemi. Pokud S!=empty, výpočet končí neúspěchem. Hana Rudová, Logické programování I, 14. května 2013 4 Implementace Prologu Abstraktní interpret - pokračování Kroky (3) až (5) představují redukci (logickou inferenci) cíle A. Počet redukcí za sekundu (LIPS) == indikátor výkonu implementace Věta Existuje-li instance C dotazu C, odvoditelná z programu P v konečném počtu kroků, pak bude tímto interpretem nalezena. Hana Rudová, Logické programování I, 14. května 2013 Implementace Prologu Prohledávání do šířky 1. Vybereme všechny klauzule Ar, které je možno unifikovat s literálem A ■ nechť je těchto klauzulí q 2. Vytvoříme q kopií množiny S 3. V každé kopii redukujeme A jednou z klauzulí Ar. ■ aplikujeme příslušný nejobecnější unifikátor 4. V následujících krocích redukujeme všechny množiny Sí současně. 5. Výpočet ukončíme úspěchem, pokud se alespoň jedna z množin Sí stane prázdnou. ■ Ekvivalence s abstraktnímu interpretem ■ pokud jeden interpret neuspěje, pak neuspěje i druhý ■ pokud jeden interpret uspěje, pak uspěje i druhý Hana Rudová, Logické programování I, 14. května 2013 Implementace Prologu Nedeterminismus interpetu 1. Selekční pravidlo: výběr cíle A z množiny cílů S ■ neovlivňuje výrazně výsledek chování interpretu 2. Způsob prohledávání stromu výpočtu: výběr klauzule A' z programu P ■ je velmi důležitý, všechny klauzule totiž nevedou k úspěšnému řešení Vztah k úplnosti: 1. Selekční pravidlo neovlivňuje úplnost ■ možno zvolit libovolné v rámci SLD rezoluce 2. Prohledávání stromu výpočtu do šířky nebo do hloubky „Prozření" - automatický výběr správné klauzule ■ vlastnost abstraktního interpretu, kterou ale reálné interprety nemají Hana Rudová, Logické programování I, 14. května 2013 6 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 nějakém kroku nenajdeme vhodnou klauzuli A', vrátíme se k předchozímu stavu (tedy anulujeme aplikace posledního unifikátoru cr) a vybereme ze zásobníku další klauzuli. 5. Pokud je zásobník prázdný, končí výpočet neúspěchem. 6. Pokud naopak zredukujeme všechny literály v S, výpočet končí úspěchem. 1 Není úplné, tj. nemusí najít všechna řešení 1 Nižší paměťová náročnost než prohledávání do šířky 1 Používá se v Prologu Hana Rudová, Logické programování I, 14. května 2013 8 Implementace Prologu Reprezentace objektů Reprezentace objektů II ■ Beztypový jazyk ■ Kontrola „typů" za běhu výpočtu ■ Informace o struktuře součástí objektu Typy objektů ■ Primitivní objekty: ■ konstanta ■ číslo ■ volná proměnná ■ odkaz (reference) ■ Složené (strukturované) objekty: ■ struktura ■ seznam Hana Rudová, Logické programování I, 14. května 2013 Objekt Příznak volná proměnná FREE konstanta CONST celé číslo INT odkaz REF složený term FUNCT Příznaky (tags): Obsah adresovatelného slova: hodnota a příznak. Primitivní objekty uloženy přímo ve slově Složené objekty ■ jsou instance termu ve zdrojovém textu, tzv. zdrojového termu ■ zdrojový term bez proměnných => každá instanciace ekvivalentní zdrojovému termu ■ 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 Implementace Prologu Hana Rudová, Logické programování I, 14. května 2013 Implementace Prologu Kopírování struktur Kopírování struktur II 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 Term F s aritou A reprezentován A+l slovy: ■ funktor a arita v prvním slově ■ 2. slovo nese první argument (resp. odkaz na jeho hodnotu) I ■ A+l slovo nese hodnotu A-tého argumentu Reprezentace vychází z orientovaných acyklických grafů: a/3 c/2 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, 14. května 2013 Implementace Prologu Hana Rudová, Logické programování 1,14. května 201 3 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 ■ i-tá položka nese hodnotu i-té proměnné v původním termu Hana Rudová, Logické programování I, 14. května 2013 13 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 M:d kostra_b ^ kostra_c X —i 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 i-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 2013 14 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/1 FREE X Hana Rudová, Logické programování I, 14. května 2013 Implementace Prologu tj. identické jako přímé vytvoření termu a(b(X) ,c(X,Y) ,d) Hana Rudová, Logické programování 1,14. května 201 3 16 Implementace Prologu Srovnání II Složitost algoritmů pro přístup k jednotlivým argumentům ■ sdílení struktur: nutná víceúrovňová nepřímá adresace ■ kopírování struktur: bez problémů ■ 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 ■ při stránkování paměti - rozptýlení vyžaduje přístup k více stránkám Z praktického hlediska neexistuje mezi těmito přístupy zásadní rozdíl Řízení výpočtu ■ Dopředný výpočet ■ po úspěchu (úspěšná redukce) ■ jednotlivá volání procedur skončí úspěchem ■ klasické volání rekurzivních procedur ■ Zpětný výpočet (backtracking) ■ po neúspěchu vyhodnocení literálu (neúspěšná redukce) ■ 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 ■ 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, 14. května 2013 17 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 ■ stav výpočtu v okamžiku volání procedury ■ aktuální parametry ■ lokální proměnné ■ pomocné proměnné ('a la registry) Zpětný výpočet (backtracking) ■ hodnoty parametrů v okamžiku zavolání procedury ■ následující klauzule pro zpracování při neúspěchu Hana Rudová, Logické programování I, 14. května 2013 19 Implementace Prologu Hana Rudová, Logické programování 1,14. května 2013 18 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) ■ Při návratu je třeba obnovit (roll-back) původní hodnoty proměnných ■ Využijeme vlastností logických proměnných ■ instanciovat lze pouze volnou proměnnou ■ jakmile proměnná získá hodnotu, nelzeji 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 ■ 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ů ■ ukazatel na aktuální vrchol zásobníku uchováván v aktivačním záznamu ■ 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 2013 20 Implementace Prologu Okolí a bod volby Aktivační záznam úspešne 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 ■ 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) ■ pokud je okolí na vrcholu zásobníku Hana Rudová, Logické programování I, 14. května 2013 21 Implementace Prologu Interpret Prologu Základní principy: ■ klauzule uloženy jako termy ■ programová databáze ■ pro uložení klauzulí ■ má charakter haldy ■ umožňuje modifikovatelnost prologovských programů za běhu (assert) ■ klauzule zřetězeny podle pořadí načtení ■ triviální zřetězení Vyhodnocení dotazu: volání procedur řízené unifikací Hana Rudová, Logické programování I, 14. května 2013 23 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 ■ Odstranění alternativních větví výpočtu => odstranění odpovídajících bodů volby ■ 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 2013 22 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 2013 24 Implementace Prologu Interpret - vlastnosti Lokální i globální zásobník ■ při dopředném výpočtu roste ■ 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. „Interpret": interpret(Query, Vars) :- call(Query), success(Query, Vars). interpret(_,_) :- failure. ■ dotaz vsazen do kontextu této speciální nedeterministické procedury ■ tato procedura odpovídá za korektní reakci systému v případě úspěchu i neúspěchu Hana Rudová, Logické programování I, 14. května 2013 Implementace Prologu Optimalizace: Indexace 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 Možno rozhodnout (parciálně) determinismus procedury Hana Rudová, Logické programování I, 14. května 2013 Implementace Prologu Indexace argumentů a(l) :- q(l). a(a) :- b(X). a([A|T]) :- c(A,T). ■ Obecně nedeterministická ■ Při volání s alespoň částečně instanciovaným argumentem vždy deterministická (pouze jedna klauzule může uspět) ■ Indexace podle prvního argumentu Základní typy zřetězení: ■ podle pořadí klauzulí (aktuální argument je volná proměnná) ■ dle konstant (aktuální je argument konstanta) ■ formální argument je seznam (aktuální argument je seznam) ■ dle struktur (aktuální argument je struktura) Indexace argumentů II ■ Složitější indexační techniky ■ podle všech argumentů ■ podle nejvíce diskriminujícího argumentu ■ kombinace argumentů (indexové techniky z databází) ■ zejména pro přístup k faktům Hana Rudová, Logické programování I, 14. května 2013 27 Implementace Prologu Hana Rudová, Logické programování I, 14. května 2013 28 Implementace Prologu Tail Recursion Optimization, TRO TRO - příklad Iterace prováděna pomocí rekurze => lineární paměťová náročnost cyklů Optimalizace koncové rekurze (Tail 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: ■ v případě úspěchu se rovnou pokračuje ■ v případě neúspěchu se vrací na předchozí bod volby („nad" aktuální klauzulí) ■ 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. 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 ■ s TRO: 1 okolí, konstatní paměťová náročnost Hana Rudová, Logické programování I, 14. května 2013 29 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. Nutné úpravy interpretu ■ disciplina směrování ukazatelů ■ 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 ■ pouze pro neinstanciované proměnné Hana Rudová, Logické programování I, 14. května 2013 31 Implementace Prologu Hana Rudová, Logické programování I, 14. května 2013 30 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: ■ Oblast kódu (programová databáze) ■ separátní oblasti pro uživatelský kód (modifikovatelný) a vestavěné predikáty (nemění se) ■ obsahuje rovněž všechny statické objekty (texty atomů a funktorů apod.) ■ Lokální zásobník (Stack) ■ Stopa (Trail) ■ Globální zásobník n. ba\da(Heap) ■ Pomocný zásobník (Push Down List, PDL) ■ pracovní paměť abstraktního počítače ■ použitý v unifikaci, syntaktické analýze apod. Hana Rudová, Logické programování I, 14. května 2013 32 Implementace Prologu Rozmístění datových oblastí Příklad konfigurace Halda > i Stopa i Zásobník ' PDL i Oblast kodu Halda i lokální zásobník musí růst stejným směrem ■ 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 2013 33 Implementace Prologu Typy instrukcí WAMu put instrukce - příprava argumentů před voláním podcíle ■ žádná z těchto instrukcí nevolá obecný unifikační algoritmus get instrukce - unifikace aktuálních a formálních parametrů ■ vykonávají činnost analogickou instrukcím unify ■ obecná unifikace pouze při get_va"lue unify instrukce - zpracování složených termů ■ jednoargumentové instrukce, používají registr S jako druhý argument ■ počáteční hodnota S je odkaz na 1. argument ■ volání instrukce unify zvětší hodnotu S o jedničku ■ obecná unifikace pouze při unify_va"lue a unify_1oca"l_va"lue Indexační instrukce - indexace klauzulí a manipulace s body volby Instrukce řízení běhu - předávání řízení a explicitní manipulace s okolím Hana Rudová, Logické programování I, 14. května 2013 35 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 o 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é: Yl, Y2, . . . ■ abstraktní znázornění lok. proměnných na zásobníku Hana Rudová, Logické programování I, 14. května 2013 34 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_va"lue A2.A5 put_va"lue A3.A6 put_va"lue A4.A7 execute b/4 Hana Rudová, Logické programování I, 14. května 2013 36 Implementace Prologu WAM - optimalizace Instrukce WAMu 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 instrukce put instrukce unify instrukce get_var Ai ,Y put_ _var Ai ,Y unify_var Y get_value Ai ,Y put_ .value Ai ,Y unify_value Y get_const Ai ,C put_ _unsafe_value Ai ,Y unify_local_value Y get_ni1 Ai put_ .const Ai ,C unify_const C get_struct Ai,F/N put_ .nil Ai unify_nil get_li st Ai put_ .struct Ai ,F/N unify_void N put_ .1 i st Ai get_var A1.A5 1 get_var A3, A4 instrukce řízení indexační instrukce get_var A2.A6 1 get_var A2.A3 allocate try_me_else Next try Next get_var A3.A7 1 get_var A1.A2 deallocate retry_me_el se Next retry Next put_const Al,f 1 put_const Al,f call Proc/N,A trust_me_el se fail trust fail put_value A2.A5 1 execute b/4 execute Proc/N put_value A3.A6 1 proceed cut_last switch. _on_ .term Var,Const,Li st.Struct put_value A4.A7 1 save_cut Y switch. _on_ .const Table execute b/4 1 load_cut Y switch. _on_ .struct Table Hana Rudová, Logické programování I, 14. května 2013 Implementace Prologu Hana Rudová, Logické programování 1,14. května 201 3 Implementace Prologu WAM - indexace Příklad indexace instrukcí Provázání klauzulí: instrukce XX_me_el se: ■ první klauzule: try_me_else; založí bod volby ■ poslední klauzule: trust_me_else; zruší nejmladší bod volby ■ ostatní klauzule: retry_me_el se; znovu použije nejmladší bod volby po neúspěchu Proceduře a(atom) :- bodyl. a(l) :- body2. a(2) :- body3. odpovídají instrukce a([X|Y]) a([X|Y]) aCs(N)) : a(fCN)) : - body4. - body5. body6. bodyľ. ■ Provázání podmnožiny klauzulí (podle argumentu): a: switch_on_term LI, L2, L3, L4 L5a: body2 ■ try L2: switch_on_const atom :Lla L6: retry. _me_ _el se L7 ■ retry 1 :L5a L6a: body3 2 :L6a L7: retry. _me_ _el se L8 ■ trust L3: try L7a L7a: body4 ■ „Rozskokové" instrukce (dle typu a hodnoty argumentu): trust L8a L8: retry. _me_ _el se L9 ■ switch_on_term Var, Const, List, Struct L4: switch_on_struct s/l :L9a L8a: body5 výpočet následuje uvedeným návěstím podle typu prvního argumentu f/1 :L10a L9: retry. _me_ _el se L10 ■ switch_on_YY: hashovací tabulka pro konkrétní typ (konstanta, struktura) LI: try_me_else L5 L9a: body6 Lla: bodyl L10: trust. _me_ _el se fail L5: retry_me_else L6 LlOa: body7 Hana Rudová, Logické programování 1, 14. května 2013 39 Implementace Prologu Hana Rudová, Logické programování 1, 14. května 2013 40 Implementace Prologu WAM - řízení výpočtu ■ execute Proč: ekvivalentní příkazu goto ■ proceed: zpracování faktů ■ all ocate: alokuje okolí (pro některé klauzule netřeba, proto explicitně generováno) ■ deal 1 ocate: uvolní okolí (je-li to možné, tedy leží-li na vrcholu zásobníku) ■ cal 1 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 2013 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 ■ 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 1 oad_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 Yl.Al; 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 2013 42 Implementace Prologu