Programowanie deklaratywne
__________________________________________________________________________________________
PROGRAMOWANIE DEKLARATYWNE
INFORMATYKA, SEM.5
WYKŁAD: 30 GODZIN
ĆWICZENIA LAB. : 30 GODZIN
________________________________________________________________________
LITERATURA
1. W.F. Clocksin, C.S. Mellish
Prolog. Programowanie.
Wydawnictwo Helion, Gliwice, 2003
2. Eugeniusz Gatnar, Katarzyna Stąpor
PROLOG język sztucznej inteligencji
Wydawnictwo PLJ, Warszawa 1991.
3. Jerzy Bartoszek, Jolanta Cybulko
Wydawnictwo Politechniki Poznańskiej. Poznań 1999
4. Grażyna Brzykcy, Adam Meissner
Programowanie w PROLOGu i programowanie funkcyjne.
Materiały do ćwiczeń
5. J. W. Lloyd
Foundations of Logic Programming.
Springer Ferlag, wyd.2, 1987
6. Kees Doets
From Logic to Logic Programming
The MIT Press, 1994
7. Ulf Nilsson, Jan Małuszyński
Logic, Progamming and Prolog
http://www.ida.liu.se/~ulfni/lpp
I. WPROWADZENIE
1. Programowanie deklaratywne a programowanie tradycyjne (imperatywne).
Programowanie imperatywne:
· Program instruuje komputer JAK przeprowadzić obliczenia.
· Zorientowane na rozwiązywanie problemów natury numerycznej, symbole posiadają tylko jedno znaczenie – wartość liczbową.
· Logika informacji (tzn. logiczne związki między danymi potrzebnymi do rozwiązania zadania) jest powiązana ze sterowaniem tą informacją; symbolicznie:
algorytm = logika + sterowanie
gdzie
logika – definicja problemu do rozwiązania
(JAKI problem),
sterowanie – sposób rozwiązania problemu (JAK).
· Ważny problem weryfikacji: sprawdzenie poprawności programu (czy wyznacza żądaną funkcję)
Programowanie deklaratywne:
· Uproszczenie zagadnienia poprawności programu przez oddzielenie logiki od sterowania:
programista – specyfikacja logicznej części algorytmu.
system – dostarczenie mechanizmu sterowania.
· Zorientowane na przetwarzanie symboliczne, o znaczeniu symboli decydują operacje, za pomocą których są przetwarzane.
· Rodzaje:
– programowanie w logice: wykorzystuje logikę elementarną jako język
programowania
– programowanie funkcyjne: sposób przetwarzania, w którym program jest
matematycznie poprawną definicją funkcji.
PROGRAMOWANIE
(deskryptywne, opisowe)
IMPERATYWNE
Programowanie
w logice
funkcyjne
Podstawo-wa zasada
JAK rozwiązać problem
(obliczyć wynik)
JAKI problem (CO ma być rozwiązane)
Program
Ciąg poleceń (instrukcji), z których każda opisuje pewną akcję, jaką ma wykonać komputer.
Zbiór zdań traktowanych jako zbiór aksjomatów pewnej teorii
Zbiór definicji funkcji
Obliczenie
Wykonanie ciągu poleceń dla danych wejściowych
Dowód twierdzenia (zapytania)
Wyznaczanie wartości wskazanej funkcji dla zadanych argumentów
Przykłady
języków
Fortran, Algol, Basic, Pascal, C/C++, Java
ADA
Prolog, Gödel, Life
LISP, Scheme. Haskell, ML
Zalety
Sprawne, wyspecjalizowane programy
Ogólne, czytelne, poprawne programy.
PRZYKŁA D
programu w języku imperatywnym (Pascal) i w języku deklaratywnym (Prolog).
ZASTOSOWANIA:
Ø przetwarzanie języka naturalnego i formalnego
Ø automatyczne dowodzenie twierdzeń
Ø symboliczne rozwiązywanie równań
Ø relacyjne bazy danych
Ø systemy ekspertowe
Ø analiza struktur biochemicznych
Ø automatyzacja projektowania
Ø planowanie akcjiII. PROGRAMOWANIE W LOGICE.
RYS HISTORYCZNY
1965 J. Robinson: metoda rezolucji z unifikacją.
1972 Powstanie języka PROLOG (PROgrammation en LOGique) na uniwersytecie w
Marsylii w zespole pod kierunkiem Alaina’a Colmerauera i Phillipe’a Roussel’a.
1973 Powstanie (również w Marsylii) pierwszego kompilatora PROLOGu napisanego
w ALGOLu.
1974 R. Kowalski: wprowadzenie SLD-rezolucji
1977 Edinburgh Prolog (D.H.D. Warren)
1982 Wybór programowania w logice jako podstawy japońskiego projektu FGCS (Fifth
Generation Computer System)
1984 Journal of Logic Programming
1986 Constraint Logic Programming (Programowanie w logice z ograniczeniami-więzami)
1. REZOLUCJA W RACHUNKU ZDAŃ.
KLASYCZNY RACHUNEK ZDAŃ – SYNTAKTYKA
DEF. Język rachunku zdań
(i) nieskończony, ale przeliczalny zbiór zmiennych zdaniowych
(ii) zbiór stałych logicznych
LOG =
(iv) zbiór wyrażeń rachunku zdań –,
gdzie dla dowolnego zbioru W , oznacza zbiór wszystkich skończonych ciągów
elementów zbioru W
DEF. Formuły.
Zbiorem FOR formuł rachunku zdań nazywamy najmniejszy zbiór taki, że
(i) ,
(ii) jeżeli , to ,
(iii) jeżeli , to
Reguły opuszczania nawiasów:
1) opuszczamy zewnętrzne nawiasy,
2) uwzględniamy siłę wiązania spójników logicznych ;
spójniki według siły wiązania poczynając od najsilniejszego:
a)
b)
c)
PRZYKŁAD 1.1.
Opuszczanie nawiasów w formułach.
KLASYCZNY RACHUNEK ZADAŃ – SEMANTYKA
DEF. Wartościowanie.
1. Wartości logiczne : 1 (prawda), 0 (fałsz)
2. Wartościowaniem nazywamy funkcję
3. Funkcją logiczną nazywamy funkcję .
Określamy funkcje:
i
następująco:
x
Wujek_Misiek