To jest stara wersja strony!


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:

Należy wziąć pod uwagę implementacje:

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

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:

:- 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)].

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

?- domain(X, [a,b]).

Oznacza to, że dziedzina zmiennej X to zbiór {a,b}.

?- domain(X, [a,b]), X = c.
 fail

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.

?- domain(X, [a,b]), domain(X, [a,c]).
 X = a

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.

?- domain(X, [a,b,c]), domain(X, [a,c]). 
domain(X, [a, c])

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.

CLP

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
:- 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 ;

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.

:- 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.

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ć:

?- puzzle(As+Bs=Cs), label(As). 

A otrzymamy rozwiązanie:

As = [9, 5, 6, 7],
 
Bs = [1, 0, 8, 5],
 
Cs = [1, 0, 6, 5, 2] ;
 
false. 

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
:- 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 ).

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:

?- oneground(X, Y, Z), Y = 5. 

W wyniku czego dostaniemy następujący wynik:

Y = 5,
Z = 1,
X in inf..sup.

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:

?- tuples_in([X,Y], [[1,2],[1,5],[4,0],[4,3]]), X = 4. 

W wyniku czego otrzymamy rozwiązanie:

X = 4,
Y in 0\/3. 

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
:- 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).

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:

?- threepath(1, 4, Ps). 

Rozwiązanie problemu:

Ps = [[1, 2, 0, 1], [2, 3, 4, 5], [3, 4, 8, 9]].
  • 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:
  1. biblioteki CLP(Q) do rozwiązywania zagadnień z ograniczeniami na liczbach wymiernych
  2. 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.

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).

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:

?- knapsack(S), variable_value(S, x(1), X1), variable_value(S, x(2), X2).

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:

X1 = 1
 
X2 = 1 rdiv 2 

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.

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).

I po wywołaniu zapytania o rozwiązanie ZPL, otrzymujemy inne od poprzedniego rozwiązanie:

X1 = 0
 
X2 = 2

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

Constraint Handling Rules zaimplementowany w SWI-Prolog bazuje na systemie CHR stworzonym w SICStus Prolog. Definiowanie nowych ograniczeń za pomocą CHR jest możliwe po załadowaniu biblioteki chr

:- use_module(library(chr)).

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 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:

:- 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).

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:

?- leq(X,Y), leq(Y,Z).

Oznacza to, że X≤Y i Y≤Z. Odpowiedź systemu jest zgodna z oczekiwaniami:

leq(_G23837, _G23841)
 
leq(_G23838, _G23841)
 
leq(_G23837, _G23838)
 
X = _G23837{leq = ...}
 
Y = _G23838{leq = ...}
 
Z = _G23841{leq = ...}
 
Yes 

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.

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 (tabling, memoization)

Metoda optymalizacji szybkości działania systemu oparta na rozwiązaniu w XSB, polegającym na zapamiętywaniu wyników raz wykonanej operacji, by nie tracić zasobów i czasu na powtarzanie tych samych operacji później. Rozwiązanie nie zostało jak na razie zastosowane 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, 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:

:- table np/2.

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. 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.

:- table avoids/2.
 
 avoids(Source,Target) :- owes(Source,Target).
 
 avoids(Source,Target) :-
 
 owes(Source,Intermediate),
 
 avoids(Intermediate,Target). 

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:

owes(andy,bill).
owes(bill,carl).
owes(carl,bill).

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 :

 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
| ?-

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] Yap Prolog User's Manual

[4] Programming in Tabled Prolog

[5] SWI-Prolog User's Manual

[6] Jairson Vitorino and Marcos Aurélio, Constraint Handling Rules, 2005.

[7] Programowanie logiczne z użyciem ograniczeń

[8] Christian Holzbaur, Metastructures vs. Atributted Variables in the Context of Extensible Unification

pl/miw/miw08_prolog_adv.1222738949.txt.gz · ostatnio zmienione: 2019/06/27 15:58 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0