Prolog - nieco inne podejście do programowania
Większość popularnych języków programowania nauczyło nas, że programowanie polega na opisywaniu komputerowi kolejnych kroków które ma wykonać. Wyobraźmy sobie jednak sposób tworzenia programów, w którym mówimy jedynie jak wygląda rozwiązanie, a od komputera wymagamy żeby sam do takiego wyniku doszedł. Tak właśnie działają języki deklaratywne (w dużym uproszczeniu, za które fanatycy mnie ukamienują). Najbardziej znanym przykładem takiego języka jest... SQL. Większość użytkowników tego języka nie jest nawet świadoma, że używa języka deklaratywnego, ale zastanówmy się przez chwilę. Nie mówimy przecież komputerowi jak ma wyszukać dane, rozkazujemy tylko:
Ziomuś, dawaj mi id usera o nicku kubut, ale znajdź je sobie jak chcesz
Nie da się ukryć, że jest to wygodne podejście do sprawy, ponieważ nie musimy martwić się implementacją przeszukiwania bazy danych ani żadnych innych operacji. Jako, że SQL jest dość popularny, dzisiaj chciałbym napisać parę słów na temat języka o nazwie Prolog. Podkreślam, że będzie to parę słów, nie kurs ;)
Trochę nudnych rzeczy o Prologu
Jak się zapewne domyślacie w Prologu także nie będziemy definiować w jaki sposób ma dojść do wyniku (choć w ograniczonym zakresie możemy to robić), będziemy natomiast żądać od niego, by sam rozwiązał nasz problem. Zalatuje sztuczną inteligencją? To dobrze, bo Prolog dobrze radzi sobie z wyzwaniami jakie stawia tworzenie sztucznego "mózgu". W Prologu nasze programy tworzymy na zasadach logiki pierwszego rzędu, czyli przygotujmy się na masę koniunkcji, alternatyw, czy implikacji. Ogólnie program prologowy składa się z definicji faktów i reguł. Pierwszym co należy powiedzieć o składni, to fakt, że linijkę (czy dokładniej - regułę/fakt) kończymy kropką, natomiast średnik traktowany jest jako alternatywa (or). Będziemy używać także przecinka jako koniunkcji (and) oraz :- jako czegoś w stylu
A jest spełnione :-(jeśli) B jest spełnione
Brzmi trochę strasznie, ale zaraz się rozjaśni. Zanim jednak będziemy mogli prologować potrzebujemy jakiegoś narzędzia które nam to umożliwi. Polecam SWI Prolog który pobrać można na stronie http://www.swi-prolog.org/. Progrm uruchamiamy, następnie wybieramy File->New by stworzyć nowy zestaw faktów. Następnie w konsoli prologa wczytamy nasz plik i będziemy mogli "rozmawiać" z maszyną prologową wypytując ją o różne ciekawe rzeczy.
Trochę przykładów
Zobaczmy może jak wygląda to w praktyce. Zacznijmy od faktów, które definiujemy w następujący sposób:
[code=Prolog] polaczenie(katowice,krakow). polaczenie(krakow,warszawa). polaczenie(warszawa,wroclaw).[/code]
Mówi to tyle, że istnieje połączenie z Katowic do Krakowa itp. Należy zaznaczyć przy tym ważną rzecz - w Prologu nazwy zaczynające się małą literą są stałą, natomiast wielką - zmienną. Dlatego też taki fakt:
[code=Prolog]polaczenie(Katowice,krakow).[/code]
będzie mówił, że z każdego miasta (bo nieważne co podstawimy pod zmienną Katowice) istnieje połączenie do Krakowa. Zapiszmy nasz plik pod nazwą test.pl (pl to rozszerzenie pików Prologa) oraz przejdźmy do konsoli. Pierwsze co musimy zrobić, to wczytać nasz plik z faktami, robimy to przez wpisanie do konsoli
[test].
Następnie spytajmy, czy z Warszawy dojedziemy do Wrocławia:
?- polaczenie(warszawa,wroclaw).
Oczywiście dostaniemy odpowiedź True. Co jednak gdy chcemy dojechać z Katowic do Warszawy? Nie istnieje połączenie bezpośrednie, więc Prolog odpowie False. Jeśli chcemy umożliwić przesiadki musimy zdefiniować regułę, która będzie mówiła kiedy można dojechać z A do C z przesiadką. Powiedzmy to najpierw po polsku:
z A można dojechać do C jeśli istnieje połączenie z A do B oraz z B do C lub z A można dojechać do C jeśli istnieje połączenie z A do C
Teraz możemy przepisać to do naszego pliku test.pl
[code=Prolog]przesiadka(A,C) :- polaczenie(A,B), polaczenie(B,C) ; polaczenie(A,C)[/code]
Teraz po ponownym wczytaniu tego pliku do maszyny prologowej po zapytaniu
?- przesiadka(katowice,warszawa).
Dostaniemy napis True.
Skomplikujmy bardziej!
Niby wszystko fajnie, ale co gdy chcemy wyszukać połączenie z dowolną liczbą przesiadek? Nie będziemy przecież pisać osobnej reguły dla każdej możliwej liczby przesiadek. Zastanówmy się chwilę, jak powiedzieć, że z A można dojechać do B z dowolną liczbą przesiadek? Wbrew pozorom nie jest to trudne, zacznijmy jednak od powiedzenia tego w sposób naturalny.
z miasta A można dojechać do miasta B jeśli istnieje bezpośrednie połączenie z A do B lub z miasta A można dojechać do miasta B jeśli istnieje bezpośrednie połączenie z A do Z, a z Z można dojechać (z przesiadkami) do B
Zawiłe? Może trochę, ale jak się w to wczytamy to nie jest to głupie. Zapiszmy to zatem zamiast naszej poprzedniej definicji reguły "przesiadka".
[code=Prolog]przesiadka(A,B) :- polaczenie(A,B); polaczenie(A,Z) , przesiadka(Z,B).[/code]
Mamy tutaj coś na styl rekurencji znanej z języków imperatywnych. Kod ten ma lekki defekt, mianowicie wpada w "pętle" gdy w zbiorze faktów będziemy mieli zamknięty cykl, jednak nie będę przedłużał wpisu omawiając jak to rozwiązać.
Słowo na koniec
Wyszło trochę dłużej i nudniej niż zamierzałem, jednak Prolog (jak wszystkie języki) to temat-rzeka i można pisać o nim w nieskończoność. Dokładnie poznają go wszyscy którzy pójdą na studia informatyczne na Uniwersytet Wrocławski. Być może porwę się na kontynuowanie tematu w kolejnym wpisie, jeśli będzie takie zapotrzebowanie (choć nie liczę na to) ;) Jako ciekawostkę na koniec powiem, że w bardzo prosty sposób możemy przygotować reguły, które rozwiążą nam "zagadkę Einsteina " i zajmie to o wiele mniej czasu niż rozwiązywanie jej na kartce ;)