Programowanie w Prologu

27.10.2009 - Damian Rusak
TrudnośćTrudność

 

Rozkręćmy się

Spróbujmy trochę rozszerzyć przykładowy program. Podajmy Prologowi informacje dotyczące poniższego drzewa genealogicznego. Dla większej czytelności, bez kolorowych ludzików :

Wypadało by wytłumaczyć wreszcie, jak pisać reguły. Najpierw zacznijmy od faktów i reguł powyżej. Zauważ, że ilość argumentów w nawiasach może być dowolna.

Dodajemy listę faktów dotyczących relacji rodzic – dziecko, oraz fakt ‘mezczyzna’. Tu pojawia się ciekawa rzecz – możemy określić w naszym modelu kobietę jako kogoś, kto nie jest mężczyzną – to oznacza w tym przypadku zapis \+. Definiujemy też regułę syn(X, Y), prawdziwą, gdy X jest mężczyzną i Y jest rodzicem X.

Wiemy już jak pisać fakty – potrzebna jest nazwa (pisana małą literą) oraz pewna ilość parametrów w nawiasach.

Jak napisać regułę? Możemy przyjąć, że reguła to wyrażenie postaci:

Gdzie wyrażenie oznacza pewną regułę bądź fakt. Symbol ‘:-‘ oznacza „odwróconą implikację”, pojęcie z logiki, ale nie jest konieczna jego znajomość.

Możemy przyjąć, że oznacza, iż reguła jest spełniona, jeśli spełnione są wszystkie wyrażenia, znajdujące się w jej ciele. Kolejne wyrażenia oddzielamy przecinkami, a po ostatnim stawiamy kropkę.

Co istotne, widzieliśmy, że w regule mogą występować zmienne. Widzieliśmy też, że Prolog stara się spełnić wyrażenia znajdujące się w ciele reguły, ukonkretniając zmienne do pewnych wartości. Jeśli po drodze to mu się nie uda (wyczerpie wszystkie możliwości), to wykona nawrót, starając się zmienić wcześniejsze wybory.

Czas na małe zadania. W jaki sposób można by zdefiniować regułę corka(X, Y), spełnioną, gdy X jest córką Y? A jak zdefiniować regułę wnuk(X, Y), spełnioną, gdy X jest wnukiem Y? Posłuż się analogią do reguły syn.

Snippet icon

Do poniższego okienka wpisz swoją propozycję reguły corka(X,Y). W jej ciele możesz korzystać ze wszystkich reguł, wypisanych powyżej.

Snippet icon

A tu wypróbuj swoją definicję reguły wnuk(X,Y):

Zauważ, że zmieniliśmy definicję reguły rodzeństwo – teraz dodaliśmy wyrażenie ‘X \= Y’, które oznacza, że X nie jest równe Y. Rozumiemy to tak, że X i Y są równe, jeśli "wskazują" na to samo miejsce w pamięci. Dzięki temu eliminujemy rozwiązania, które w poczet rodzeństwa Ali zaliczałyby ją samą.

 

Jak można by zdefiniować, że ktoś jest czyimś dziadkiem, albo siostrzeńcem? Spróbuj zdefiniować w okienkach poniżej reguły, możesz korzystać z reguł córka(X,Y) oraz wnuk(X,Y):

Snippet icon

siostrzeniec(X,Y), prawdziwą, gdy X jest siostrzeńcem Y.(Dla jasności - X jest siostrzeńcem Y, jeśli X jest synem siostry Y). Zwróć uwagę na to, że reguły są sprawdzane po kolei (o pewnych niebezpieczeństwach z tym związanych opowiada dalsza część artykułu), więc jeśli Twoja reguła nie funkcjonuje dobrze, może warto zamienić niektóre wyrażenia miejscami.

Snippet icon

dziadek(X,Y), prawdziwą, gdy X jest dziadkiem Y.

Zwróć uwagę na to, jak wiele zależności „w rodzinie” można zdefiniować, wiedząc jedynie, kto jest czyim dzieckiem, oraz znając płeć członków rodziny. To właśnie jest siła Prologa – umiejętność wnioskowania ze zbioru podstawowych faktów.

Przyjrzyjmy się pewnej ciekawej regule :

Dwie rzeczy zastanawiają – dlaczego ta reguła jest zdefiniowany dwa razy i czy to możliwe, aby w ciele reguły pojawiło się wyrażenie, korzystające z niej samej?

Przy okazji, możemy wprowadzić bardziej "naukowe" pojęcie i nazywać regułę predykatem.

Zacznijmy od pierwszego pytania. Otóż taki sposób zapisu oznacza, że jeśli Prolog próbuje spełnić cel potomek(X, Y), to powinien najpierw sprawdzić pierwszą z dwóch możliwości. Jeśli to mu się nie powiedzie Prolog wypróbuje również drugą możliwość. Takie różne wersje reguły nazywamy klauzulami. Klauzule są wypróbowywane w kolejności, w jakiej je podamy Prologowi w programie.

Teraz odpowiedź na drugie pytanie – owszem, możemy tak uczynić. Nazywamy to definicją rekurencyjną. Zauważ, jak pasuje nam takie zestawienie klauzul predykatu potomek. X jest potomkiem Y jeśli Y jest rodzicem X, lub jeśli Z jest rodzicem X i Z jest potomkiem Y. Dzięki temu potomek to ktoś, kto jest połączony z kimś wyżej w drzewie genealogicznym, i możemy „przejść” dowolną ilość razy do góry, z dziecka do rodzica.

Sprawdź, jakie wyniki Prolog poda, gdy zapytamy, czyim potomkiem jest Marzena. A co Prolog odpowie, gdy zapytamy go, kto jest potomkiem Adama?

Snippet icon

Jak to zapisać? Możesz przetestować takie cele w poniższym okienku. Użyj zmiennej o nazwie X, aby zobaczyć wynik:

 

A co stałoby się, gdybyśmy zamienili klauzule predykatu potomek miejscami, do takiej postacji:

Snippet icon

Spróbuj wpisać klauzule predykatu potomek do okienka poniżej, a zostaną uruchomione na teście (Prolog zostanie zapytany, kto jest potomkiem Adama).   Zobacz, jaka będzie odpowiedź, gdy wpiszesz je w podanej kolejności, a jaka, gdy wpiszesz je na odwrót:

 

To pokazuje nam, że ważna jest kolejność. Nie tylko klauzul. Zauważ, że Prolog stara się spełnić wyrażenia pojawiające się w ciele klauzuli w tej kolejności, w jakiej zostały napisane. Może się zdarzyć, że zamiana tych wyrażeń będzie prowadzić do podania rozwiązań w innej kolejności, nie odnalezienia rozwiązania w ogóle, czy nawet innego rozwiązania!

Załóżmy, że przestawiliśmy kolejność klauzul i wyrażeń w definicji predykatu potomek. Problem wynika z tego, że gdy Prolog chce odszukać rozwiązanie dla X i Y, pierwszą rzeczą jaką musi zrobić, to sprawdzić, do czego ukonkretnić Z i Y, aby Z był potomkiem Y. Ale aby to zrobić, sprawdza pierwszą klauzulę potomka i znów sprawdza pierwszą klauzulę potomka i tak w nieskończoność…

Zauważ, że nazywamy kolejne zmienne Z1, Z2, … . Tak naprawdę nazwa ma znaczenie lokalne. Jeśli klauzula wywoła sama siebie (jak w naszym przykładzie), to Z1 różni się od Z2. Robi się to jaśniejsze, gdy myślimy o zmiennej jako o czymś, co wskazuje miejsca gdzie ma się znajdować ten sam obiekt.

Problem z tym zapętleniem wynika z kolejności, o której wspominaliśmy. Prolog działa po kolei – najpierw stara się spełnić pierwszy z warunków.

Widać to dobrze na rysunkach, gdzie poszukiwanie rozwiązania przypomina drzewo. W istocie nazywa się to drzewem wyprowadzenia. Na tych rysunkach pierwsze wyrażenie z ciała każdej klauzuli znajduje się najbardziej na lewo.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Uświadomiliśmy sobie, że trzeba uważnie planować, w jakiej kolejności klauzule znajdują się w programie i jak wygląda kolejność w ciele klauzuli.

Wiemy też już, że choć niekonwencjonalny, Prolog jest wygodnym językiem. Pozwala za pomocą zbioru faktów i reguł reprezentować system wnioskowania. Przypomnijmy – to co robimy, pisząc program w Prologu, to stworzenie pewnego modelu świata. Podajemy Prologowi fakty i reguły, które są prawdziwe w tym modelu. Oczywiście możemy stworzyć modele znacznie bardziej skomplikowane, niż model opisujący zależności rodzinne. W Prologu można na przykład wprowadzić arytmetykę i struktury danych. Jeśli chciałbyś poćwiczyć pisanie programów w Prologu i dowiedzieć się więcej na temat jego składni, polecamy zapoznanie się ze SWI-Prologiem.

Teraz czas na trochę więcej swobody. Za pomocą poniższego okienka możesz wpisać dowolny zestaw swoich faktów i predykatów, oraz przetestować ich działanie. Oto jak to zrobić:

1.Sporządź listę faktów i predykatów, z których chcesz korzystać (np. modyfikując nasze rodzinne drzewo, albo tworząc coś zupełnie nowego).

2.Dodaj, po liście predykatów, instrukcję

main :-

a potem kolejne wyrażenia, jak w ciele predykatu. To predykat main - w Prologu nawet program jest predykatem! Ten cel zostanie spełniony, jeśli zostaną spełnione wyrażenia w jego ciele - w ten sposób możesz realizować swoje kolejne zamierzenia. Skorzystaj też z predykatu write(X), który jest zawsze prawdziwy, a jego efektem ubocznym jest wypisanie wartości zmiennej X.

Możesz na przykład napisać:

 

rodzic(adam, piotr).
rodzic(ewa,piotr).

para(X,Y) :-
rodzic(X,Z),
rodzic(Y,Z),
X \= Y.

main :-
  para(adam,X),
  write(X).

Wynikiem, jaki otrzymasz, będzie ewa. Spróbuj koniecznie swoich pomysłów!

Snippet icon Tu możesz wpisać swój program w Prologu. Być może kilka razy napotkasz na błąd, lecz warto próbować dalej!

Trochę teorii

Być może zastanawiasz się, na jakiej podstawie powstał Prolog i jak dokładnie zbudowany jest system wnioskowania, który pozwala Prologowi korzystać z wiedzy, jaką mu dostarczamy? Następne akapity będą właśnie o tym.

 

5
Twoja ocena: Brak Ocena: 5 (6 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com