pp3-print.pdf

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 Deﬁniowania faktów dotycz acych obiektów i zwi azków miedzy nimi.

z Deﬁniowania 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 uniﬁkacj a (uzgadnianiem).

Jezeli baza wiedzy zawiera tylko fakty, to uniﬁkacja 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:

Inne pliki z tego folderu:

Inne foldery tego chomika: