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.
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.
- 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
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.
Pomysłowy Dobromir
Rada 1
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)).
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
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.
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
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).
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
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:
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:
