AIwiki

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.

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).

Ć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ć 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 (;).

Ć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).

Ć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).

Czy zamiast Y można wpisać inny symbol?

Ć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).

Czy kolejność wpisywania linii ma znaczenie?

Jeżeli koniunkcję celów oznaczamy przecinkiem, to jak zapytać kto jest matką, a kto ojcem roberta?

Ćwiczenie

Proszę spróbować dopisać do programu takie linijki:

  famme(kasia).
  homme(krzys).
  parent(kasia,krzys).

Czy nazwa użytych symboli wpływa na działanie programu? Jakie są ograniczenia na używane symbole?

Ć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).

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.

Ć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.

Jak zdefiniować potomka, krewnego?

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.

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.

?- write('Hello world'), nl.

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. Napisz program obliczający wynik równania kwadratowego (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ć 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).

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: Four_color_theorem

Ćwiczenie

Definiujemy 3 kolory:

kolor(czerwony).
kolor(zielony).
kolor(niebieski).

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.

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 Ciąg Fibonacciego.

Problem Blocks_world

Wczytaj 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

Problem http://pl.wikipedia.org/wiki/Wieże_Hanoi.

Problem Towers_of_hanoi

Ćwiczenie

Proszę pobrać program 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.

Więcej ciekawych problemów bibliotece programów.