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
jtchorzewski@interia.pl
Jerzy.Tchorzewski@ap.siedlce.pl
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ę