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ą (pure – purity) 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 ewaluacji – lazy 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
Materiały¶
- Książki:
- Joshua Suereth D. Scala in Depth. (dostępna w BT)
- Martin Odersky, Lex Spoon, Bill Venners. Programming in Scala. (dostępna online)
- Michel Schinz, Philipp Haller. Scala Tutorial for Java programmers. (dostępna online)
- Harold Abelson, Gerald Jay Sussman, Julie Sussman. Structure and Interpretation of Computer Programs (dostępna online)
- Wideo:
- Kelsey Innis. Learning Functional Programming without Growing a Neckbeard. SF Scala 2012.
- Neal Ford. Functional Thinking. OSCON 2013.
- Martin Odersky. Working Hard to Keep It Simple. OSCON Java 2011.
- Martin Odersky. Scala – the Simple Parts. SF Scala 2014.
- Venkat Subramaniam. Why Scala?
- Philip Wadler. Faith, Evolution, and Programming Languages: from Haskell to Java. Tech Mesh 2012.
- Rúnar Bjarnason. Functional Programming is Terrible. NEScala 2014.
- Robert C Martin. Functional Programming; What? Why? When? NDC2014. (Motywacja).
- Rich Hickey. The Values of Values. JaxConf 2012.
- John Hughes and Mary Sheeran. Why Functional Programming Matters. Code Mesh 2015. (Historia i ciekawostki).
- Inne: