Przybliżona treść zadania z drugich laboratoriów sztucznej inteligencji:

Opracować program transformujący listę na drzewo binarne BST oraz sortujący to drzewo za pomocą przeszukiwania pre-order.

Mając doświadczenie implementowania takich drzew i algorytmów przeszukiwania w języku C nie obawiałem się zaimplementowania takiego algorytmu w innym języku. Wychodziłem z założenia, że co najwyżej pomęczę się trochę z inną składnią języka. Jak się okazało, aby zaimplementować taki algorytm w języku Prolog musiałem poświęcić całą niedzielę i nie zdążyłbym, gdyby nie pomoc moich znajomych.

Podstawową różnicą między Prologiem a C jest to, że Prolog należy do klasy języków deklaratywnych, w przeciwieństwie do C, który pochodzi z klasy języków proceduralnych. W językach deklaratywnych zapisuje się opis problemu. Na początku ciężko było sobie wyobrazić program, który będzie rozwiązywał problemy logiczne nie mający wprowadzonego algorytmu jak to miało miejsce w C, a jedynie garść faktów i reguł. Prolog bazując na nich i wykorzystując rachunek predykatowy pierwszego rzędu :) przeprowadza wnioskowanie, na zasadzie którego jest w stanie zwrócić rozwiązanie algorytmu po przetworzeniu naszego za Nie będę rozpisywał się o składni tego języka czy działaniu, bo nie widzę potrzeby dublowania istniejących już stron traktujących o programowaniu w tym języku.

Szczególnie polecam lekturę:

Wracając do problemu transformacji listy na drzewo BST.

list2bst([], _).
list2bst([GLOWA|OGON], TREE) :-
add2bst(HEAD, TREE),
list2bst(OGON, TREE).

Pierwszym krokiem do zrozumienia przeze mnie zasady działania i wnioskowania było zrozumienie rekurencyjnej postaci opisywania reguł. W Prologu nie występują pętle. Jedyna możliwość nakazania przeszukania wszystkich możliwości jest rekurencyjne wywoływanie funkcji. Gdy się przyjrzymy można zauważyć podobieństwo do rekurencyjnego zapisu w C. Funkcja list2bst przyjmuje dwie wartości – listę składającą się z głowy (GLOWA) i reszty listy (OGONA) oraz zmienną TREE, która jest nam narazie niepotrzebna. Aby reguła była spełniona fakt add2bst musi być spełniony (w tym przypadku add2bst jest zawsze spełniony). list2bst(OGON,TREE) wywołuje swoją kopię, z tym, że przekazuje tylko OGON listy. Tym sposobem z listy początkowej zdejmowane są poszczególne głowy listy, aż dojdziemy do predykatu, który mówi Prologowi co zrobić gdy lista jest pusta – list2bst([],_).

Poniżej zamieszczam rozwiązany problem transformacji listy na drzewo BST oraz przeszukiwania pre-order wraz z komentarzami.

list2bst([], _). %Warunek stopu rekurencji. Inaczej fakt mowiacy co zrobic jesli lista jest pusta.
list2bst([HEAD|TAIL], TREE) :-
add2bst(HEAD, TREE),
list2bst(TAIL, TREE).
%Regula przekazujaca do add2bst glowe listy. Rekurencyjne wywolanie list2bst pozwala na przekazanie do add2bst kolejnej "glowy ogona" poprzedniej listy.

add2bst(ELEM, TREE) :- %Deklaracja przypadku, gdy TREE jest niezdefiniowane (pierwsze uzycie).
var(TREE), %Predykat wbudowany zwracajacy YES, gdy term TREE nie byl jeszcze zunifikowany. Przydatne gdy drzewo jeszcze nie istnieje. W kolejnych przeszukiwaniach regula nigdy nie wnioskuje prawdy.
TREE = wezel(_, ELEM,_). %Unifikacja TREE (wezla).
add2bst(ELEM, TREE) :-
wezel(LEFT, DATA, _) = TREE,
ELEM @=<> DATA,
add2bst(ELEM, RIGHT).

pre_order(nil). %Warunek stopu rekurencji, gdy pre_order natknie sie na nieistniejacy wezel.
pre_order(TREE) :-
wezel(LEFT,DATA,RIGHT)=TREE, %unifikacja wezla z podanego TREE.
pre_order(LEFT),
write(DATA), %wypisywanie zmiennej DATA na ekran.
pre_order(RIGHT).
%Sprawdzenie dzialania programu polega na zadania zapytania w konsoli podajacego w argumencie liste.
%Przykladowe zapytanie -? list2bst([2,-1,4,5,1,0],TREE), pre_order(TREE).
%W odpowiedzi Prolog zwroci wyniki przeszukiwania pre_order oraz wyglad drzewa w postaci TREE = wezel(lewy,root,prawy).

Do sprawdzenia działania programu oraz nauki języka polecam GNU Prolog.

Strona programu: http://www.gprolog.org/