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:

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.