|
|
pl:dydaktyka:krr:lab_sterowanie_wnioskowaniem [2017/07/17 10:08] |
pl:dydaktyka:krr:lab_sterowanie_wnioskowaniem [2019/06/27 15:50] (aktualna) |
| ====== 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ść. |
| |
| |
| ===== 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]] |
| |