Różnice między wybraną wersją a wersją aktualną.
|
pl:dydaktyka:krr:lab_sterowanie_wnioskowaniem [2013/03/06 09:30] gjn [Wymuszanie nawrotów] pitagoras |
pl:dydaktyka:krr:lab_sterowanie_wnioskowaniem [2019/06/27 15:50] |
||
|---|---|---|---|
| Linia 1: | Linia 1: | ||
| - | ====== 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]] | ||
