Programowanie deklaratywne

PD

rok akademicki

2010/2011

W2

Wstęp do języka Prolog

Uniwersytet Przyrodniczo-Humanistyczny,

Wydział Nauk Ścisłych

Instytut Informatyki,

Katedra Sztucznej Inteligencji

dr inż. Jerzy Tchórzewski

[e-mail]

[e-mail]

Agenda

1. Prolog językiem programowania logicznego

2. Predykat podstawową jednostka Prologu

3. Reguły w Prologu

4. Termy języków pierwszego rzędu

5. Programowanie logiczne w Prologu

6. Składnia w Prologu

7. Unifikacja termów

• Prolog jest to 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ą.

• Program w Prologu składa się z faktów oraz reguł

wnioskowania.

• Aby go uruchomić należy wprowadzić odpowiednie

zapytanie.

• Prolog opiera się o rachunek predykatów pierwszego

rzędu, jednak ogranicza się tylko do klauzul Horna.

• Istnieją jednak wbudowane predykaty wyższego rzędu.

1. Prolog językiem programowania

logicznego

• W Prologu wprowadza się bazę faktów i reguł.

• Na bazie wykonuje się zapytania.

• 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
tomasz i agata to argumenty.

Predykat może zostać użyty do wyrażenia pewnych

faktów o

świecie, które są znane programowi.

2. Predykat podstawową jednostką Prologu

Programista musi nadać im znaczenie.

Jedną z interpretacji zdania ojciec(tomasz,

agata) jest
"tomasz to ojciec agaty".
Ale także można zinterpretować:
"ojcem tomasza jest agata".

Prolog nie ma pojęcia, co oznaczają te

stwierdzenia,
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ć skutki uboczne, jak na przykład
wbudowany predykat

write(‘Witaj'), który wypisuje na ekranie ‘Witaj'.

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).

3. Reguły w Prologu

Reguły mogą używać zmiennych, które zapisuje się zaczynając od

wielkiej litery (dla odróżnienia od stałych, zaczynających się z

małej litery).

Na przykład:

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

To oznacza:

"dla każdych X i Y, jeśli rodzic(X,Y) i

jest_rodzaju_męskiego(Y)

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.

3. Zmienne w Prologu

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.

4. Termy języków pierwszego rzędu

• Term – wyrażenie składające się ze

zmiennych oraz symboli funkcyjnych o

dowolnej argumentowości (w tym o

argumentowości 0, czyli stałych), z pewnego

ustalonego zbioru.

• W wielu dziedzinach matematyki używa się

określenia term na oznaczenie napisów

(wyrażeń) formalnych, które mogą

być traktowane jako nazwy obiektów

matematycznych.

• Niech τ będzie alfabetem języka pierwszego

rzędu.

• τ jest zbiorem stałych, symboli funkcyjnych i

symboli relacyjnych (predykatów).

• Każdy symbol ma jednoznacznie określony

charakter (stała, symbol funkcyjny, predykat).

• Każdy z symboli funkcyjnych i predykatów ma

określoną wartość (którą jest dodatnia liczba

całkowita).

• Język ma ustaloną nieskończoną listę

zmiennych.

• Termy języka to elementy

najmniejszego zbioru.

Przykłady termów:

• x1 * x1,
• x1 * (x2 * (x1 * (x2 * x1)))
• (x1 * (x1 * (x1 * (x1 * x1)))) * (x1 * (x2 * (x1 * (x2

* x1))))

W analogiczny sposób wprowadza się

termy w językach wyższych rzędów, a

także w bardziej skomplikowanych

logikach.

5. Programowanie logiczne w

Prologu

Nazywane także programowaniem w logice lub programowaniem w języku

logiki, jako metoda programowania deklaratywnego, w której

program podawany jest jako pewien zestaw zależności, a obliczenia są

dowodem pewnego twierdzenia w oparciu o te zależności.

Na przykład dla stwierdzenia, czy w danym grafie skierowanym istnieje

ścieżka z pewnego punktu do pewnego innego punktu zapisuje się

krawędzie jako relację:

edge(Skąd, Dokąd).

Zapis w Prologu:

connected(X, Y) :- X = Y.
connected(X, Y) :- edge(X,Z), connected(Z, Y).

Co czytamy następująco:

istnieje ścieżka z X do Y, jeśli X = Y
istnieje ścieżka z X do Y, jeśli dla jakiegoś Z istnieje krawędź z X do Z, oraz

ścieżka z Z do Y

(co nie oznacza drogi, należałoby użyć wówczas go()

Jak to możliwe, że komputer potrafi rozwiązać problem znając jedynie

jego opis a nie algorytm rozwiązania?

• Robert Kowalski w swoim artykule z roku 1979 zatytułowanym

Algorithm = Logic + Control
zwrócił uwagę na nowy punkt widzenia na pojęcie algorytmu.

• Dotychczas przez algorytm rozumiano sposób postępowania

prowadzący do rozwiązania problemu.

• Jednak dzięki zautomatyzowaniu procesu dowodzenia twierdzeń

logicznych, a szczególnie dzięki opracowaniu przez Robinsona w

roku 1965 zasady rezolucji, stało się możliwe automatyczne

wywnioskowanie rozwiązania na podstawie zbioru formuł

logicznych opisujących problem.

• Rozpatrzmy dla przykładu problem znajdowania najmniejszego

elementu w zbiorze liczb.

• Kiedy myślimy o nim w sposób imperatywny jawi się nam przed

oczyma program zawierający pętlę for-do, która przebiega

wszystkie elementy zbioru porównując je z najmniejszym

dotychczas znalezionym elementem.

• Natomiast stosując podejście deklaratywne

skupiamy się na warunku jaki musi spełniać element

zbioru, aby uznać go za najmniejszy.

• Szukamy więc takiego elementu zbioru, że nie

istnieje w zbiorze element od niego mniejszy.

• Warunek jaki ma spełniać szukany element

najmniejszy N, dla danego zbioru liczb Z, wyrazić

możemy formalnie w sposób następujący:

N w Z   i   nieprawda, że (X w Z   i   X < N),

gdzie:
w - warunek przynależności do zbioru,
< - relacja mniejszości między liczbami.

• Początkującemu programiście w Prologu największy

problem sprawia przestawienie się z imperatywnego

postrzegania algorytmu na deklaratywny, tj. z

wyobrażania sobie działających instrukcji na opis

warunków jakie musi spełniać rozwiązanie.

• Kiedy już opanuję się tę sztukę,

– to po wpisaniu do komputera opisu problemu (Logic z

równania Kowalskiego)

– i uruchomieniu procedury wnioskującej, np. zasady rezolucji

Robinsona (Control z tego samego równania),

– system wywnioskuje nam co jest rozwiązaniem naszego

problemu.

Co więcej, jeśli jest wiele rozwiązań, to wywnioskuje

je wszystkie po kolei.

6. Składnia w Prologu

Termy to wyrażenia służące nie do wyliczania wartości,

ale do wyrażania obiektów występujących w programie.

Niech stała jacek wyraża chłopca o imieniu Jacek,
a stała barbara dziewczynę o imieniu Barbara.

Aby zrozumieć zwrot:

"stała x wyraża obiekt O"
potrzebne jest pojęcie interpretacji, która każdej stałej

występującej w programie przypisuje pewien obiekt

(interpretujemy stałą jako ten obiekt).

W naszej interpretacji stałej jacek odpowiada konkretny chłopiec o

tym imieniu.

Możliwe są też inne interpretacje np. w której stałej jacek

odpowiada jedna z dwóch pacynek z dobranocki „Jacek i

Agatka".

Przykłady interpretacji termów i funktorów

INT – intepretacja

INT(jasio) =chłopiec o imieniu Jasio

INT(ojciec/1) =funkcja przypisująca osobie jej ojca,

INT(matka/1) =funkcja przypisująca osobie jej matkę,

INT(ojciec(jasio)) =ojciec Jasia,

INT(matka(jasio)) =matka Jasia,

INT(para(ojciec(jasio), matka(jasio))) =rodzice

Jasia,INT(matka(ojciec(jasio))) =babcia Jasia ze strony ojca.

• Bardziej formalnie, interpretacja jest funkcją, która

każdej stałej w programie przypisuje obiekt z

otaczającego świata i to zarówno rzeczywistego jak i

fikcyjnego, a nawet abstrakcyjnego.

• Jeśli Jacek i Barbara tworzą parę, to para ta stanowi

pewien obiekt inny niż np. para dwóch gołębi.

• Z tego powodu pary te muszą być w programie

wyrażone różnymi termami.

• Parę Jacka i Barbary wyrażać możemy termem:

para(jacek, barbara).

• A parę gołębi termem:

para-gołębi(samiec, samiczka).

• W termie tym występuje dwuargumentowy funktor

para, który spina dwa inne proste termy jacek i

barbara w jeden term złożony para(jacek,

barbara).

• Analogicznie ze stałych samiec i samiczka można

utworzyć term para-gołebi(samiec, samiczka)

reprezentujący parę dwóch gołębi.

• W naszej interpretacji funktorowi para odpowiada

dwuargumentowa funkcja, której wartością jest

obiekt będący parą dwóch obiektów będących jej

argumetami.

• Jeśli interpretację oznaczymy symbolem INT, to

obiekt będący interpretacją termu t oznaczać

będziemy symbolem INT(t), natomiast interpretację

n-argumentowego funktora f oznaczać będziemy

symbolem INT(f/n).

7. Unifikacja termów

W termach mogą występować zmienne.

Z formalnego punktu widzenia nie interpretuje się zmiennych

(jedynie stałe i funktory), ale na nasze potrzeby wystarczy

uznać, że zmiennej w termie odpowiada dowolny obiekt.

Pod zmienne występujące w termie można podstawiać inne termy.

Jeśli w termie ojciec(X),

który można zinterpretować

jako "każdy ojciec" (bo ojciec dowolnej osoby),

za zmienną X podstawimy stałą jasio, to otrzymamy term

ojciec(jasio),

czyli term reprezentujący już nie dowolnego ojca, ale konkretnie

ojca Jasia.

Unifikacja dwóch termów polega na znalezieniu takich podstawień

za zmienne występujące w tych termach, aby po ich wykonaniu

termy stały się identyczne.

Oczywiście nie zawsze takie podstawienia istnieją.

Dla przykładu termów

ojciec(X) i matka(Y)

nie da się zunifikować, bo trudno sobie wyobrazić by istniało jakieś

indywiduum będące czyimś ojcem i jednocześnie matką tej samej

osoby.

W Prologu do unifikacji dwóch termów służy predykat

=.

Podczas sprawdzenia warunku

t1=t2

albo termy zostaną zunifikowane i zostanie wykonane na nich

odpowiednie podstawienie zmiennych

albo, jeśli takie podstawienie nie istnieje, warunek nie będzie spełniony i

nastąpi niepowodzenie.

Dzięki unifikacji można rozkładać termy złożone na

prostsze wyrażenia.

Dla przykładu wykonując unifikację

para(jacek, barbara) = para(X, Y)

pod zmienną X zostanie podstawiony pierwszy element

pary, czyli stała jacek,

a pod zmienną Y drugi jej element, czyli stała barbara.

Jeśli podczas unifikacji pod pewną zmienną zostanie

podstawiony term zawierający tę zmienną, to w

wyniku takiego podstawienia powstanie nieskończony

term.

Na przykład w wyniku wykonania unifikacji:

X = f(X, g(X))

zostanie podstawiony nieskończony term:

f(f(f(...,  g(...)),  g(f(...,  g(...)))),  g(f(f(...,

 g(...)),  g(f(...,  g(...)))))),

gdzie ... oznacza nieskończony fragment

termu powielający strukturę całego termu.

Nie ma w Prologu:

• słów kluczowych,

• brak rozróżnienia we/wy

• brak funkcji

• brak zmiennych (klasycznych)

• brak jawnej sekwencyjności, czy

iteracyjności

Prolog dostarcza:

• metody strukturalizowania informacji, termy

• programowania deklaratywnego

• rekurencji, jak metody przetwarzania informacji

• unifikacji - mechanizmy dopasowywania

wzorców

• rezolucji - metody wnioskowani logicznego

• strategii sterowania wnioskowaniem

• Prolog jest językiem deklaratywnym.

• Jego deklaratywność polega na tym, że

programista deklaruje (wymienia)
jedynie obiekty konieczne do
rozwiązania problemu oraz związki, jakie
pomiędzy tymi obiektami zachodzą, w
postaci tzw. faktów oraz reguł.

• Zadanie do rozwiązania przedstawiane

jest w postaci celu.

Fakty

•

Fakty mogą opisywać obiekty

np. Jan lubi Marię

Fakt ten dotyczy dwóch obiektów: Jana i Marii

Zawiera też relację: lubi

Zapis tego faktu w Prologu: lubi(jan,maria).

Uwagi:
1.

Nazwy obiektów i relacji zaczynają się małymi

literałami

2.

Najpierw zapisuje się relację, a potem w nawiasach

okrągłych obiekty rozdzielone przecinkami

3.

Fakt kończy się kropką

Konwencja Prologowa

• Podczas definiowania związków pomiędzy

obiektami w formie faktów obowiązuje Konwencja
Prologowa:

– fakt pierwszy: osoba lubiąca
– Fakt drugi: osoba lubiana

Różne fakty: lubi(jan,maria) oraz lubi(maria, jan)

Przykłady faktów:
cenny(złoto) – złoto jest cenne
kobieta(janina) – Janina jest kobietą
posiada(jan,złoto) – Jan posiada złoto
ojciec(jan,maria) – Jan jest ojcem marii
daje(jan.gazeta,maria) – Jan daje gazetę marii

Interpretacja

• Z użyciem każdej nazwy wiąże się interpretacja

• O wyborze konkretnej interpretacji decyduje programista,

stąd ważna jest dokumentacja programów prologowych

• Nazwy obiektów ujętych w nawiasy okrągłe nazywa się

argumentami (nie ma nic wspólnego z potocznym słowem
racja w dyskusji)

• Nazwę relacji znajdującą się przed nawiasem okrągłym

nazywa się

predykatem

• Predykat ma wiele argumentów, np. predykat

– cenny

ma jeden argument: złoto,

– posiada

ma dwa argumenty: jan i złoto

– Nazwy obiektów i relacji sa całkowicie dowolne (decyduje

programista)

Relacje

• Mogą mieć dowolna liczbę argumentów
• Np. Chcemy zdefiniować predykat gra za

pomocą trzech argumentów:

Otrzymamy:

– gra(jan,maria,fudbol)
– gra(janina,staszek,badminton)

– Użycie wielu argumentów występuje w złożonych

opisach relacji (występujących w nich powiązań)

– W Prologu zbiór faktów nazywa się bazą faktów

(baza danych stałych)

Zapytania

• Kiedy zostaną fakty wprowadzone

(zdefiniowane) istnieje wówczas możliwość

zadawania o nie pytań

• W Prologu zapytanie wygląda tak samo jak

fakt, ale poprzedza się go specjalnym

symbolem ?-

• Np. ?- posiada(maria,gazeta) – czy Maria ma

gazetę? (czy w bazie faktów istnieje fakt

mówiący, że Maria ma gazetę)

• Nie jest to zapytanie o wszystkie gazety, ani

zapytanie o gazety w ogólności

• Po zadaniu pytania Prolog szuka w bazie faktów takich faktów, które

pasują do faktu użytego w zapytaniu

• Dwa fakty pasują do siebie jeżeli maja identyczne predykaty i argumenty

• Jeśli Prolog znajdzie fakt pasujący do zapytania odpowie

yes, w

przeciwny razie odpowie no

• Niech będzie następującą baza faktów:

lubi(jarek,ryby)
lubi(jarek,maria)
lubi(maria,ksiazka)
lubi(jan,ksiazka)
lubi(jan,francja)

Należy zadać pytania:

?- lubi(jarek,pieniadze)
no
?- lubi(maria,jarek)
no
?- lubi(maria, ksiazka)
yes

Zmienne

• Każda zmienna może być ukonkretniona (wiemy jakiemu

odpowiada obiektowi) lub nieukonkretniona

• Wszystkie nazwy zaczynające się z dużej litery traktowane

są w Prologu jako zmienne

• Np. ?-lubi(jan,X)

• Niech występuje baza faktów:

lubi(jan,kwiaty)
lubi(jan,maria)
lubi(pawel,maria)

• ?-lubi(JAN,x)
• X=kwiaty (następuje ukonkretnienie)
• ; - daje możliwość kontynuacji (wznowienia) przeszukiwania
• X=maria

Koniunkcje

• Czy Jan i Maria lubią się nawzajem?

• Można dać do wykazania Prologowi dwa cele (dwa zapytania)

– Czy Jan lubi Marię?

– Czy Maria lubi Jana?

Niech będzie baza faktów:

lubi(maria,czekolada)
lubi(maria,wino)
lubi(jan,wino)
lubi(jan,maria)

W Prologu spójnik i zapisuje się jako przecinek
?-lubi(jan,maria), lubi(maria,jan)
Oczywiście w tej bazie nie ma lubi(maria,jan), stąd będzie odpowiedź no

Czy istnieje coś co lubi Jan i lubi Maria?
W Prologu zadajemy to pytanie tak:

?-lubi(maria,X), lubi(jan,X)

Uwaga: każdy cel wstawia w bazie faktów zaznaczenie (zakładkę), ze coś

znalazł

Nawracanie

Czy istnieje coś co lubi Maria i jednocześnie lubi

to Jan?

1. W bazie faktów odszukiwany jest pierwszy cel.

Kiedy argument X jest nieukonkretniony
może pobrać dowolna wartość. Pierwszym
znalezionym dopasowaniem jest

lubi(maria,czekolada)

Prolog oznacza miejsce znalezienia faktu na

wypadek, gdyby to było potrzebne ponownie
(po wznowieniu przeszukiwania)

2. W bazie faktów poszukiwany jest fakt

lubi(jan,czekolada)

Stąd następnym celem jest

lubi(jan,X)

ale X=czekolada (X oznacza czekolada), a takiego faktu nie ma

w bazie faktów, więc Prolog stara się znaleźć inne
dopasowanie

lubi(maria,X)

Ale tym razem przeszukiwanie zaczyna się od ostatnio

zaznaczonego miejsca

Potrzebne jest jednak cofnięcie ukonkretnienia zmiennej, aby

Prolog mógł nadać inną wartość (następuje nawrót, stąd
mechanizm nawracania)

3. Oznaczone miejsce to lubi(maria,czekolada), więc od tego faktu

zaczyna się dalsze wyszukiwanie

Następny pasujący fakt to

lubi(maria,wino)

Zmienne X otrzymuje teraz wartość wino (X=wino)

Prolog ponownie zaznacza miejsce wystąpienia tego faktu w bazie

faktów

A następnie tak jak poprzedni stara się uzgodnić drugi cel, tym

razem szukając faktu

lubi(jan,wino)

Tym razem Prolog go znajduje cel został uzgodniony).
Pojawi się odpowiedni komunikat i miejsce zostaje oznaczone

W tej sytuacji znalezione są oba cele, zmiennej X odpowiada nazwa

wino (jest ukonkretniona)

Pierwszy cel spowodował zaznaczenia lubi(maria,wino),
a drugi cel spowodował zaznaczenia lubi(jan,wino)

Literatura

U. Nilsson, J. Ma luszynski: Logic, Programming and Prolog. John Wiley & Sons,

1990 (http://www.ida.liu.se/ ulfni/lpp/)

K. R. Apt From Logic Programming to Prolog. 1997.

K. Doets {From Logic to Logic Programming. MIT, 1994.

J. W. Lloyd {Foundations of Logic Programming. Springer, Berlin, wyd. 2, 1987.

K. R. Apt {Logic Programming. W: J. van Leeuwen, ed. Handbook of Theoretical

Computer Science. 1990, vol. B. 17/ 20

L. Sterling, E. Shapiro The Art of Prolog. MIT, wyd. 2, 1994.

F. Kluzniak, S. Szpakowicz Prolog for Programmers. Academic Press, 1985.

W. F. Clocksin, C. S. Mellish Programming in Prolog. Springer, 1994. (Prolog.

Programowanie. Wyd. Helion, 2003).

R. O'Keefe The Craft of Prolog. MIT, 1990.

M. Ben-Ari Logika matematyczna w informatyce, WNT

• Dziękuję za uwagę