Programowanie funkcyjne/Wstęp

Wstęp

Celem tego przedmiotu jest przedstawienie programowania funkcyjnego – paradygmatu i stylu programowania, oraz towarzyszących mu technik programistycznych. W trakcie zajęć będziemy korzystać z języka progamowania Ocaml. (Nie jest to jednak w żadnej mierze kurs programowania w Ocamlu.) Zaczniemy od krótkiego intuicyjnego porównania paradygmatu programowania funkcyjnego, oraz najpopularniejszego paradygmatu programowania – programowania imperatywnego. W kilju początkowych wykładach przedstawiamy podstawy programowania w Ocamlu. Następnie poznamy jedną z podstawowych koncepcji programowania funkcyjnego: procedury wyższych rzędów. W kolejnym wykładzie zaprezentujemy (uproszczoną) semantykę operacyjną podstawowego fragmentu języka. Następnie zajmiemy się modułami (strukturami) ich interfejsami (sygnaturami) oraz modułami sparametryzowanymi (funktorami). Poznamy też, jak w języku funkcyjnym mogą być zrealizowane konstrukcje imperatywne. Zostaną one następnie zastosowane do zaimplementowania spamiętywania i uleniwiania obliczeń. Te zaś techniki zostaną użyte do zaimplementowania strumieni. Na zakończenie przedstawimy krótki przegląd innych najpopularniejszych funkcyjnych języków programowania.

Porównanie paradygmatu funkcyjnego i imperatywnego

Najbardziej popularny paradygmat programowania, to programowanie imperatywne. Języki programowania takie, jak C, C++, Java, czy Pascal, to języki imperatywne. (Dodatkowo, część z nich to języki obiektowe.) Istotą programowania imperatywnego jest to, że program zawiera zmienne (lub obiekty) oraz operacje. Zmienne i obiekty charakteryzują się stanem, który może ulegać zmianie w czasie. Operacje służą wykonywaniu obliczeń, zmianie stanu zmiennych (przypisanie) lub obiektów, oraz kontrolują przepływ sterowania w obrębie programu.

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.

Charakterystyczne dla programowania funkcyjnego jest również to, że funkcje są "obywatelami pierwszej kategorii", tzn. przysługują im wszystkie te prawa, co innego rodzaju 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. Jak zobaczymy, zasada ta jest jak konstytucja i wiele innych cech programowania funkcyjnego będzie z niej wynikać.

Porównajmy zastosowanie paradygmatów funkcyjnego i imperatywnego do tworzenia programów. 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ć jakiegoś 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ą. Tworzenie programu polega na tworzeniu coraz to bardziej złożonych funkcji i stałych, oraz na obliczaniu wartości wyrażeń.

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 o bardziej skomplikowanej naturze). 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.

Specyfikacja programu może być mniej lub bardziej formalna. Jeśli jest sformalizowana, to zwykle ma 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. W przypadku programów funkcyjnych zarówno specyfikacja jak i program mają postać obiektów matematycznych. Stąd łatwiej wykazać poprawność programu.

W przypadku programów imperatywnych, musimy wnioskować o zachodzących zmianach stanów zmiennych lub obiektów. Jeżeli mamy do czynienia z aliasingiem lub strukturami wskaźnikowymi, 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 takie problemy w ogóle nie powstają, 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 zastępując je słownikowych strukturami danych (zwanymi mapami), co zwiększa złożoność czasową o czynnik $O(\log n)$.

Programowanie imperatywne można porównać do klucza francuskiego, a programowanie funkcyjne do kombinerek. Są to dwa narzędzia o podobnym, ale nie identycznym, przeznaczeniu. Dobry programista powinien znać oba narzędzia i wiedzieć kiedy które zastosować. Czasami należy użyć jednego z tych podejść, czasami drugiego, a czasami można je łączyć, tak aby tworzyć programy łatwo i tworzyć programy łatwe do zrozumienia.

Ocaml

W trakcie tego wykładu 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,
• z polimorfizmem,
• ze statycznym wiązaniem identyfikatorów,
• ze (statyczną) kontrolą typów,
• pozwalający na modularyzację programów,
• bogaty --- rozbudowany system typów, biblioteki (około 500 str. dokumentacji),
• zawierający konstrukcje imperatywne i wyjątki (tzn. konstrukcji imperatywnych można używać tylko w drodze wyjątku ;-),
• obiektowy (z tego akurat nie będziemy korzystać),
• inkrementacyjny (tzn. kompilator działa w cyklu: wczytaj, oblicz/zdefiniuj, wypisz).

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

Funkcję wyznaczającą wartość bezwzględną możemy opisać wzorem:

W Pascalu możemy ją zaimplementować w następujący sposób:

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

Natomiast w Ocamlu jej definicja będzie miała taką postać:

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

Zwróćmy uwagę na funkcyjny if. Nie obejmuje on instrukcji, ale wyrażenia. Powyższy kod w Ocamlu jest bliższy podanemu wzorowi, niż programowi w Pascalu.

Silnia

Wzór opisujący silnię ma postać:

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

Oto iteracyjny program w Pascalu obliczający silnię:

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

W Ocamlu iteracja jest wyrażona za pomocą rekurencji:

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

Znowu, program w Ocamlu bardziej przypomina wzór niż program w Pascalu.

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}$

Program w Pascalu:

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;

Program w Ocamlu:

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 język programowania. Jest on 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. Iteracja jest tu wyrażona za pomocą rekurencji.

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

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

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

W trakcie wykładu poznamy inne sposoby definiowania funkcji obliczającej iczby 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.