--- pl:miw:miw08_prolog_adv [2008/09/30 06:20]
miw
+++ pl:miw:miw08_prolog_adv [2019/06/27 15:50] (aktualna)
@@ Linia 1: / Linia 1: @@
+====== Opis ======
+Sławomir Polański, <wawele@gmail.com>
+==== Prolog_Adv ====
+celem projektu jest opis, pogłębiona analiza i prezentacja przykładów wykorzystania rozszerzeń Prologu o zaawansowane mechanizmy takie jak:
+  * CLP http://en.wikipedia.org/wiki/Constraint_logic_programming **2**
+  * jak to się ma do CHR  **2**
+  * tabled resolution http://en.wikipedia.org/wiki/Memoization **3**
+  * atrybuty i dziedziny, np. w [[http://www.sics.se/sicstus/docs/latest4/html/sicstus.html/lib_002datts.html#lib_002datts|SICStusie]] **1**
+  * inne
+Należy wziąć pod uwagę implementacje:
+  * [[http://xsb.sourceforge.net|XSB]]  **3+**
+  * [[http://www.swi-prolog.org/|SWI]] **1**
+  * [[http://www.ncc.up.pt/~vsc/Yap/|YAP]]  **2**
+  * [[http://www.amzi.com/|Amzi!]]
+  * [[http://www.itee.uq.edu.au/~pjr/HomePages/QuPrologHome.html|QuProlog]]
+  * [[http://trinc-prolog.com|TrincProlog]]
+  * [[http://www.sics.se/sicstus|SICStus]]
+====== Spotkania ======
+====== Projekt ======
+====== Sprawozdanie ======
+===== Wstęp =====
+CLP z angielskiego Constraint Logic Programming to programowanie logiczne z ograniczeniami. Ograniczenie to prosta logiczna relacja między kilkoma niewiadomymi (zmiennymi), z których każda przyjmuje wartość z danej dziedziny. Np. „koło jest w środku kwadratu” zadaje relację między dwoma obiektami, bez precyzowania ich konkretnej pozycji, czyli ich współrzędnych. Możemy również dodać inny obiekt, powiedzmy trójkąt i stworzyć następne ograniczenie, np. „kwadrat jest po prawej stronie trójkąta”.
+W ostatnich latach to popularny sposób modelowania i rozwiązywania wielu problemów z dziedziny:
+  * sztucznej inteligencji
+  * przetwarzania mowy
+  * problemów kombinatorycznych
+  * sporządzania harmonogramów (ang. scheduling)
+  * projektowania obwodów drukowanych
+  * przetwarzania języków naturalnych (konstruowanie efektywnych parserów)
+  * systemów baz danych (zapewnienie spójności danych)
+  * biologii molekularnej (sekwencjonowanie DNA)
+  * inżynierii elektronicznej(lokalizacja błędów).
+Ideą programowania CLP jest rozwiązywanie problemów poprzez zadawanie ograniczeń (warunków, własności), które muszą być spełniane przez rozwiązanie. Problem spełniania ograniczeń, na którym CLP bazuje to Constraint Satisfaction Problem (CSP). Jesto to problem, dla którego istnieje:
+    * skończony zbiór zmiennych ''X={x1,...,xn}'',
+    * funkcja przypisująca każdej zmiennej skończoną dziedzinę,
+    * skończony zbiór ograniczeń.
+Rozwiązaniem CSP jest przypisanie każdej zmiennej wartości z jej dziedziny, spełniającą wszystkie ograniczenia. Zadaniem jest znalezienie jednego rozwiązania lub wszystkich. W ogólności zadanie postawione w CSP jest obliczeniowo skomplikowane (problem NP-trudny).
+Najistotniejszą cechą i największą zaletą programowania z ograniczeniami jest ich propagacja. Technika ta stała się najlepsza metodą dla wielu problemów kombinatorycznych. Zasadą działania propagacji jest usuwanie wartości nie spełniających ograniczeń z domen zmiennych. Języki do programowania z ograniczeniami mają możliwość wyrażania zmiennych z zakresu domen liczb naturalnych (najczęściej stosowane),
+przedziałów liczb rzeczywistych, zbiorów i innych. Aby zobrazować propagacje ograniczeń rozważmy prosty przykład:
+''x ∈ {1..5}, y ∈ {1..6}''
+Gdy na powyższe dwie zmienne wprowadzimy ograniczenie ''x>y+1'', wtedy
+propagacja ograniczeń zredukuje powyższe domeny do następujących wartości:
+''x ∈ {3, 4, 5}, y ∈ {1, 2, 3}''
+ponieważ wartości {1, 2} z domeny ''x'' nie spełniają ograniczenia ''x>y+1'' dla żadnej z
+wartości z domeny ''y''. Podobnie można rozpatrywać wartości {4, 5, 6} z domeny ''y''.
+Ograniczenia nie są zazwyczaj tak proste ja to przedstawiono, często łączą ze sobą
+wiele zmiennych, a metody usuwania poszczególnych wartości, zwane algorytmami
+filtracyjnymi są bardzo złożone.
+CLP jest wspierane przez wprowadzenie specjalnych zmiennych, tzw. zmiennych z atrybutami. Kiedy ich atrybuty będą oznaczać dziedziny zmiennych, będzie można wykonywać operacje nie tylko na zmiennych, ale także ich dziedzinach. Dostęp do danych, będzie wówczas szybszy i łatwiejszy, co ułatwi pracę programistom, poprawi także czytelność oraz szybkość wykonywanego programu.
+Nie zawsze jednak CLP dostarcza odpowiednich narzędzi, by zadanie przed jakim stanął programista mogło być szybko i wydajnie rozwiązane. Kiedy programista spotyka się z na tyle złożonymi i specyficznymi problemami, że istniejące w bibliotekach ograniczenia są niewystarczające do stworzenia wydajnego i dobrze zoptymalizowanego programu, musi on zdefiniować od nowa lub zmodyfikować już istniejące ograniczenia jak i określić reguły ich przetwarzania. Do tego służy mu język programowania CHR (z ang. Constraint Handling Rules).
+W projekcie mowa jest też o technice spamiętywania (ang. memoization), zastosowanej w niektórych dystrybucjach Prologu, dzięki której możliwe jest wydajniejsze i bezpieczniejsze działanie programu (przeciwdziałanie występowaniu nieskończonych pętli).
+=====SWI-Prolog 5.6=====
+====CLP====
+Costraint Logic Programming zostało wprowadzone po to, by można było rozwiązywać w Prologu problemy logiczne razem z matematycznymi. Dotychczasowe  możliwości programu pozwalały jedynie na tworzenie stosunkowo prostych reguł z użyciem operacji matematycznych, choć nawet i one nie były satysfakcjonujące.
+==Przykład==
+Rozważmy przykład podatnika, który ma za zadanie odprowadzić podatek 50% od dochodów, jeśli w ciągu roku były większe niż 150000. W innym przypadku ma odprowadzić 25% od kwoty rocznego dochodu pomniejszonego o kwotę 30000. Reguły można zapisać w następujący sposób [9]:
+<code prolog>
+tax(Income; 0.5*Income) <- greater(Income; 150000).
+tax(Income; 0.25*(Income − 30000)) <- ¬greater(Income; 150000).
+</code>
+Teraz jeśli podatnik dostał odpowiedź z urzędu skarbowego, że ma do zapłacenia 25000 od 130000 rocznego przychodu, ktoś chciałby sprawdzić za pomocą sformułowanej wyżej reguły czy jest to kwota prawidłowo obliczona za pomocą wywołania:
+<code prolog>
+tax(130000,25000).
+</code>
+Niestety, reguła ta nie będzie mogła być wykorzystana, ponieważ Prolog nie będzie mógł sprawdzić czy wartości ''25000 i 0.25*(130000-30000)'' są takie same przy użyciu standardowego algorytmu unifikacji, czyli uzgadniania wartości. W tym celu należało rozszerzyć algorytm unifikacji i wprowadzić CLP. Między innymi dzięki wprowadzeniu [[pl:miw:miw08_prolog_adv#zmienne_z_atrybutami_dziedziny|zmiennych z atrybutami]] było to możliwe.
+==== ====
+CLP jest wspierane przez SWI-Prolog począwszy od wersji 5.5.4, kiedy pojawiła się biblioteka CLP z ograniczeniami dla liczb rzeczywistych. W wersji 5.6 została rozszerzona, a dopiero w wersji 5.6.7 wprowadzono ograniczenia dla liczb wymiernych. Programista ma do dyspozycji szereg modułów: ''clp/clp_distinct, clp/simplex, clp/clpfd , clpqr'', które zostaną omówione w dalszej części opracowania.
+  * ''clp_distinct'' dostarcza ograniczenia ''all_distinct(Vars)'', polegającego na poszukiwaniu rozwiązania, dla którego porównywane elementy Vars różnią się od siebie oraz ''vars_in(Vars,Domain)'' określające zmienne ''Vars'' w zbiorze ''Domain'', który jest listą  nieujemnych liczb całkowitych
+==Przykład==
+<code prolog>
+:- use_module(library(bounds)).
+:- use_module(library(clp_distinct)).
+?- [X,Y] in 1..2, vars_in([X, Y],[1, 2]), all_distinct([X, Y]), label([X, Y]).
+X = 1,
+Y = 2 ;
+X = 2,
+Y = 1 ;
+</code>
+W wyniku działania programu zostają znalezione pary zmiennych X i Y, różniące się od siebie wartościami,a zarazem należące do dziedziny {1,2}. W programach CLP mogą być wykorzystywane atrybuty przypisywane zmiennym,właśnie takim jak X i Y widocznym w przykładzie. Konieczna często jest modyfikacja wartości tych atrybutów, by zostało znalezione rozwiązanie. Widać też jak implementacja tzw. zmiennych z przypisanymi atrybutami stanowi wsparcie dla CLP. Predykat ''in/2'' określa zmienną jako element zbioru {1,2}, a ''label/1'' powoduje, że wyszukiwane są rozwiązania z dziedzin zmiennych i podawane są w formie konkretnych wartości liczbowych, a nie symbolicznych(np.''_G10110'').
+==== ====
+   * clpfd, czyli moduł CLP ze zmiennymi określonymi na skończonych zbiorach (dziedzinach). Biblioteka clpfd może być wykorzystywana do modelowania i rozwiązywania rozmaitych kombinatorycznych problemów jak planowanie czy alokacja zadań. Większość predykatów tej biblioteki to ograniczenia (relacje), określone na  dziedzinach, będących skończonymi zbiorami liczb całkowitych. Predykaty umożliwiają konwersję wyrażeń do ich wartości liczbowej, tak że rozrastanie się wyrażeń może postępować we wszystkich kierunkach. Biblioteka dostarcza także predykatów, umożliwiających systematyczne poszukiwanie rozwiązań, których dziedziny są zbiorami skończonymi. Wyrażeniem jest tutaj liczba całkowita, zmienna, ujemne wyrażenie, dodawanie wyrażeń, ich mnożenie oraz odejmowanie, minimum lub maksimum dwóch wyrażeń, reszta z dzielenia wyrażeń przez siebie, wartość bezwzględna, dzielenie liczb całkowitych. Natomiast ograniczeniami są relacje nierówności >  , ≥ , <  ,≤ , ≠ oraz relacja równości =, oznaczane odpowiednio ''#> , #>= , #< , #=< , #\= i #='' . Do ograniczeń należy także koniunkcja  ''P, Q'' , które mogą być zarówno nierównościami jak i równaniami lub mogą przyjmować wartości logiczne ''0'' lub ''1'', ich alternatywa , implikacja , implikacja odwrotna, równoważność oraz negacja jednego z nich, oznaczane odpowiednio ''P #/\ Q , P #\/ Q , P #''==''> Q , P #<''=='' Q , P #<''==''> Q, #\ Q''.
+==Przykład==
+Poniżej jest przykład wykorzystania biblioteki ''clpfd'' dla rozwiązania puzzli SEND + MORE = MONEY, gdzie poszczególne zmienne ''S,E,N,D,M,O,R,Y'' oznaczają cyfry liczb ''SEND, MORE i MONEY''. Zmienne należą zatem do zbioru liczb naturalnych {0,1,2,3,4,5,6,7,8,9} z wyjątkiem ''S i M'', które są różne od 0. Wszystkie zmienne są od siebie różne.
+<code prolog>
+:- use_module(library(clpfd)).
+puzzle([S,E,N,D] + [M,O,R,E] = [M,O,N,E,Y]) :-
+Vars = [S,E,N,D,M,O,R,Y],
+Vars ins 0..9,
+all_different(Vars),
+S*1000 + E*100 + N*10 + D +M*1000 + O*100 + R*10 + E #= M*10000 + O*1000 + N*100 + E*10 + Y,
+M #\= 0, S #\= 0.
+</code>
+''ins/2'' oznacza, że zmienne ''Vars'' są elementami zbioru jednocyfrowych liczb naturalnych, ''all_different/1'' że wszystkie zmienne są różne od siebie, a w dalszych linijkach widać zapis ograniczeń za pomocą odpowiednich wyrażeń dodawania, mnożenia, literałów i zmiennych. Przy tak zdefiniowanym predykacie puzzle, by otrzymać rozwiązanie zadania należy wpisać:
+<code prolog>
+?- puzzle(As+Bs=Cs), label(As). </code>
+A otrzymamy rozwiązanie:
+<code prolog>
+As = [9, 5, 6, 7],
+Bs = [1, 0, 8, 5],
+Cs = [1, 0, 6, 5, 2] ;
+false. </code>
+Predykat ''label/1'' powinno stosować się do wszystkich zmiennych, gdyby otrzymane rozwiązanie nie było podane w formie pojedynczych wartości liczb. Dzięki bibliotece ''clpfd'' znaleziono rozwiązanie puzzli S = 9, E = 5, N = 6, D = 7, M = 1, O = 0, R = 8, Y = 2.
+=== ===
+W oparciu o moduł ''clpfd'' można także definiować własne ograniczenia, lecz prace nad tą funkcją nie zostały zakończone dla bieżącej wersji SWI-Prolog tj. 5.6. i będą dalej rozwijane. Aktualne możliwości tworzenia ograniczeń przez użytkownika można prześledzić na przykładzie ograniczenia ''oneground(X,Y,Z)'', polegającego na przypisaniu ''Z'' wartości 1, kiedy przynajmniej ''X'' lub ''Y'' otrzymało swoją instancję.
+==Przykład==
+<code prolog>
+:- use_module(library(clpfd)).
+:- multifile clpfd:run_propagator/2.
+oneground(X, Y, Z) :-
+clpfd:make_propagator(oneground(X, Y, Z), Prop),
+clpfd:init_propagator(X, Prop),
+clpfd:init_propagator(Y, Prop),
+clpfd:trigger_once(Prop).
+clpfd:run_propagator(oneground(X, Y, Z), MState) :-
+( integer(X) -> clpfd:kill(MState), Z = 1 ;
+integer(Y) -> clpfd:kill(MState), Z = 1 ;
+true ).
+</code>
+Jak widać kluczowymi predykatami dla definiowania ograniczeń są ''make_propagator/2, init_propagator/2, run_propagator/2, trigger_once/1 i kill/1.'' Pierwszy z nich ''clpfd:make_propagator/2'' jest wykorzystywany do przekształcenia reprezentacji nowego ograniczenia, stworzonej przez użytkownika do postaci rozumianej przez Prolog. Ta wewnętrzna postać następnie jest przypisywana do X i Y za pomocą ''clpfd:init_propagator/2''. Od tej pory predykat z zawartą logiką ograniczenia ''run_propagator'' jest przywoływany za każdym razem, kiedy dziedziny X i Y zmienią się. Z kolei ''clpfd:trigger_once/1'' daje możliwość wywołania predykatu ''run_propagator/2'' nawet jeśli dziedziny zmiennych jeszcze się nie zmieniły. Wreszcie ''clpfd:run_propagator/2'' jest rozszerzony do takiej formy, aby zdefiniować działanie ograniczenia. Jak wyjaśniono jest to predykat automatycznie wywoływany w Prologu. Jego pierwszym argumentem jest reprezentacja ograniczenia zdefiniowana przez użytkownika ''oneground(X,Y,Z)'', a drugim argumentem jest zmienny stan ''MState'', który może być wykorzystany, aby uniknąć później wywołania ''run_propagator/2''  przez zastosowanie predykatu ''clpfd:kill/1''. Nowe ograniczenie ''oneground(X,Y,Z)'' może być wywołane w następujący sposób:
+<code prolog>
+?- oneground(X, Y, Z), Y = 5. </code>
+W wyniku czego dostaniemy następujący wynik:
+<code prolog>
+Y = 5,
+Z = 1,
+X in inf..sup.
+</code>
+=== ===
+Biblioteka ''clpfd'' dostarcza jeszcze jednego ciekawego rozwiązania. Predykat ''tuples_in/2'' umożliwia sprawdzanie kompatybilności tablic, tak więc może dopasowywać listy zmiennych do siebie. Ma on postać ''tuples_in(Tuples, Relation)'', gdzie ''Relation'' musi być listą list liczb całkowitych. Jeśli chodzi o elementy listy ''Tuples'' to są one ograniczone przez elementy listy ''Relation''. Relacja ''tuples_in/2'' może zostać wykorzystana w Prologu w następujący sposób:
+<code prolog>
+?- tuples_in([X,Y], [[1,2],[1,5],[4,0],[4,3]]), X = 4. </code>
+W wyniku czego otrzymamy rozwiązanie:
+<code prolog>
+X = 4,
+Y in 0\/3. </code>
+ Lista [X,Y] została dopasowana do tych elementów drugiej listy ''Relation'',dla których pierwszy ich element był równy 4. W ten sposób otrzymano rozwiązanie dla którego X = 4, a Y przyjmuje wartość 0 lub 3, czyli chodzi o listy [4,3] i [4,0]. Relacja ta może być potem zastosowana w problemie planowania przejazdu pociągiem.
+==Przykład==
+<code prolog>
+:- use_module(library(clpfd)).
+trains([[1,2,0,1],[2,3,4,5],[2,3,0,1],[3,4,5,6],[3,4,2,3],[3,4,8,9]]).
+threepath(A, D, Ps) :-
+Ps = [[A,B,_T0,T1],[B,C,T2,T3],[C,D,T4,_T5]],
+T2 #> T1,
+T4 #> T3,
+trains(Ts),
+tuples_in(Ps, Ts).
+</code>
+''Trains'' to lista przyjazdów i odjazdów pociągów z jednego punktu do drugiego. Predykat ''threepath/3'' umożliwia za pomocą odpowiednich warunków i ''tuples_in/2'', wyszukanie trzech połączeń z listy ''trains'', realizujących podróż z punktu A do punktu D. Zapytanie użytkownika, w którym pyta on o połączenia z punktu 1 do 4 wygląda następująco:
+<code prolog>
+?- threepath(1, 4, Ps). </code>
+Rozwiązanie problemu:
+<code prolog>
+Ps = [[1, 2, 0, 1], [2, 3, 4, 5], [3, 4, 8, 9]].
+</code>
+==== ====
+  * ''clpqr'', czyli moduł umożliwiający modelowanie problemów CLP, określonych na zbiorach liczb wymiernych i rzeczywistych. Działanie CLP(Q,R) w SWI-Prolog opiera się na systemie CLP(Q,R) w SICStus Prolog, opracowanym przez Christiana Holzbaura [2]. System CLP(Q,R) składa się z dwóch składników:
+=== ===
+  - biblioteki CLP(Q) do rozwiązywania zagadnień z ograniczeniami na liczbach wymiernych
+  - biblioteki CLP(R) do rozwiązywania problemów z ograniczeniami na liczbach rzeczywistych, wykorzystujących reprezentację zmiennoprzecinkową
+=== ===
+Obie biblioteki dostarczają tych samych predykatów z wyjątkiem ''bb_inf/4'' w CLP(Q) i ''bb_inf/5'' w CLP(R). Jest to dozwolone, by używać dwóch bibliotek w jednym programie, ale używanie ograniczeń zarówno w CLP(Q) i CLP(R) dla tych samych zmiennych zakończy się zgłoszeniem wyjątku. Trzeba zwrócić uwagę na to, że ładowanie biblioteki clpqr przeprowadza się następująco:
+'':- use_module(library(clpq)).''
+lub
+ '':- use_module(library(clpr)).''
+Do pracy z ograniczeniami użytkownik dysponuje predykatami określającymi kres górny zbioru ''sup/2'', kres dolny - ''inf/2'', ''bb_inf'',  minimum - ''minimize/1'', maksimum - ''maximize/1'', dodawanie ograniczeń - ''{}/1'', sprawdzanie zgodności ograniczeń - ''entailed/1'', zapisywanie ograniczeń zmiennych do listy - ''dump/3''. System CLP(Q,R) radzi sobie także z nieliniowymi ograniczeniami takimi jak mnożenie, dzielenie, element maksymalny i minimalny, wartość bezwzględna, potęgowanie oraz podstawowe funkcje trygonometryczne, po tym jak spełnione są odpowiednie warunki.
+==== ====
+  * ''simplex''
+=== ===
+Zagadnienie programowania liniowego składa się ze zbioru ograniczeń liniowych, pewnej liczby zmiennych i funkcji kosztu. Celem jest przypisanie takich wartości zmiennym, aby funkcja kosztu przyjmowała wartości maksymalne lub minimalne dla zmiennych, spełniających ograniczenia liniowe. Wiele problemów optymalizacji może być modelowanych w ten sposób.
+==Przykład==
+Rozważmy plecak z określoną pojemnością ''C'' i przedmioty o wartości v(i) oraz rozmiarze s(i). Celem jest włożenie do plecaka jak największej ilości przedmiotów, nie przekraczając jego pojemności i uzyskując maksymalną sumę ich wartości. Niech ''C = 8'' i są dwa rodzaje przedmiotów: jeden o wartości 7 i rozmiarze 6 oraz dwa przedmioty o rozmiarze i wartości równej 4, a zmienne ''x(1) i x(2)'' oznaczają ile poszczególnych przedmiotów każdego rodzaju jest pakowanych do plecaka.
+<code prolog>
+knapsack_constrain(S) :-
+gen_state(S0),
+constraint([6*x(1), 4*x(2)] =< 8, S0, S1),
+constraint([x(1)] =< 1, S1, S2),
+constraint([x(2)] =< 2, S2, S).
+knapsack(S) :-
+knapsack_constrain(S0),
+maximize([7*x(1), 4*x(2)], S0, S).</code>
+Predykat ''gen_state/1'' definiuje warunki początkowe problemu, ''constraint/3'' określa ograniczenia zadania programowania liniowego (ZPL): ''6x(1)+4x(2)≤8, x(1)≤1'' oraz ''x(2)≤2'', a ''maximize/3'' definiuje maksymalizowaną funkcję celu ''Q(x) = 7x(1) + 4x(2)''. Dla poprawnego sformułowania zadania kluczowe jest odpowiednie wpisanie stanów ''S0, S1, S2 i S'' w definicji predykatów ''knapsack_constrain i knapsack''. Stany te są wewnętrzną reprezentacją stanu wynikowego lub początkowego pewnego etapu poszukiwania rozwiązania.
+Zapytanie użytkownika o rozwiązanie wygląda tak:
+<code prolog>
+?- knapsack(S), variable_value(S, x(1), X1), variable_value(S, x(2), X2).
+</code>
+gdzie ''knapsack/1'' to wywołanie zdefiniowanego ZPL, a ''variable_value/3'' posłużyło do zapytania o wartość zmiennej ''x(1)'', a potem ''x(2)'' w ustalonym stanie ''S''. Odpowiedź wygląda tak:
+<code prolog>
+X1 = 1
+X2 = 1 rdiv 2 </code>
+to znaczy ''x(1)= 1'', a ''x(2) = 0.5.'' Do plecaka zatem należy spakować jeden przedmiot pierwszego rodzaju i połowę drugiego, aby uzyskać ich maksymalną wartość. Jeśli przedmioty muszą zachować integralność, należy ponownie zdefiniować zadanie, tak aby zmienne przyjmowały wartości całkowite.
+<code prolog>
+knapsack_integral(S) :-
+knapsack_constrain(S0),
+constraint(integral(x(1)), S0, S1),
+constraint(integral(x(2)), S1, S2),
+maximize([7*x(1), 4*x(2)], S2, S).</code>
+I po wywołaniu zapytania o rozwiązanie ZPL, otrzymujemy inne od poprzedniego rozwiązanie:
+<code prolog>
+X1 = 0
+X2 = 2</code>
+Wszystkie numeryczne wielkości są domyślnie zamieniane na liczby wymierne przez użycie predykatu ''rationalize/1'' i arytmetyka liczb wymiernych jest stosowana w rozwiązywaniu zadań programowania liniowego. W bieżącej implementacji modułu ''simplex'' wszystkie zmienne są domyślnie nieujemne.
+====CHR====
+Kiedy programista spotyka się z na tyle złożonymi i specyficznymi problemami, że istniejące w bibliotekach CLP ograniczenia są niewystarczające do stworzenia wydajnego i dobrze zoptymalizowanego programu, musi on zdefiniować od nowa lub zmodyfikować już istniejące ograniczenia jak i określić reguły ich przetwarzania. Umożliwia mu to język Constraint Handling Rules,  zaimplementowany w SWI-Prolog. Bazuje on na systemie CHR stworzonym w SICStus Prolog. Definiowanie nowych ograniczeń za pomocą CHR jest możliwe po załadowaniu biblioteki ''chr'', dostępnej w SWI-Prolog od wersji 5.6.0:
+<code  prolog>:- use_module(library(chr)).</code>
+Co prawda w CLP zostały wprowadzone możliwości implementacji nowych ograniczeń przez użytkownika, ale tylko w module ze skończonymi zbiorami dziedzin.  Ponadto prace nad tym  rozwiązaniem nie zostały zakończone i będą postępować, a rezultaty wysiłków programistów będzie można obserwować w kolejnych wersjach SWI-Prolog. Chociażby właśnie z tego względu CHR jak na razie dostarcza użytkownikom najlepszych rozwiązań do tworzenia własnych zaawansowanych ograniczeń. Ponadto CHR umożliwia ich modyfikację, by można je było dostosowywać do własnych potrzeb. Podobnie jak CLP ma wbudowane pewne standardowe ograniczenia jak na przykład relacje równości, ale w odróżnieniu od CLP, CHR nie służy do poszukiwania rozwiązań zadań w zbiorach dziedzin zmiennych tylko do definiowania ograniczeń.
+==Przykład==
+Jednym z ograniczeń jest relacja nierówności. By lepiej zrozumieć metodę definiowania ograniczeń za pomocą CHR, można podać w tym języku definicję relacji ≤. Niech nazywa się ''leq''. Poniższy program definiuje mechanizm działania jednego ograniczenia ''leq/2'':
+<code prolog>
+:- module(leq,[leq/2]).
+:- use_module(library(chr)).
+:- chr_constraint leq/2.
+reflexivity @ leq(X,X) <=> true.
+antisymmetry @ leq(X,Y), leq(Y,X) <=> X = Y.
+idempotence @ leq(X,Y) \ leq(X,Y) <=> true.
+transitivity @ leq(X,Y), leq(Y,Z) ==> leq(X,Z).</code>
+Jak widać definicja zawiera w sobie szereg reguł, określających naturę relacji. W tym przypadku są to : zwrotność, antysymetria, idempotentność i przechodniość. Ich nazwy poprzedzają znak ''@'', a po nich występują predykaty zdefiniowane przez użytkownika (heads), wbudowane (guards) lub oba rodzaje ograniczeń (body), definiujące własności relacji ≤. Pomiędzy predykatami użytkownika a dalszą częścią tzw. reguły występują znaki ''<''=''>'' , ''''==''>'' lub ''\'' razem z  ''<''=''>'' w zależności od tego, który z trzech rodzajów reguły (simplification, propagation, simpagation) został w definicji ograniczenia ''leq/2'' wyskorzystany. Deklaracja nowego ograniczenia tworzona jest za pomocą predykatu ''chr_constraint/1''.
+Kiedy powyższy program zostanie zapisany i załadowany w SWI-Prolog, użytkownik może wykorzystać relację ''leq/2'' w następujący sposób:
+<code prolog>?- leq(X,Y), leq(Y,Z).</code>
+Oznacza to, że ''X≤Y'' i ''Y≤Z''. Odpowiedź systemu jest zgodna z oczekiwaniami:
+<code prolog>leq(_G23837, _G23841)
+leq(_G23838, _G23841)
+leq(_G23837, _G23838)
+X = _G23837{leq = ...}
+Y = _G23838{leq = ...}
+Z = _G23841{leq = ...}
+Yes </code>
+Oznacza to, że ''X≤Z i Y≤Z i X≤Y''. System podał zatem logiczny wynik w postaci ograniczeń, na podstawie warunków podanych przez użytkownika, co mogłoby być np. wykorzystane w rozwiązywaniu problemu CLP.
+====Zmienne z atrybutami, dziedziny====
+Zmienne z atrybutami zostały wprowadzone, by umożliwić rozszerzenie algorytmu unifikacji [1] w Prologu, co z kolei stanowi podstawę do wprowadzenia rozmaitych języków CLP [8].
+Mając do dyspozycji możliwość nadawania zmiennym atrybutów i modyfikacji ich wartości,zdefiniowano predykat, określający dziedzinę danej zmiennej. Jest to ''domain/2''.
+===Przykład===
+Na podstawie definicji predykatu ''domain/2'' można zaobserwować tworzenie zmiennych z atrybutami (nadawanie zmiennym atrybutów) i wykonywanie na nich operacji:
+<code prolog>
+:- module(domain,[ domain/2]).
+:- use_module(library(ordsets)).
+domain(X, Dom) :-
+var(Dom), !,
+get_attr(X, domain, Dom).
+domain(X, List) :-
+list_to_ord_set(List, Domain),
+put_attr(Y, domain, Domain),
+X = Y.
+% Zmiennej z atrybutem o wartości Domain została przypisana wartość Y
+attr_unify_hook(Domain, Y) :-
+( get_attr(Y, domain, Dom2)
+-> ord_intersection(Domain, Dom2, NewDomain),
+( NewDomain == []
+-> fail
+; NewDomain = [Value]
+-> Y = Value
+; put_attr(Y, domain, NewDomain)
+)
+; var(Y)
+-> put_attr( Y, domain, Domain )
+; ord_memberchk(Y, Domain)
+).
+% Tłumaczenie atrybutów z tego modułu do pozostałych celów
+attribute_goals(X) -->
+{ get_attr(X, domain, List) },
+[domain(X, List)].
+</code>
+==== ====
+Działanie predykatu ''domain/2'' wynika z zapisanej w module domain logiki i wykorzystania dobrodziejstw zmiennych z atrybutami przy użyciu między innymi takich predykatów jak ''put_attr/3'', ''get_attr/3'', ''var/1'', ''attr_unify_hook/2'', ''attribute_goals/3''.
+   * ''put_attr(Var,Module,Value)'' powoduje przypisanie wartości ''Value'' do atrybutu ''Module'' zmiennej ''Var'' i utworzenie zmiennej z atrybutem, o ile wcześniej zmienna ''Var'' nią nie była
+  * ''get_attr(Var,Module,Value)'' pobiera aktualną wartość ''Value'' atrybutu ''Module'' zmiennej ''Var'', jeśli zmienna nie jest powiązana z atrybutem ''Module'' działanie kończy się niepowodzeniem bez zgłoszenia błędu
+  * ''var(Term)'' kończy się sukcesem o ile ''Term'' jest zmienną z przypisanym atrybutem
+  * ''attr_unify_hook(AttValue, VarValue)'' jest wywoływana po tym jak atrybutowi (np. dziedzinie) zmiennej jest przypisana wartość. Jej działanie sprowadza się do szukania części wspólnej przypisanych atrybutowi wartości.
+===Przykłady zapytań dla domain/2===
+ <code prolog>?- domain(X, [a,b]).</code>
+Oznacza to, że dziedzina zmiennej X to zbiór {a,b}.
+ <code prolog>?- domain(X, [a,b]), X = c.
+ fail</code>
+Oznacza to, że X należy do zbioru pustego, ponieważ po określeniu dziedziny zmiennej X jako zbioru {a,b} i przypisaniu tej samej zmiennej X wartości c,   część wspólna obu zbiorów {a,b} i {c} jest zbiorem pustym, a algorytm unifikacji kończy swoje działanie niepowodzeniem.
+ <code prolog>?- domain(X, [a,b]), domain(X, [a,c]).
+ X = a</code>
+W tym przypadku część wspólna obu zbiorów, zdefiniowanych jako dziedziny zmiennej X jest jednoelementowym zbiorem {a} i odpowiada on wartości zmiennej  X.
+ <code prolog>?- domain(X, [a,b,c]), domain(X, [a,c]).
+domain(X, [a, c])</code>
+W ostatnim przypadku widać, że algorytm unifikacji porównał dwie dziedziny tej samej zmiennej, by znaleźć wspólną wartość. Znalazł iloczyn zbiorów {a,b,c} i {a,c} i zapisał jako nową dziedzinę zmiennej X.
+==== ====
+Tak samo wygląda działanie zmiennych z atrybutami w Yap Prolog i SICStus Prolog.
+=====YAP Prolog 5.1.3=====
+  * CLP
+W Yapie aktualnie wykorzystywany jest pakiet CLP(R) dostarczany wraz z SWI-Prolog. Jest on częścią systemu CLP(Q,R) opracowanego dla SICStus Prolog i Yap przez Christiana Holzbaura. Moduł ten omówiony jest w części poświęconej SWI-Prolog. Pozostałych bibliotek wspierających CLP brak.
+  * CHR
+CHR wykorzystywany w Yapie został dostosowany do systemu CHR z SWI-Prolog i stał się jego wiernym odzwierciedleniem. Istnieją pewne różnice w  niektórych pragmach, opcjach i deklaracjach ''handler/1'' i ''rules/1'', ale nie są one istotne. Dla Yap i SICSTus zastosowano dwufazowy kompilator, który pliki ''.chr'' tłumaczy na ''.pl'' w pierwszej kolejności. W SWI-Prolog reguły CHR mogą być zapisywane w pliku o dowolnym rozszerzeniu.
+  * Technika spamiętywania (memoization, tabling)
+Technika oparta na metodzie optymalizacji szybkości działania programu, zaimplementowanej w XSB (patrz niżej). Jak na razie nie została zastosowana w SWI-Prolog, przy czym w YAP nie ma wsparcia dla niektórych predykatów obsługiwanych w ten zoptymalizowany sposób oraz tzw. "coroutiningu".
+=====XSB 3.1=====
+====Technika spamiętywania (tabling, memoization)====
+Technika optymalizacji szybkości działania programu oparta na rozwiązaniu, polegającym na zapamiętywaniu wyników raz wykonanej operacji, by nie tracić zasobów i czasu na powtarzanie tych samych operacji później.
+Technika optymalizacji, polegająca na spamiętywaniu rozwiązań, zastosowana w XSB, ma prostą idee. Opiera się na zakazie wykonywania tej samej procedury dwukrotnie. Kiedy po raz pierwszy jest wykonana, należy zapamiętać wszystkie zwracane wartości i jeśli zostanie potem powtórnie użyta, należy wykorzystać wcześniej wykonane obliczenia. W XSB programista wskazuje, które wywołania mają zostać umieszczone w tablicy w następujący sposób:
+<code prolog>:- table np/2.</code>
+Ten przykład oznacza, że wszystkie wywołania, odnoszące się do procedury ''np/2'' o dwóch argumentach, powinny być umieszczone w tablicy. Przykładem wykorzystania tablic w technice spamiętywania, może być definicja domknięcia przechodniego (transitive closure) w grafach.
+==Przykład==
+Załóżmy, że mamy zbiór faktów, definiujących predykat ''owes/2''. Fakt ''owes(andy, bill)'' oznacza, że Andy jest winny Billemu trochę pieniędzy. Wówczas używamy predykatu ''owes/2'' do zdefiniowania predykatu ''avoids/2'', który mówi o tym, kto kogo unika z powodu długu.
+<code prolog>:- table avoids/2.
+ avoids(Source,Target) :- owes(Source,Target).
+ avoids(Source,Target) :-
+ owes(Source,Intermediate),
+ avoids(Intermediate,Target). </code>
+Teraz zakładamy, że krawędzie grafu skierowanego są zapisane w predykacie ''owes/2''. W XSB możemy posłużyć się deklaracją table i gwarantuje ona, że ten predykat będzie prawidłowo obliczony, nawet jeśli graf w ''owes/2'' jest cykliczny. Intuicyjnie wydaje się być jasne, że jakiekolwiek wywołanie ''avoids/2'' zakończy się, ponieważ jest skończenie wiele możliwości wywołań dla jakiegokolwiek skończonego grafu i odkąd technika spamiętywania gwarantuje, że żadne wywołanie nie będzie wykonywane więcej niż jeden raz, w końcu wszystkie konieczne wywołania zostaną wykonane, a obliczenia zostaną zakończone. Problem z Prologiem był taki, że w grafach cyklicznych, to samo wywołanie było wykonywane i powtarzane nieskończoną ilość razy.
+W samej rzeczy wykonywanie wykonywanie programu na tak określonym grafie:
+<code prolog>
+owes(andy,bill).
+owes(bill,carl).
+owes(carl,bill).</code>
+dla zapytania: ''avoids(andy,X)'', co zobaczyliśmy doprowadzi do wykonywania operacji w nieskończonej pętli bez użycia deklaracji table, dostarczonej pod XSB. Z uwzględnieniem table, będzie można zobaczyć następujące wyniki dla podobnego zapytania :
+<code prolog> warren% xsb
+XSB Version 1.4.2 (95/4/6)
+[sequential, single word, optimal mode]
+| ?- [graph].
+[Compiling ./graph]
+[graph compiled, cpu time used: 0.589 seconds]
+[graph loaded]
+yes
+| ?- avoids(andy,Y).
+Y = bill;
+Y = carl;
+no
+| ?-
+</code>
+==== ====
+Jak widać wykorzystanie tablic pomaga nie tylko w optymalizacji działania programów, ale także przeciwdziała ich zapętleniom
+=====Podsumowanie=====
+Szereg technologii wykorzystywanych w Prologu, opartych jest na rozwiązaniach zastosowanych w SICStus Prolog, jak na przykład CHR, CLP(Q,R) i zmienne z atrybutami. Aktualnie tylko SWI-Prolog poszerzył możliwości programowania w CLP o dodatkowe moduły jak ''simplex'' , ''clpfd'' z możliwością tworzenia własnych ograniczeń i ''clp_distinct'', oferując największy zestaw narzędzi do programowania w CLP i CHR, przy użyciu między innymi specjalnych zmiennych. Mimo to są implementacje takie jak XSB i YAP, które wykorzystują innowacyjne techniki optymalizacji, oszczędzające zasoby i przeciwdziałające występowaniu nieskończonych pętli, których SWI-Prolog jeszcze nie wprowadził. Można zauważyć tendencje, że pozostałe dystrybucje Prologu jak XSB czy Yap staraja się być kompatybilne z SWI-Prolog.
+====== Materiały ======
+[1] Christian Holzbaur. //Realization of forward checking in logic
+programming through extended unification.// Report TR-90-11,
+Oesterreichisches Forschungsinstitut fuer Artificial Intelligence,
+Wien, Austria, 1990.
+[2] Holzbaur Christian: OFAI clp(q,r) Manual, Edition 1.3.3, Austrian Research Institute for Artificial Intelligence,
+Vienna, TR-95-09, 1995.1
+[3] [[http://www.dcc.fc.up.pt/~vsc/Yap/documentation.html#SEC118 | Yap Prolog User's Manual]]
+[4] [[ http://www.cs.sunysb.edu/~warren/xsbbook/node14.html | Programming in Tabled Prolog]]
+[5] [[http://gollem.science.uva.nl/cgi-bin/nph-download/SWI-Prolog/refman/refman.pdf | SWI-Prolog User's Manual ]]
+[6] [[http://www.cin.ufpe.br/~in1006/2005/Slides/CHRBasics.ppt | Jairson Vitorino and Marcos Aurélio, Constraint Handling Rules, 2005.]]
+[7] [[http://www-users.mat.uni.torun.pl/%7Efly/materialy/pl/referaty/CLP/index.html | Programowanie logiczne z użyciem ograniczeń]]
+[8] [[http://books.google.pl/books?id=iKIFlxm-6eUC&pg=PA260&lpg=PA260&dq=unification+holzbaur&source=web&ots=NipAbew5jf&sig=mzRfimw8lpGXTlJSEQvBjbpfn_g&hl=pl&sa=X&oi=book_result&resnum=8&ct=result#PPA260,M1 | Christian Holzbaur, Metastructures vs. Atributted Variables in the Context of Extensible Unification]]
+[9][[http://www.ida.liu.se/~ulfni/lpp/bok/bok.pdf| Ulf Nilsson, Jan Małuszyński. LOGIC PROGRAMMING AND PROLOG (2ED)]]

Pokaż stronę Poprzednie wersje

Menadżer multimediów Do góry

AIwiki

Menu

Dla Studentów

Old specialized AI courses

SMaDA/SMaIDA/AIDA

Informatyka (EAIiIB)

Studia Dr

Inne materialy dydaktyczne

Archiwum

Dyplomanci

Geist Season of Code

HeKatE

Public

Różnice