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 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 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 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 learner.pl Początkowa baza wiedzy jest w pliku 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 Blocks_world

Wczytaj 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 Towers_of_hanoi

Ćwiczenie

Proszę pobrać program 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 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 Datalog.

Zobacz przykładowe środowisko 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: 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

pl/dydaktyka/krr/lab_sterowanie_wnioskowaniem.txt · ostatnio zmienione: 2017/07/17 08:08 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0