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 kilku 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). Dowiemy się 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: Haskella i Scheme'a (dialektu Lispu).

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 coraz bardziej skomplikowane pojęcia matematyczne, 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łownikowymi 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 przede wszystkim 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,
• 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ć),

Haskell

Innym popularnym językiem funkcyjnym jest Haskell ([1]). Haskell to język:

• czysto funkcyjny (bez konstrukcji imperatywnych),
• leniwy,
• z polimorfizmem,
• ze statycznym wiązaniem identyfikatorów,
• ze (statyczną) kontrolą typów,
• pozwalający na modularyzację programów,

Scheme

[2] to dialekt języka Lisp opracowany na MIT. Jest to język:

• w pełni funkcyjny,
• minimalistyczny,
• z polimorfizmem,
• z dynamicznym wiązaniem identyfikatorów,
• z dynamiczną kontrolą typów,
• zawierający konstrukcje imperatywne,

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:

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

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;;

W Haskellu taką:

abs x | x > 0 = x
      | x < 0 = -x

A w Scheme'ie taką:

(define (abs x) 
  (if (>= x 0) x (- x)))

Zwróćmy uwagę na funkcyjny if. Nie obejmuje on instrukcji, ale wyrażenia. Powyższy kod w językach funkcyjnych 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 językach funkcyjnych iteracja jest wyrażona za pomocą rekurencji. W Ocamlu:

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

W Haskellu:

silnia 0 = 1
silnia n = n * silnia (n - 1)

W Scheme'ie:

(define (factorial n) 
  (if (= n 0) 1 (* n (factorial (- n 1)))))

Znowu, program funkcyjny 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);;

W Haskellu:

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

W Scheme'ie:

(define (fib n) 
  (if (< n 2) n (+ (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.

W Ocamlu:

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

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

W Haskellu:

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

W Scheme'ie:

(define (fibpom n)
  (if (= n 0) 
      (cons 0 1) 
      (let ((p (fibpom (- n 1))))
           (cons (cdr p) (+ (car p) (cdr p))))))

(define (fib n) (car (fibpom n)))

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

W trakcie wykładu poznamy inne sposoby definiowania funkcji obliczającej liczby Fibonacciego.

Literatura

• [AS] H. Abelson, G. J. Sussman, Struktura i interpretacja programów komputerowych, WNT 2002.
• [L] X. Leroy, The Objective Caml system, [3]
• [ChMP] E. Chailloux, P. Manoury, B. Pagano, Developing Applications with Objective Caml, [4]
• [R] D. Rémy, Using, Understanding and Unraveling the Ocaml Language, [5]
• [GIH] P. Hudak, J. Peterson, J. Fasel, A Gentle Introduction to Haskell, [6]
• [RWH] B. O'Sullivan, D. Stewart, J. Goerzen, Real World Haskell, O'Reilly 2008, [7]

Podziękowania

Niniejsze materiały powstały na podstawie notatek do prowadzonych przeze mnie, na przestrzeni kilku lat, wykładów z Programowania funkcyjnego, oraz ze Wstępu do programowania i Metod programowania (w ramach potoku funkcyjnego). Chciałbym gorąco podziękować moim kolegom, którzy w tym czasie prowadzili ćwiczenia z tych przedmiotów, a w szczególności: Jackowi Chrząszczowi, Grzegorzowi Grudzińskiemu i Mikołajowi Konarskiemu. Ich uwagi miały wpływ na postać prowadzonych zajęć, a więc i również na te materiały. W szczególności część zamieszczonych tu zadań pochodzi od nich.