Both sides previous revision
Poprzednia wersja
Nowa wersja
|
Poprzednia wersja
|
pl:miw:miw08_prolog_adv [2008/09/30 05:55] miw |
pl:miw:miw08_prolog_adv [2019/06/27 15:50] (aktualna) |
| |
| |
====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. | |
| |
| |
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. | 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== | ==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: | 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> | <code prolog> |
tax(Income; 0.5*Income) <- greater(Income; 150000). | tax(Income; 0.5*Income) <- greater(Income; 150000). |
tax(130000,25000). | tax(130000,25000). |
</code> | </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. | 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 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. |
| |
| |
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==== |
| |
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'' | 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> | <code prolog>:- use_module(library(chr)).</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. | 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. |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
=====XSB 3.1===== | =====XSB 3.1===== |
| |
| |
| |
| |
==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. |
| |
| |
| |
| |
[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]] | [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)]] |