===== -. Programowanie w Prologu ===== ==== Programowanie nieklasyczne ==== Prolog NIE jest klasycznym językiem programowania. Nie ma w nim: * słów kluczowych (typu IF THEN ELSE, DO WHILE, GOTO), * brak rozróżnienia we/wy w sensie klasycznego wywoływania funkcji, * brak funkcji, (można jednak prowadzić proste obliczenia; funkcje mogą być zastępowane predykatami), * brak instrukcji podstawienia/przypisania; inne rozumienie zmiennych, * brak jawnej sekwencyjności, czy iteracyjności (z małymi wyjątkami), * brak dualizmu dane/program! Prolog dostarcza: * metody strukturalizowania informacji, //termy//, * programowania //deklaratywnego//, * //rekurencji//, jak metody przetwarzania informacji, * //unifikacji// - mechanizmy dopasowywania wzorców, * //rezolucji// - metody wnioskowani logicznego, * strategii sterowania wnioskowaniem. ==== Budowa programów ==== Elementy składniowe programu: * //stałe//: stałe znakowe a także liczby (atomy), * //niewiadome/szukane// (odpowiadają tzw. zmiennym logicznym, które __nie__ mają zbyt wiele wspólnego ze zmiennymi w klasycznych językach programowania), * //termy//: symbole funkcyjne wraz z argumentami, obiekty strukturalnie złożone. Program składa się z: * szeregu //klauzul// (ang. //clause//), wyróżniamy: * //fakty// (klauzule proste, formuły atomowe/atomiczne), * //reguły// (klauzule złożone), * oraz //celu// (ang. //goal//). ==== Prosty program ==== **Ćwiczenie** Proszę przyjrzeć się poniższemu, prostemu programowi (klasyczny przykład //Rodzina//). rodzic(kasia,robert). rodzic(tomek,robert). rodzic(tomek,eliza). kobieta(kasia). kobieta(eliza). mezczyzna(tomek). mezczyzna(robert). Proszę uruchomić [[https://swish.swi-prolog.org/|SWISH]] i wpisać w nim podobny program, dotyczący własnej (albo innej) rodziny. Program jest kompilowany, a zawarta w nim wiedza dodawana do bazy wiedzy dostępnej z powłoki SWI. Można to sprawdzić: ?- kobieta(X). Po ukazaniu się 1. odpowiedzi należy wcisnąć klawisz średnika (;). ==== Wyświetlanie bazy wiedzy ==== **Ćwiczenie** Sprawdzić działanie predykatu ''listing/0''. Sprawdzić działanie predykatu ''listing/1'': ?- listing(rodzic). W sytuacjach kiedy nie interesują nas wartości pewnych szukanych w predykacie, możemy użyć tzw. szukanych anonimowych. Na przykład: ''czy Robert ma rodziców?'' ?- rodzic(_,robert). ==== Zadawanie celu (pytań) ==== **Ćwiczenie** Systemowi można teraz zadawać pytania, cele do zrealizowania. Kto jest mężczyzną? ?- mezczyzna(X). Czy tomek jest mężczyzną? ?- mezczyzna(tomek). Czy reksio jest mężczyzną? ?- mezczyzna(reksio). Czy kasia jest rodzicem roberta? ?- rodzic(kasia,robert). Czyim rodzicem jest kasia? ?- rodzic(kasia,X). Czy zamiast X można wpisać inny symbol? Jaki? Kto jest rodzicem robert? ?- rodzic(Y,robert). 8-) Czy zamiast ''Y'' można wpisać inny symbol? ==== Rozbudowa programu ==== **Ćwiczenie** Proszę rozbudować program do poniższej, analogicznej (co do liczby osób i zależności) formy: rodzic(kasia,robert). rodzic(tomek,robert). rodzic(tomek,eliza). rodzic(robert,anna). rodzic(robert,magda). rodzic(magda,jan). kobieta(kasia). kobieta(eliza). kobieta(magda). kobieta(anna). mezczyzna(tomek). mezczyzna(robert). mezczyzna(jan). 8-) Czy kolejność wpisywania linii ma znaczenie? 8-) Jeżeli koniunkcję celów oznaczamy przecinkiem, to jak zapytać kto jest matką, a kto ojcem roberta? ==== Czy Prolog jest po polsku? ==== **Ćwiczenie** Proszę spróbować dopisać do programu takie linijki: famme(kasia). homme(krzys). parent(kasia,krzys). 8-) Czy nazwa użytych symboli wpływa na działanie programu? Jakie są ograniczenia na używane symbole? ==== Reguły wnioskowania ==== **Ćwiczenie** Proszę dopisać poniższe reguły (klauzule złożone) i sprawdzić ich działanie. matka(X,Y) :- rodzic(X,Y), kobieta(X). ojciec(X,Y) :- rodzic(X,Y), mezczyzna(X). 8-) Proszę zdefiniować reguły opisujące: brata, siostrę, dziadka i babcię. Proszę dokładnie sprawdzić ich działanie. Jaki pojawia się problem przy bracie/siostrze? Uwaga na operator: ''\='' Proszę się zastanowić nad własnymi regułami opisującymi relacje w rodzinie. ==== Reguły rekurencyjne ==== **Ćwiczenie** Rekurencja jest jednym z podstawowych mechanizmów programowania w Prologu. Proszę się przyjrzeć regułom opisującym przodka: przodek(X,Y) :- rodzic(X,Y). przodek(X,Z) :- rodzic(X,Y), przodek(Y,Z). Te dwie klauzule, w tym przypadku reguły, opisują dokładnie jeden predykat: //przodek/2//. 8-) Jak zdefiniować potomka, krewnego? ===== -. Obserwacje ===== ==== Styl ==== Poprawny styl kodowania bardzo wpływa na przejrzystość programów w Prologu. Program w Prologu jest pewną reprezentacją wiedzy, powinien być zrozumiały dla osoby znającej jedynie notację (relacyjną) użytą w Prologu. Czytelnik kodu programu nie musi znać //algorytmu// czy //modelu// (np. obiektowego), żeby zrozumieć program. To sam program JEST algorytmem, modelem. ==== Alternatywa ==== Tak, w Prologu jest operator alternatywy (ang. //OR//), ale //nie//, nie jest niezbędny, ani nie powinno się go używać. W praktyce ten sam efekt uzyskujemy pisząc kolejne klauzule, a zyskujemy na przejrzystości. ==== Klasyczny program ==== ?- write('Hello world'), nl. ===== -. Arytmetyka w Prologu ===== W Prologu nie można w sposób //bezpośredni// wykonywać obliczeń arytmetycznych. Służy do tego predykat //is//. **Ćwiczenie** 1. Sprawdzić działanie: ?- X is 2 + 2. ?- Y is 2.5 + ( 4 / 2). ?- Z is 2 + 0.001. Uwaga: ?- A is 3. ?- B is A + 4. ?- A is 3, B is A + 4. Operacje arytmetyczne: ?- X is 2 + 2. ?- X is 2 * 3. ?- X is 4 / 2. ?- X is 4 / 3. ?- X is 4 // 3. Uwaga na //podstawianie//: ?- X is 2 + 5. ?- X = 2 + 5. ?- 2 + 5 =:= 1 + 4. ?- 2 + 5 =:= 3 + 4. ?- 2 + 5 =:= 4 + 4. Przećwiczyć użycie operatorów: ?- 2 < 3. ?- 2 > 3. ?- 3 > 3. ?- 3 >= 3. ?- 3 =< 3. 2. 8-) Napisz program obliczający wynik [[http://pl.wikipedia.org/wiki/R%C3%B3wnanie_kwadratowe|równania kwadratowego]] ([[wp>Quadratic Equation]]) ''ax^2 + bx + c = 0'' w dziedzinie liczb rzeczywistych. Zaimplementuj predykaty: * ''delta/4'' -- obliczający deltę, argumenty kolejno: współczynnik a, współczynnik c, współczynnik c, wynik, * ''kwadrat/4'' -- obliczający wynik równania kwadratowego, argumenty kolejno: a, b, c, wynik. Zwróć uwagę na niedeterminizm w predykacie ''kwadrat/4'', który znajduje zero, jedno, albo dwa rozwiązania; mogą się przydać [[http://www.swi-prolog.org/pldoc/man?section=arith|funkcje matematyczne]], w szczególności do obliczenia pierwiastka używa się ''sqrt/1''. Zwróć uwagę, że najbardziej naturalnym sposobem użycia ww. przedykatów będzie podawanie 3 pierwszych argumentów jako stałe (dane w zadaniu), a czwarty jako niewiadomą (do wyliczenia). ===== - Wybrane problemy rozwiązane w Prologu ===== ==== Kolorowanie Mapy ==== Problem: mamy mapę taką jak poniżej |Bialorus |------------ Polska | ---------------| | | Ukraina Czechy| Slowacja|----------- ----------------- Należy ja pokolorować 3 kolorami, tak aby żadne sąsiadujące państwa nie miały takiego samego koloru: [[wp>Four_color_theorem]] **Ćwiczenie** Definiujemy 3 kolory: kolor(czerwony). kolor(zielony). kolor(niebieski). 8-) Należy zdefiniować predykat ''koloruj/5'', tak aby zadając pytanie: ?- koloruj(Polska,Bialorus,Ukraina,Slowacja,Czechy). dostać wszystkie możliwości pokolorowania tej konkretnej mapy. Uwaga: predykat ''koloruj/5'' definiuje zależności geograficzne. Uwaga: w Prologu operator ''\='' to nieidentyczność, czy też niemożliwość uzgodnienia termów. ===== Dla Zainteresowanych ===== ==== Więcej rekurencji ==== Typowym przykładem wykorzystania mechanizmu rekurencji jest obliczanie wartości funkcji silnia. Poniżej znajduje się kod realizujący tą funkcjonalność. factorial(0,1). factorial(Number,Result) :- Number > 0, NewNumber is Number-1, factorial(NewNumber,NewResult), Result is Number*NewResult. **Ćwiczenie** Wpisz, przetestuj i przemyśl działanie programu rekurencyjnie liczącego silnię. Uruchom program w trybie śledzenia wykonywania (trace). **Ćwiczenie** Opierając się na silni napisz program wypisujący [[http://pl.wikipedia.org/wiki/Ci%C4%85g_Fibonacciego|Ciąg Fibonacciego]]. ==== Świat klocków ==== Problem [[wp>Blocks_world]] Wczytaj {{:pl:prolog:prolog_lab:blocks.pl|}} Narysuj na kartce zamodelowany świat. Jakie pytania można zadać? above(b1,b2). above(b3,b5). left(b1,b7). left(b3,b3). **Ćwiczenie** Opisz w programie taki świat: a1 a2 a3 c1 c3 a4 a5 c2 c4 ==== Wieże Hanoi ==== Problem [[http://pl.wikipedia.org/wiki/Wieże_Hanoi]]. Problem [[wp>Towers_of_hanoi]] **Ćwiczenie** Proszę pobrać program {{:pl:prolog:prolog_lab:hanoi.pl|hanoi.pl}}. Przetestować i przemyśleć. Predykat //move/4// działa następująco:\\ np. //move(3,left,right,center)// przenosi 3 krążki ze stosu //left// na stos //right// przy pomocy stosu //center//. Przykład: ?- move(3,left,right,center). Move top disk from left to right Move top disk from left to center Move top disk from right to center Move top disk from left to right Move top disk from center to left Move top disk from center to right Move top disk from left to right Analizując kod programu proszę zauważyć, że algorytm rozwiązania problemu opiera się na dekompozycji na podproblemy. ==== Jeszcze więcej ==== Więcej ciekawych problemów [[https://ai.ia.agh.edu.pl/pl:prolog:pllib:start|bibliotece programów]].