Paradygmaty Programowania: Haskell, Prolog i Teoria Informatyki

Paradygmaty Programowania – Kompendium (Haskell, Prolog, Teoria)

I. Teoria Ogólna

1. Definicja Paradygmatu

Zbiór koncepcji reprezentujących podejście do implementacji algorytmów. Definiuje sposób patrzenia na przepływ sterowania i wykonanie programu.

2. Model von Neumanna

• 5 bloków: Pamięć (M), Jednostka Arytmetyczno-Logiczna (ALU), Jednostka Sterująca (CC), Wejście, Wyjście.
• CPU: Składa się z ALU oraz CC.
• Kluczowa cecha: Dane i instrukcje (kod) są przechowywane w tej samej pamięci.
• Cykl pracy: Pobranie → Dekodowanie → Wykonanie.

3. Translatory

• Kompilator: Tłumaczy cały kod źródłowy przed uruchomieniem. Generuje szybki kod wynikowy, jest statyczny.
• Interpreter: Tłumaczy i wykonuje instrukcje jedna po drugiej. Jest wolniejszy, ale bardziej interaktywny.
• Hybryda: Kompilacja do kodu pośredniego (byte-code) i uruchamianie w Maszynie Wirtualnej (np. JVM).

4. Rodzaje Paradygmatów

• Imperatywny: Zmiana stanu maszyny (zmienne, pamięć) poprzez sekwencję instrukcji.
• Obiektowy: Wykorzystuje obiekty (dane + metody), enkapsulację, dziedziczenie oraz polimorfizm.
• Funkcyjny: Opiera się na ewaluacji funkcji matematycznych; brak stanu, zmiennych i efektów ubocznych.
• Logiczny: Wykorzystuje fakty, reguły i cele. Opiera się na dowodzeniu twierdzeń i unifikacji.

II. Haskell (Paradygmat Funkcyjny)

Cechy Języka

• Leniwy (Lazy): Oblicza wyrażenie tylko wtedy, gdy jego wynik jest rzeczywiście potrzebny.
• Czysty (Pure): Ta sama funkcja dla tych samych argumentów zawsze zwraca ten sam wynik. Brak efektów ubocznych.
• Silnie typowany: Brak niejawnych konwersji typów (np. z Int na Float).

Składnia List

• Głowa (x) i Ogon (xs): Wzorzec (x:xs).
• [1,2,3] to cukier składniowy dla 1:(2:(3:[])).
• Typ String to w rzeczywistości lista znaków [Char].

Rekurencja Ogonowa (Tail Recursion)

Ważne: Wywołanie samej siebie jest ostatnią operacją w funkcji. Dzięki temu nie zużywa ona stosu (optymalizacja). Zazwyczaj wymaga użycia akumulatora.

Przykłady Kodu Haskell

-- 1. Silnia (Pattern Matching)
silnia 0 = 1
silnia n = n * silnia (n-1)

-- 2. Długość listy (Rekurencja ogonowa z akumulatorem)
len list = lenAcc list 0
lenAcc [] acc = acc
lenAcc (_:xs) acc = lenAcc xs (acc + 1)

-- 3. Odwracanie listy (Szybkie z akumulatorem)
reverse list = revAcc list []
revAcc [] acc = acc
revAcc (x:xs) acc = revAcc xs (x:acc)

-- 4. QuickSort (List Comprehension)
qsort [] = []
qsort (x:xs) = qsort [y | y <- xs, y <= x] ++ [x] ++ qsort [y | y <- xs, y > x]

-- 5. Funkcje wyższego rzędu
-- map f list (aplikuje f do każdego elementu)
-- filter p list (zostawia elementy spełniające predykat p)
-- foldr/foldl (redukcja listy do pojedynczej wartości)

III. Prolog (Paradygmat Logiczny)

Struktura Programu

• Fakt: kobieta(anna). (musi kończyć się kropką).
• Reguła: babcia(X,Z) :- matka(X,Y), rodzic(Y,Z). (X jest babcią Z, jeśli...).
• Głowa :- Ciało: Przecinek (,) oznacza AND, średnik (;) oznacza OR.
• Wielkie litery: Zmienne (np. X, Wynik).
• Małe litery: Atomy (np. anna, x).

Unifikacja (=)

Mechanizm dopasowywania termów i podstawiania zmiennych:

• mia = mia → YES.
• mia = vincent → NO.
• X = mia → YES (X przyjmuje wartość mia).
• k(s(g), Y) = k(X, t(k)) → YES (X=s(g), Y=t(k)).
• X = 3+2 → X jest strukturą +(3,2), a nie wynikiem 5.

Arytmetyka (is)

• X is 3+2 → X=5 (wymusza obliczenie prawej strony).
• Prawa strona musi być w pełni znana (brak niewiadomych zmiennych).
• Operatory porównania: =:= (równe), =\= (różne), <, >, =<, >=.

Listy w Prologu

• [H|T] (Głowa | Ogon).
• [a,b,c] jest równoważne [a | [b,c]].

Przykłady Kodu Prolog

-- 1. Member (Czy element jest na liście)
member(X, [X|_]).           % Jest głową
member(X, [_|T]) :- member(X, T). % Lub znajduje się w ogonie

-- 2. Append (Łączenie list)
append([], L, L).
append([H|T], L2, [H|L3]) :- append(T, L2, L3).

-- 3. Length (Rekurencja ogonowa z akumulatorem)
len(L, N) :- accLen(L, 0, N).
accLen([], Acc, Acc). 
accLen([_|T], Acc, Result) :- 
    NewAcc is Acc + 1, 
    accLen(T, NewAcc, Result).

-- 4. Silnia
silnia(0, 1).
silnia(N, Wynik) :- 
    N > 0, 
    N1 is N - 1, 
    silnia(N1, W1), 
    Wynik is N * W1.

Strategia Przeszukiwania

• DFS (Depth-First Search): Przeszukiwanie w głąb.
• Kolejność: Od góry do dołu (klauzule w bazie) oraz od lewej do prawej (cele w regule).
• Backtracking (Nawroty): Gdy cel nie zostanie spełniony, system cofa się do ostatniego punktu wyboru.

IV. Porównanie Języków i Zestawy Zadań

Zestaw 1

Zad. 1: Unifikacja

• Definicja: Proces dopasowywania dwóch termów tak, aby stały się identyczne, poprzez znalezienie najprostszego podstawienia dla zawartych w nich zmiennych.
• Występowanie: Głównie w Prologu (wnioskowanie) oraz Haskellu (inferencja typów).

Zad. 2: Paradygmaty

• Imperatywny: Program to sekwencja instrukcji zmieniających stan (np. C).
• Obiektowy: Komunikacja między obiektami (np. Java).
• Funkcyjny: Ewaluacja funkcji, brak stanu (np. Haskell).
• Logiczny: Baza wiedzy i dowodzenie twierdzeń (np. Prolog).

Zad. 3: Funkcja pobierająca N elementów (Haskell)

mojePobierz :: Int -> [a] -> [a]
mojePobierz n _  | n <= 0 = []
mojePobierz _ []          = []
mojePobierz n (x:xs)      = x : mojePobierz (n-1) xs

Zad. 4: Analiza programu 'fun'

Funkcja odwraca listę (naiwna implementacja reverse). Wykorzystuje rekurencję zwykłą, co przy użyciu operatora ++ daje złożoność O(n²).

Zestaw 2

1. Porównanie programowania imperatywnego i logicznego

• Model: Imperatywne to zmiana stanu; logiczne to wnioskowanie.
• Podejście: Imperatywne: "Jak to zrobić?"; Logiczne: "Co jest prawdą?".
• Zmienne: W imperatywnym są mutowalne; w logicznym są to niemutowalne niewiadome.

2. Analiza kodu 'elem' (Haskell)

Sprawdza obecność elementu w liście. Wymaga klasy typów Eq dla porównań.

3. Silnia w dwóch paradygmatach

W Haskellu definiowana przez dopasowanie wzorca i wyrażenie matematyczne. W Prologu jako relacja między liczbą a jej silnią, wykorzystująca is do obliczeń.

4. Ostatni element listy

-- Haskell
ostatni [x] = x
ostatni (_:xs) = ostatni xs

-- Prolog
ostatni(X, [X]).
ostatni(X, [_|T]) :- ostatni(X, T).