Prolog (język programowania)

Prolog (od francuskiego Programmation en Logique) – jeden z najpopularniejszych języków programowania logicznego. Prolog powstał jako język programowania służący do automatycznej analizy języków naturalnych, jest jednak językiem ogólnego zastosowania, szczególnie dobrze sprawdzającym się w programach związanych ze sztuczną inteligencją. Prolog w przeciwieństwie do większości popularnych języków jest językiem deklaratywnym.

Prolog

Pojawienie się	1972
Paradygmat	programowanie logiczne
Typowanie	beztypowy
Implementacje	SWI-Prolog, GNU Prolog
Pochodne	ISO Prolog, Edinburgh Prolog
Twórca	Alain Colmerauer
Platforma sprzętowa	wieloplatformowy
Platforma systemowa	wieloplatformowy

Program w Prologu składa się z zestawu klauzul, gdzie każda klauzula jest faktem lub regułą wnioskowania. Aby uruchomić program, należy wprowadzić odpowiednie zapytanie. Prolog jest językiem programowania służącym do rozwiązywania problemów, które dotyczą obiektów i relacji między obiektami. Mówiąc „John ma książkę.”, deklarujemy relacje między obiektem „John”, a drugim indywidualnym obiektem „książka”. Dodatkowo relacja określa konkretną kolejność: John jest właścicielem książki, a nie książka właścicielem Johna. Zadając pytanie „Czy John ma książkę?” chcemy dowiedzieć się o relacji między tymi dwoma obiektami. Dużo problemów może być wyrażonych określając obiekty i relacje między nimi. W Prologu „obiekt” odnosi się do bytu, który może być prezentowany przy użyciu termu. Ważne jest, aby zrozumieć, że reguły są zazwyczaj uproszczone i w rzeczywistości znaczą więcej niż zawiera to reguła.

Prace nad projektem, dzięki któremu powstał Prolog rozpoczęły się już pod koniec 1970 roku, niemniej jednak wstępna wersja Prologu została stworzona w 1971 roku przez Alaina Colmeraurera i Phillipe’a Roussela. Systemy Q, a także doświadczenie nabyte przez Alaina Colmeraurera w trakcie ich wdrażania, miały znaczący wpływ na powstanie Prologu. Zalążka języka Prolog autorzy dopatrują się w artykule Alana Robinsona „Logika zorientowana maszynowo oparta na zasadzie rozdzielczości”, gdyż artykuł ten był źródłem prac na temat automatyzacji dowodzenia twierdzeń, a taka jest zasadniczo budowa Prolog.

Prolog opiera się na rachunku predykatowym pierwszego rzędu, jednak ogranicza się tylko do klauzul Horna. Istnieją w nim ponadto wbudowane predykaty wyższego rzędu.

Ogólne zasady

W Prologu podaje się bazę faktów i reguł. Potem można wykonywać zapytania na tej bazie. Podstawową jednostką w Prologu jest predykat. Predykat składa się z nagłówka i argumentów, na przykład: ojciec(tomasz, agata), gdzie ojciec to nagłówek a tomasz i agata to argumenty. Predykat może zostać użyty do wyrażenia pewnych faktów o świecie, które są znane programowi. W tym przypadku programista musi nadać im znaczenie. Jedną z interpretacji zdania ojciec(tomasz, agata) jest „tomasz to ojciec agaty”. Równie dobrze jednak mogłoby to znaczyć „ojcem tomasza jest agata”. Prolog nie zajmuje się znaczeniem stwierdzeń. Wszystko co robi to manipulacja symbolami w oparciu o reguły. Dlatego można wybrać dowolny sposób zapisu tego, że „tomasz to ojciec agaty”, pod warunkiem konsekwentnego przestrzegania kolejności argumentów w całym programie.

Pewne predykaty mogą, oprócz wyrażania faktów, mieć dodatkową funkcjonalność, jak na przykład wbudowany predykat

write('Cześć').

który wypisuje na ekranie „Cześć”.

Reguły

Baza danych Prologu może też zawierać reguły. Przykład reguły to:

jest(światło) :- włączony(przycisk).

Zapis :- oznacza „wtedy, gdy” lub „jeśli”. Ta reguła oznacza, że zdanie jest(światło) jest prawdziwe wtedy, gdy prawdziwe jest zdanie włączony(przycisk). Każda reguła musi być zakończona kropką. Reguły mogą używać zmiennych. Zmienne zapisuje się zaczynając od wielkiej litery, dla odróżnienia od stałych, zaczynających się małą. Na przykład:

ojciec(X, Y) :- rodzic(X, Y), jest_rodzaju_męskiego(X).

To oznacza: „dla każdych X i Y, jeśli rodzic(X,Y) i jest_rodzaju_męskiego(X) to ojciec(X, Y). Przesłanka i wniosek są zapisane w odwrotnej kolejności niż zwykle w logice. Co więcej, reguły muszą mieć predykat jako wniosek. Można umieścić wiele predykatów we wniosku, połączonych koniunkcją, na przykład:

a,b,c :- d.

ale oznacza to tyle samo, co trzy oddzielne reguły:

a :- d.
b :- d.
c :- d.

Nie można napisać reguły a;b :- c, czyli „jeśli c to (a lub b)”. Wynika to z ograniczenia zapisu do klauzul Horna.

Zapytania

Kiedy zostały zdefiniowane fakty można zadać pytania na ich temat. Zapytanie w Prologu wygląda dokładnie jak fakt, ale przed nim należy postawić znak zapytania:

 ?- ojciec(tomasz, agata).

co znaczyłoby: „Czy Tomasz jest ojcem Agaty?”.

Kiedy pytanie jest zadawane w Prologu, system przeszukuje całą zdefiniowaną bazę, aby znaleźć fakty, które ujednolicą fakt w pytaniu. Jeżeli znajdzie je to odpowie – yes, jeżeli nie istnieją zwróci odpowiedź – no.

Dopasowywanie wyrażeń

Dopasowywanie jest jednym z fundamentów Prologu. Definicja dopasowywania wyrażeń:

1. Jeżeli term1 i term2 są stałymi, to term1 i term2 są równe, wtedy i tylko wtedy, gdy są tym samym atomem lub tą samą liczbą.
2. Jeżeli term1 jest zmienną, a term2 jest jakimkolwiek typem termu, to term1 i term2 są równe, gdy term1 jest instancją term2. Podobnie jest, gdy term2 jest zmienną, a term1 jest jakimkolwiek typem termu. (Jeżeli term1 i term2 są zmiennymi, to są swoimi instancjami i mówimy, że współdzielą wartości.)
3. Jeżeli term1 i term2 są termami złożonymi, to są równe wtedy i tylko wtedy, gdy spełniają kolejne wymienione warunki. Mają one ten sam funktor i arność. Wszystkie ich korespondujące argumenty pasują. Instancje zmiennych są zgodne.
4. Dwa termy są równe, wtedy i tylko wtedy, gdy wynika to z poprzednich trzech klauzul.

Listy

Lista jest uporządkowaną sekwencją termów zapisanych w nawiasach kwadratowych przedzielonych przecinkami:

[jabłko, gruszka, pomarańcza, truskawki]
[1,2,4,7]
[(2+2),dom(texas), X]
[[a,b,c],lista]

Elementami listy mogą być wszystkie rodzaje termów. Lista może być tworzona i rozkładana dzięki unifikacji. Każda lista może być podzielona na głowę i ogon poprzez symbol „|”. Ogon listy zawsze jest listą, natomiast głowa listy jest elementem, np.

[a|[b,c,d]] = [a,b,c,d]
[a|[]] = [a]

Rekurencja

Podobnie jak w innych językach programowania w Prologu można używać rekurencji. Rekurencja pozwala na wykonywanie działań na liście, szukanie konkretnego elementu lub wykonywanie konkretnych działań na każdym napotkanym elemencie – poprzez rozłożenie problemu na proste elementy, i zstępujące powtarzanie algorytmu. Procedura kończy się, gdy nie jest potrzebne ponowne wywołanie.

Przykłady

Operacje na listach

% list_member(X,Y) = X należy do listy Y
% reimplementacja standardowego member(X,Y)
list_member(X, [X|_]).
list_member(X, [_|Y]) :-
        list_member(X, Y).

% list_append(X,Y,Z) = Z powstaje ze sklejenia X i Y
% reimplementacja standardowego append(X,Y,Z)
list_append([], X, X).
list_append([H|T], X, [H|Y]) :-
        list_append(T, X, Y).

% suma_elementow_listy(Lista, N) = N jest sumą elementów należących do Listy
suma_elementow_listy([], 0).
suma_elementow_listy([H|T], Wynik) :-
        suma_elementow_listy(T, Tmp),
        Wynik is H+Tmp.

% jak wyżej, lecz z użyciem rekurencji prawostronnej
suma_elementow_listy_tail(Lista, Wynik) :-
        suma_elementow_listy_tail(Lista, 0, Wynik).
suma_elementow_listy_tail([], Wynik, Wynik).
suma_elementow_listy_tail([H|T], Akumulator, Wynik) :-
        Akumulator2 is H+Akumulator, suma_elementow_listy_tail(T, Akumulator2, Wynik).

Linki zewnętrzne

• polskie
  • Strona Przemysława Kobylańskiego
  • Strona Artura Michalskiego
• angielskie
  • Darmowy kompilator języka Prolog
  • Kompilator GNU Prolog
  • książka Logic Programming and Prolog (2 wyd.) przez Ulf Nilsson i Jan Maluszynski
  • Learn Prolog Now!