Programowanie w Prologu

Prowadzący: Paweł Marczewski

Opis

If traditional languages are like prose, Prolog is like poetry.

W tym roku zapraszam na wstęp do Prologu i tym samym do fascynującego paradygmatu, jakim jest programowanie w logice. Tak jak rok temu, nauczymy się nowego, zupełnie innego sposobu myślenia o komputerze.

Będzie o tym:

• Jak mówić komputerowi, co chcemy dostać (a on sam już sobie wymyśli, jak)
• Jak cofać się w czasie i wykonywać obliczenia na wszystkie sposoby naraz
• Jak używać zmiennych, które się nie zmieniają
• Jak wyciągnąć z listy element, którego tam jeszcze nie dodaliśmy

i takie różne.

Skupimy się przede wszystkim na programowaniu, nie na części teoretycznej.

Wymagania

Powinieneś:

• Umieć programować (w C/Pascalu/Javie/… - nie chodzi o język, ale o doświadczenie): wiedzieć, co to procedura, zmienna, rekurencja, drzewo.
• Znać trochę rachunku zdań - wiedzieć, co to alternatywa, koniunkcja, implikacja, kwantyfikatory, prawa de Morgana.
• (Styczność z programowaniem funkcyjnym nie zaszkodzi, ale nie jest wymagana).

Jeśli bierzesz ze sobą laptopa (mile widziany, ale nieobowiązkowy - szczególnie, że na miejscu chyba będą komputery), zainstaluj na nim SWI-Prolog.

Zadania kwalifikacyjne

Nie trzeba zrobić wszystkiego, żeby się zakwalifikować.
Zadanie 1 wymaga umiejętności programowania i myślenia. Zadania 2 i 3 wymagają tylko umiejętności myślenia.
Na rozwiązania czekam pod adresem moc.liamg|celopmuh#moc.liamg|celopmuh.

Zadanie 1

Dana jest następująca definicja listy:

type 
  PList = ^List; { pusta lista to nil }
  List = record
    n: Integer;
    next: PList;
  end;

lub w C:

struct list {
  int n;
  struct list *next; /* pusta lista to NULL */
}

Listę reprezentuje oczywiście wskaźnik do danej struktury.

Napisz (w Pascalu lub w C) funkcję, która dla danej listy
1a. zwraca sumę jej elementów,
1b. zwraca listę, składającą się z elementów danej listy podzielnych przez 3,
1c. zwraca listę, składającą się z elementów danej listy podzielonych przez 3,
1d*. zwraca odwróconą wersję danej listy
1e**. zwraca posortowaną wersję danej listy

(najlepiej, jeśli pierwotna lista nie ulegnie przy tym modyfikacji).

Nie wolno ci korzystać z pętli (while, for, repeat, goto, …).

Zadanie 2

Załóżmy prawdziwość następujących formuł:

1. $e(a)$
2. $\forall x. (e(x) \Rightarrow e(s(s(x))))$
3. $\forall x. (\neg e(x) \Rightarrow o(x))$
4. $l(nil,a)$
5. $\forall xyz. (l(y,z) \Rightarrow l(x.y,s(z)))$

gdzie

• $p, o, e, l$ to predykaty mogące być prawdziwe dla pewnych termów (np. wiemy, że e jest prawdziwe dla termu a, co zapisujemy $e(a)$)
• termy to napisy postaci $a, nil, s(x), x.y$, gdzie x, y to termy - na przykład termem może być $a.(s(a).nil)$
• $\forall x.$ czytamy "dla każdego termu x zachodzi…"
• $\exists x.$ czytamy "istnieje taki term x, że zachodzi…"
• (x, y, z… nazywamy po prostu zmiennymi)
• $a \Rightarrow b$ czytamy "jeśli a, to b"
• $\vee, \wedge, \neg$ oznaczają alternatywę, koniunkcję, negację ("lub", "i", "nie").

Dla każdej z poniższych formuł napisz (i, jeśli potrafisz, uzasadnij), czy:

• musi być prawdziwa (dla każdych termów x,y,z),
• musi być fałszywa (dla każdych x,y,z),
• nie musi być ani prawdziwa, ani fałszywa.

1. $e(a)$
2. $o(x) \wedge e(x)$
3. $o(x) \vee e(x)$
4. $l(nil, s(s(s(a))))$
5. $l(x.(y.(z.nil)),s(s(s(a))))$

FAQ

Widzę, że mój niezbyt dokładny opis tego, czym są termy, a czym predykaty, spowodował wiele wątpliwości.

Co robią kropka, s()? Nic nie robią, po prostu są. Jeśli za x przypiszemy $a$, za y przypiszemy $b$, to x.y oznacza po prostu $a.b$.

Czy na przykład a.b jest prawdziwe albo fałszywe? Nie, termy nie mają wartości logicznej. Można powiedzieć, że (na przykład) predykat e nie zachodzi dla $a.b$, czyli nie zachodzi $e(a.b)$.

Co to jest a, nil? To takie napisy. Stałe. Nie mają wartości i nic pod nie nie podstawiamy. (W przeciwieństwie do x,y,z… które są zmiennymi.)

W razie dalszych wątpliwości polecam drugi i trzeci rozdział tego kursu (szczególnie początek trzeciego) (ale nie przerażajcie się - nasze zadania powinny być sporo prostsze od tych rozdziałów.)

Zadanie 3*

Co mogą opisywać termy z poprzedniego zadania? Co mogą oznaczać predykaty? Czy ich definicja jest jednoznaczna?