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

[e-mail]

[e-mail]

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, AB, 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,

http://www.swi-prolog.org

– Daniel Diaz, GNU-Prolog,

http://gnu-prolog.inria.fr

• 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ę