pp3-print.pdf
(
203 KB
)
Pobierz
Paradygmaty programowania cz. III
Paradygmaty programowania cz. III
Marcin Szpyrka
Katedra Automatyki, AGH w Krakowie
Instytut Fizyki, UJK w Kielcach
2010/11
Marcin Szpyrka
Paradygmaty programowania cz. III
1/63
Literatura
[1] Dennis Merritt: Adventure in Prolog, Amzi, 2004
http://www.amzi.com/AdventureInProlog
[2] Quick Prolog:
http://www.dai.ed.ac.uk/groups/ssp/bookpages/quickprolog/quickprolog.html
[3] W. F. Clocksin, C. S. Mellish: Prolog. Programowanie. Helion, 2003
[4] SWI-Prolog’s home: http://www.swi-prolog.org
[5] Learn Prolog Now!: http://www.learnprolognow.org
[6] Ulf Nilsson, Jan Maluszy nski: Logic, Programming and Prolog, John Wiley &
Sons Ltd., pdf, http://www.ida.liu.se/ ulfni/lpp
[7] http://home.agh.edu.pl/ ligeza/wiki/prolog
[8] http://www.im.pwr.wroc.pl/ przemko/prolog
Marcin Szpyrka
Paradygmaty programowania cz. III
2/63
Prolog
Prolog jest jezykiem programowania w logice. Jest on oparty na rachunku
predykatów pierwszego rzedu. Prolog jest jezykiem deklaratywnym. Prolog został
opracowany w 1971 roku na Uniwersytecie w Marsylii. Współczesnie dostepnych
jest kilkadziesi at implementacji Prologu. Na zajeciach stosowany bedzie kompilator
SWI: http://www.swi-prolog.org
Programowanie w Prologu składa sie z:
z
Definiowania faktów dotycz acych obiektów i zwi azków miedzy nimi.
z
Definiowania reguł dotycz acych obiektów i zwi azków miedzy nimi.
z
Zadawania zapyta n o obiekty i zwi azki miedzy nimi.
Predykat
Predykat jest funkcj a okreslon a w rozwazanym zbiorze obiektów (uniwersum),
o wartosciach logicznych (prawda, fałsz).
Marcin Szpyrka
Paradygmaty programowania cz. III
3/63
Fakty
Fakty s a najprostsz a form a zapisywania predykatów w Prologu. S a one podobne do
rekordów zapisywanych w bazach danych i zawieraj a informacje o swiecie, którego
dotyczy rozwi azywany problem.
1
pred
(
arg1
,
arg2
, ...
argN
).
gdzie:
zpred
– nazwa predykatu,
zarg1, ...
– argumenty predykatu,
zN
– arnosc predykatu,
z
kropka – znak ko ncz acy zapis predykatu w Prologu.
2
kobieta
(
ola
).
3
mezczyzna
(
tomek
).
4
mezczyzna
(
max
).
5
rodzic
(
ola
,
max
).
6
rodzic
(
tomek
,
max
).
7
rodzice
(
max
,
tomek
,
ola
).
8
adres
(
max
,
kwiatowa
,7).
Powyzszy kod zapisany w pliku z rozszerzeniem pl stanowi przykład prostego
programu w prologu.
Marcin Szpyrka
Paradygmaty programowania cz. III
4/63
SWI-Prolog – przykład pracy interaktywnej
1
$ swipl
2
Welcome to SWI
-
Prolog
(
Multi
-
threaded
,
Version
5.6.47)
3
...
4
For help
,
use
?-
help
(
Topic
).
or
?-
apropos
(
Word
).
5
?- [
przyklad01
].
6
% przyklad01 compiled 0.00 sec, 1,824 bytes
7
Yes
8
?-
kobieta
(
ola
).
9
Yes
10
?-
kobieta
(
ela
).
11
No
12
?-
kobieta
(
X
).
13
X
=
ola
14
?-
mezczyzna
(
X
).
15
X
=
tomek
;
16
X
=
max
17
?-
rodzic
(
Y
,
max
).
18
Y
=
ola
;
19
Y
=
tomek
20
?-
adres
(
max
,
X
,
Y
).
21
X
=
kwiatowa
,
22
Y
= 7
23
?-
adres
(
ola
,
X
,
Y
).
24
No
25
?-
halt
.
Marcin Szpyrka
Paradygmaty programowania cz. III
5/63
Termy
Argumentem predykatu w Prologu moze byc dowolny poprawny Term. Podstawowe
termy w Prologu to:
z
liczby całkowite,
z
atomy – stałe tekstowe rozpoczynaj ace sie z małej litery,
z
zmienne – nazwa rozpoczynaj aca sie od wielkiej litery lub znaku podkreslenia,
z
struktury – złozone struktury danych (analogia do struktur w jezyku C).
Dostepne z Prologu znaki, z których mozemy budowac termy to: małe i wielkie litery
alfabetu łaci nskiego, cyfry oraz symbole
+ -
*
/ \ ^ , . ~ : ? @ # $ &
Jezeli chcemy, aby atom rozpoczynał sie z wielkiej litery lub aby zawierał spacje, to
musi zostac umieszczony w pojedynczych apostrofach, np.:
1
’Ala’
2
’taki sobie atom’
3
’Jan Kowalski’
Marcin Szpyrka
Paradygmaty programowania cz. III
6/63
Zapisywanie faktów – przykład
biuro
1
pomieszczenie
(
biuro
).
2
pomieszczenie
(
hol
).
3
pomieszczenie
(
piwnica
).
4
pomieszczenie
(
kuchnia
).
5
pomieszczenie
(
salon
).
6
polozenie
(
biurko
,
biuro
).
7
polozenie
(
jablko
,
kuchnia
).
8
polozenie
(
latarka
,
biurko
).
9
polozenie
(
pralka
,
piwnica
).
10
polozenie
(
koc
,
pralka
).
11
polozenie
(
brokuly
,
kuchnia
).
12
polozenie
(
krakersy
,
kuchnia
).
13
polozenie
(
komputer
,
biuro
).
14
drzwi
(
biuro
,
hol
).
15
drzwi
(
kuchnia
,
biuro
).
16
drzwi
(
hol
,
salon
).
17
drzwi
(
kuchnia
,
piwnica
).
18
drzwi
(
salon
,
kuchnia
).
19
jadalne
(
jablko
).
20
jadalne
(
krakersy
).
21
niesmaczne
(
brokuly
).
22
jestem
(
kuchnia
).
hol
kuchnia
piwnica
salon
Przykład z: http://www.amzi.com/AdventureInProlog
Marcin Szpyrka
Paradygmaty programowania cz. III
7/63
Proste zapytania
z
Zapytania w Prologu s a realizowane na zasadzie dopasowywania wzorców.
Wzorzec z zapytania, do którego chcemy dopasowac odpowiedz nazywany jest
celem. Jezeli w bazie wiedzy, któr a dysponuje Prolog znajduje sie fakt pasuj acy
do celu, to zapytanie ko nczy sie sukcesem.
z
Dopasowywanie wzorców w Prologu nazywane jest unifikacj a (uzgadnianiem).
Jezeli baza wiedzy zawiera tylko fakty, to unifikacja ko nczy sie sukcesem jezeli:
– nazwy predykatów w celu i bazie wiedzy s a takie same,
– oba predykaty maj a tak a sam a arnosc,
– wszystkie argumenty tych predykatów s a takie same.
z
Cele mog a byc uogólniane przez zastosowanie zmiennych.
Jezeli cel zawiera zmienn a, to na etapie uzgadniania (przy porównywaniu
argumentów) pasuje ona do dowolnego termu. Po uzgodnieniu zmienna jest
wi azana z odpowiedni a wartosci a.
Marcin Szpyrka
Paradygmaty programowania cz. III
8/63
Nawroty
1
?- [
mieszkanie
].
2
% mieszkanie compiled ...
3
?-
polozenie
(
Co
,
kuchnia
).
4
Co
=
jablko
;
5
Co
=
brokuly
;
6
Co
=
krakersy
;
7
?-
polozenie
(
Co
,
Gdzie
).
8
Co
=
biurko
,
9
Gdzie
=
biuro
;
10
Co
=
jablko
,
11
Gdzie
=
kuchnia
;
12
Co
=
latarka
,
13
Gdzie
=
biurko
;
14
Co
=
pralka
,
15
Gdzie
=
piwnica
;
16
Co
=
koc
,
17
Gdzie
=
pralka
;
18
Co
=
brokuly
,
19
Gdzie
=
kuchnia
;
20
Co
=
krakersy
,
21
Gdzie
=
kuchnia
;
22
Co
=
komputer
,
23
Gdzie
=
biuro
24
?-
1
polozenie
(
biurko
,
biuro
).
2
polozenie
(
jablko
,
kuchnia
).
3
polozenie
(
latarka
,
biurko
).
4
polozenie
(
pralka
,
piwnica
).
5
polozenie
(
koc
,
pralka
).
6
polozenie
(
brokuly
,
kuchnia
).
7
polozenie
(
krakersy
,
kuchnia
).
8
polozenie
(
komputer
,
biuro
).
Kiedy Prolog próbuje zrealizowac cel, (jak
w powyzszych przykładach), przeszukuje
baze wiedzy i zaznacza miejsce, w którym
sie to udało. Wybranie srednika oznacza,
ze przeszukiwanie bedzie kontynuowane
od miejsca zaznaczenia, w celu
znalezienia kolejnych ropzwi aza n.
Marcin Szpyrka
Paradygmaty programowania cz. III
9/63
Złozone cele – spójnik i
z
Proste cele w Prologu mozna ł aczyc ze sob a za pomoc a przecinka, konstruuj ac
cele złozone. Przecinek pełni role spójnika i.
z
Jezeli ta sama zmienna pojawia sie w zapytaniu wiecej niz jeden raz, to musi
miec uzgodnione te same wartosci we wszystkich miejscach, w których
wystepuje.
z
Zakres zmiennej jest ograniczony do zapytania, w którym wystepuje. W innym
zapytaniu zmienna o takiej samej nazwie moze miec uzgodnion a inn a wartosc.
1
?-
polozenie
(
X
,
kuchnia
),
jadalne
(
X
).
2
X
=
jablko
;
3
X
=
krakersy
;
4
No
5
?-
„Znajdz jakies X znajduj ace sie w kuchni i sprawdz czy jest jadalne. Jesli nie to
nawróc, znajdz inne X znajduj ace sie w kuchni i sprawdz czy jest jadalne. Powtarzaj
dopóki cel nie zostanie spełniony lub nie ma wiecej zadnych X-ów znajduj acych sie
w kuchni.”
Przy realizacji złozonego celu Prolog próbuje spełniac kolejne podcele od lewej do
prawej strony. Przy realizacji kolejnych podcelów obowi azuj a uzgodnienia wartosci
zmiennych zrealizowane we wczesniejszych podcelach.
Marcin Szpyrka
Paradygmaty programowania cz. III
10/63
Plik z chomika:
inf.ujk
Inne pliki z tego folderu:
primes.hs
(0 KB)
math.hs
(0 KB)
zadanie1_6.hs
(0 KB)
pp7-print.pdf
(118 KB)
pp6-print.pdf
(230 KB)
Inne foldery tego chomika:
prolog
Zgłoś jeśli
naruszono regulamin