Programowanie deklaratywne
PD
rok akademicki
2010/2011
W1
Wstęp do programowania deklaratywnego
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.
Wiedza i sposoby reprezentacji
wiedzy
2.
Metody reprezentacji wiedzy
3.
Reguły w reprezentacji wiedzy
4.
Rachunek predykatów
5.
Przekształcenia w rachunku
predykatów
6.
Formalny opis języka predykatów
7.
Definicja termu
8.
Formuły atomowe
1. Wiedza oraz sposoby jej
reprezentacji
• Reprezentacja wiedzy stanowi jeden z podstawowych problemów,
który jak dotychczas nie został jeszcze w pełni rozwiązany
• Wiedza składa się z
opisów, inaczej faktów, relacji i procedur
• Tak rozumianą wiedzę można reprezentować na różne sposoby
• opisy
stanowią zdania w jakimś języku, którego elementarnymi
składnikami są pierwotne cechy i pojęcia (służą one do identyfikacji i
rozróżniania obiektów i klas),
• baza opisów zawiera także reguły lub algorytmy wykorzystywane do
interpretacji danych wejściowych w konkretnych zastosowaniach
• relacje odzwierciedlają zależności i asocjacje (skojarzenia) pomiędzy
faktami w bazie wiedzy
• procedury zawierają sposoby na generowanie nowych faktów przy
wykorzystaniu faktów istniejących oraz procedur
2. METODY REPREZENTACJI WIEDZY
• Metody symboliczne:
reprezentacja proceduralna,
reprezentacja deklaratywna
• Metody niesymboliczne (np. sztuczne sieci neuronowe)
Reprezentacja proceduralna
polega na określeniu zbioru
procedur, działanie których reprezentuje wiedzę o dziedzinie
Reprezentacja deklaratywna
polega na określeniu zbioru
specyficznych dla rozpatrywanej dziedziny faktów , stwierdzeń i
reguł
Zaletą reprezentacji proceduralnej
jest duża efektywność
reprezentowania procesów np. zapisanie w postaci równania prawa fizyki
Zaletą reprezentacji deklaratywnej
jest z kolei łatwość opisu i
formalizacji
Podstawowe metody reprezentacji wiedzy
• Metody reprezentacji wiedzy zajmują się modelowaniem
świata rzeczywistego z wykorzystaniem komputerów
• Do najczęściej stosowanych metod reprezentacji wiedzy
zalicza się:
1) metody bazujące na bezpośrednim zastosowaniu
logiki: rachunku zdań, rachunku predykatów
2) metody wykorzystujące zapis stwierdzeń
3) metody wykorzystujące systemy regułowe (wektory
wiedzy)
4) metody z wykorzystaniem sieci semantycznych
5) metody oparte na ramach
6) metody używające modeli obliczeniowych
3. Reguły w reprezentacji wiedzy
• W SE stosowane są reguły odnoszące się do
konkretnych obiektów, jak też reguły obejmujące
pewien zbiór obiektów – tzw. reguły ogólne (mogą być
one spełnione przez różne obiekty zbioru),
• dzięki temu reguły ogólne umożliwiają znaczne
zwiększenie stopnia ogólności utworzonej bazy wiedzy
(uzyskuje się to rozpatrując elementy stwierdzeń nie
jako wartości stałe, lecz jako zmienne, np.
IF (@syn,jest_synem,@ojciec) AND
(@ojciec,jest_synem,@dziadek)
THEN (@syn,jest_wnukiem,@dziadek)
przy czym napisy poprzedzone symbolem @ sa
traktowane jako zmienne
Generowanie reguł z reguły ogólnej
• Podczas wnioskowania zmienne są zastępowane
odpowiednimi stałymi określonymi w wyniku dopasowania
reguły do istniejącego zbioru stwierdzeń
• jest to proces tzw unifikacji, np. można zmienne zastąpić
stałymi:
@syn Jan, @ojciec Adam, @dziadek Jacek
co prowadzi do reguły:
IF(Jan,jest_synem,Adam)
AND (Adam,jest_synem,Jacek)
THEN (Jan,jest_wnukiem,Jacek)
W ten prosty sposób na podstawie jednej reguły zawierającej
zmienne można generować wiele reguł dopasowanych do
danej bazy faktów
4. Rachunek predykatów
• Rachunek predykatów stanowi podstawę programowania w
języku logiki
• Rachunek predykatów jest rozszerzeniem rachunku zdań
poprzez wprowadzenie kwantyfikatorów :
- dla każdego,
- istnieje takie,że
• Wyrażenie W(x), w którym występuje zmienna xi które staje się
zdaniem prawdziwym lub fałszywym, gdy w miejsce x podstawimy
wartość zmiennej x nazywa się funkcją zdaniową lub predykatem
• Predykat składa się z nazwy i dowolnej liczby argumentów, które
nazywa się termami
• termami mogą być stałe (symbole) alfanumeryczne, jak też
numeryczne i zmienne oraz wyrażenia
• W wyniku podstawienia stałych za zmienne otrzymuje się
zdania prawdziwe lub fałszywe
• przyporządkowanie termom symboli, a nazwie relacji między
obiektami prowadzi do zdefiniowania semantyki języka
predykatów
• zaletą predykatów jest prostota i klarowność interpretacji
zdań
• Podstawowymi elementami języka predykatów są:
1) alfabet teorii (stałe, zmienne, symbole operacji
logicznych),
2) termy (każda zmienna jest termem, stała
będąca obiektem jest termem, itp.),
3) formuły atomowe,
4) formuły
Język rachunku predykatów pierwszego rzędu
• Ważną rolę odgrywają tzw klauzule, które są
alternatywami literałów, przy czym literałem
nazywamy predykat albo zanegowany
predykat
• Wśród formuł wyróżnia się pewien ich
podzbiór, a mianowicie poprawnie zbudowane
formuły rachunku predykatów, do których
zaliczamy literały oraz poprawnie zbudowane
formuły rachunku predykatów połączone
spójnikami logicznymi: , , , , a także
objęte kwantyfikatorami: ,
• Istnieje twierdzenie, które mówi, ze każdy
zbiór poprawnie zbudowanych formuł można
przekształcić w zbiór klauzul
5. Przekształcenia w rachunku predykatów
1)
usuniecie symbolu implikacji,
2)
ograniczenie do literału zakresu negacji, rozdział
zmiennych,
3)
usunięcie kwantyfikatorów szczegółowych,
4)
przekształcenie w formułę prefiksową,
5)
przekształcenie w koniunkcyjna postać normalną,
6)
usuniecie kwantyfikatorów ogólnych,
7)
usuniecie symbolu koniunkcji,
8)
przemianowanie zmiennych
6. Formalny opis języka predykatów
• Alfabet rachunku predykatów pierwszego rzędu tworzą:
a) stałe (Const), które dzieli się na:
1) stałe oznaczające obiekty (symbole podstawowych
elementów danego rachunku IConst)
2) nazwy funkcji i-miejscowych (symbole funkcji FConst)
3) nazwy predykatów i-miejscowych (symbole
predykatów PConst)
b) zmienne (Var)
c) symbole operacji logicznych: , , , , a także
kwantyfikatory: (dla każdego), (istnieje)
d) termy (które są argumentami predykatów jako stałe,
zmienne, funkcje)
7. Definicja termu
Termy opisuje się używając definicji
rekurencyjnej jako obiekty o
następujących właściwościach:
1) każda swobodna zmienna jest termem
2) każda stała oznaczająca obiekt jest termem
3) jeśli s,t T
m
, to (st) T
m
, przy czym (st) oznacza
rezultat złożenia dwóch termów
4) jeśli f FConst, a t1, t2, ..., ti są termami , to f(t1,
t2, ...,
ti) tez jest termem
8. Formuły atomowe
• Formuły atomowe są podstawowymi elementarnymi
formułami zbudowanymi na podstawie prostych
predykatów bez użycia symboli operacji logicznych
• Formuły atomowe można zdefiniować następująco:
jeśli p PConst i t1, t2, ..., ti T
m
to p(t1,t2,...,ti) AForm
• Formuły (Form) są formułami zbudowanymi z uzyciem
podstawowych symboli operacji logicznych, co można
zdefiniować nastepujaco:
jeśli A,B Form to A,B, A, B, AB, A B, A B Form
jeśli A Form i x Var to
x
A i
x
A Form
Przykład formuły rachunku predykatów
• Przekształcenie poprawnie zbudowanej formuły rachunku
predykatów w klauzulę
• Niech
x
{P(x)
{
y
[P(y)
P(f(x,y))]
y
[Q(x,y)
P(y)]}}
1) w pierwszym kroku pozbywamy się symbolu implikacji, korzystając ze
znanego w logice przekształcenia
(U W
U W)
w wyniku czego otrzymuje się
x
{ P(x)
{
y
[ P(y)
P(f(x,y))]
y
[ Q(x,y)
P(y)]}}
2) w drugim kroku ogranicza się do literału zakres negacji:
x
{ P(x)
{
y
[ P(y)
P(f(x,y))]
y
[Q(x,y)
P(y)]}}
3) dokonuje się rozdziału zmiennych tzn każdemu
kwantyfikatorowi przypisuje się inna zmienna:
x
{ P(x)
{
y
[ P(y)
P(f(x,y))]
y
[Q(x,z)
P(z)]}}
4) usuwa się kwantyfikator szczegółowy
otrzymując:
x
{ P(x)
{
y
[P(y)
P(f(x,y))]
[Q(x,g(x))
P(g(x))]}}
5) następnie następuje przeniesienie kwantyfikatorów
ogólnych na lewa stronę przekształconego wyrażenia
muzykując formułę prefiksową:
x
y
{ P(x)
{
[P(y)
P(f(x,y))]
[Q(x,g(x))
P(g(x))]}}
6 i 7) wreszcie dokonuje się
przekształcenia w koniunkcyjna postać
normalną korzystając ze znanego
przekształcenia z logiki
A (B C) D E (A B C) (A D)
(A E)
co po wykorzystaniu w rozważanym
przykładzie prowadzi do postaci:
[P(x)P(y)
P(f(x,y))]
P(x)[Q(x,g(x)
)
]
[P(x)
P(g(x))]}}
8) z ostatniego wyrażenia po usunięciu symbolu koniunkcji
otrzymuje się postać klauzulowa:
P(x)P(y)
P(f(x,y))
P(x)Q(x,g(x))
P(x)
P(g(x))]
po czym dla wygody można przemianować zmienne (dziewiąty
krok)
P(x
1
)P(y
1
)
P(f(x
1
,y
1
))
P(x
2
)Q(x
2
,g(x
2
))
P(x
3
)
P(g(x
3
))]
w rezultacie otrzymuje się klauzulowa postać zawierającą
predykaty, które łatwo jest implementować np. w PROLOGu
Kompilatory Prologu
SICStus Prolog
(Swedish Institute of Computer Science)
Profesjonalna (p latna) realizacja Prologu,
zgodna ze standardem ISO,
http://www.sics.se/isl/sicstuswww/site/index.html
SWI Prolog
Wolne oprogramowanie (free software),
http://www.swi-prolog.org/
MIM Prolog
Malenka realizacja pelnego Prologu, MS DOS.
Zastosowania Prologu
NASA (Clarissa):
• przeglądarka dla astronautów sterowana głosem
• implementacja: głownie SICStus Prolog
• instalacja na międzynarodowej stacji kosmicznej w
styczniu 2005
• pierwsze użycie: wyprawa 27 czerwca 2005
Ericsson AB (Network Resource Manager)
• konfiguracja i zarządzanie sieciami teleinformatycznymi
• implementacja: C++, SICStus Prolog, Java
• Prolog użyty we wczesnej fazie tworzenia prototypu
oraz w końcowej fazie (optymalizacja)
Zastosowania w medycynie
• m.in. Projekt poznania ludzkiego genomu Human
Genome Project
PFlow
system przepływu dokumentów (ang. workflow system)
opracowany na potrzeby belgijskiego urzędu zatrudnienia
w codziennym użyciu od września 2000 roku
języki programowania: Mercury, Java oraz XML
główny serwer napisany w języku Mercury,
moduł obsługi klienta zaimplementowany w Javie
Mercury { w pełni deklaratywny język programowania w
logice}
zdaniem autorów systemu:
użycie deklaratywnego języka programowania w logice do
utworzenia jądra systemu było podstawą odniesionego
sukcesu.
Windows NT
konfigurator sieci (David Hovel) (deklaratywne)
informacje przechowywane w postaci prologowych
faktów
wynik zapytania prologowego (znalezienie najlepszej
konguracji) zapamiętywany w bazie danych NT
wprowadzenie nowego produktu { minuty pracy}
Leśnictwo
• modelowanie procesu rozwoju drzew, lasu
(Wlk.Brytania)
,,Prolog is clearly a superior tool for rule-based
construction algorithms„ (David Hovel)
SWI Prolog
• Współcześnie jest dostępnych wiele
implementacji Prologu, w tym swobodnie
dostępne kompilatory Prologu:
– Jan Wielemaker, SWI-Prolog,
– Daniel Diaz, GNU-Prolog,
• Podstawowym interfejsem jest w SWI powłoka.
• W powłoce pracuje się podobnie jak w powłoce
unixowej, oczywiście z uwzględnieniem specyfiki
Prologu.
Programy w Prologu -
podsumowanie
Elementy składniowe programu:
– atomy: stałe znakowe,
– niewiadome/szukane (tzw. zmienne logiczne),
– termy: symbole funkcyjne przyjmujące argumenty
Program składa się z
• szeregu klauzul (ang. clause), wyróżniamy:
– fakty (klauzule proste)
– reguły (klauzule złożone)
• oraz celu (ang. goal)
Uruchamianie
programu
Do uruchomienia programu należy
załadować plik z kodem w Prologu przy
pomocy predykatu consult/1 (skrót
[nazwa].)
Operację tę należy powtarzać po każdej
modyfikacji kodu.
• SWI dostarcza przede wszystkim
zaawansowanej powłoki, wyposażonej
w bibliotekę GNU ReadLine.
• Cennym uzupełnieniem jest edytor GNU
Emacs ze środowiskiem edycyjnym
(trybem) prolog.el.
• SWI w wersji rozszerzonej o środowisko
XPCE dostarcza również narzędzi
programistycznych, takich jak
wbudowany edytor emacs.
Literatura
U. Nilsson, J. Małuszynski: 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.
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. Warszawa 2005.
F. Kluźniak, S. Szpakowicz: Prolog. WNT. Warszawa 1983
• Dziękuję za uwagę