Both sides previous revision
Poprzednia wersja
Nowa wersja
|
Poprzednia wersja
|
pl:miw:miw08_prolog_adv [2008/09/30 04:14] 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. | |
| |
| |
| |
| |
| ====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. |
| |
==== ==== | ==== ==== |
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 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==== |
| |
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: |
| |
<code prolog>:- use_module(library(chr)).</code> | <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". |
| |
| |
| |
=====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. |
| |
| |
| |
| |
[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)]] |