PF:Moduł Wstęp

Test animacji

<applet code="PSViewer" archive="images/d/dd/Psviewer.jar" align="left" width="600" height="580"> <param name="DIR" value="images/3-4/"> </applet>

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.

Uwaga

Od tej pory będziemy używać słowa funkcja na określenie pojęcia matematycznego, a słowa procedura na określenie pojęcia programistycznego

Wartość bezwzględna

Przykład Wartość bezwzględna

Wzór: $|x|=\{\begin{array}{ll}x& \text{; gdy }x\ge 0\\ -x& \text{; gdy }x<0\end{array}$

Pascal:

function abs(x : real) : real;
begin
  if x >= 0.0 then abs := x else abs := -x
end;

Ocalm:

let abs x = 
  if x >= 0.0 then x else -. x;;

Zwróćmy uwagę na funkcyjny \codeline{if}.

Przykład Wartość bezwzględna

Wzór:

$|x|=\{\begin{array}{ll}x& \text{; gdy }x\ge 0\\ -x& \text{; gdy }x<0\end{array}$

Pascal:

function abs(x : real) : real;
begin
  if x >= 0.0 then abs := x else abs := -x
end;

Ocalm:

let abs x = 
  if x >= 0.0 then x else -. x;;

Zwróćmy uwagę na funkcyjny if.

Silnia

Wzór:

$\begin{array}{c}0!=1\\ n!=n\cdot (n-1)!\end{array}$

Pascal:

function silnia (n : integer): integer;
var
  i, a : integer;
begin
  a := 1;
  for i := 1 to n do
     a := a * i;
  silnia := a
end;

Ocaml:

let rec silnia n = 
  if n < 2 then 1 else n * silnia (n - 1);;

Liczby Fibonacciego

Wzór:

$\begin{array}{c}{\text{Fib}}_0=0\\ {\text{Fib}}_1=1\\ {\text{Fib}}_n={\text{Fib}}_{n-2}+{\text{Fib}}_{n-1}\end{array}$

Pascal:

function fib (n : integer) : integer;
var
  a, b, c, i : integer;
begin
  a := 0;
  b := 1;
  for i := 1 to n do begin
    c := a + b;
    a := b;
    b := c
  end;
  fib := a
end;

Ocaml:

let rec fib n = 
  if n < 2 then n else fib (n - 1) + fib (n - 2);;

Taki program jest prostym przełożeniem wzoru na program, jest jednak nieefektywny. Możemy zapisać program działający podobnie do powyższego programu w Pascalu, gdzie w każdym kroku iteracji pamiętamy dwie kolejne liczby Fibonacciego.

let rec fibpom n = 
  if n = 0 then
    (0, 1)
  else
    let (a, b) = fibpom (n - 1)
    in (b, a + b);;

Procedura pomocnicza \codeline{fibpom} spełnia specyfikację: $\text{fibpom n}=({\text{Fib}}_n,{\text{Fib}}_{n+1})$.

let fib n =
  let (a, b) = fibpom n
  in a;;

W trakcie wykładu poznamy lepsze sposoby definiowania liczb Fibonacciego.

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 Rémy, Using, Understanding and Unraveling the Ocaml Language,
  http://caml.inria.fr/pub/docs/u3-ocaml/.
• 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.

Uwaga

W niniejszych notatkach wykorzystano fragmenty innych pozycji poświęconych programowaniu funkcyjnemu, lub ogólnie programowaniu, a w szczególności z następujących pozycji: M.Benke, G.Grudziński, M.Konarski, Tajny skrypt lab SML, A.Tarlecki, slajdy do wykładu z Programowania funkcyjnego, M.Kubica, notatki do wykładu ze Wstępu do programowania (potok funkcyjny),publikacje Olimpiady Informatycznej,podanej literatury.

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.