Paradygmaty programowania/Ćwiczenia 13: Programowanie w logice w Prologu I

Zadanie 1

Rozważmy program prologowy:

 p(X, Y, Y) :- X =< Y.
 p(X, Y, Z) :- X < Z, W is Z − 1, p(X, Y, W).

Co zostanie wypisane po wpisaniu celu p(5, X, 15)?

Wskazówka:

Kolejne liczby całkowite od 15 do 5.

Zadanie 2*

Napisać program obliczający największy wspólny dzielnik dwóch dodatnich liczb całkowitych za pomocą algorytmu Euklidesa z odejmowaniem. Chodzi o taki algorytm:

 function nww(x, y)
   while x ≠ y do
     if x > y then x := x – y
     else y := y – x
   return x

Wskazówka:

Trudność tego zadania zasadza się na konieczności rozpatrzenia dwóch przypadków (x < y oraz x > y), czego w dotychczasowych wykładach poświęconych Prologowi nie omawialiśmy. Rzecz jest jednak prosta — piszemy dwie klauzule, każda dotycząca jednego przypadku (plus pierwsza „brzegowa”, obsługująca przypadek równych argumentów). Uzgodnienie powiedzie się w tylko jednej z nich. Program może więc wyglądać tak:

 nww(X, X, X) :- X > 0.
 nww(X, Y, Z) :- X > Y, Y > 0, W is X - Y, nww(Y, W, Z).
 nww(X, Y, Z) :- X < Y, X > 0, W is Y - X, nww(X, W, Z).

Zadanie 3

Program z poprzedniego zadania można zastosować do wyliczenia największego wspólnego dzielnika dwóch liczb lub do sprawdzenia, że dzielnik równa się pewnej liczbie. Co się jednak stanie, jeśli wpiszemy cel postaci nww(X, 28, 4)?

Wskazówka:

Interpreter stwierdzi, że argument nie jest wystarczająco ukonkretniony. Rzecz bierze się już z pierwszej próby uzgodnienia celu z drugą klauzulą definicji nww — relacja X > Y, w której jeden argument jest nieukonkretnioną zmienną, nie potrafi przecież „wygenerować” dopasowań.

Zadanie 4

Załóżmy, że mamy dwie relacje, P oraz Q, wyrażone dwuargumentowymi funktorami p i q. Jak zdefiniować relację R będącą złożeniem relacji P i Q? Chodzi o relację R taką, że xRy wtw xPz i zQy dla pewnego z.

Wskazówka:

Można niemal dosłownie przetłumaczyć algebraiczną definicję złożenia relacji:

 r(X, Y) :- p(X, Z), q(Z, Y).

Zadanie 5

Mamy relacje P i Q jak w poprzednim zadaniu. Jak zdefiniować ich przecięcie, czyli relację R taką, że xRy wtw xPy i xQy?

Wskazówka:

Jeszcze prościej niż w poprzednim zadaniu...

 r(X, Y) :- p(X, Y), q(X, Y).

Zadanie 6

Tym razem mamy jedną relację dwuargumentową P. Jak zdefiniować jej domknięcie zwrotne i przechodnie, czyli relację R taką, że xRy wtw $x_{0}Px_{1},x_{1}Px_{2},\ldots ,x_{n-1}Px_{n}$ dla pewnych $x_{0},x_{1},\ldots ,x_{n},$ gdzie $x_{0}=x$ i $x_{n}=y$.

Wskazówka:

Klasyczne rozwiązanie jest następujące:

 r(X, X).
 r(X, Y) :- p(X, Z), r(Z, Y).

Zadanie 7*

Fabryka produkuje kilka różnych produktów, nazwijmy je p1, p2 i p3. Produkty są produkowane ze składników, które nazwijmy s1, s2, s3 i s4. Zbudować prologową bazę danych, która będzie przechowywała następujące informacje:

• Opis każdego produktu, wyszczególniający które składniki są potrzebne do jego produkcji (na ogół produkt nie wymaga użycia wszystkich składników).
• Spis dostępnych w tej chwili składników.

Następnie zdefiniować dwie relacje:

• możnaprodukować(X) — stwierdzająca, że fabryka posiada wszystkie składniki potrzebne do wyprodukowania produktu X.
• potrzebuje(X, Y) — stwierdzająca, że produkt X potrzebuje składnika Y.

Całość należy zaprogramować nie używając bezpośrednio list (w tym sęk...).

Wskazówka:

Bazę danych można zapisać np. tak:

 produkt(p1, skł(s1, skł(s3, skł(s4, koniec)))).
 produkt(p2, skł(s2, koniec)).
 produkt(p3, skł(s2, skł(s3, koniec))).

 jest(s1).
 jest(s2).
 jest(s3).

Funktor skł służy do stworzenia odpowiednika listy, której obiecaliśmy jawnie nie używać... Funktor zeroargumentowy koniec służy do zaznaczenia, że dalszej części listy już nie będzie. Notabene, tego typu konstrukcja listy jest w istocie taka sama jak zwykłe listy prologowe — różnica polega jedynie na zgrabnej obudowie składniowej.

Relacje możnaprodukować i potrzebuje (wraz z dwiema relacjami pomocniczymi) możemy teraz określić następująco:

 należy(X, skł(X, _)).
 należy(X, skł(_, Y)) :- należy(X, Y).

 potrzebuje(X, Y) :- produkt(X, Z), należy(Y, Z).

 jestwszystko(koniec).
 jestwszystko(skł(X, Y)) :- jest(X), jestwszystko(Y)).

 możnaprodukować(X) :- produkt(X, Y), jestwszystko(Y).

Zadanie 8

Przyjrzyj się funktorowi należy z rozwiązania poprzedniego zadania. Zaobserwuj, co się dzieje, gdy użyjemy go z konkretnym pierwszym argumentem i zmienną w miejscu drugiego, np. należy(abc, X).

Wskazówka:

Traktując struktury złożone z zagnieżdżonych funktorów skł jako listy, wynik możemy interpretować jako coraz dłuższe listy zawierające element abc.