PF:Moduł Wstęp

Porównanie paradygmatu funkcyjnego i imperatywnego

Jaki jest cel programowania? Pisząc program staramy się osiągnąć jakiś cel. Jak w każdej działalności, dobrze jest najpierw uzmysłowić sobie co chcemy osiągnąć, a dopiero potem starać się to osiągnąć --- inaczej możemy uzyskać niezamierzone rezultaty. Cel, do którego dążymy zwykle opisuje się w tzw. specyfikacji. Specyfikacja może być mniej lub bardziej formalna. Jeśli jest sformalizowana, to nasz cel ma zwykle postać relacji między danymi, a wynikami. Program, który tworzymy powinien mieścić się w ramach określonych przez specyfikację. Weryfikacja poprawności programu polega na sprawdzeniu, że faktycznie tak jest.

Paradygmat funkcyjny polega na tym, że pisząc program tworzymy pojęcia matematyczne, coraz bardziej skomplikowane, aż do osiągnięcia celu. Pojęcia te mają postać stałych i funkcji, stąd nazwa programowanie funkcyjne.Oczywiście tworzone funkcje są wykonywalne, tzn. dostarczając argumentów możemy obliczyć ich wartości. Weryfikacja programu funkcyjnego polega na udowodnieniu, że tworzone przez nas funkcje zawierają się w relacjach określonych przez specyfikacje (i są określone na odpowiednich dziedzinach).

Charakterystyczne dla programowania funkcyjnego jest również to, że funkcje są "obywatelami pierwszej kategorii", tzn. przysługują im wszystkie te prawa, co innym wartościom. W tej chwili nie jest jeszcze jasne o jakie prawa może chodzić. Można jednak śmiało powiedzieć, że jest to jedna z fundamentalnych zasad programowania funkcyjnego.

Porównajmy paradygmat funkcyjny i imperatywny. Programowanie imperatywne jest powszechnie znane. Na czym jednak polega paradygmat imperatywny? W naszych programach zwykle staramy się wymodelować istotny dla nas fragment otaczającego nas świata. Świat ten, składa się (na codzienny użytek) z przedmiotów. Przedmiotom tym odpowiadają w programach imperatywnych zmienne lub obiekty. Przedmioty w świecie rzeczywistym zmieniają się wraz z upływem czasu. Podobnie więc, zmienne i obiekty obdarzone są stanem, który może się zmieniać w czasie. Dane są to pewne przedmioty, na których należy wykonywać określone czynności, w wyniku których przeistoczą się one w wyniki. Upływ czasu w świecie rzeczywistym jest modelowany przez upływ czasu w komputerze, a zmiany stanów są realizowane przez przypisania.

Pojęcie czasu nie jest tak bardzo obecne w programach funkcyjnych. Oczywiście, aby użyć pojęcia musimy je najpierw zdefiniować, a żeby uzyskać wynik funkcji musimy najpierw dostarczyć argumentów. W "czystym" programowaniu funkcyjnym nie występuje jednak pojęcie zmiennej, ani przypisania. Nie ma też pętli, jako konstrukcji związanych z czasem i zmianą.

Charakterystyka programowania funkcyjnego

Jeśli nie ma zmiennych, przypisania, ani pętli, to co jest? Zamiast operacji mamy obliczanie wyrażeń. Zamiast przypisań mamy definiowanie stałych i funkcji (funkcje to w pewnym sensie też stałe, tylko bardziej skomplikowane). Zamiast pętli mamy rekurencję.

Charakterystyczne dla programowania funkcyjnego jest to, że często bardzo łatwo jest napisać poprawny program, przepisując sformułowanie problemu, choć zwykle nie jest to najefektywniejszy program. Efektywny program jest dużo trudniejszy do napisania i nie zawsze jest tak przejrzysty jak jego nieefektywny odpowiednik. Mimo wszystko, łatwiej jest weryfikować programy funkcyjne niż imperatywne. W przypadku programów imperatywnych, musimy wnioskować o zachodzących zmianach. Jeżeli mamy do czynienia z aliasingiem, musimy wiedzieć, co ulega zmianie na skutek każdego przypisania, a co nie. Narażeni jesteśmy na błędy typu: czemu ta zmienna zmieniła wartość? czy te dwie instrukcje powinny być wykonywane w tej, czy odwrotnej kolejności? W przypadku programowania funkcyjnego nie mamy takich problemów, co poprawia czytelność programów i ułatwia ich weryfikację.

Programowanie funkcyjne daje nam również do ręki pewne techniki programistyczne, które nie występują w imperatywnych językach programowania, jak: funkcje wyższych rzędów, strumienie, czy funktory. Poznamy je w trakcie tego wykładu.

Skłamałbym, gdybym twierdził, że programowanie funkcyjne jest pozbawione wad. Jedna z takich wad, którą zwykle programiści odczuwają boleśnie jest brak (w czystym programowaniu funkcyjnym) imperatywnych tablic. Można się jednak bez nich obyć, czasami modyfikując algorytm, a w najgorszym przypadku zwiększając złożoność czasową o czynnik $O(\log n)$ --- używając słownikowych struktur danych zwanych mapami.

Ocaml

Na zajęciach będziemy korzystać z języka Ocaml (Objective Caml). Jest on dostępny pod adresem http://caml.inria.fr/. Ocaml to język:

• w pełni funkcyjny,
• inkrementacyjny (cykl: wczytaj, oblicz/zdefiniuj, wypisz),
• z kontrolą typów,
• z polimorfizmem,
• pozwalający na modularyzację programów,
• bogaty --- rozbudowany system typów, biblioteki (481 str. dokumentacji, tfu!),
• z konstrukcjami imperatywnymi (hurra?) i wyjątkami (tzn. imperatywności można używać tylko w drodze wyjątku ;-),
• z których będziemy nawet korzystać (a jednak!),
• obiektowy (z tego akurat nie będziemy korzystać),
• ze statycznym wiązaniem identyfikatorów.

Kilka poglądowych przykładów

Przyjrzyjmy się kilku bardzo prostym przykładom. Skoro mówimy o programowaniu funkcyjnym, spróbujmy zaprogramować kilka prostych funkcji (Od tej pory będziemy używać słowa funkcja na określeniepojęcia matematycznego, a słowa procedura na określenie pojęcia programistycznego...WSTAWIC JAKO FOOTNOTE )

Literatura

• H.Abelson, G.J.Sussman, Struktura i interpretacja programów komputerowych, WNT 2002.
• E.Chailloux, P.Manoury, B.Pagano,Developing Applications with Objective Caml,
  http://caml.inria.fr/oreilly-book/.
• Didier Remy, Using, Understanding and Unraveling the Ocaml Language,
  http://caml.inria.fr/pub/docs/u3-ocaml/. (POPRAWIC REMY)
• X.Leroy,The Objective Caml system,
  http://caml.inria.fr/pub/docs/manual-ocaml/index.html.
• M.Benke, G.Grudziński, M.Konarski,Tajny skrypt lab ML,
  http://zls.mimuw.edu.pl/~mikon/ftp/TSLS.

Sprawy organizacyjne (CZY TO POWINNO TU BYC?)

Na zajęciach będziemy się posługiwać językiem Ocaml. Zaliczenie wykładu polega na zdaniu (prostego) egzaminu pisemnego. Zaliczenie laboratorium polega na napisaniu programu zaliczeniowego i jego ,,obronie. Program zaliczeniowy powinien być rozsądnej wielkości, świadczący o opanowaniu praktycznym programowania funkcyjnego, podzielony na moduły, przejrzyście napisany i skomentowany. Implementacja programu powinna w istotny sposób wykorzystywać funkcyjny charakter języka (procedury wyższych rzędów, funktory, strumienie, \dots). Temat programu dowolny, ale zatwierdzony przez prowadzącego laboratorium. ,,Obrona polega na 10-cio minutowej prezentacji programu.