Programowanie w Prologu
27.10.2009 - Damian Rusak
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.
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):
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?
A co stałoby się, gdybyśmy zamienili klauzule predykatu potomek miejscami, do takiej postacji:
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!
Trochę teoriiByć 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. (6 ocen) |
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com