|
|
pl:dydaktyka:krr:lab_sterowanie_wnioskowaniem [2013/03/06 09:30] gjn [Wymuszanie nawrotów] pitagoras |
pl:dydaktyka:krr:lab_sterowanie_wnioskowaniem [2017/07/17 10:08] |
====== KRR: Prolog - rekurencja i sterowanie wnioskowaniem ====== | |
| |
===== Rozbudowa programu ===== | |
| |
Rozbuduj program //fam2.pl// | |
| |
Proszę się zastanowić nad własnymi regułami opisującymi relacje w rodzinie. | |
Dodaj nowe fakty dotyczące mężczyzn, kobiet, rodziców. | |
| |
Proszę zdefiniować reguły opisujące: brata, siostrę, dziadka i babcię. Proszę dokładnie sprawdzić ich działanie. | |
Jaki pojawia się problem przy bracie/siostrze? Uwaga na operator: ''\='' | |
| |
| |
===== Rekurencja ===== | |
| |
Rekurencja jest jednym z podstawowych mechanizmów programowania w Prologu. Proszę się przyjrzeć regułom opisującym przodka: | |
| |
<code prolog> | |
przodek(X,Y) :- | |
rodzic(X,Y). | |
| |
przodek(X,Z) :- | |
rodzic(X,Y), | |
przodek(Y,Z). | |
</code> | |
| |
Te dwie klauzule, w tym przypadku reguły, opisują dokładnie jeden predykat: //przodek/2//. | |
| |
Jak zdefiniować potomka, krewnego? | |
| |
Typowym przykładem wykorzystania mechanizmu rekurencji jest obliczanie wartości funkcji silnia. | |
Poniżej znajduje się kod realizujący tą funkcjonalność. | |
| |
<code prolog> | |
factorial(0,1). | |
factorial(Number,Result) :- | |
Number > 0, | |
NewNumber is Number-1, | |
factorial(NewNumber,NewResult), | |
Result is Number*NewResult. | |
</code> | |
| |
| |
**Ćwiczenie** | |
| |
Wpisz, przetestuj i przemyśl działanie programu rekurencyjnie liczącego silnię. | |
| |
===== Wymuszanie nawrotów ===== | |
| |
Predykat //fail/0// pozwala na wymuszanie nawrotów w procesie poszukiwania rozwiązania, co pozwala w szczególności na znalezienie wszystkich rozwiązań problemu. | |
| |
Przypomnienie: Prolog używa strategii przeszukiwania wgłąb drzewa rozwiązań problemu i zatrzymuje się po napotkaniu 1. poprawnego rozwiązania. | |
| |
**Ćwiczenie** | |
| |
Pobrać i wczytać program {{pl:prolog:prolog_lab:fam2.pl}} | |
| |
Wyświetlić go przez listing. | |
| |
Sprawdzić działanie: | |
| |
?- kobieta(K),write(K),write(' to kobieta.'),nl. | |
| |
Jak wymusić odnajdywanie kolejnych kobiet. | |
| |
Sprawdzić działanie: | |
| |
?- kobieta(K),write(K),write(' to kobieta.'),nl,fail. | |
| |
Sprawdzić działanie: | |
| |
?- kobieta(K),fail. | |
| |
Dlaczego nic się nie pojawia? | |
| |
Pobrać i wczytać program {{pl:prolog:prolog_lab:capitals.pl}} | |
| |
Sprawdzić działanie: | |
| |
?- capital_of(A,B), write(B), write(' to stolica '), write(A), nl. | |
?- capital_of(A,B), write(B), write(' to stolica '), write(A), nl, fail. | |
| |
| |
Generowanie trójkątów pitagorejskich: | |
<code prolog> | |
%%% liczby-pitagoras.pl | |
| |
%%% Prosty program ilustrujący ideę generacji/wyszukiwania rozwiązań w Prologu | |
%%% i zastosowania do generowania całkowitoliczbowych trójkątów Pitagorejskich | |
| |
% Fakty: definicja dostępnych cyfr. | |
cyfra(0). | |
cyfra(1). | |
cyfra(2). | |
cyfra(3). | |
cyfra(4). | |
cyfra(5). | |
cyfra(6). | |
cyfra(7). | |
cyfra(8). | |
cyfra(9). | |
| |
% Przykładowa definicja liczby trzycyfrowej | |
liczba(X):- | |
cyfra(S), | |
cyfra(D), | |
cyfra(J), | |
X is 100*S+10*D+J. | |
% Generacja trójkąta i wypisywanie A*A + B*B = C*C | |
pitagoras :- | |
liczba(A), A > 0, A =< 20, | |
liczba(B), B > 0, B =< 20, | |
liczba(C), C > 0, C =< 25, | |
D is A*A + B*B - C*C, | |
D = 0, | |
write('A = '),write(A), write(' '), | |
write('B = '),write(B), write(' '), | |
write('C = '),write(C), write(' '),nl, | |
fail. | |
pitagoras :- | |
write('====='). | |
| |
| |
% Modyfikacje: | |
% 1. Zmiana zakresu. | |
% 2. Zmiana kolejności. | |
% 3. Zmiana sposobu wypisywania. | |
| |
% eof | |
</code> | |
| |
===== Interakcja z programem ===== | |
| |
==== Wypisywanie na wyjściu ==== | |
| |
Predykat //write/1// wypisuje term na wyjście; //nl/0// przechodzi do nowej linii. | |
| |
**Ćwiczenie** | |
| |
Przetestować działanie: | |
| |
write('Ala ma '),write('kota'),nl,write('w ciapki!'). | |
| |
| |
==== Programy interaktywne ==== | |
| |
Predykat read/1 pozwala na pobieranie danych od użytkownika. | |
| |
| |
**Ćwiczenie** | |
| |
Proszę oglądnąć zastosowanie //read/1// na przykładzie programu {{pl:prolog:prolog_lab:interac.pl}} | |
| |
Po załadowaniu proszę wpisać: | |
| |
?- go. | |
| |
==== Prosta obsługa plików ==== | |
| |
Prosty zapis do plików można zrealizować przez predykaty //tell/0// i //told/0// (przekierowanie stdout). | |
| |
Prosty odczyt z plików można zrealizować przez predykaty //see/0// i //seen/0// (przekierowanie stdin). | |
| |
Proszę oglądnąć zastosowanie //tell/told// oraz //assert/retract// na przykładzie programu {{pl:prolog:prolog_lab:learner.pl}} | |
Początkowa baza wiedzy jest w pliku {{pl:prolog:prolog_lab:learner_kb.pl}} | |
| |
Należy uruchomić program przez ''start.'' | |
| |
Jakie 3 przypadki odpowiedzi są brane pod uwagę? Co dzieje się przy wyjściu z programu i jak to wpływa na jego kolejne uruchamianie? | |
| |
Uwaga: operator ''\+'' oznacza //negację//. | |
| |
===== Wybrane problemy rozwiązane w Prologu ===== | |
| |
==== Świat klocków ==== | |
Problem [[wp>Blocks_world]] | |
| |
Wczytaj {{:pl:prolog:prolog_lab:blocks.pl|}} | |
| |
Narysuj na kartce zamodelowany świat. | |
Jakie pytania można zadać? | |
<code prolog> | |
above(b1,b2). | |
above(b3,b5). | |
left(b1,b7). | |
left(b3,b3). | |
</code> | |
| |
| |
==== Wieże Hanoi ==== | |
Problem [[http://pl.wikipedia.org/wiki/Wieże_Hanoi]]. | |
| |
Problem [[wp>Towers_of_hanoi]] | |
| |
**Ćwiczenie** | |
| |
Proszę pobrać program {{:pl:prolog:prolog_lab:hanoi.pl|hanoi.pl}}. | |
Przetestować i przemyśleć. | |
| |
Predykat //move/4// działa następująco:\\ | |
np. //move(3,left,right,center)// przenosi 3 krążki ze stosu //left// na stos //right// przy pomocy stosu //center//. | |
| |
Przykład: | |
<code prolog> | |
?- move(3,left,right,center). | |
Move top disk from left to right | |
Move top disk from left to center | |
Move top disk from right to center | |
Move top disk from left to right | |
Move top disk from center to left | |
Move top disk from center to right | |
Move top disk from left to right | |
</code> | |
| |
Analizując kod programu proszę zauważyć, że algorytm rozwiązania problemu opiera się na dekompozycji na podproblemy. | |
| |
===== Dynamiczna modyfikacja reguł ===== | |
| |
assert/retract pozwala również dodawać/usuwać reguły: | |
| |
<code prolog> | |
:-dynamic(a/1), dynamic(b/2). | |
| |
a(1). a(2). | |
| |
addrule:- assert((b(X,Y):-a(X),a(Y))). | |
| |
delrule:- retract((b(_,_):-_)). | |
| |
start:-addrule, b(X,Y), write(X), write(' '), write(Y),nl,fail. | |
start. | |
</code> | |
| |
W powyższym programie predykat ''addrule/0'' dodaje (''delrule/0'' usuwa) dynamicznie regułę: | |
<code> | |
b(X,Y):-a(X),a(Y). | |
</code> | |
| |
| |
===== Zadawanie celu ===== | |
| |
Konstrukcja: | |
| |
:- cos. | |
| |
pozwala na podanie celu w programie, np.: | |
| |
:- dynamic(capital_of/2). | |
:- go. | |
:- start. | |
| |
Prolog przystąpi do zrealizowania celu po załadowaniu kodu. | |
| |
Uruchomienie programu ze wskazanego pliku (''plik.pl'') z poziomu systemu operacyjnego można zrealizować za pomocą: | |
| |
swipl -s program.pl -g go -t halt | |
| |
===== Składnia ===== | |
| |
Atomy, Termy, Klauzule i Predykaty - arność. | |
| |
===== Prosty program diagnostyczny ===== | |
| |
Program realizuje prosty system diagnostyczny (w praktyce wnioskujący wstecz system ekspertowy). | |
Jest to kompletny program wyposażony w: | |
* bazę wiedzy o problemie | |
* mechanizm wnioskowania - wyszukiwanie rozwiązań | |
* dynamiczną modyfikację/rozbudowę bazy wiedzy | |
* obsługę plików (i/o) | |
* interfejs (prosty) użytkownika | |
| |
System: {{pl:prolog:prolog_lab:car.pl}} | |
| |
Plik pomocniczy: {{pl:prolog:prolog_lab:getyesno.pl}} | |
| |
===== Wbudowany system pomocy ===== | |
| |
Sprawdź działanie: | |
?- help. | |
?- help(write/1). | |
| |
| |
===== Śledzenie pracy programu ===== | |
| |
Interpretery Prologu pozwalają na śledzenie pracy programu. W tym celu należy ustawić tzw. trace point. | |
| |
Trace points: | |
* trace/0 - ustawia trace point na wszystkich predykatach, w wersji swi-prolog używanej na laboratorium, ''trace/0'' śledzi **następny zadany cel**, np. | |
<code prolog> | |
?- trace,kobieta(K),rodzic(K,_). | |
</code> | |
* trace/1 - ustawia trace point na wskazanym predykacie, | |
* trace/2 - modyfikuje dla wskazanego predykatu śledzone zdarzenia (call, redo, exit, fail), np.: | |
* trace(something/1,-all) - zdejmuje trace point ze wskazanego predykatu //something/1//, | |
* trace(something,+call) - ustawia trace point śledzący jedynie wywołania na wskazane predykaty //something// o dowolnej arności. | |
| |
Predykat //debugging/0// wypisuje ustawione trace points. | |
Predykat //debug/0// wchodzi do trybu debug. | |
Predykat //nodebug/0// wychodzi z trybu debug. | |
| |
**Ćwiczenie** | |
| |
Pobrać i wczytać program {{pl:prolog:prolog_lab:fam2.pl}} | |
| |
Sprawdzić działanie: | |
| |
<code prolog> | |
?- trace(matka). | |
[debug] ?- matka(kasia,robert). | |
[debug] ?- ojciec(tomek,robert). | |
[debug] ?- nodebug. | |
?- matka(kasia,robert). | |
?- debug. | |
[debug] ?- trace(matka,-all). | |
[debug] ?- matka(kasia,robert). | |
[debug] ?- trace(matka,+call). | |
[debug] ?- matka(kasia,robert). | |
[debug] ?- nodebug. | |
?- trace. | |
[debug] ?- matka(kasia,robert). | |
[debug] ?- nodebug. | |
</code> | |
| |
W SWI Prologu można też skorzystać z dodatkowego pakietu XPCE, w którym jest też wizualny debugger. | |
| |
Należy wyjść z bieżącej sesji SWI. Uruchomić interpreter z powłoki unixa przez przez polecenie ''xpce''. | |
Następnie uruchomić graficzny tracer przy użyciu predykatu guitracer/0. | |
| |
| |
===== Dla Zainteresowanych ===== | |
| |
==== Datalog ==== | |
Tym poziom znajomości Prologu, mniej więcej odpowiada językowi [[wp>Datalog]]. | |
| |
Zobacz przykładowe środowisko [[http://DES.sf.net|DES]]. | |
| |
==== Kolorowanie Mapy ==== | |
Problem: mamy mapę taką jak poniżej | |
| |
<code prolog> | |
| |
|Bialorus | |
|------------ | |
Polska | | |
---------------| | |
| | Ukraina | |
Czechy| Slowacja|----------- | |
----------------- | |
</code> | |
| |
Należy ja pokolorować 3 kolorami, tak aby żadne sąsiadujące państwa nie miały takiego samego koloru: | |
[[wp>Four_color_theorem]] | |
| |
| |
**Ćwiczenie** | |
| |
Definiujemy 3 kolory: | |
| |
<code prolog> | |
kolor(czerwony). | |
kolor(zielony). | |
kolor(niebieski). | |
</code> | |
| |
Należy zdefiniować predykat ''koloruj/5'', tak aby zadając pytanie: | |
| |
?- koloruj(Polska,Bialorus,Ukraina,Slowacja,Czechy). | |
| |
dostać wszystkie możliwości pokolorowania tej konkretnej mapy. | |
| |
Uwaga: predykat ''koloruj/5'' definiuje zależności geograficzne. | |
| |
Uwaga: w Prologu operator ''\='' to nieidentyczność, czy też niemożliwość uzgodnienia termów. | |
| |
| |
===== Źródła ===== | |
| |
* [[http://www.amzi.com/AdventureInProlog/a8recurs.php|AIP:8]] | |
* [[http://www.learnprolognow.org/lpnpage.php?pagetype=html&pageid=lpn-htmlch3|LPN:3]] | |
| |