Prolog

From ESIpedia

Prolog (ang. PROgramming in LOGic) jest językiem programowania wywodzącym się z nurtu badań w zakresie programowania logicznego (ang. logic programming). Programowanie logiczne, określane również programowaniem w języku logiki narodziło się na początku lat siedemdziesiątych jako rezultat wcześniejszych prac w zakresie automatycznego dowodzenia twierdzeń i sztucznej inteligencji. Z chwilą opracowania w 1972 roku przez Colmarauera i Roussela języka Prolog, programowanie logiczne nabrało waloru praktycznej użyteczności. Do wzrostu popularności tego języka przyczyniło się między innymi zwiększenie efektywności jego implementacji. Programowanie logiczne można traktować zarówno jako ilustrację wykorzystania logiki do reprezentowania problemów jak i przykład podejścia regułowego do reprezentacji wiedzy.

Pojęcie programowania logicznego nie jest dobrze zdefiniowane. Najczęściej jednak ogranicza się jego zakres do sytuacji, gdy informacja jest reprezentowana za pomocą tzw. klauzul Horna, a dedukcja jest przeprowadzana zasadniczo z wykorzystaniem wnioskowania zstępującego (ang. top-down inference), opartego o zasadę rezolucji Robinsona (1965). Wnioskowanie zstępujące w pewnym sensie jest uogólnieniem reguły modus tollens połączonej z operacją ukonkretnienia (ang. instantiation). W tym przypadku procedura wnioskowania rozpoczyna się od zaprzeczenia jednej ze zbioru klauzul. Następnie wykorzystuje się implikacje oraz asercje w celu uzyskania nowych zaprzeczeń. Wnioskowanie kończy się w momencie wyprowadzenia klauzuli pustej. Można jednak rozumieć programowanie logiczne szerzej, włączając w to pojęcie np. negację przez porażkę lub operator obcięcia (ang. cut operator). Programowanie logiczne opiera się na dwóch zasadniczych ideach: traktowania logiki jako języka programowania oraz reprezentowania algorytmów w postaci dwóch rozdzielonych składników: logiki oraz sterowania. Wykonywanie programów logicznych stało się również możliwe po nadaniu im interpretacji proceduralnej.

Prolog jest językiem deklaratywnym, złożonym ze zbioru reguł, faktów i celu (ang. goal, a nie imperatywnym w odróżnieniu od np. Pascala czy języka "C"). Oznacza to między innymi, że sposób rozwiązania problemu nie jest opisywany algorytmem. Zamiast tego w Prologu wykorzystywany jest wbudowany w system prologowy mechanizm wnioskowania. Podstawową jednostką syntaktyczną i reprezentacji semantyki są predykaty.

Przykład prostego programu prologowego:

 Cel:     ?- lubi(jas,X).
 Reguła:  lubi(X,Y) :- interesuje_sie(Y,'sztuczna inteligencja').
 Fakt:    interesuje_sie(wiola,'sztuczna inteligencja').
 Rozwiązanie: X=wiola
              yes

Cel możemy interpretować w następujący sposób: "Kogo lubi Jaś?". Reguła opisuje relację, że "X lubi Y jeśli Y interesuje się sztuczną inteligencją". Fakt stwierdza natomiast, że "Wiola interesuje się sztuczna inteligencję". Na tej podstawie, wykorzystując wnioskowanie dedukcyjne prolog odnajduje rozwiązanie, że tą osoba, którą lubi Jaś jest Wiola. Niektóre dialekty prologu zamiast dwuznaku ':-' umożliwiają użycie słowa kluczowego "if". Argumenty predykatów rozpoczynające się od dużych liter oznaczają zmienne.

Teraz podamy bardziej złożony przykład ilustrujący zapisane w Prologu definicje realcji pokrewieństwa rodzinnego:

fakty:

 ojciec(druzus, germanik).
 ojciec(druzus, klaudiusz).
 ojciec(germanik, neron).
 ojciec(germanik, kaligula).
 ojciec(klaudiusz, brytanik).
 matka(liwia, druzus).
 matka(messalina, oktawia).

reguły:

 kobieta( X ) :-  matka( X, Y ).
 mężczyzna( X ) :- ojciec( Y ).
 rodzic(  X, Y ) :-  ojciec( X, Y).
 rodzic( X, Y ) :- matka( X, Y ).
 brat( X, Y) :-
      meżczyzna( X ), mężczyzna ( Y ),
      rodzic( Z, X ), rodzic( Z, Y ),
      X <> Y.
 dziadek( X, Y ) :- ojciec( X, Z ), rodzic( Z, Y ).

Cele w Prologu mogą wyglądać następująco:

 ?- matka( X, druzus ).         Można to interpretować jako pytanie: "Kto był matką Druzusa?"
 X = liwia
 yes

 ?- dziadek( X, brytanik ).     Można to interpretować jako pytanie:  "Kto był dziadkiem Brytanika?”
 X = druzus
 yes

O ile w latach 80. i 90. większość programów w USA z dziedziny SI było napisanych w Lispie i jego dialektach, to w Europie i Japonii dominował Prolog. Zainteresowanie tym językiem wyraźnie wzrosło w momencie gdy został wybrany jako język maszynowy w japońskim projekcie komputerów piątej generacji. Z założenia te komputery miały być silnie współbieżne, zatem zaczęły się również rozwijać dialekty Prologu do przetwarzania równoległego, np Concurrent Prolog czy Parlog. Podstawowym dialektem Prologu (quasi-standardem) stał się tzw. dialekt edynburski. Wiąże się to z jego implementacjami opracowanymi głównie w Edynburgu m.in. dla takich systemów komputerowych jak: DECsystem-10, DEC VAX, PDP-11 oraz ICL 2980. W pewnym okresie popularny stał się również micro-PROLOG.

Autor wpisu: Krzysztof Michalik

Bibliografia

Więcej informacji można znaleźć m.in. w:

Bratko I.: Prolog Programming for Artificial Intelligence. Addison-Wesley. Reading MA 1986.
Campbell J.A. (Ed.): Implementations of PROLOG. Ellis Horwood Series ARTIFICIAL INTELLIGENCE. Wiley. New York N.Y. 1985.
Clocksin W.F., Mellish C.S.: Programming in Prolog. Springer-Verlag. Berlin 1984.
Kowalski R.: Logika w rozwiązywaniu zadań. WNT. Warszawa 1989.
Michalik K. (1986): Programowanie logiczne. INFORMATYKA, nr 5.
Michalik K (1986). Programowanie logiczne jako narzędzie sztucznej inteligencji. I Ogólnopolskie Konwersatorium nt. "Sztuczna inteligencja",ZG Polskiego Towarzystwa Cybernetycznego, Warszawa.