====== 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:
przodek(X,Y) :-
rodzic(X,Y).
przodek(X,Z) :-
rodzic(X,Y),
przodek(Y,Z).
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ść.
factorial(0,1).
factorial(Number,Result) :-
Number > 0,
NewNumber is Number-1,
factorial(NewNumber,NewResult),
Result is Number*NewResult.
**Ć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:
%%% 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
===== 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ć?
above(b1,b2).
above(b3,b5).
left(b1,b7).
left(b3,b3).
==== 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:
?- 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
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:
:-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.
W powyższym programie predykat ''addrule/0'' dodaje (''delrule/0'' usuwa) dynamicznie regułę:
b(X,Y):-a(X),a(Y).
===== 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.
?- trace,kobieta(K),rodzic(K,_).
* 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:
?- 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.
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
|Bialorus
|------------
Polska |
---------------|
| | Ukraina
Czechy| Slowacja|-----------
-----------------
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:
kolor(czerwony).
kolor(zielony).
kolor(niebieski).
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]]