Różnice między wybraną wersją a wersją aktualną.
| Both sides previous revision Poprzednia wersja Nowa wersja | Poprzednia wersja | ||
|
pl:miw:miw08_prolog_adv [2008/09/30 01:43] miw |
pl:miw:miw08_prolog_adv [2019/06/27 15:50] (aktualna) |
||
|---|---|---|---|
| Linia 1: | Linia 1: | ||
| ====== Opis ====== | ====== Opis ====== | ||
| Sławomir Polański, <wawele@gmail.com> | Sławomir Polański, <wawele@gmail.com> | ||
| + | |||
| + | |||
| + | |||
| Linia 10: | Linia 13: | ||
| * 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: | ||
| Linia 19: | Linia 22: | ||
| * [[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 ====== | ||
| Linia 25: | Linia 28: | ||
| ====== Sprawozdanie ====== | ====== Sprawozdanie ====== | ||
| + | |||
| + | |||
| Linia 79: | Linia 84: | ||
| ponieważ wartości {1, 2} z domeny ''x'' nie spełniają ograniczenia ''x>y+1'' dla żadnej z | 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''. | wartości z domeny ''y''. Podobnie można rozpatrywać wartości {4, 5, 6} z domeny ''y''. | ||
| - | Jednak możemy wprowadzić takie ograniczenie jak ''x+y=6'', które nie usuwa żadnych wartości | + | Ograniczenia nie są zazwyczaj tak proste ja to przedstawiono, często łączą ze sobą |
| - | z domen. 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 | wiele zmiennych, a metody usuwania poszczególnych wartości, zwane algorytmami | ||
| filtracyjnymi są bardzo złożone. | filtracyjnymi są bardzo złożone. | ||
| Linia 88: | Linia 92: | ||
| 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). | 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. | + | 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). |
| Linia 113: | Linia 117: | ||
| - | ====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. | ||
| Linia 166: | Linia 156: | ||
| - | ==== ==== | ||
| - | 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), | + | ====CLP==== |
| - | X = Y. | + | 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== | |
| - | % Zmiennej z atrybutem o wartości Domain została przypisana wartość Y | + | 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> | |
| - | attr_unify_hook(Domain, Y) :- | + | tax(Income; 0.5*Income) <- greater(Income; 150000). |
| - | + | tax(Income; 0.25*(Income − 30000)) <- ¬greater(Income; 150000). | |
| - | ( 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> | </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 | ||
| Linia 544: | 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 573: | Linia 517: | ||
| ====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== | ||
| Linia 620: | 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 637: | Linia 691: | ||
| 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===== | ||
| + | |||
| + | |||
| Linia 659: | Linia 716: | ||
| ====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: | ||
| Linia 667: | 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 718: | 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 745: | Linia 806: | ||
| [7] [[http://www-users.mat.uni.torun.pl/%7Efly/materialy/pl/referaty/CLP/index.html | Programowanie logiczne z użyciem ograniczeń]] | [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)]] | ||
