Różnice

Różnice między wybraną wersją a wersją aktualną.

Odnośnik do tego porównania

Both sides previous revision Poprzednia wersja
Nowa wersja
Poprzednia wersja
pl:miw:miw08_prolog_adv [2008/09/30 05:54]
miw
pl:miw:miw08_prolog_adv [2019/06/27 15:50] (aktualna)
Linia 122: Linia 122:
  
  
-====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. 
  
  
Linia 261: Linia 166:
 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(Income; 0.25*(Income − 30000)) <- ~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: ​ 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: ​
Linia 270: Linia 175:
 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.
    
Linia 577: Linia 483:
  
 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. ​
 +
 +
  
  
Linia 609: Linia 517:
 ====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>​
Linia 656: Linia 564:
  
 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.
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
 +
  
  
Linia 683: Linia 698:
  
 =====XSB 3.1===== =====XSB 3.1=====
 +
  
  
Linia 710: Linia 726:
  
 ==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.
Linia 761: Linia 777:
  
 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.
 +
  
  
Linia 791: Linia 808:
  
 [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)]]
pl/miw/miw08_prolog_adv.1222746896.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