Proszę dołączyć do zespołu na Teamsach

Do sprawozdania: sekcje 1-4, program + odpowiedzi na pytania zaznaczone tak: 8-)

12. 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ć 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?

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

14. 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 równania kwadratowego (Quadratic Equation) ax^2 + bx + c = 0 w dziedzinie liczb rzeczywistych. Zaimplementuj predykaty:

  • delta/4 – obliczający deltę, argumenty kolejno: a, b, 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.

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

Świat klocków

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

Wieże Hanoi

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.

Jeszcze więcej

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

pl/dydaktyka/psi/labs/lab_prolog.txt · ostatnio zmienione: 2021/10/22 17:30 przez ikaf
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0