Wstęp do programowania funkcyjnego

Ostatnio zastanawiałem się, dlaczego większość utworów muzycznych, tych szczególnie pełnych wyrazu i ekspresji jest rozpisana w tonacjach C-mol, G-mol lub E-mol. Dlaczego by nie Hisis-dur? Przyczyną tego, jest fakt, że praktycznie każdy muzyk poznaje wpierw tonację C.
Muzycy rodzą się w C.

Podejrzewam, że wasze początki programowania funkcyjnego, będą nasuwały skojarzenie z graniem kolęd w tonacji Hisis-dur. Wszyscy urodziliśmy się w C (w sensie programowania proceduralnego) i kiedy przyjdzie nam zagrać w Hisis w jednej chwili utracimy naszą płynność grania i pewność siebie. Będziemy się zacinać co krok i zadawać pytanie - czemu gram w Hisis ?? Prawdę mówiąc, nie liczę na to, by ktokolwiek zagrał tą kolędę do końca. Moim celem minimum jest ukazanie wam nowego horyzontu programistycznego. Zarysowanie nowej jakości.

Będziemy mówić o programowaniu funkcyjnym (zwanym też funkcjonalnym), a żeby nie paść ofiarą teoretycznej suchoty, całość oprzemy na języku programowania Haskell.

Aby się nie pogubić, zorganizowałem ten artykuł w następujący sposób:
1 Wstęp do programowania funkcyjnego
     1.1 Paradygmat programowania funkcyjnego
     1.2 Pozyskanie Haskell'a i wprowadzenie w interfejs
     1.3 O czym NIE powiemy
     1.4 O czym powiemy

Paradygmat programowania funkcyjnego

Z definicji programowanie funkcyjne jest metodą programowania w której najważniejszym narzędziem (w zasadzie jedynym) są funkcje. Co w tym nowego? - zapytacie. Mianowicie funkcje mogą być przekazywane do innych funkcji jako argumenty i mogą być zwracane jako wyniki, tak jak zwykłe zmienne.

Tyle mówi definicja, ale istota programowania funkcyjnego leży poza nią:

W programowaniu funkcyjnym rozwiązujemy problemy nie poprzez pisanie rozwiązania, tylko poprzez opisywanie problemu.

To jest to! Wystarczy poprawnie opisać problem, a kompilator wygeneruje za nas odpowiedni kod. Magia.

Konsekwencje i zalety takiego podejścia są oszałamiające:

• zamiast tradycyjnego ciągu instrukcji, wykonywanych w ściśle ustalonej kolejności, mamy opis problemu wyrażany za pomocą matematycznych zależności i wyrażeń, przy czym nie znamy kolejności, w której będą one wykonywane.
• Instrukcja przypisania staje się bezużyteczna, gdyż nie znamy chwili w której będzie ona wykonana.
• Nie obsługujemy mechanizmów przydzielania i zwalniania pamięci.
• Ponieważ nie musimy sterować kolejnością wykonania, unikamy wielu potencjalnych błędów.

Na forum jest osoba, która używa podpisu w stylu: "Aby rozwiązać problem, wpierw trzeba go dobrze opisać". W przypadku Haskell'a wygląda to odrobinę inaczej: "dobry opis jest rozwiązaniem problemu".

Prawdopodobnie największą zaletą programowania funkcyjnego, jest wynikające z pominięcia wszelkich instrukcji przypisania, jak i instrukcji sterujących przepływem programu znaczne uproszczenie kodu. Kod napisany w języku funkcyjnym, jest znacząco krótszy od analogicznego kodu w języku proceduralnym, ponadto jest on na tyle czytelny, że sam w sobie jest dokumentacją.

Przykład? Typowa implementacja algorytmu sortowania szybkiego (ang. Quick Sort, opisany w dziale algorytmy przez Adama Boducha), zajmuje 20-30 linijek kodu (kodu pełnego warunków, przypisań itd). W Haskellu Quick Sort rozpisuje się w dwóch linijkach! przy czym kod jest tak czytelny, że praktycznie mówi sam za siebie. Oto nasz pierwszy program w Haskellu:

quicksort [ ] = [ ]
quicksort (x : xs) = quicksort [y | y<-xs, y<x] ++ [x]  ++ quicksort [y | y<-xs, y>=x]

To wszystko! 20-30 linijek przemienionych w super-czytelne dwie!

Po przeczytaniu artykułu Haskell 1) Wartości i typy każdy z was, będzie w stanie całkowicie zrozumieć składnię powyższego przykładu, jak i rozpisywać podobne do niego, proste programy.

ale ...
Nie dajmy się zwariować! Oto mroczna strona programowania funkcyjnego:

• przejrzysty kod nie idzie w parze z wydajnością obliczeniową, w rzeczywistości programowanie w Haskell'u opiera się na rekurencji (powyższy przykład jest przecież rekurencją), a jak wiemy, rekurencja pociąga za sobą spowolnienie i zwiększenie zajmowanych zasobów pamięci.
• rozwiązywanie pewnych problemów w Haskell'u jest nieporozumieniem. Np. tworzenie w Haskell'u FPP shootera można porównać do budowania bazy danych w paincie (dobra, trochę przesadzam :) ). Praktycznie warunkiem jest to, aby problem dawał się sprowadzić do matematycznych zależności.

Na chwilę zatrzymam się przy ostatnim punkcie. Generalnie funkcjonuje twierdzenie, że wszystkie języki programowania, które spełniają pewne elementarne warunki, są sobie równe - w tym sensie, że zbiór rozwiązywalnych w nich problemów jest identyczny. Dlatego ostatecznie, w Haskellu można napisać shootera (aczkolwiek nie jest to dobry pomysł), podobnie jak shootera można w pewnym sensie napisać na maszynie Turinga :-) (ale herezje, to jest chyba odpowiedni czas na kolejny rozdział)

Pozyskanie Haskell'a i wprowadzenie w interfejs

Haskell jest obok ML czy Scheme przykładem języka funkcyjnego (jest nim też w istocie Mathematica). Przy czym Haskell znaczy tylko tyle, co abstrakcyjna specyfikacja języka. W rzeczywistości będziemy operować na Hugs 98, który jest jego interpreterem.

Wpierw pozyskajmy odpowiednie pliki:
(Zestaw McHaskell, olimpijczyk):

1. Kanapka: Interpretator Hugs 98
2. Frytki: Dokumentacja Haskell 98
3. Napój: A Gentle Introduction to Haskell 98

Mamy już wszystko, czego będziemy potrzebować.

Gdy będziecie instalować Hugs'a, sugeruję wybrać instalację "Custom", gdyż tylko w ten sposób można jawnie określić katalog docelowy. Ponieważ Hugs'a będziemy uruchamiać poprzez aplikację winhugs.exe, dobrym pomysłem jest utworzenie skrótu do tego pliku.

Poniżej opiszę kilka typowych czynności związanych z pisaniem i wykonywaniem nowego programu, niemniej gorąco zachęcam do prześledzenia przynajmniej trzeciego rozdziału dokumentacji hugs'a (dostępnej między innymi z Menu Start).

Powiedzmy, że chcemy zaimplementować wspomniany wcześniej algorytm sortowania szybkiego. Uruchamiamy winhugs.exe. Interpreter pracuje w trybie interakcyjnym, jednak programy piszemy w oddzielnych plikach (wszystko co napiszemy w konsoli, przepada). Takie oddzielne pliki są nazywane modułami (rozszerzenie .hs) i z technicznego punktu widzenia, moduł jest zwyczajnie zbiorem definicji.

Dlatego, otwórzmy plik tekstowy (np. w notatniku) Qsort.hs, a następnie wpiszmy do niego następującą treść:

module Qsort where
quicksort [ ] = [ ]
quicksort (x : xs) = quicksort [y | y<-xs, y<x] ++ [x]  ++ quicksort [y | y<-xs, y>=x]

teraz musimy wczytać moduł do interpretera (w ten sposób nasze definicje stają się dostępne z poziomu konsoli). można to zrobić na kilka sposobów, klikając dwukrotnie na pliku Qsort.hs, albo z poziomu interpretatora, używając komendy ":load Qsort"

Gdy tekst zachęty zmieni się z Prompt> na Qsort>, możemy użyć zdefiniowanej przez nas funkcji. Możemy przykładowo wpisać:

Qsort> quicksort [4,2,3,2,1,6,2]

O czym NIE powiemy

Przede wszystkim nie powiemy o istnieniu w Haskell'u takich tworów jak Monady (ang.monads). Czyli elementarnych składników rzeczywistości obdarzonych możliwościami poznawczymi.

Prawdopodobnie nie wspomnimy o klasach, przeładowywaniu oraz będziemy milczeć w temacie obsługi wyjątków i komunikacji I/O.

O czym powiemy

Przetłumaczyłem dla was pierwszy rozdział z dokumentu "Gentle introduction to Haskell". Jeśli ktoś preferuje angielską wersję, to nie widzę powodu, dla którego miałby czytać moje tłumaczenie. Jednocześnie wiele terminów musiałem ukuć, gdyż nie mają one swoich odpowiedników w języku polskim. Za wszelkie poprawki będę bardzo wdzięczny.

W następnym artykule powiemy o tym, jak faktycznie wygląda struktura programowania w Haskell'u. Poznamy wiele elementarnych terminów (takich jak dopasowywanie szablonu), a w szczególności skupimy się na niezwykle złożonym systemie kontroli typów (poznamy typy wielopostaciowe i rekurencyjne, nauczymy się definiować nowe).

Jeżeli uznacie, że temat jest ciekawy i warto go kontynuować, oraz jeśli przebrniecie (ze zrozumieniem) przez pierwszy rozdział, to rozważam napisanie dwóch kolejnych:

Haskell 2) Funkcje (czy to nie jest zabawne, że omawiając język funkcyjny, możemy nie wspomnieć o funkcjach)
Haskell 3) "Case i Dopasowywanie szablonu.

Nie czekajmy dłużej, proponuję w tej chwili uruchomić Hugs'a, otworzyć nowy "testowy" dokument i zapoznać się z treścią następnego artykułu - Haskell 1) Wartości i typy.

Powodzenia i dobrej zabawy w świecie wszechobecnej rekurencji.

Wasz oddany starszy kapral Kapustka.