Wprowadzenie

Prezentacja: http://www.cs.put.poznan.pl/ksiek/fp/basics/

Paradygmaty

Paradygmat programowania to styl który określa podstawowe mechanizmy używane do tworzenia programów. Np. paradygmaty/style programowania:

  • obiektowy (object-oriented) – programy składają się z obiektów posiadających stan (pola) i kod (metody),
  • imperatywny (imperative) – programy składają się z sekwencji instrukcji modyfikujacych stan programu,
  • deklaratywny (declarative)– programy składają się z deklaracji opisujących stan bez wskazania przepływu sterowania,
  • aspektowy (aspect-oriented) – programy składają się z oddzielnych, przecinających się aspektów,
  • zdarzeniowy (event-driven) – przepływ sterowania oparty na wymianie komunikatów między niezależnymi częściami programu.

Paradygmaty opisują tylko pewne aspekty programowania, w związku z czym można je łączyć ze sobą. Języki programowania koncentrują się na pewnych podzbiorach paradygmatów:

  • C – imperatywny
  • Java, C#, Python, Ruby, Pascal – imperatywny + obiektowy
  • Prolog – deklaratywny

Język może używać pewnych technik jakiegoś paradygmatu, jednocześnie nie będąc “językiem tego paradygmatu,” tj. nie koncentrując się na tym paradygmacie, np.: biblioteka AspectJ pozwala na programowanie aspektowe w Javie, ale Java nie jest przez to językiem aspektowym.

Paradygmat Funkcyjny

Paradygmat funkcyjny (functional paradigm) to styl programowania deklaratywnego, gdzie wykonanie programu traktuje się jak ewaluację wyrażeń matematycznych. Jest to przeciwne programowaniu imperatywnemu, gdzie wykonanie programu jest równoznaczne z wykonaniem pewnej sekwencji instrukcji które modyfikują stan systemu. Paradygmat funkcyjny preferuje bezstanowość (statelessness), przejrzystość referencyjną (referential transparency) i niezmienność danych (immutability).

Przykładowo, jeśli mamy listę liczb całkowitych i chcemy obliczyć ich sumę, taki program w stylu imperatywnym wygladałby następująco:

def sum(list):
    result = 0
    for e in list:
       result += e
    return result

Wykonanie tego programu powoduje, że przy każdej iteracji pętli stan jest modyfikowany (wartość zmiennej result jest zmieniana na nową). W stylu funkcyjnym równowazny program można zapisać w ten sposób:

def sum(list):
    def plus(x, y):
        return x + y
    return reduce(plus, list)

Funkcja reduce zaaplikuję funkcję plus do par elementów listy i zwróci wynik. W wydaniu funkcyjnym nie istnieje stan który jest modyfikowany przy dodawaniu każdego nowego elementu.

Bezstanowość prowadzi do “bezczasowości”, podmiany wywołania funkcji przez jej implementację; eliminuje efekty uboczne, wycieki pamięci.

Programowanie funkcyjne opera się na 3 podstawowych koncepcjach które pozwalają na pisanie programów takich jak ten: funkcje pierwszej klasy, rekurencja i czystość.

Funkcje pierwszej klasy

Koncepcja funkcji pierwszej klasy (first-class functions) oznacza, że funkcje są obiektami pierwszej klasy (first-class citizens), tzn. może przypisywać je do zmiennych, przekazywać jako argument, zwracać jako wartość. Ta koncepcja jest związana z funkcjami wyższego rzędu (higher-order functions), która mówi o tym, że funkcja może otrzymać inną funkcję jako argument lub zwrócić ją jako wartość.

Mechanizm funkcji pierwszej klasy pozwala w naszym programie przekazać funkcję plus jako argument funkcji reduce.

Inne związane z tym hasłem koncepcje które będziemy zgłębiac podczas tego przedmiotu to domknięcia, częściowa aplikacja i fold.

Rekurencja

Wiele języków posiada mechanizm rekurencji (tj. wywoływanie funkcji wewnątrz ciała tejże funkcji), natomiast jest to często mechanizm o ograniczonym zastosowaniu ze względu na ograniczenia stosu. Każda funkcja przy aplikacji (wywołaniu) tworzy nową ramkę stosu która zawiera informacje potrzebne do wykonania tej funkcji (np. adres powrotu). To znaczy, że jeśli rekurencja ma głębokość n (pierwsza funkcja wywołuje drugą funkcję, która wywołuje trzecią funkcję..., która wywołuje n-tą funkcję) to na stosie powstanie n ramek. Dla dostatecznie dużego n spowoduje to, że stos przepełni pamięć.

Natomiast rekurencja jest mechanizmem, który pozwala iterować po strukturach danych bez potrzeby trzymania stanu:

def sum(list):
    if list == []:
        return 0;
    else:
        return list[0] + sum(list[1:])

W związku z tym programowanie funkcyjne polega na rekurencji (w miejsce pętli). Problem z przepełnieniem stosu jest omijany przez zastosowanie techniki programistycznej rekurencji ogonowej (tail call recursion), gdzie ostatnia operacja jaką wykonuje dana funkcja to rekorencyjne wywołanie funkcji.

def sum(list, result):
    if list == []:
        return result;
    else:
        return sum(list[1:], list[0] + result)      # tail call

Mając funkcję z rekurencją ogonową można następnie przeprowadzić optymaliację rekurencji ogonowej (tail call optimization) która polega na usunięciu ramki stosu działajacej funkcji zanim wykonamy jej ostatnią operację. W ten sposób de facto rekurencja o głębokości n zostanie wykonana w 1 ramce stosu. Dzięki temu problem przepełniania stosu nie występuje.

W językach nie-funkcyjnych ta optymalizacja może być zasymulowana przez trampolinę (trampolining).

Czystość

Funkcja jest funkcją czystą (purepurity) jeśli nie wywiera wpływu na otoczenie inaczej niż przez wynik, tj. nie zawiera efektów ubocznych (side effects). Pozwala to kompilatorowi na optymalizację (w szczególności pryz leniwej ewaluacjilazy evaluation) i daje większą kompozycyjność, a także pozwala na wykonywanie kodu współbieżnie. W efekcie języki funkcyjne mogą być referencyjnie przejrzyste (referentially transparent), tj. dane wyrażenie zawsze ewaluować będzie się w ten sam sposób.

Większość funkcyjnych języków programowania pozwala na efekty uboczne, ale ma jednocześnie pewien w pełni funkcjonalny podzbiór języka który pozwala na zupełnie czyste programowanie.

Z czystością wiążą się koncepcje leniwej ewaluacji (lazy evaluation) i niezmienności (immutability) “zmiennych” i struktur danych.

Zalety programowania funkcyjnego

Zalety programowania funkcyjnego:
  • Zwięzłość – rozwiązania prostych problemów przeniesione do kompilatora; każda linia programu jest:

    • tańsza do wytworzenia
    • tańsza w utrzymaniu
  • Programowanie współbieżne:
    • Determinizm
    • Bezpieczeństwo wątków (thread safety)
    • Mniej problemów współbieżnych
  • Testowanie jednostkowe – brak efektów ubocznych

  • Dowodzenie poprawności i optymalizacja

Maybe functional programming isn’t the answer... or maybe functional programming can’t magically protect you from using poor abstractions and writing bad code.

Michael Shaw. Game development in Scala.
Wady programowania funkcyjnego:
  • Wymagania pamięciowe.
  • Inny sposób myślenia o problemach – przestrzeń, nie czas.

Twierdzenie Church-Rosser, Church-Turing.

Języki funkcyjne

Języki funkcyjne:
  • Scala
  • Ocaml
  • F#
  • Haskel
  • Erlang
  • Lisp
  • Clojure

Podczas gdy języki funkcyjne nie są popularne, to elementy języków funkcyjnych są uznawane za

Języki z elementami funkcyjnymi:
  • Python
  • Groovy
  • Ruby
  • Javascript

Ankieta