Program prezentuje realizację prostej bazy danych.

Baza jest opisywana przy pomocy predykatu rodzina/3. Osoby w rodzinie są opisywane przy pomocy termu osoba/4.

Rekord:

rodzina(
	osoba(jan,  kowalski, data(5,kwiecien,1946), pracuje(tpsa,3000)),
	osoba(anna, kowalski, data(8,luty,1949),     pracuje(szkola,1500)), 
	[
	 osoba(maria, kowalski, data(20,maj,1973), pracuje(argo_turist,4000)),
	 osoba(pawel, kowalski, data(15,listopad,1979), zasilek)],
	 ).

Do bazy dostarczony jest interfejs, pozwalający na wyszukiwanie osób o pewnych własnościach. Przykładowe własności - elementy interfejsu:

zona(X) :-
	rodzina(_,X,_).
 
dziecko(X) :-
	rodzina(_,_,Dzieci),
	nalezy(X,Dzieci).

Pełny program repr-fam.pl

Ćwiczenie

Pobrać program repr-fam.pl

Przeglądnąć całość.

Zadać pytania:

• jakie są osoby w bazie?
• jakie są dzieci w bazie?
• pokazać pensje wszystkich osób,
• jakie dzieci urodziły się w 1979r.?
• znaleźć wszystkie żony, które pracują,
• znaleźć osoby urodzone przed 1950 r, których pensja jest mniejsza niż 3000,
• itd.

Korzystając z wiedzy zdobytej na poprzednim laboratorium, proszę policzyć zarobki wszystkich osób:

?- bagof(X,istnieje(X),L),zarobki(L,Z).

Dopisać kolejne 2 rodziny.

Powtórzyć pytania, kreatywnie…

Program flight_planner-1.pl pozwala na znalezienie trasy przelotu.

Uwaga: w kodzie powyżej znajduje się ciekawe użycie operatora / /2. Proszę zwrócić uwagę na poniższy kod. Prolog nie wylicza wyniku działania operatora (nie ma nigdzie is) ale uzgadnia jego argumenty, gdyż operator po prawej i po lewej stronie = jest taki sam.

?- a/b = X/Y.
 
X = a
Y = b
 
?- a/b = Z.
 
Z = a/b

Ćwiczenie

Pobrać program flight_planner-1.pl

Przetestować, np.:

?- flight(ljubljana,london,Dzien,_,Wylot:_,_),Wylot >=18.
 
Dzien = mo
Wylot = 20 ;
 
Dzien = we
Wylot = 20 ;
 
Dzien = th
Wylot = 20 ;
 
Dzien = sa
Wylot = 20 ;

Czyli w które dni tygodnia mamy bezpośredni lot z Ljubljany do Londynu, po 18.

Albo: jak można dostać się z Ljubljany do Edynburga w czwartek?

?- route(ljubljana,edinburgh,th,R).
 
R = [ljubljana/zurich/jp322/11:30, zurich/london/sr806/16:10, london/edinburgh/ba4822/18:40]

Rozbudować - dodać własne trasy.

Uwaga: wyrażenie

:-  op( 50, xfy, :).

definiuje nowy operator (omówione na kolejnym laboratorium). W uproszczeniu: chcemy móc pisać g:m, zamiast :(g,m).

Predykaty display, write_canonical wypisują Prologową reprezentację termów.

Np.

?- A=1, display(A).
1
 
?- A=[1], display(A).
.(1, [])
 
?- A=[1,a], display(A).
.(1, .(a, []))
 
?- A=[1,a,[ala,ma,[kota]]], display(A).
.(1, .(a, .(.(ala, .(ma, .(.(kota, []), []))), [])))

W przypadku długich list może przydać się print/1.

?- X=[1,2,3,45,6,7,8,9,32,4,6,ff,7,d],print(X).
[1, 2, 3, 45, 6, 7, 8, 9, 32, 4, 6, ff, 7, d]
 
X = [1, 2, 3, 45, 6, 7, 8, 9, 32|...]

Operator cut, pisany przy pomocy ! pozwala na zablokowanie procesu nawrotu w wybranym miejscu. Te zmienne logiczne, które zostały zunifikowane przed napotkaniem !, nie mogą ulec zmianie. W efekcie można uniknąć wyszukiwania niechcianych, zbędnych, a czasem wręcz niepoprawnych rozwiązań.

Przykład 1:
Baza wiedzy:

c(1).
c(2).
 
a(X) :- c(X), !.

Proszę zadać cel:

?- a(X), write(X), fail.

X zostaje zunifikowany z 1 - c(1). Cut uniemożliwia dalsze nawroty.

Przykład 2:
Baza wiedzy:

c(1).
c(2).
d(2).
 
a(X) :- c(X), !, d(X).

Proszę zadać cel:

?- a(1).
?- a(2).
?- a(X).

Dla celu a(X) X nie zostanie zunifikowany! (odp. interpretera: No.) Reguła jest prawdziwa dla X=2, ale Prolog nie znajdzie takiego rozwiązania, bo uniemożliwiony został nawrót. d(1) przy takiej bazie wiedzy nie jest prawdziwe.

Przykład 3:
Baza wiedzy:

c(1).
c(2).
c(3).
d(1).
d(2).
d(3).
 
a(X,Y) :- c(X), !, d(Y).

Proszę zadać cel:

?- a(X,Y), write('X = '), write(X), write(', Y = '), writeln(Y), fail.

Proszę zauważyć, że dla zmiennej logicznej Y, której unifikacja przebiega po wykonaniu odcięcia, nawroty są możliwe.

Przykład 4:
Baza wiedzy:

b(1).
b(2).
c(2).
c(3).
 
a(X) :- b(X), !, c(X).
a(X) :- c(X).

Proszę zadać cel:

?- a(X).
?- a(3).

Po napotkaniu cut odcinane są także pozostałe reguły predykatu. Dlaczego wobec tego a(3) jednak zwraca prawdę?

Przykłady inspirowane Prolog Cuts and Negation

Ćwiczenie

Proszę dopisać do bazy wiedzy znany już predykat należy/2:

nalezy1(X,[X|_]) :- write(X).
nalezy1(X,[_|O]) :-
	nalezy1(X,O).

Sprawdzić działanie dla list:

?- nalezy1(a,[a,b,c]),fail.

?- nalezy1(a,[a,b,a,c]),fail.

Zmodyfikować:

nalezy2(X,[X|_]) :- !, write(X).
nalezy2(X,[_|O]) :-
	nalezy2(X,O).

Przetestować:

?- nalezy2(a,[a,b,c]),fail.

?- nalezy2(a,[a,b,a,c]),fail.

A nastęnie sprawdzić działanie predykatu once/1.

?- once((nalezy1(a,[a,b,a,c]))),fail.

Wpisać predykat:

max1(X,Y,X) :- X >= Y.
max1(X,Y,Y) :- X < Y.

a następnie prześledzić jego działanie:

?- spy(max1).
% Spy point on max1/3
 
[debug]  ?- trace.
 
[trace]  ?- max1(2,3,X).

Następnie dopisać:

max2(X,Y,X) :- X >= Y, !.
max2(_,Y,Y).

i sprawdzić:

?- spy(max2).
% Spy point on max2/3
 
[debug]  ?- trace.
 
[trace]  ?- max2(2,3,X).

Poza predykatem fail/0 mamy do dyspozycji predykat true/0. Przy ich użyciu można skonstruować odpowiednik operatora \+ (negacja) - predykat not/0, który z logicznego punktu widzenia mógłby wyglądać tak:

not(P) :- P,!,fail;true.

albo w nieco mniej zwartej, ale bardziej czytelnej postaci:

not(P) :- P,!,fail.
not(_).

Ćwiczenie

?- true.
 
?- fail.
 
?- not(true).
 
?- not(fail).
 
?- \+ true.
 
?- \+ fail.

Proszę przeanalizować poniższe problemy, w miarę czasu i możliwości.

Zastanówmy się nad próbą implementacji prostej gry typu Minecraft. Kluczowym elementem gry jest silnik wokselowy, który odpowiada za renderowania ogromnego świata przy użyciu prostych klocków zwanych wokselami. Zaczniemy od rysowania przykładowego woksela. Proszę uruchomić program cuboid.pl (wymagane XPCE) i przeanalizować jego działanie.

?- cuboid(2,2,2).

Następnie proszę zapoznać się z kodem odpowiadającym za animację animation.pl:

?- sm.

Zadania:

1. Przerobić predykat cuboid tak, żeby można było sprecyzować jego pozycję w przestrzeni
2. Napisać predykat cuboids, który przyjmuje listę współrzędnych i rysuje w nich sześciany o zadanej długości boku
3. Przy pomocy predykatu cuboids należy zamodelować złożony obiekt ze świata Minecraft
4. Bazując na kodzie z animation.pl należy wprawić krowę w ruch sinusoidalny, imitujący kota z filmu
5. [Dla odważnych] dodać do animacji dźwięk podobny do tego z filmu

Pytania:

1. Czy rozsądne jest rysowanie wszystkich klocków? Jak wykryć, które klocki są widoczne z perspektywy gracza? Pomocny może okazać się link
2. Czy możliwe jest zrobienie w podobny sposób imitacji poniższego filmu?

Rozważmy problem kolorowania mapy.

W jaki sposób policzyć ile jest rozwiązań problemu?

Napisz odpowiednie zapytanie albo predykat. Podpowiedź: utwórz listę rozwiązań, policz elementy listy.

Powyższy problem można przedstawić w sposób ogólny definiując predykaty: panstwo/1, kolor/1, sasiad/2 określające odpowiednio: nazwy państw, kolory, oraz państwa sąsiadujące ze sobą.

Ćwiczenie

Zaimplementuj powyższą bazę wiedzy korzystając z tematu Kolorowanie Mapy. Napisz klauzule predykatu koloruj/1, który znajduje odpowiednie pokolorowanie w formie listy: [ [panstwo1,kolor1], [panstwo2,kolor2], … ].

Podpowiedź:

1. wygeneruj listę państw,
2. wygeneruj: [panstwo1,kolor1] dla każdego państwa, rekurencyjnie przegladajac listę państw, w rezultacie otrzymując kandydata na rozwiązanie: [ [panstwo1,kolor1], [panstwo2,kolor2], … ]
3. sprawdź czy w wygenerowanym kandydacie na rozwiązanie sąsiadujące państwa nie mają tego samego koloru; uwaga: przydatne będzie użycie forall/2.

Jedna z możliwych postaci zagadki Einstein'a (patrz http://en.wikipedia.org/wiki/Einstein_puzzle, http://pl.wikipedia.org/wiki/Zagadka_Einsteina).

5 ludzi różnych narodowości zamieszkuje 5 domów w 5 różnych kolorach. Wszyscy palą papierosy 5 różnych marek i piją 5 różnych napojów. Hodują zwierzęta 5 różnych gatunków. Który z nich hoduje rybki?

1. Norweg zamieszkuje pierwszy dom.
2. Anglik mieszka w czerwonym domu.
3. Zielony dom znajduje się bezpośrednio po lewej stronie domu białego.
4. Duńczyk pije herbatkę.
5. Palacz Rothmansów mieszka obok hodowcy kotów.
6. Mieszkaniec żółtego domu pali Dunhille.
7. Niemiec pali Marlboro.
8. Mieszkaniec środkowego domu pija mleko.
9. Palacz Rothmansów ma sąsiada, który pija wodę.
10. Palacz Pall Malli hoduje ptaki.
11. Szwed hoduje psy.
12. Norweg mieszka obok niebieskiego domu.
13. Hodowca koni mieszka obok żółtego domu.
14. Palacz Philip Morris pija piwo.
15. W zielonym domu pija się kawę.

Ćwiczenie

Proszę pobrać kod einstein2.pl i zastanowić się na jego działaniem.

Uzyskanie poprawnego rozwiązania:

1 ?- rozwiazanie(Hodowca_rybek).
Hodowca_rybek = niemiec ;
fail.

W przytoczonej wyżej wersji zagadki pytamy o hodowcę rybek. Proszę wykonać odpowiednią modyfikację, aby dowiedzieć się, jakie papierosy palą mieszkańcy poszczególnych narodowości.

Uzyskanie poprawnego rozwiązania:

1 ?- rozwiazanie(S).
S = [norweg, dunhill] ;
S = [dunczyk, rothmans] ;
S = [anglik, pall_mall] ;
S = [niemiec, marlboro] ;
S = [szwed, phillip_morris] ;
fail.

Proszę wrócić do oryginalnej wersji i sprawdzić, jak usunięcie któregoś z ograniczeń (ze wskazówek zagadki) wpływa na rozwiązanie. Proszę usunąć np. ograniczenie nr 13.

Pojawia się alternatywne rozwiązanie.

1 ?- rozwiazanie(Hodowca_rybek).
Hodowca_rybek = dunczyk ;
Hodowca_rybek = niemiec ;
fail.

Pliki poniżej zawierają niektóre klasyczne algorytmy sortowania w Prologu. Patrz również: http://en.wikipedia.org/wiki/Sorting_algorithm oraz po polsku: http://pl.wikipedia.org/wiki/Sortowanie

Ćwiczenie

Pobrać kod algorytmów i prześledzić ich działanie:

• bubblesort.pl
• insertsort.pl
• mergesort.pl
• quicksort.pl

Przypomnienie z podstaw informatyki: jaką złożoność obliczeniową mają te algorytmy?

Porównać ich wydajność, sortując losową listę liczb (np. z zakresu od 0 do 100) o zadanej długości (np. 30), wygenerowaną przy pomocy mkrandom.pl

?- mkrandom(100,30,X), time(bubblesort(X,B)), time(quicksort(X,Q)).
% 19,749 inferences, 0.00 CPU in 0.00 seconds (0% CPU, Infinite Lips)
% 701 inferences, 0.00 CPU in 0.00 seconds (0% CPU, Infinite Lips)