Programowanie w Logice

Algorithm = Logic + Control

Robert Kowalski

Aktualności

Opis kursu

Moduł wprowadzający w programowanie w logice. Wykład składa się z trzech części. Pierwsza część prezentuje podstawy programowania w logice. W części drugiej prezentowane są bardziej zaawansowane techniki programowania w Prologu, natomiast w części trzeciej zostaną omówione podstawy programowania ograniczeń - techniki w istotny sposób przyspieszającej poszukiwanie rozwiązań. Podczas laboratoriów rozwiązywane są zadania z list zadań, które sprawdzają umiejętność programowania w Prologu.

Zasady zaliczenia

Ocena końcowa

Jako ocena końcowa zostanie przyjęta ocena uzyskana na laboratorium (2.0 gdy od 0 do 49 pkt, 3.0 gdy od 50 do 59 pkt, 3.5 gdy od 60 do 69 pkt, 4.0 gdy od 70 do 79 pkt, 4.5 gdy od 80 do 89 pkt, 5.0 gdy od 90 do 100 pkt).
Ocena z grupy kursów Programowanie w Logice jest wyliczana na podstawie średniej ważonej liczby punktów uzyskanych na laboratorium i liczby punktów uzyskanych z kolokwium (wagi odpowiednio 40% i 60%).
~~Aby zaliczyć grupę kursów należy zarówno z laboratorium jak i z kolokwium uzyskać co najmniej po 50 punktów.~~

Laboratorium

Podczas zajęć laboratoryjnych zaliczane są listy zadań (przy każdej z nich podano maksymalną liczbę punktów do uzyskania i termin jej zaliczenia).
Student zaliczając listę zadań musi umieć odpowiedzieć na pytania weryfikujące samodzielność jego pracy nad rozwiązaniami.
Jeśli nie zaliczy się listy zadań, to ma się za nią 0 punktów.
Jeśli spóźni się jeden tydzień z zaliczeniem listy, to ma się z niej maksymalnie połowę punktów.
Jeśli spóźni się ponad tydzień z zaliczeniem listy, to ma się za nią 0 punktów.
W ostatnim tygodniu zajęć, prowadzący laboratoria przysyłają do wykładowcy liczbę punktów jaką uzyskali z laboratoriów poszczególni studenci.
Nie ma możliwości zaliczania laboratorium podczas sesji egzaminacyjnej.

Wykład

~~Na przedostatnim wykładzie odbywa się kolokwium, z którego można uzyskać od 0 do 100 punktów.~~
~~Zadania na kolokwium mogą dotyczyć każdego z przedstawionych na wykładzie zagadnień.~~

Ocena celująca

Jeśli student uzyskał z laboratorium co najmniej 95 punktów, to może ubiegać się o ocenę celującą. W tym celu należy przed rozpoczęciem sesji poinformować wykładowcę pisząc e-mail. W odpowiedzi otrzyma się tytuł krótkiego "wypracowania" (max 2 strony), które należy odesłać w ciągu maksymalnie 3 dni.
Jeśli student uzyskał z laboratorium co najmniej 95 punktów i z kolokwium co najmniej 95 punktów, to może odpowiadać na ocenę celującą podczas konsultacji wykładowcy w pierwszym tygodniu sesji (powinien przed rozpoczęciem sesji poinformować o tym fakcie wykładowcę pisząc e-mail).

Progi stosowane przy wyliczaniu oceny końcowej

% ocena(+LAB, +KOL, -OCENA)
%     Wylicza ocenę z grupy kursów, przy czym LAB jest liczbą 
%     punktów z laboratorium (od 0 do 100) a KOL jest liczbą
%     punktów z kolokwium (od 0 do 100).
%
ocena(LAB, _,   2.0) :- LAB < 50, !.
ocena(_,   KOL, 2.0) :- KOL < 50, !.
ocena(LAB, KOL, 3.0) :- 0.4*LAB + 0.6*KOL < 60, !.
ocena(LAB, KOL, 3.5) :- 0.4*LAB + 0.6*KOL < 70, !.
ocena(LAB, KOL, 4.0) :- 0.4*LAB + 0.6*KOL < 80, !.
ocena(LAB, KOL, 4.5) :- 0.4*LAB + 0.6*KOL < 90, !.
ocena(_,   _,   5.0).

Plan wykładu

Pierwsza część wykładu, dotycząca samego języka Prolog, prowadzona jest na podstawie książki Clocksina i Mellisha.

Wprowadzenie pl_wyk1.pdf
Działanie Prologu pl_wyk2.pdf
Struktury danych pl_wyk3.pdf
Poszukiwanie rozwiązań pl_wyk4.pdf
Wejście i wyjście pl_wyk5.pdf
Przykłady programów pl_wyk6.pdf
Śledzenie działania programu pl_wyk7.pdf
Gramatyki metamorficzne pl_wyk8.pdf
Interfejs graficzny pl_wyk9.pdf
Korutyny i wątki pl_wyk10.pdf
Zmienne, dziedziny i ograniczenia pl_wyk11.pdf
Proste ograniczenia pl_wyk12.pdf
Globalne ograniczenia kombinatoryczne pl_wyk13.pdf
Kolokwium
Przykłady programów z ograniczeniami pl_wyk14.pdf

Programy prezentowane podczas wykładu znajdziesz w repozytorium prolog-pl.git.

Gdy w roku 2020 po raz pierwszy zajęcia odbywały się zdalnie przygotowałem wykłady w postaci filmów. Filmy dostępne są ze strony: blog.

Literatura

Postawowa

W.F. Clocksin, C.S. Mellish. Programming in Prolog. Springer-Verlag London, 2013. (dostęp z kampusu PWr)
R.A. O’Keefe. The Craft of Prolog. The MIT Press, 1990.
L. Sterling, E. Shapiro. The Art of Prolog. The MIT Press, 1994.

Uzupełniająca

M. Bramer. Logic Programming with Prolog. Springer-Verlag London, 2013. (dostęp z kampusu PWr)
SWI-Prolog Reference Manual

Narzędzia programistyczne

SWI-Prolog

Listy zadań laboratoryjnych

Programowanie w Prologu można dodatkowo ćwiczyć rozwiązując zadania ze strony P-99: Ninety-Nine Prolog Problems (rozwiązania tych zadań nie będą oceniane przez prowadzących zajęcia).

Rozwiąż samodzielnie poniższe listy zadań.

Lista 0 (0 pkt) realizacja 1. zajęcia pl_lista0.pdf
Lista 1 (10 pkt) zaliczenie 2. zajęcia pl_lista1.pdf
Lista 2 (10 pkt) zaliczenie 4. zajęcia pl_lista2.pdf
Lista 3 (10 pkt) zaliczenie 5. zajęcia pl_lista3.pdf
Lista 4 (20 pkt) zaliczenie 7. zajęcia pl_lista4.pdf
Lista 5 (10 pkt) zaliczenie 8. zajęcia pl_lista5.pdf
Lista 6 (10 pkt) zaliczenie 11. zajęcia pl_lista6.pdf
Lista 7 (10 pkt) zaliczenie 13. zajęcia pl_lista7.pdf
Lista 8 (10 pkt) zaliczenie 14. zajęcia pl_lista8.pdf
Lista 9 (10 pkt) zaliczenie 15. zajęcia pl_lista9.pdf

Kolokwium

Miejsce i termin

Wyniki

Wyniki będą opublikowane w systemie JSOS.

Quiz

Zabaw się w system Prolog i samemu znajdź odpowiedzi na poniższe pytania. Swoją odpowiedź (może być więcej niż jedna) możesz porównać z prawidłową klikając na treści pytania.

?- X is 0, Y is X+1.

X = 0, Y = 1

?- X is 0, X is X+1.

false

?- f(X, a) = f(b, Y).

X = b, Y = a

?- f(X, a) = f(b, X).

false

?- member(X, [[1, 2], [3, 4]]), member(3, X).

X = [3, 4]

?- member(X, [[1, 2], [3, 4], [2, 5]]), member(2, X), \+member(1, X).

X = [2, 5]

?- length(X, 2), member(1, X), member(2, X).

X = [1, 2]
X = [2, 1]

?- append(_, [1 | X], [1, 2, 3, 1, 2, 3]), append(Y, [2 | _], X).

X = [2, 3, 1, 2, 3], Y = []
X = [2, 3, 1, 2, 3], Y = [2, 3, 1]
X = [2, 3], Y = []

?- X = [1, 2 | X], member(Y, X).

X = [1, 2 | X], Y = 1
X = [1, 2 | X], Y = 2
X = [1, 2 | X], Y = 1
X = [1, 2 | X], Y = 2
...
nieskończenie wiele odpowiedzi

?- freeze(X, Y = b), freeze(Z, X = a), Z = c.

X = a,
Y = b,
Z = c.

?- dif(f(X, Y), f(Y, X)).

dif(Y, X).

Pomysłowy Dobromir

Rada 1

Jeś masz sprawdzić warunek $\forall X\, p(X)$, to zamiast niego sprawdź logicznie równoważny mu warunek $\neg \exists X\, \neg p(X)$.

Prolog lubi poszukiwać wartości spełniające zadany warunek, natomiast nie przepada za sprawdzaniem czy wszystkie dane spełniają dany warunek. Unikaj zatem w sprawdzanych przez Prolog warunkach (w celu albo w ciele klauzuli) kwantyfikatorów ogólnych.

Przykład
Niech predykat p/2 wyraża relację o dziedzinie D. Warunek zwr, spełniony gdy relacja jest zwrotna, można wyobrazić sobie jako sprawdzenie, że nie ma takiej wartości w dziedzinie D, która nie jest sama ze sobą w relacji. Można do tego dojść bardziej formalnie:
$$\begin{eqnarray*}
\mbox{zwr} \leftarrow \forall X \in D\, p(X, X) & \equiv & \mbox{zwr} \leftarrow \forall X\, (X \in D \rightarrow p(X, X))\\
& \equiv & \mbox{zwr} \leftarrow \forall X\, (X \not\in D \vee p(X, X))\\
& \equiv & \mbox{zwr} \leftarrow \neg \exists X\, \neg (X \not\in D \vee p(X, X))\\
& \equiv & \mbox{zwr} \leftarrow \neg \exists X\, (X \in D \wedge \neg p(X, X))\\
& \equiv & \mbox{zwr} \leftarrow \neg \exists X\, ( (p(X, \_) \vee p(\_, X)) \wedge \neg p(X, X))\\
\end{eqnarray*}$$
Ostatni warunek można zapisać w Prologu w postaci następującej klauzuli:
zwr :- \+ ((p(X, _); p(_, X)), \+ p(X, X)).

Rada 2

Prolog nie wywnioskuje jakie dane spełniają zanegowany warunek.

Jeśli każemy Prologowi sprawdzić warunek \+ p(X), to nie oczekujmy, że znajdzie on taką wartość X, która nie spełnia warunku p/2. Prolog aby sprawdzić warunek \+ p(X), będzie sprawdzać czy są takie dane X, że spełniają warunek p(X). Jeśli są, to \+ p(X) zawodzi a jeśli ich nie ma, to \+ p(X) jest spełniony ale pod X nic nie zostanie podstawione (taki sposób sprawdzania nazywa się w Prologu "negacja jako niepowodzenie").

Przykład
Niech program składa się z następujących faktów:

p(a).
p(b).
p(c).

Zadajmy Prologowi pytanie:

?- \+ p(X).
false.

Negatywna odpowiedź wynika z tego, że warunek p(X) jest spełniony np. dla X = a.

Rada 3

"Programs must be written for people to read, and only incidentally for machines to execute." -- Harold Abelson

Staraj się pisać programy tak aby były czytelne. W artykule Coding Guidelines for Prolog znajdziesz zalecenia co do dobrego stylu programowania w Prologu.

Przykład

Zamiast pisać regułę w jednym wierszu:

liczba(X) :- ujemna(X); zero(X); dodatnia(X).

pisz warunki z treści reguły w kolejnych wierszach z wcięciem:

liczba(X) :-
        ujemna(X);
        zero(X);
        dodatnia(X).

Jeszcze lepiej uwypuklić użycie alternatywy:

liczba(X) :-
        (  ujemna(X)
        ;  zero(X)
        ;  dodatnia(X)
        ).

Osobiście wolę zapisać powyższą regułę w postaci trzech prostych reguł:

liczba(X) :-
        ujemna(X).
liczba(X) :-
        zero(X).
liczba(X) :-
        dodatnia(X).

Przykład

Jeśli negujesz złożoną formułę, to stosując wcięcia zwiększ jej czytelność.

Zamiast w ten sposób:

dobra(X) :-
        \+ (zla(X); gorsza(X); najgorsza(X)).

napisz tak:

dobra(X) :-
        \+ (  zla(X)
           ;  gorsza(X)
           ;  najgorsza(X)
           ).

albo jeszcze lepiej zastosuj prawo de Morgana:

dobra(X) :-
        \+ zla(X),
        \+ gorsza(X),
        \+ najgorsza(X).

Rada 4

Pisząc program w Prologu, nie zapominaj o zasadzie zamkniętego świata, o prologowej negacji jako niepowodzeniu i o tym, że w programie można wyrażać tylko wiedzę pozytywną. Gdy o tym zapomnisz, możesz być zaskoczony uzyskaną od Prologu odpowiedzią.

Rozpatrzmy następujący przykład:

lubi(przemko, prolog).
lubi(przemko, X) :- lubi(X, prolog).

Na pytanie co lubi przemko otrzymujemy dwie odpowiedzi, że przemko lubi język programowania prolog i lubi samego siebie (bo lubi wszystkich, którzy lubią prolog):

?- lubi(przemko, X).
X = prolog ;
X = przemko .

Jeśli zapytamy się czy przemko lubi muzykę, to otrzymamy odpowiedź przeczącą, gdyż zgodnie z zasadą zamkniętego świata, nie jest prawdziwe to, czego nie opisano w programie:

?- lubi(przemko, muzyka).
false.

Nie da się w programie wyrazić wiedzy negatywnej o tym, że przemko czegoś nie lubi. Poniższa klauzula nie jest poprawna, gdyż definiowany warunek musi być atomowy (nie może być ani zanegowany ani nie może być alternatywą innych warunków):

\+ lubi(przemko, python). % niepoprawna klauzula

Możemy próbować zdefiniować warunek nie_lubi/2, który chcielibyśmy aby wyrażał, kto czego nie lubi (przemko nie lubi języka Python):

nie_lubi(przemko, python).

Dopiszmy do definicji predykatu lubi/2 jeszcze trzecią klauzulę:

lubi(przemko, prolog).
lubi(przemko, X) :- lubi(X, prolog).
lubi(X, Y) :- \+ nie_lubi(X, Y).

Gdy teraz zapytamy się czy przemko lubi muzykę, to otrzymamy odpowiedź twierdzącą:

?- lubi(przemko, muzyka).
true.

To dlatego, że warunek nie_lubi(przemko, muzyka)zawodzi (zasada zamkniętego świata) a zatem warunek \+ nie_lubi(przemko, muzyka) jest spełniony (negacja jako niepowodzenie) i można z niego wywnioskować, że lubi(przemko, muzyka).

Zadajmy jednak pytanie czy przemko lubi język Python:

?- lubi(przemko, python).
true.

DLACZEGO TAKA ODPOWIEDŹ??? PRZECIEŻ NAPISANO, ŻE PRZEMKO NIE LUBI PYTHONA!!!

Otóż dlatego, że warunek nie_lubi/2 nie jest zaprzeczeniem (komplementarny do) warunku lubi/2.

A tak Prolog wnioskował, że przemko lubi prolog:

nie_lubi(python, prolog) zawodzi z zasady zamkniętego świata
\+ nie_lubi(python, prolog) bo, z negacji jako niepowodzenie, warunek nie_lubi(python, prolog) zawodzi
lubi(python, prolog) wynika z trzeciej reguły bo \+ nie_lubi(python, prolog)
lubi(przemko, python) wynika z drugiej reguły bo lubi(python, prolog)

Github Copilot

Sztuczna inteligencja nie zawsze prawdę ci powie: