LIK320 / Prolog



Lingwistyka komputerowa 320
Programowanie w Prologu - powtórzenie
Ćwiczenia 2. Tryb pracy mechanizmu wnioskowania, funktory, listy
Integralną częścią języka Prolog jest tzw. mechanizm wnioskowania. Działanie
mechanizmu wnioskowania omówimy na następującym przykładzie:/* dziadek(A,B) - A jest dziadkiem B */
/* ojciec(A,B) - A jest ojcem B */
/* dziecko(A,B) - A jest dzieckiem B */

dziadek(X,Y) :- ojciec(X,Z), dziecko(Y,Z). /* (k1) */
dziadek(karol,maurycy). /* (k2) */

ojciec(karol,elzbieta). /* (k3) */
ojciec(karol,august). /* (k4) */

dziecko(henryk,elzbieta). /* (k5) */
dziecko(teofil,august). /* (k6) */

Cel:?-dziadek(karol,W).

Poniżej podano schematyczne przedstawienie kilku pierwszych kroków mechanizmu
wnioskowania przy realizacji celu dziadek(karol,W).



(zn1)
dziadek(karol,Y)
(k1)
X=karol,Y=W

 
 ojciec(karol,Z)
 
 

 
 dziecko(Y,Z)
 
 
realizacja pierwszego podcelu



(zn1)
dziadek(karol,Y)
(k1)
X=karol,Y=W

(zn2)
ojciec(karol,elzbieta)
(k3)
Z=elzbieta

 
 dziecko(Y,elzbieta)
 
 
realizacja drugiego podcelu

odpowiedź pierwsza W=henryk, nawrót do
(zn3)


(zn1)
dziadek(karol,Y)
(k1)
X=karol,Y=W

(zn2)
ojciec(karol,elzbieta)
(k3)
Z=elzbieta

(zn3)
dziecko(henryk,elzbieta)
(k5)
Y=W=henryk

porażka, usunięcie (zn3) i przejście do (zn2)


(zn1)
dziadek(karol,Y)
(k1)
X=karol,Y=W

(zn2)
ojciec(karol,august)
(k4)
Z=elzbieta

 
 dziecko(Y,august)
 
 
Sterowanie mechanizmem wnioskowania
Działanie mechanizmu wnioskowania można modyfikować używając m.in. predykatów
wbudowanych cut i fail.
cut
Standardowy bezargumentowy predykat cut (predykat odcięcia),
alternatywnie oznaczany jako !, jest interpretowany logicznie jako
zawsze prawdziwy i służy do ograniczania nawrotów. Realizacja tego predykatu,
występującego jako jeden z podcelów w ciele klauzuli, uniemożliwia nawrót do
któregokolwiek z poprzedzających go podcelów przy próbie znajdowania rozwiązań
alternatywnych. Wszystkie zmienne, które zostały ukonkretnione podczas
realizacji poprzedzających odcięcie podcelów w ciele klauzuli zostają
"zamrożone" (zachowują nadane im wartości). Przykład:ojciec(jan, staś).
ojciec(jan, marek).
dziecko(kasia, staś).
dziecko(marysia, staś).
dziecko(joasia, marek).

/* I możliwość */
dziadek(X, Z):- ojciec(X, Y), dziecko(Z, Y).
/* ?- dziadek (jan, X). znajduje 3 rozwiązania */

/* II możliwość */
/* dziadek(X, Z):- ojciec(X, Y), !, dziecko(Z, Y). */
/* ?- dziadek (jan, X). znajduje 2 rozwiązania */

/* III możliwość */
/* dziadek(X, Z):- ojciec(X, Y), dziecko(Z, Y), !. */
/* ?- dziadek (jan, X). znajduje 1 rozwiązanie */

fail
Drugim predykatem modyfikującym standardowy proces poszukiwania rozwiązań
jest bezargumentowy predykat fail. Wykonanie tego predykatu zawsze
zawodzi. Najczęściej jest on używany w celu wymuszenia nawrotów. Użyty w
kombinacji z predykatem cut (w kolejności: !, fail) zapobiega
użyciu innej klauzuli przy próbie znalezienia rozwiązań alternatywnych, co
oznacza niepowodzenie wykonania całej procedury.
Przykład:pyt :- matka(X, maria), write(X), fail.

pyt.

Predykat fail zawsze zawodzi - będąc jednym z podcelów powoduje więc
porażkę celu głównego pyt. Oznacza to, że zmienna X
ukonkretniona w czasie realizacji celu głównego pozostaje ostatecznie
niezwiązana. Wbudowany predykat write umożliwia wypisywanie
"chwilowych" wartości zmiennej X. Predykat fail wymusza
nawroty, umożliwiając sukcesywne ukonkretnianie zmiennej X
wartościami z bazy danych (nastąpi wypisanie wszystkich matek mających córkę o
imieniu Maria). Druga klauzula pyt gwarantuje ostateczny sukces celu
głównego pyt (dzięki czemu interpreter odpowiada w końcu Yes
zamiast No).
Funktory
Obiekty mogą być reprezentowane przez stałe lub termy
złożone (struktury). Term złożony ma postać
f(arg1,...,argn), gdzie f jest funktorem o arności n.
Mylące może być to, że termy złożone zapisywane są podobnie jak relacje.
Należy jednak pamiętać, że obiekty reprezentowane przez funktory mogą być
argumentami predykatów, natomiast niedopuszczalne jest, aby argumentem predykatu
był inny predykat (z wyjątkiem pewnych predykatów specjalnych np.
call):



posiada(osoba(jan, kowalski), samochód(opel, astra, 1997))
dobrze

ojciec(jan, janek).matka(halina, ojciec(jan, janek)).
źle!
Jeśli zapiszemy w programie fakt samochód(opel, astra, 1997), to
samochód jest interpretowany jako predykat i nie może już być
argumentem innego predykatu.
Listy
Lista jest podstawową strukturą rekurencyjną w języku Prolog. Jest ona
ciągiem złożonym z dowolnej liczby elementów, którymi mogą być termy tj. stałe,
zmienne i struktury. Jako że lista jest strukturą (termem złożonym), do jej
konstrukcji użyto dwuargumentowego funktora . (tzw. operator
cons). Poniżej podano przykłady list zapisanych przy pomocy tego
operatora.
(Ogólnie dla listy zawierającej n elementów należy użyć operatora
. n razy. Koniec listy jest zaznaczany przy użyciu specjalnego
atomu [], który oznacza też listę pustą.)
Aby uniknąć uciążliwego zapisu za pomocą funktora ., przyjęto
zamiast niego używać nawiasów kwadratowych, zaś elementy listy odzielać
przecinkami. Każdą listę można podzielić na dwie części: głowę
(head) i ogon (tail). W przypadku użycia funktora
., głową jest zawsze pierwszy argument, zaś ogonem - drugi. W zapisie
przy użyciu nawiasów kwadratowych głową jest pierwszy element listy, ogonem
natomiast pozostała część listy (bez głowy). Uwaga: Lista pusta (tj.
[]) nie posiada ani głowy, ani ogona. Podział listy na głowę i ogon
jest w zasadzie jedyną operacją, za pomocą której można rekurencyjnie
przetwarzać listy. Istnieje symbol | reprezentujący tę operację, więc
zapis [X|Y] oznacza listę, której głową jest X, zaś ogonem -
Y, np. zapytanie [X|Y]=[1,2,3] da następujące wiązania
zmiennych: X=1,Y=[2,3].
Przykład podziału listy na głowę i ogon:



lista
głowa
ogon

[a,b,c,d]
a
[b,c,d]

[a,b,[c,d]]
a
[b,[c,d]]

[]
brak
brak

[elemencik]
elemencik
[]

[[1,2],[3,4],5]
[1,2]
[[3,4],5]
Zmienne anonimowe
Jeżeli w klauzuli zmienna jest użyta tylko raz, to w zasadzie oznacza to, że
jej użycie jest bezsensowne. SWI-Prolog zgłasza w takim wypadku ostrzeżenie
podczas kompilacji. Zmienną występującą tylko raz lepiej jest zapisywać jako
specjalną zmienną anonimową o postaci _ (znak podkreślenia).
Przykłady:/* Fragment definicji procedury multiply(X,Y,Z) (X pomnożone przez Y
daje Z) */
multiply(0, _, 0). /* 0 pomnożone przez dowolną liczbę daje 0 */

/* Fragment definicji procedury member(E, L) (E jest elementem listy L) */
member(W, [X | _]) :- W = X.

Zadania z ćwiczeń 2
Zadanie 1 Zmodyfikować przy pomocy odcięcia poniższą procedurę
objętość (nie usuwając żadnego faktu z bazy), aby przy realizacji celu
objętość(Z) uzyskać (a) jedną, (b) dwie, (c) cztery, (d) osiem
odpowiedzi.dlugość(10).
dlugość(20).
szerokość(1).
szerokość(2).
wysokość(5).
wysokość(6).
objetość(X):-
dlugość(A),
szerokość(B),
wysokość(C),
X is A*B*C.
objetość(30).

Zadanie 2 Opisać powiązania między członkami rodziny (np. własnej)
stosując funktor osoba zamiast stałych. Termy z takim funktorem mogą
mieć następującą postać: osoba(imię, nazwisko, wiek,
miejsce_zamieszkania). Przykłady faktu: ojciec(osoba(jan, kowalski, 50,
poznań), osoba(janek, kowalski, 20, warszawa)). Wykonać kilka celów typu:
odszukać wujka osoby o imieniu jan zamieszkałego w Poznaniu. Utworzyć procedurę,
który wypisuje wszystkie osoby spełniające pewien warunek.
Zadanie A Utworzyć krótką bazę danych wypożyczalni filmów składającą
się z filmów (o pewnych parametrach, m.in. ograniczenia wiekowego) i osób o
pewnych danych (między innymi: wiek). Napisać predykat dwuargumentowy
może_pożyczyć, który sprawdza, czy osoba reprezentowana przez pierwszy
argumente może pożyczyć film będący drugim argumentem.
Zadanie 3 Sprawdzić wyniki, jakie daje SWI-Prolog dla następujących
zapytań (nie trzeba wprowadzać do bazy danych żadnych faktów):?- [ala, ma, kota] = [kota, ma, ala].
?- [1,2,3] = [X,Y].
?- [1,2,3,osiem] = [1|Ogon].
?- [1|[2|[3|[osiem]]]] = [1|Ogon].
?- [[0,1,2],[3,4],[5]] = [Glowa|Ogon].
?- [ala,ma,kota,a,ola,ma,psa] = [ala,ma,kota,a|X].
?- [alfa(1,2), alfa(3,4), alfa(5,6)] = [alfa(X,2)|Ogon].

Zadanie 4 Zdefiniować predykat pisz_listę(L), który wypisuje
na ekranie wszystkie elementy listy L. Skorzystać z predykatu
jednoargumentowego write. Wskazówka: napisać dwie reguły dla predykatu
pisz_listę(X) - (1) wypisanie listy pustej, (2) wypisanie listy,
składającej się z głowy i ogona (z wywołaniem rekurencyjnym).
Zadanie 5 Zdefiniować predykat należy(E, L) - element
E należy do listy L. Wskazówka: sformułować dwie reguły -
(1) E jest głową listy, (2) E należy do ogona listy.
Zadanie 6 (dodatkowe) Zdefiniować predykat dopasuj(L, W, Z),
który dla listy L zwraca jej podlistę Z pasującą do
zadanego wzorca W. Wzorzec jest listą, której elementami mogą być
następujące stałe:

n - pasuje do liczby,
a - pasuje do atomu,
l - pasuje do elementu będącego (dowolną) listą,
. - pasuje do dowolnego elementu,
* - pasuje do podlisty o dowolnej długości (także pustej).

Np. wzorzec [n,n] oznacza podlistę złożoną z dwóch liczb, zaś
wzorzec [a,*,n] - podlistę zaczynającą się atomem i kończącą się
liczbą.
Wskazówka: użyć predykatów wbudowanych atom, integer.
Przykład oczekiwanego działania predykatu:?- dopasuj([x,a,15,101,ala,ma,kota,[1,2],a,b,c],[n,n,*,l,.],Z).

Z = [15, 101, ala, ma, kota, [1,2], a]

Yes

Zadanie B (dodatkowe) Zdefiniować predykat pomiędzy(A, B, X),
który daje wszystkie liczby naturalne nie mniejsze od A i nie większe
od B. Przykład oczekiwanego działania predykatu:?- pomiędzy(3, 5, X).

X = 3; [naciśnięto średnik]

X = 4;

X = 5;

No

Nie używać operatora is. Wskazówka: użyć predykatu wbudowanego
succ.
Zadanie C (dodatkowe) Napisać predykat, w którym trzeci argument
będzie połączeniem list-dwóch pierwszych argumentów. Wskazówka: sformułować dwie
reguły - (1) pierwsza lista jest pusta, (2) pierwsza lista składa się z głowy i
ogona.
Zadanie 7 Znaleźć ostatni element listy (zdefiniować predykat
ostatni(E, L)).
Zadanie D (dodatkowe) Sprawdzić, czy pierwsza lista jest początkiem
drugiej listy (zdefiniować predykat początek(Lista1,Lista2)).
Zadanie E (dodatkowe) Zdefiniować predykat podziel (ListaWej,
Liczba, ListaMniejsze, ListaWiększe) dzielący listę ListaWej na
dwie listy: ListaMniejsze jest listą tych liczb z
ListyWej, które są mniejsze od Liczby, a
ListaWiększe jest listą tych liczb z ListyWej, które są
większe od Liczby.
Zadanie F (dodatkowe) Dla danej liczby uzyskać listę odwróconą.
Wskazówka: można np. utworzyć predykat trójargumentowy odwróć_liste(Lista,
ListaOdwrocona, ListaPomoc).
Zadanie G (dodatkowe) Zdefiniować parę predykatów, które wyznaczają
składniki listy na odpowiednio parzystych i nieparzystych pozycjach.
Zadanie H (dodatkowe) Zdefiniować predykat (trójargumentowy), który
usuwa dany element z listy.
Zadanie I (dodatkowe) Zdefiniować predykat (czteroargumentowy), który
w danej liście zamienia wszystkie wystąpienia danego elementu na inny dany
element.
Zadanie J (dodatkowe) Zdefiniować predykat (dwuargumentowy), który
sprawdza czy lista podana jako drugi argument jest permutacją listy podanej jako
pierwszy argument. Na podstawie tego predykatu zdefiniować predykat, który
wypisuje wszystkie permutacje danej listy.
Zadanie K (dodatkowe) Rozwiązać (przy użyciu Prologu) następujący
kryptarytm:





E
A
R
T
H





A
I
R




F
I
R
E

+

W
A
T
E
R






N
A
T
U
R
E
Różnym literom odpowiadają różne cyfry. Żadna liczba nie może zaczynać się
zerem.
Zadanie L (dodatkowe) Dla danej listy znaleźć listę bez powtórzeń
elementów.
Zadanie M (dodatkowe) Listę bez powtórzeń będziemy interpretować jako
zbiór. Skonstruować predykaty sprawdzające inkluzję, równość i różnicę
zbiorów.
Zadanie N (dodatkowe) Dla danego zbioru wypisać jego zbiór potęgowy
(wszystkie podzbiory).
Zadanie P (dodatkowe) Zdefiniować predykat sortuj(L, P),
który dla listy liczb L daje posortowaną niemalejąco listę P.
Zadanie Q (dodatkowe, zadanie jest pracochłonne i wymaga dobrego
zaznajomienia się z predykatami standardowymi Prologu) Dany ciąg wejściowy
znaków zamienić na listę słów.