Both sides previous revision
Poprzednia wersja
Nowa wersja
|
Poprzednia wersja
|
pl:miw:miw08_prolog_adv [2008/09/29 18:30] miw |
pl:miw:miw08_prolog_adv [2019/06/27 15:50] (aktualna) |
====== Opis ====== | ====== Opis ====== |
Sławomir Polański, <wawele@gmail.com> | Sławomir Polański, <wawele@gmail.com> |
| |
| |
| |
| |
| |
* jak to się ma do CHR **2** | * jak to się ma do CHR **2** |
* tabled resolution http://en.wikipedia.org/wiki/Memoization **3** | * tabled resolution http://en.wikipedia.org/wiki/Memoization **3** |
* atrybuty i dziedziny, np. w [[http://www.sics.se/sicstus/docs/latest/html/sicstus/Attributes.html|SICStusie]] **1** | * atrybuty i dziedziny, np. w [[http://www.sics.se/sicstus/docs/latest4/html/sicstus.html/lib_002datts.html#lib_002datts|SICStusie]] **1** |
* inne | * inne |
Należy wziąć pod uwagę implementacje: | Należy wziąć pod uwagę implementacje: |
* [[http://www.itee.uq.edu.au/~pjr/HomePages/QuPrologHome.html|QuProlog]] | * [[http://www.itee.uq.edu.au/~pjr/HomePages/QuPrologHome.html|QuProlog]] |
* [[http://trinc-prolog.com|TrincProlog]] | * [[http://trinc-prolog.com|TrincProlog]] |
* [[http://www.sics.se/sicstus|SICStus]] [[http://www.sics.se/sicstus/docs/latest4/html/sicstus.html/lib_002datts.html#lib_002datts]] | * [[http://www.sics.se/sicstus|SICStus]] |
| |
====== Spotkania ====== | ====== Spotkania ====== |
| |
| |
===== Wstęp ===== | |
CLP z angielskiego Constraint Logic Programming to programowanie logiczne z ograniczeniami typu X+Y>0, gdzie X, Y to zmienne określone na pewnych zbiorach. W ostatnich latach to popularny sposób modelowania i rozwiązywania wielu problemów z dziedziny: sztucznej inteligencji, problemów kombinatorycznych, przetwarzania mowy, harmonogramowania, przetwarzania języków naturalnych, systemów baz danych, biologii molekularnej, inżynierii elektronicznej. Jego główną zaletą jest deklaratywność, czyli sformułowanie zadania jest programem rozwiązującym to zadanie. Programowanie to bazuje na modelowaniu zadania jako problemu spełnienia ograniczeń - Constraint Satisfaction Problem (CSP). Ograniczenia są zależne od dziedzin zmiennych, których dotyczą. Najpopularniejszą dziedziną zmiennych była skończona dziedzina liczb naturalnych. Innymi dziedzinami są skończone zbiory, drzewa, przedziały rzeczywiste. Najistotniejszą cechą i największą zaletą programowania z ograniczeniami jest ich propagacja. Jej działanie sprowadza się do usuwania wartości nie spełniających ograniczeń z domen zmiennych. | |
| |
W rozwiązywaniu problemów formułowanych w Prologu, często konieczna jest unifikacja, czyli uzgadnianie wartości dwóch wielkości, tak by były sobie równe. Dla zastosowania rozszerzonego algorytmu unifikacji [1] wprowadzono specjalne zmienne (ang. attributed variables). Zwiększają one możliwości rozwiązywania zadań programowania logicznego, a więc i CLP. Umożliwiają na przykład operacje na dziedzinach zmiennych, dla których dziedzina jest atrybutem o wartości, określonej przez zbiór liczb, które zmienna może przyjąć. | |
| |
Nie zawsze jednak CLP dostarcza odpowiednich narzędzi, by zadanie mogło być szybko i wydajnie rozwiązane. Kiedy programista spotyka się ze złożonymi i specyficznymi problemami, a istniejące ograniczenia nie spełniają jego oczekiwań, czasem musi zdefiniować ograniczenia od nowa lub zmodyfikować już istniejące jak i określić reguły ich przetwarzania. Do tego służy mu język programowania CHR (z ang. Constraint Handling Rules). | |
| |
=====SWI-Prolog 5.6===== | |
| |
| |
| |
| |
| ===== 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==== | |
| |
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'', a jego działanie wygląda następująco: | |
===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. | |
| |
| |
| |
| |
==== ==== | |
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ł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) }, | ====CLP==== |
| |
[domain(X, List)]. | 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> | </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. |
| |
==== ==== | ==== ==== |
Tak samo wygląda działanie zmiennych z atrybutami w Yap Prolog i SICStus Prolog. | 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==== | |
| |
CLP jest wspierane przez SWI-Prolog począwszy od wersji 5.5. Programista ma do dyspozycji szereg modułów: ''clp/clp_distinct, clp/simplex, clp/clpfd , clpqr''. | |
| |
* ''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 | * ''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 |
| |
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. | 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==== | ====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'' | 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: |
| |
'':- use_module(library(chr)).'' | <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 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ń. | 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== | ==Przykład== |
| |
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. | 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. |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
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. | 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". |
| |
* 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===== | =====XSB 3.1===== |
| |
| |
| |
| |
| |
====Technika spamiętywania (tabling, memoization)==== | ====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: | 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: |
| |
==Przykład== | ==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. | 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. | <code prolog>:- table avoids/2. |
| |
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. | 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. |
| |
| |
| |
| |
| |
| |
| |
[6] [[http://www.cin.ufpe.br/~in1006/2005/Slides/CHRBasics.ppt | Jairson Vitorino and Marcos Aurélio, Constraint Handling Rules, 2005.]] | [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)]] |