Lingwistyka komputerowa 320

Programowanie w Prologu - powtórzenie

Ćwiczenia 1. Fakty, reguły, cele, operator równości, operatory arytmetyczne

Powtórzenie podstawowych pojęć

Prolog jest językiem deklaratywnym. Jego deklaratywność polega na tym, że programista deklaruje (wymienia) jedynie obiekty konieczne do rozwiązania problemu oraz związki, jakie pomiędzy tymi obiektami zachodzą, w postaci tzw. faktów oraz reguł. Zadanie do rozwiązania przedstawiane jest w postaci celu.

fakty

symbol_predykatu(obiekt1, obiekt2,obiekt3,... obiektn).

reguły

Reguły to warunkowe stwierdzenia o istnieniu pewnych zależności między obiektami. Znaczenie reguł można przedstawić schematycznie w następujący sposób:

nazwa_powiązania(obiekt1, obiekt2, obiekt3,... obiektn) if nazwa_powiązania1(obiekt₁1, obiekt₁2, obiekt₁3,...obiekt₁m₁) and nazwa_powiązania2(obiekt₂1, obiekt₂2, obiekt₂3, ... obiekt₂m₂) and ... nazwa_powiązaniak(obiekt_k1, obiekt_k2,obiekt_k3,... obiekt_km_k).

Warunkowy charakter reguł polega na tym, że predykat występujący po lewej stronie słowa if jest prawdziwy jedynie wówczas, gdy prawdziwe są wszystkie warunki zapisane po prawej stronie. Słowa kluczowe if oraz and zastępujemy symbolami odpowiednio :- oraz ,. Przykład reguły: lubi(magda,X):- mezczyzna(X), przystojny(X)., predykat lubi jest tutaj głową reguły (głowa składa się tylko z jednego predykatu), zaś dwa warunki mezczyzna(X) i przystojny(X) tworzą ciało reguły. Uwaga: zakres zmiennej jest lokalny - dotyczy tylko jednej reguły, np.

ma_powodzenie(X):- lubi(magda, X), lubi(dorota,X).

dotyczy tego samego X, ale reguły

ma_powodzenie(X) :- lubi(magda, X).
ma_powodzenie(X) :- lubi(dorota, X).

dotyczyć mogą różnych X-ów.

Fakty i reguły stanowią tzw. klauzule. W przypadku faktów mamy do czynienia z klauzulami składającymi się tylko z głowy. Fakty i reguły występujące w programie tworzą tzw. bazę danych programu. Zbiór klauzul o takiej samej głowie i identycznej liczbie argumenty (arności) tworzy tzw. procedurę.

cel

Mając skonstruowaną bazę danych programu, można ją wykorzystać poprzez zadawanie pytań (celów). Celem jest:

• pytanie o prawdziwość podanych faktów,
• polecenie znalezienia nazw obiektów będących w relacji z innymi obiektami.

Cel może być albo pojedynczym predykatem, albo koniunkcją predykatów (tzw. podcelów). Przykłady celów:

?- lubi(marta,piotr).	czy Marta lubi Piotra?
?- lubi(piotr,marta).	czy Piotr lubi Martę?
?- lubi(marta,X).	kogo lubi Marta?

Transfer programów do pamięci

Jako interpretera Prologu używać będziemy programu SWI-Prolog działającego w Linuksie. Wszelkie informacje o SWI-Prologu można znaleźć na stronie http://www.swi-prolog.org/. Z podanej strony można także ściągnąć najnowsze wersje binarne dla różnych systemów operacyjnych.

Na komputerach uczelnianych SWI-Prolog jest już zainstalowany - w systemie Linux wystarczy wydać polecenie pl, by uruchomić interpreter.

SWI-Prolog nie udostępnia edytora programów. Programy prologowe można zapisywać używając dowolnego edytora (np. pico, vim, emacs). Najwygodniej mieć równocześnie otwarte dwa okna - jedno z interpreterem, drugie z edytorem. Programy napisane w języku SWI Prolog mają domyślne rozszerzenie .pl (przez co niestety mogą się mieszać z programami w języku Perl, które przypadkowo mają takie same rozszerzenie).

Aby skonsultować (wczytać do pamięci) pliki plik1.pl, plik2.pl, ... należy wydać interpreterowi następujące polecenia:

?- [plik1].
?- [plik2].

Uwaga: wczytywane pliki muszą być w tym samym katalogu, spod którego uruchamiany jest program pl.

Inna metoda uruchamiania plików polega na utworzeniu pliku o nazwie np. start.pl i o następującej treści:

:- [plik1]. 
:- [plik2].

Następnie wystarczy skonsultować ten plik poprzez cel:

?- [start].

Omówienie niektórych elementów języka

równość i uzgadnianie

Równość jest wbudowanym predykatem infiksowym. Wyrażenie A=B oznacza próbę uzgodnienia (matching) zmiennych A i B, tj. sprawienia, by były sobie równe. W przypadku wyrażenia A=B możemy mieć następujące możliwości:

• A jest zmienną ukonkretnioną, tj. związaną z pewną stałą, B jest zmienną wolną - wówczas B zostanie ukonkretniona przez wartość zmiennej A,
• B jest zmienną ukonkretnioną, A jest zmienną wolną - wówczas B zostanie ukonkretniona przez wartość zmiennej B,
• jeśli obie zmienne są wolne, to wtedy następuje ich powiązanie, w efekcie którego jeżeli później jedna z nich zostanie ukonkretniona, to druga automatycznie przyjmie tę samą wartość,
• jeśli obie zmienne są ukonkretnione, następuje porównanie ich wartości i równość zachodzi, jeśli ta sama wartość występuje po obu stronach predykatu =.

operator specjalny is

Operator is służy do ukonkretniania występującej po lewej stronie zmiennej przez wartość termu znajdującego się po prawej stronie. Term ten musi być wyrażeniem arytmetycznym, ponieważ Prolog stara się najpierw obliczyć jego wartość. Inne struktury nie są dopuszczalne.

Przykład zastosowania wyrażeń arytmetycznych:

długość(obiekt, 10).
szerokość(obiekt, 20).
powierzchnia(X, Y):- dlugość(X, A),
	             szerokość(X, B),
		     Y is A * B.	

(Patrz także dodatek.)

Zadania z ćwiczeń 1

Zadanie 1 (dla "niewprawionych") Utworzyć plik z faktami i predykatami podanymi jako przykłady (lubi, przystojny, ma_powodzenie) i uzupełnić kilkoma klauzulami. Wypróbować różnego typu cele: sprawdzenie prawdziwości pewnych faktów (np. ?- ma_powodzenie(jan)), wyszukanie pewnych informacji (np. ma_powodzenie(X)).

Zadanie 2 Dane jest drzewo genealogiczne:

Utworzyć bazę danych:

• fakty: rodzic, mężczyzna, kobieta,
• reguły: matka, ojciec, dziecko, wnuk, potomek, przodek, brat, siostra.

Zadawać cele:

1. sprawdzające poprawność faktów,
2. sprawdzające poprawność reguł, np. przodek(eugenia, maria),
3. wyszukujące, np. przodek(X, maria).

(W celu wyszukania kilku odpowiedzi należy po wyświetleniu odpowiedzi nacisnąć ';'.)

Zadanie A (dodatkowe) Na przykładzie rodziny zdefiniować pewną relację symetryczną, np. rodzeństwo, czyli napisać taką regułę, która umożliwi wywnioskowanie, że rodzeństwo(b, a) na podstawie faktu rodzeństwo(a, b).

Zadanie B (dodatkowe) Informacje o rodzinie poszerzyć o dane dotyczące wieku oraz o pewne dodatkowe klauzule poszerzające relację pokrewieństwa. Sprawdzić, czy istnieje jakaś osoba z poprzedniego pokolenia młodsza od osoby z młodszego pokolenia (np. ciocia młodsza od bratanka).

Zadanie 3 Zdefiniować relację większy(X, Y, Z), której dwoma pierwszymi elementami są dwie liczby, a trzecim elementem jest większa z nich.

Zadanie 4. Zdefiniować dwuargumentową relację moduł, w której drugim argumentem jest wartość bezwzględna pierwszego argumentu.

Zadanie 5. Zdefiniować rekurencyjnie relację silnia, której drugim argumentem jest wartość silni pierwszego argumentu. Wskazówka - skorzystać z następującego opisu sumowania kolejnych liczb naturalnych od 0 do N.

suma(0,0).  /* suma 0 liczb wynosi 0 */

suma(N, Nwynik) :-
     N > 0, 
     M is N-1, /* za M przyjmij N-1  */
     suma(M, Mwynik), /* oblicz rekurencyjnie sumę N-1 liczb */
     Nwynik is N + Mwynik. /* do uzyskanej sumy dodaj N */

Zadanie C (dodatkowe) Zdefiniować operację potęgowania liczb naturalnych.

Zadanie D (dodatkowe) Napisać predykat, który opisuje rozwiązanie problemu wieży z Hanoi: N krążków poukładanych jeden na drugim od największego (na spodzie) do największego należy przenieść na inną wieżę w tym samym układzie. Nie można krążka większego położyć na mniejszy. Mamy do dyspozycji trzecią wieżę pomocniczą.
Wskazówki: 1. Opis rozwiązania może wyglądać tak "przenieś krążek z wieży pierwszej na drugą, przenieś krążek z wieży trzecią na pierwszą", itp. 2. Aby przenieść N krążków z wieży pierwszej na drugą, należy przeniesć N-1 krażków na wieżę trzecią, następnie przenieść pozostały krażek na wieżę drugą i przenieść N-1 krążków z wieży trzeciej na drugą.

Zadanie 6 (dodatkowe) Napisać predykat slownie, którego pierwszym argumentem jest liczba, a drugim liczebnik w języku polskim odpowiadający tej liczbie, przykład oczekiwanego działania predykatu:

?- slownie(5, L).

L = pięć

Yes

?- slownie(214, L).

L = 'dwieście czternaście'

Yes

Ograniczyć się do liczb naturalnych mniejszych od 10000. Wskazówka: użyć predykatu wbudowanego concat, który skleja napisy podane jako dwa pierwsze argumenty; przykład działania predykatu concat:

?- concat('Ala',' ma kota', S).

S = 'Ala ma kota'

Yes

Dodatek

niektóre operatory w Prologu

?- X = 2+3

X = 2+3

Yes
?- [5, X] = [Y, 7].

X = 7
Y = 5

Yes

?- X == X.

X = _G174

Yes
?- X == Y.

No

?- X == 5.

No

?- X =:= 2+3.

ERROR: Arguments are not 
sufficiently instanstiated
[Prolog próbuje wyliczyć 
wartość arytmetyczną X, 
co nie ma sensu]

Yes
?- 22-12+2 =:= 7+5.

Yes

?- X is 2+3.

X = 5

Yes
?- 5 is 2+3.

Yes

?- X is 5/2.

X = 2.5

Yes

?- X is 5//2.

X = 2

Yes

?- X is 14 mod 10.

X = 4

Yes

Uwaga: znaczenie operatorów / i // zależy od interpretera Prologu (może być na odwrót).