PROLOG-PROGRAMOWANIE W JĘZYKU LOGIKI

Literatura:

1. Clocksin W., Mellish C. Prolog programowanie, Helion,
Gliwice 2004.
2. Szajna J., Adamski M., Kozłowski T., Turbo Prolog,
WNT, Warszaw 1991.

Strony internetowe.
www/prolog_tutorial/pt_framer.htlm

http://home.agh.edu.pl/~mitu/jsi2004.htm
l

http://pl.wikipedia.org/wiki/Prolog

PROGRAMOWANIE W JĘZYKU LOGIKI

Dostępne programy:

Turbo Prolog

– (pod DOS-em) obecnie już nie rozwijany

SWI Prolog

– wolne oprogramowanie wersje WIN i LINUX

Visual Prolog

– darmowa wersja edukacyjna.

Linki do innych wersji dostępne na stronie Wikipedii

http://pl.wikipedia.org/wiki/Prolog

PROGRAMOWANIE W JĘZYKU LOGIKI

PROLOG język programowania powstały w Marsylii

w 1972 roku. Twórca Alain Colmerauer.

W tym samym roku:

- Intel wypuszcza procesor 8008,
- Powstaje pierwszy program poczty elektronicznej ,
pojawia się w nim symbol @,
- Dennis Ritche podaje specyfikację jezyka C,
- Powstaje Cray Research, twórca w 4 lata później
superkomputera Cray.

Dziedziny zastosowań języka Prolog

relacyjne bazy danych,
logika matematyczna,
rozwiązywanie problemów abstrakcyjnych,
przetwarzanie języków naturalnych,
automatyzacja projektowania,
symboliczne rozwiązywanie równań,
analiza struktur biochemicznych,
zagadnienia sztucznej inteligencji.

Cechy charakterystyczne języka

Prolog

Jest to język opisowy i deklaratywny,

podczas gdy
większość języków programowania ma
charakter
proceduralny.

Programowanie w Prologu polega głównie

na opisaniu
znanych faktów i relacji dotyczących
badanego problemu.

Programowanie w Prologu składa się z :

-Deklarowania faktów dotyczących obiektów i
relacji
miedzy nimi,
- Definiowania reguł dotyczących obiektów i
związków
między nimi,
- Zadawania zapytań o obiekty i związki
miedzy nimi.

Wady języka Prolog

- nieefektywne przetwarzanie baz danych,

- zbyt ścisłe wnioskowanie,

- założenie o zamkniętości wiedzy, ( jeżeli nie można
wykazać jakiejś własności, przyjmuje się, że jest fałszywa).

Niektóre pojęcia z logiki i programowania

- Literał - wartość wpisana bezpośrednio w kod programu.
W logice matematycznej każde zdanie proste lub jego
zaprzeczenie jest literałem.

-Klauzula – zbiór literałów, który jest prawdziwy, gdy ich
alternatywa jest prawdziwa.

- Klauzula Horna – klauzula, w której co najwyżej jeden
element jest niezanegowany.

Niektóre pojęcia z logiki i programowania

TERM

- symbol stałej, oznacza pojedynczy byt lub

pojęcie, przykłady: angielski, wojtek,
chwila,

- symbol zmiennej, symbol ten może oznaczać
w
różnych chwilach różne byty, przykłady: X,
Człowiek,

- term złożony, składający się z symbolu
funkcyjnego i
uporządkowanego zbioru termów będących
jego
argumentami, przykłady:
żona(henryk),odległość( X,Y).

Niektóre pojęcia z logiki i programowania

PREDYKAT

Nazwa relacji łączącej obiekty (argumenty),

przykłady:
ojciec(kazimierz, halina), corka(anna,
wladysław),
cenny(szafir).

Nazwy obiektów i relacji są dowolne.

Relacje mogą mieć dowolna liczbę
argumentów, np: gra1(jan, staszek, poker),
gra2(maria, halina, wojtek, anna, brydz).

Przedstawianie wiedzy w Prologu

OBIEKTY i RELACJE

Prolog rozwiązuje problemy dotyczące obiektów i relacji
pomiędzy nimi, więc podana mu informacja ma również
głównie postać relacji.

Informacja, że Ewa ma zegarek mówi, że istnieje pewna
relacja pomiędzy dwoma obiektami Ewa i zegarek.
Zapisujemy to w postaci :
ewa(zegarek). lub zegarek(ewa).,
w zależności od sposobu dalszego wykorzystania tej
informacji.

Przedstawianie wiedzy w Prologu

FAKTY

Informację, że Maria jest matką Jana zapisujemy w postaci:
matka(maria,jan).

Kolejność argumentów jest dowolna, ale musi być

jednakowa dla kolejnych takich relacji.

Nazwy obiektów występujących w nawiasach nazywamy

argumentami, samą zaś relację nazywamy predykatem.

Nazwy obiektów i predykatów piszemy z małej litery.

Przedstawianie wiedzy w Prologu

ZAPYTANIA

Prolog jest językiem konwersacyjnym i komunikacja z

nim polega na ogół na zadawaniu pytań.

Po podaniu pytania Prolog przeszukuje stworzoną miedzy

innymi poprzez podanie faktów bazę danych i szuka faktów
pasujących do faktu podanego w zapytaniu. Nazywamy to
uzgadnianiem celu.

Dwa fakty pasują do siebie jeśli maja takie same

predykaty i takie same ich argumenty. Przykłady zapytań:
lubi(jan,piwo). Prolog odpowie Yes lub No.
lubi(jan,X).

Prolog wymieni obiekty, które lubi Jan.

lubi(Y,piwo).

Prolog wymieni obiekty, które lubią piwo.

Przedstawianie wiedzy w Prologu

ZMIENNE

W Prologu obiekty mogą występować w postaci jawnej

( przykład jan) lub w postaci zmiennych którym konkretne
obiekty przypisuje Prolog.

Zmienne mogą być ukonkretnione, jeżeli jest jej już

przypisany jakiś obiekt, lub nieukonkretnione (swobodne),
w przeciwnym wypadku.

Nazwy zmiennych, podobnie jak nazwy predykatów i ich

argumentów są dowolne. Nazwy zmiennych piszemy
zawsze z dużej litery. Przykłady zmiennych:
X, NajmniejszaWartosc, SumaCiagu, ZyskPodzielony.

Przedstawienie wiedzy w Prologu

KONIUNKCJA

Relacje występujące w bazie danych mogą mieć postać

bardziej złożoną niż tylko proste fakty. W tym celu stosuje
się koniunkcję. W Prologu oznacza ją przecinek „ ,”.

Zapytanie lubi(jan,maria), lubi(maria, jan) oznacza

koniunkcję celów.

Prolog szukając faktów spełniających koniunkcję celów

najpierw stara się spełnić cel począwszy od lewej a dopiero
po jego spełnieniu przechodzi do prób spełnienia kolejnych
celów, na prawo od spełnionego już celu.

Przedstawienie wiedzy w Prologu

KONIUNKCJA cd

Zapytanie:

lubi(jan,X), kolorWlosow(X,jasne).
spowoduje najpierw próbę uzgodnienie celu lubi(jan,X).
Po jego ewentualnym uzgodnieniu X będzie juz
ukonkretnione X* i nastąpi próba uzgodnienia celu
kolorWłosów(X*,jasne).

Jeżeli próba ta nie powiedzie się to Prolog spróbuje

uzgodnić na nowo cel pierwszy a następnie dopiero cel
drugi. Taki sposób Prologu działania nazywamy
nawracaniem.

Przedstawienie wiedzy w Prologu

REGUŁY

Jeżeli chcemy wprowadzić informacje tego samego

rodzaju o wielu obiektach to nie ma potrzeby wielokrotnego
wypisywania podobnych predykatów. Zamiast tego
używamy reguł. Informację, że X jest bratem Y jeżeli X jest
mężczyzną i X oraz Y mają tych samych rodziców w
Prologu zapisujemy następująco:
brat(X,Y):-mężczyzna(X), rodzice(X,Matka,Ojciec),
rodzice(Y,Matka,Ojciec).
Taki sposób przedstawienia informacji nazywamy reguła.
Ogólna postać GłowaReguły :-TreśćReguły.
Reguła kończy się kropką.

Przedstawienie wiedzy w Prologu

Informacje dotyczące jakiegoś predykatu można

podawać w dwóch postaciach ;
-faktów,
-reguł.

Predykat definiuje się więc jako zbiór faktów i reguł.

Jedne i drugie nazywamy klauzulami predykatu.

Przedstawienie wiedzy w Prologu

KOMENTARZE

W celu poprawienia czytelności programu stosujemy

komentarze;

% --------------------------- komentarz ----------------------------

/* ---------------------------- komentarz --------------------------*/

SKŁADNIA PROLOGU

Program Prologu składa się z termów. Term to stała,
zmienna lub struktura. Każdy term zapisujemy jako ciąg
znaków. Dopuszczalne znaki w Prologu:

1. Duże litery alfabetu łacińskiego,

2. Małe litery alfabetu łacińskiego,

3. Cyfry {0,1,,,9}

4.Znali specjalne{+ - * / \ ~ ^ <> . ? @ # $ &

SKŁADNIA PROLOGU

TERMY - STAŁE

Stałe nazywają konkretne obiekty lub konkretne relacje.

Istnieją dwa rodzaje stałych: atomy i liczby całkowite.
Istnieją dwa rodzaje atomów:
-składające się z liter i cyfr i znaku podkreślenia _
(muszą zaczynać się małą literą),
-składające się z wyłącznie z symboli.
Atom ujęty w pojedynczy cudzysłów ' może zawierać
dowolne znaki.

SKŁADNIA PROLOGU

TERMY - ZMIENNE

Zmienne mają postać atomów, ale ich nazwy zaczynają

się dużą literą lub podkreśleniem _.
Zmienna anonimowa.
Czasami interesuje nas czy jakikolwiek obiekt jest w relacji
z innym obiektem. Używamy wtedy zmienne anonimowej _ .

Na przykład jeśli chcemy sprawdzić, czy Anna ma

jakąkolwiek siostrę formułujemy zapytanie siostra(anna,_).
Otrzymujemy wtedy odpowiedź Yes lub No.

Zmienne anonimowe są po to, aby nie wymyślać różnych

nazw zmiennych, które i tak nie będą nigdy użyte.

SKŁADNIA PROLOGU

TERMY – STRUKTURY

Struktura to pojedynczy obiekt, składający się z zestawu

innych obiektów, zwanych składnikami struktury. Składniki
są pogrupowane w strukturę , aby ułatwić ich przetwarzanie.

Informację, że Jan posiada książkę Noce i Dnie

Marii Dąbrowskiej, wydaną w 1987 roku możemy zapisać
w postaci struktury:

posiada(jan(ksiazka(maria_dabrowska(noce_i_dnie(1987))))).

Struktury mogą występować w zapytaniach i mogą
zawierać zmienne.

SKŁADNIA PROLOGU

OPERATORY

Ze względu na czytelność programu operacje

arytmetyczne zapisuje się zwykle przy pomocy operatorów.

Wyrażenie x+y*z zapisane jako struktura w Prologu

miałoby postać: +(x,*(y,z).

W Prologu operatory nie powodują żadnych obliczeń,

term 3+5 nie oznacza 8, jest tylko wariantowym zapisem
struktury +(3,5).

Operatory posiadają trzy cech: położenie, priorytet i

łączność.

SKŁADNIA PROLOGU

OPERATORY – priorytety

Priorytet operatora mówi o kolejności operacji. Każdy

operator posiada w Prologu klasę priorytetu. Jest to liczba
całkowita, związana z danym operatorem. Konkretna jej
wartość zależy od wersji Prologu. Im niższa jest to liczba,
tym większy jest priorytet danej operacji. Zawsze + i – mają
niższy priorytet niż *i /.

STRUKTURA PROGRAMU w PROLOGU

DOMAINS

liczba = integer

PREDICATES

suma(liczba, liczba,liczba)

CLAUSES

suma( SumaLiczb, Liczba1, Liczba2):-
SumaLiczb=Liczba1+Liczba2.

GOAL

suma(X,3,56).

Przykład

ex0000

E:\prolog\PROLOG.EXE

SKŁADNIA PROLOGU

OPERATORY – łączność

Operatory łączne lewostronnie muszą mieć po lewej

stronie operacje o takim samym lub niższy priorytecie, a po
prawej o priorytecie niższym. Wszystkie operacje
arytmetyczne (dodawanie, odejmowanie, mnożenie,
dzielenie) są łącznymi lewostronnie. Struktura 8/4/4 jest
interpretowana jako(8/4)/4.

W praktyce używanie nawiasów eliminuje wątpliwości

dotyczące interpretacji.

Struktury zawierające operacje arytmetyczne są

strukturami jak inne i żadne obliczenia nie są dokonywane,
dopóki nie wymusi tego odpowiedni predykat.

RÓWNOŚĆ I UNIFIKACJA

Operator = może być operatorem arytmetycznym
przypisania , w przypadku, gdy po lewej stronie występuje
pojedyncza zmienna nieukonkretniona.
Przykład:

ex01

.

W przeciwnym razie jest operator porównania.
Przykład:

ex02

W Prologu zmienna, której w klauzuli nadano już wartość

nie zmienia jej aż do zakończenia tej klauzuli.

RÓWNOŚĆ I UNIFIKACJA cd

Unifikacja czyli ukonkretnianie (uzgadnianie) może

odbywać się w wyniku operacji przypisania lub też poprzez
uzgadnianie parametrów celu i klauzuli.

Uzgodnienie to może zajść jeżeli:

-cel i klauzula mają tą samą nazwę i można uzgodnić każdą
parę ich parametrów, to znaczy musi zachodzić jeden z
następujących warunków :
- obydwa parametry są zmiennymi (powiązanie zmiennych),
- jeden parametr jest zmienną, drugi stałą(ukonkretnienie
zmiennych,
- obydwa parametry są stałymi o tej samej wartości.

RÓWNOŚĆ I UNIFIKACJA cd

Klauzula

Wywołanie Efekt uzgodnienia

a1(5,6)

a1(5,X)

X=6(ukonkretnienie zm.)

a1(5,6)

a1(Y,6)

Y=5 (ukonkretnienie zm.)

a1(5,A)

a1(5,Y)

Y=A (powiązanie zm.)

a1(5,6)

a1(6,Y)

bez ukonkretnienia

alfa(f(5,6))

alfa(X)

X=f(5,6)

alfa(f(5,6))

alfa(f(5,6))

bez ukonkretnienia

Przykład

ex03

OPERACJE ARYTMETYCZE

Na operacje arytmetyczne składa się porównywanie liczb

oraz obliczanie wartości wyrażeń.

Porównywanie liczb:

=:=, =\=, <, >, =<, =>. Predykaty te wyliczają wartości
termów, traktując je jak wyrażenia algebraiczne.

Argumentami tych predykatów mogą być zmienne

ukonkretnione liczbami całkowitymi, liczby zapisane jako
stałe lub wyrażenia algebraiczne.

Obliczanie wartości wyrażeń:

Operator = oblicza wartość wyrażenia po prawej stronie,
wynik jest dopasowywany do lewego argumentu.

SPEŁNIANIE CELÓW

Zapytanie ma zazwyczaj postać koniunkcji celów, które

mają być spełnione. Fakt zawarty w programie może od razu
spełnić cel. Reguła pozwala spełniać zadanie stopniowo
poprzez spełnianie koniunkcji jej podcelów. Klauzula może
zostać użyta jeśli pasuje do spełnianego celu. Jeżeli
w którymś miejscu reguły nie można spełnić celu
realizowana jest operacja nawracania to jest cofnięcie
programu i próba znalezienia alternatywnych rozwiązań.

Przykład zapytania w postaci koniunkcji

ex000.

PROLOG -STRUKTURY DANYCH

Strukturę Prologu można zawsze przedstawić w postaci

drzewa. I tak klauzulę rodzice( jasio, anna, marian)
pokazuje drzewo:

rodzice

jasio

anna

filip

PROLOG -STRUKTURY DANYCH

Struktury ksiazka(noce_i_dnie, autor((maria, dabrowska))

oraz +(a,*(b,c) można zapisać w postaci drzew:

+ ksiazka

a * noce_i_dnie

autor

b c maria dabrowska

Oba drzewa różnią się między sobą jedynie nazwami
wierzchołków.

Obie struktury mają taką samą postać, mają jedynie

różne nazwy węzłów.

PROLOG -STRUKTURY DANYCH, LISTY

Lista jest dowolnej długości

uporządkowanym ciągiem elementów.
Elementami listy mogą być dowolne termy:
stałe, zmienne, struktury, w tym również listy.

Listę można zapisać w postaci specjalnego
rodzaju drzewa.
Lista jest albo struktura pustą, nie zawierająca
żadnych elementów, albo strukturą z dwiema
składowymi, głową i ogonem. Koniec listy
zapisujemy jako ogon będący listą pustą. Listę
pustą oznacza się symbolem []. Listę możemy
zapisać jako relację „ . ” której argumentami
są głowa i ogon. Listę zawierającą tylko jeden
element a zapisujemy więc w postaci .(a,[]).

PROLOG -STRUKTURY DANYCH, LISTY

Odpowiada temu drzewo:

.

a [ ]

Z kolei lista składająca się z trzech atomów

a,b, c , może być zapisana w postaci .( a, .(b, .(
c, []))), lub w formie drzewa:

.

.

.

a

b

c

[]

REKURENCJA W PROLOGU

Procedury odwołujące się do siebie samych

noszą nazwę procedur rekurencyjnych.
Muszą one składać się z dwóch elementów:
- warunku zakończenia rekurencji
- opisu procesu odwołania rekurencyjnego

Przykład: Obliczenie długości listy.
Warunek stopu:
dlugosc_listy([],0).
Opis odwołania rekurencyjnego:
dlugosc_listy([_|Ogon],I):-
dlugosc_listy(Ogon,J), I=J+1.

Jest to tak zwana rekurencja lewostronna

REKURENCJA W PROLOGU cd

Rekurencja prawostronna polega na

wprowadzeniu dodatkowej zmiennej zwanej
akumulatorem.

dlugosc_listy(L,N):-
dlugosc_akumulatora(L,0,N).
dlugosc_akumulatora([],A,A).
dlugosc_akumulatora([_|Ogon],A,N):- A1 is A
+ 1,
dlugosc_akumulatora(Ogon,A1,N).

Na początku nadajemy akumulatorowi wartość
zero, aby w każdym odowłaniu zwiększać tą
wartość o jeden.

PRZESZUKIWANIE REKURENCYJNE LIST

Listy przetwarza się dzieląc ją na głowę i

ogon. Listę z głową X i ogonem Y oznaczamy
symbolem [X|Y].

Chcemy sprawdzić, czy term X należy należy

do listy. W tym celu sprawdzamy,
1. czy term X jest równy termowi głowy listy

member(X,[X,_]), możemy też

zapisać

member(X,[Y|_]) :-X=Y.

2. czy term X należy do ogona listy:

member(X,[_|Y]):- member(X,Y).

Podsumowując sprawdzanie przynależności do
listy realizują dwie klauzule:
member(X,[X|_]).
member(X,[_|Y]:- member(X,Y).
Przykład

ex06

ODWZOROWYWANIE STRUKTUR

Proces zamiany kolejnych składników starej
struktury na nową nazywamy
odwzorowywaniem.

Przykład
program zamieniający cyfry {0,1,2} na cyfry
{9,8,7}. Przykład

ex07

A

B

C

D

E

F

F

G

AND

AND

AND

NOT

bramkaAnd(0,0,0).

bramkaAnd(0,1,0).

bramkaAnd(1,0,0).
bramkaAnd(1,1,1).

bramkaNot(0,1).

bramkaNot(1,0).

uklad(A,B,C,D,E,F,G):-

bramkaAnd(A,B,D),
bramkaAnd(B,C,E),

bramkaAnd(E,F,G),

bramkaNot(D,F).

OPERACJE WEJŚCIA , WYJŚCIA

Wejście:
- readChar( Znak) – wczytanie znaku, bez
oczekiwania
na wciśnięcie Enter,
- inkey(Znak) – sprawdza zawartość bufora
klawiatury,
pobiera pierwszy znak, jesli pusty zawodzi,
- readInt(Liczba) – czyta liczbę całkowitą,
- readReal(Liczba) – czyta liczbę rzeczywistą,
- readln(Wiersz) – czyta jedną zmienną
tekstową, zawodzi
po wciśnięciu Esc, czyta zmienne symbol i
string.
Wyjcie
-write(argument1, argument2,...)- wyświetlenie
podanego
ciągu stałych i zmiennych.

Sterowanie działaniem programu

Mechanizm nawracania możemy modyfikować
korzystając
z wbudowanych predykatów:

odcięcie !

- powoduje zaprzestanie dalszego

ukonkretniania już ukonkretnionych
zmiennych,

fail/true

– predykat któr zawsze zawodzi/jest

spełniony

findAll

- predykat tworzący listę ze wszystkimi

rozwiązaniami,

not

– przeczenie,

repeat

– predykat generujący nawroty,

free/bound

- predykaty sprawdzające

ukonkretnienie
zmiennych

Dziękuję za uwagę, zapraszam na

laboratorium.