Podstawy Programowania Funkcyjnego Epizod 2

michalkulinski.blogspot.com 5 lat temu

Dlaczego to programowanie nazywa się funkcyjne?

W poprzednim odcinku opowiedziałem Ci, o co chodzi z tym całym zgiełkiem wokół programowania funkcyjnego. Pamiętasz? Przejrzystość Referencyjna i pociąg towarowy z wieloma rdzeniami? Skoro jesteś tu, i czytasz odcinek 2., zakładam, iż moje argumenty przekonały Cię i chcesz dowiedzieć się czegoś więcej.

Poniższy tekst jest luźnym tłumaczeniem wpisu bloga Roberta Cecila "Wujka Boba" Martina z dnia 02 stycznia 2013 ze strony:

https://blog.cleancoder.com/uncle-bob/2013/01/02/FPBE2-Whys-it-called-functional.html

Proszę o komentarze, o ile ta luźność jest zbyt daleko posunięta.

A więc następnym pytaniem, które czeka na odpowiedź, jest: Dlaczego to nazywa się "Funkcyjnym" programowaniem? Prostą odpowiedzią na to pytanie jest to, iż Programowanie Funkcyjne to programowanie przy użyciu funkcji (ehhh). Spośród wszystkich odpowiedzi, ta jest całkiem słaba. No, jest akurat precyzyjna, i brzmi całkiem nieźle; ale tak naprawdę nie odpowiada na nasze pytanie. W końcu, programy napisane w Javie są programami z funkcjami.

A więc dlaczego słowo "funkcyjne"?

Wkurzę pewnie w tej chwili wszystkich matematycznych perfekcjonistów; ponieważ zamierzam użyć analogii z rachunkiem różniczkowym. Nie będę się tym przejmował za bardzo, ponieważ po prostu ukradłem ten pomysł z Wikipedii.

Czy wiesz, co znaczy $\frac{dy}{dx}$? W szczególności, w wyrażeniu $\frac{dy}{dx}$ czym jest $y$? Oczywiście $y$ jest funkcją. Wyrażenie $\frac{dy}{dx}$ jest pochodną tej funkcji. Czyli $\frac{dy}{dx}$ przyjmuje funkcję jako swój argument wejściowy i zwraca pochodną tej funkcji jako wynik. Mam rację?

Rozważ $\frac{d(x^2)}{dx}$: to równa się $2x$. Zauważ, iż $2x$ jest funkcją. Więc argument wejściowy i wyjściowa wartość są obie funkcjami.

Czekaj. Jak nazwiesz coś, co przyjmuje argumenty i zwraca wartość? Nazwiesz to funkcją. A więc $\frac{dy}{dx}$ jest funkcją, która przyjmuje funkcję i zwraca funkcję.

Co by było, gdybyśmy mieli taki język programowania komputerów? Co by było, gdybyśmy mogli pisać funkcje, które przyjmują funkcje jako argumenty, operować na nich, bez rozwiązywania ich, i potem zwracać nowe funkcje jak wynik? Jak byś nazwał taki język? Jakie inne słowo mogłoby być lepsze niż: funkcyjny?

I już widzę tych wściekłych na mnie purystów języków funkcyjnych wściekłych za to, iż to kompletnie nieodpowiedni sposób definicji języka funkcyjnego. Ale to jest jeden krok do przodu – i to bardzo istotny krok.

A więc, co to znaczy przesłać funkcję jako argument do innej funkcji? Spójrzmy jeszcze raz na program "kwadraty liczb całkowitych". Pamiętasz? To było po prostu:

(take 25 (squares-of (integers)))

Zróbmy z tego funkcję, dodając nazwę i definicję argumentu:

(defn squint [n]
  (take n (squares-of (integers))))

Jestem pewny, iż ogarniasz składnię sam. To nic trudnego.

Mając definicję squint, możemy wyświetlić 25 kwadratów liczb całkowitych przy użyciu:

(println (squint 25))

Jak dotąd, to nic innego, jak tylko proste wywołania funkcji i definicje. Ale czym jest ta funkcja squares-of. Jak jest zdefiniowana?

(defn square [n] (* n n))

(defn squares-of [list]
  (map square list))

Teraz zaczyna się robić trochę bardziej interesująco! Nie jest niespodzianką, iż funkcja square po prostu mnoży argument przez jego samego. To definicja squares-of jest interesująca, ponieważ przesyła funkcję square jako argument do funkcji o nazwie map.

Funkcja map jest jedną z podstaw programowania funkcyjnego. Pobiera dwa argumenty: funkcję f i listę l; i zwraca nową listę, wywołując funkcję f na każdym elemencie listy l.

Przesyłanie funkcji jako argument to nie jest coś, co programiści Javy robią często. Z drugiej strony nie jest to zupełnie obcy pomysł. Każdy programista Javy, który uczył się Wzorca Polecenie, lub używał Listenerów w Swingu, zrozumie, co tu się dzieje.

Co więcej, w tej chwili coraz więcej języków programowania zaczęło wykorzystywać pomysł funkcji przekazywanych jako argumenty. Ta funkcjonalność jest czasem nazywana "bloki" lub "lambdy". Jest bardzo częstym elementem języka Ruby; stała się ostatnio istotną częścią C#. Chodzą słuchy, iż ta funkcjonalność zostanie dodana w Javie niedługo.[1]

Więc może nie będziemy musieli uczyć się nowego języka. Może nasze stare języki będą stawały się coraz bardziej i bardziej funkcyjne i będziemy mogli używać tych funkcyjnych funkcjonalności, jak tylko staną się on coraz bardziej dostępne.

Ta droga prowadzi do szaleństwa, płaczu i zgrzytania zębami! Język z elementami funkcyjnymi nie jest językiem funkcyjnym; i program napisany z kilkoma lambdami tu i tam, nie jest funkcyjnym programem.

Żeby przekonać się, dlaczego to prawda, musimy spojrzeć na funkcję integers.

(defn integers []
  (integers-starting-at 1))

OK, to nic trudnego. Funkcja integers-starting-at po prostu przyjmuje liczbę całkowitą jako argument i zwraca listę wszystkich liczb całkowitych, zaczynając od tego, co jest w argumencie.

(defn integers-starting-at [n]
  (cons n (lazy-seq (integers-starting-at (inc n)))))

Ten przykład wymaga słówka wyjaśnienia. Ale nie bój się, to jest adekwatnie całkiem proste.

Na początku jest funkcja cons; która jest skrótem dla "zbuduj listę" (construct list). Funkcja cons przyjmuje dwa argumenty: element, i listę. Zwraca nową listę jako starą listę z dołożonym z przodu elementem. Czyli (cons 2 [3 4]) zwraca [2 3 4].

Teraz z kolei wszyscy ludzie od Clojure są wkurzeni na mnie, bo to nie jest do końca tak. Z drugiej strony różnica jest czymś, czym nie musimy się teraz przejmować. Na tę chwilę zapamiętaj tylko to: funkcja cons tworzy listę poprzez dołożenie jej pierwszego argumentu do drugiego; który to drugi musi być listą.

Teraz możesz sobie pomyśleć, iż cons po prostu przyczepia ten element z przodu listy; ale to nie jest tak. W rzeczywistości, to nie jest choćby bliskie prawdy. Widzisz, cons w żaden sposób nie zmienia listy z drugiego argumentu. Zamiast tego zwraca całkiem nową listę złożoną z zawartości listy z drugiego argumentu i elementu dodanego na początku.

O kurcze, teraz to już ludzie od Clojure są na mnie naprawdę źli; ponieważ to znowu nie do końca prawda. I pewnie masz mnie za wariata, bo co za głupek kopiowałby całą zawartość jednej listy do drugiej listy tylko po to, żeby wrzucić jeden element na początek?

OK, więc tak, cons w zasadzie rzeczywiście wkłada element na początek listy, i nie, nie kopiuje starej listy do nowej listy. Z drugiej strony, robi to w taki sposób, iż możesz udawać, iż listy wejściowa i wyjściowa są zupełnie inne. Praktycznie rzecz biorąc, wyjście cons jest całkowicie nową listą - nawet, jeżeli tak nie jest.

Zbity z tropu? Nie martw się, w rzeczywistości to nie jest takie trudne do zrozumienia. Rozważ listę [1 2 3]. o ile zaimplementujemy ją jako listę jednokierunkową, będzie wyglądała tak: 1->2->3. Teraz odpalmy cons z 0 na początku. To daje nam 0->1->2->3. Zauważ jednak, iż stara lista przez cały czas istnieje w nowej liście. To jest ta tajemnica! Stara lista pozostaje niezmieniona w nowej liście. Więc możemy stworzyć pozory, iż cons zwróci całkiem nową listę, pozostawiając starą listę niezmienioną.

To jest wskazówka do wyjaśnienia tego, co wszystkie prawdziwe języki funkcyjne tak naprawdę robią. One pozwalają Ci tworzyć coś, co wydaje Ci się być całkowicie nowymi strukturami danych, podczas gdy zachowują stare struktury danych nietknięte; i robią to bez kopiowania. W kręgach funkcyjnych to jest znane jako trwałość; co więcej, struktury danych, które zachowują się w ten sposób, są znane jako trwałe struktury danych. Takie struktury danych zarządzają cały czas swoją historią. Nic nigdy nie zostaje wyedytowane lub skasowane w ich wnętrzu. Jednak mają one wiele różnych "punktów-wejścia" i każdy z nich zapewnia inny widok na dane. Pomyśl o tym, jak o systemie zarządzania kodem źródłowym. Chociaż kasujesz i edytujesz linie kodu, nic nigdy nie kasuje się ani nie edytuje w repozytorium kodu źródłowego. Cała historia jest zachowana. Po prostu masz różne punkty wejścia do kodu źródłowego, które pozwalają Ci widzieć różne migawki z przeszłości.

A więc wróćmy do naszego programu. Spójrzmy na integers-starting-at

(defn integers-starting-at [n]
  (cons n (lazy-seq (integers-starting-at (inc n)))))

Co jest tym, co funkcja cons dodaje z przodu i z przodu czego to jest dodawane? Podczas pierwszego przejścia n będzie 1, więc cons zwróci listę, która rozpoczyna się od 1. To ma oczywisty sens, ponieważ naszym celem jest wyświetlenie kwadratu z 1.

OK, ale co jest to coś, do którego cons dokłada 1? To jasne, iż 1 jest dodawana na początku listy zwracanej przez funkcję lazy-seq.

Tutaj zaczyna się magia. Widzisz, lazy-seq jest funkcją, która zwraca tzw. leniwą sekwencję. Leniwa sekwencja to zwykła lista — ale z niespodzianką. Zamiast listy jednokierunkowej z wartościami takimi, jak 1->2->3, leniwa sekwencja jest wartością połączoną z funkcją: 1->f. Ta funkcja, kiedy jest wywołana, zwraca następną wartość połączoną z inną funkcją: 2->f. I z jaką funkcją te wartości są połączone? Popatrz dobrze! To argument funkcji lazy-seq.

Tym argumentem funkcji lazy-seq jest rekurencyjne wywołanie funkcji integers-starting-at z argumentem wartości funkcji (inc n). Funkcja inc po prostu zwraca jej argument powiększony o 1.

A więc czym jest leniwa sekwencja? Leniwa sekwencja jest listą, której elementy są obliczane tylko wtedy, kiedy są potrzebne, i nie wcześniej. Za każdym razem, kiedy prosisz leniwą sekwencję o następny element w liście, ona po prostu wywołuje funkcję, która jest powiązana z aktualnym elementem.

Stąd, leniwa sekwencja nie ma rozmiaru. Możesz wciąż i wciąż pytać o więcej elementów w nieskończoność; i wciąż te elementy nie zostaną obliczone, dopóki to nie będzie potrzebne.

Funkcja map też zwraca leniwą sekwencję. Tu jest przykład implementacji:

(defn map [f l]
  (if (empty? l)
    []
    (cons (f (first l)) (lazy-seq (map f (rest l))))))

Funkcja first po prostu zwraca pierwszy element listy będącej jej argumentem. Funkcja rest po prostu zwraca listę z argumentu minus jej pierwszy element; czyli resztę listy. Więc map jest po prostu rekurencyjną funkcją, która odpala funkcję f na każdym elemencie listy l, tworząc nową leniwą sekwencję wyników.

Została nam jeszcze jedna rzecz, zanim złożymy wszystko razem: funkcja take. Po tym wszystkim, co do tej pory razem przeszliśmy, ta będzie naprawdę bardzo prosta.

(defn take [n l]
  (if (zero? n)
    []
    (cons (first l) (take (dec n) (rest l)))))

Jak widzisz, funkcja take zwraca listę złożoną z pierwszych n elementów listy l.

A teraz, poćwiczmy trochę Przejrzystość Referencyjną, i rozkodujmy (ręcznie) wartość wywołania:

(squint 2)

Najpierw podmieńmy squint jej definicją.

Potem podmieńmy take jej definicją. To jest trochę zawiłe, bo musimy użyć rekurencji.

(if (zero? 2)
  []
  (cons (first (squares-of (integers)))
    (if (zero? (dec 2))
      []
      (cons (first (rest (squares-of (integers))))
        (if (zero? (dec (dec 2)))
          []
          ...)))))

Zatrzymałem się na trzecim wyrażeniu if, ponieważ (dec (dec 2)) wynosi zero. W rzeczywistości znamy wartość logiczną tych if-ów, więc możemy usunąć je wszystkie:

(cons (first (squares-of (integers)))
  (cons (first (rest (squares-of (integers))))
    []))

To jasne, iż mając tylko dwa wywołania funkcji cons, ten fragment kodu zwróci listę z dwoma elementami w środku. Możemy trochę posprzątać, zamieniając wywołania funkcji integers z ich definicjami.

(cons (first (squares-of (integers-starting-at 1)))
 (cons (first (rest (squares-of (integers-starting-at 1))))
   []))

Ponieważ wywołanie (squares-of (integers-starting-at 1)) występuje dwa razy, obliczmy je raz i zamieńmy wywołania z ich wartościami. Zaczniemy zamianę od squares-of:

(map square (integers-starting-at 1)

A potem integers-starting-at:

(map square (cons 1 (lazy-seq (integers-starting-at 2)))

Teraz zamieńmy map. Ponieważ map zaczyna się z (if (empty? l) ...), i ponieważ (cons 1...) gwarantuje, iż lista nie będzie pusta, możemy pominąć wyrażenie if i użyć tylko ciała funkcji.

(cons (square (first (cons 1 (lazy-seq...))))
  (map square (rest (lazy-seq (integers-starting-at 2)))))

Te wywołanie do first może być łatwo zredukowane:

(cons (square 1)
  (map square (rest (lazy-seq (integers-starting-at 2)))))

A teraz odrobinę więcej magii. Wywołanie funkcji rest zwraca "resztę" listy poprzez wywołanie funkcji przesłanej do lazy-seq

(cons (square 1)
  (map square (integers-starting-at 2)))

Możemy powtórzyć tę analizę dla (map square (integers-starting-at 2)):

(cons (square 1)
  (cons (square 2)
    (map square (integers-starting-at 3)))

I teraz możemy zredukować funkcję squares

(cons 1
  (cons 4
    (map square (integers-starting-at 3)))

Zostawiliśmy naszą poprzednią analizę dla całej funkcji w następującym stanie:

(cons (first (squares-of (integers-starting-at 1)))
  (cons (first (rest (squares-of (integers-starting-at 1))))
    []))

Teraz możemy wstrzyknąć naszą wartość dla (squares-of (integers-starting-at 1)).

(cons
  (first (cons 1
            (cons 4
            (map square (integers-starting-at 3))))
  (cons
    (first (rest (cons 1
                    (cons 4
                    (map square (integers-starting-at 3)))))
    []))

Pierwsze first jest łatwo zredukować. (first (cons x 1)) to po prostu x; więc możemy zignorować drugi argument funkcji cons.

(cons
  1
  (cons
    (first (rest (cons 1
                       (cons 4
                       (map square (integers-starting-at 3)))))
    []))

Te (first (rest...)) jest także łatwo obliczyć.

(cons
  1
  (cons 4 []))

I wynik tego, to oczywiście [1 4].

Zauważyłeś, co stało się z tym (integers-starting-at 3)? Nigdy nie zostało obliczone. Dlaczego? Ponieważ oryginalna (take 2...) potrzebowała tylko 2 wartości, więc trzecia nigdy nie była potrzebna.

I to prowadzi do ważnego odkrycia. Większość z nas pisze programy, które przepychają dane przez całość programu. Ale (take 25 (squares-of (integers))) jest pętlą, która ciągnie dane poprzez całość programu. To jest gruntowna różnica, i coś, nad czym później zamierzamy spędzić dużo więcej czasu.

Do tego momentu wszyscy ludzie od Clojure, wszyscy ludzie od programowania funkcyjnego, i wszyscy ludzie od matematyki są już na mnie porządnie wściekli; ponieważ tak bardzo uprościłem. I to jest prawda; jest ogrom rzeczy, po których tylko się prześlizgnąłem i na które machnąłem ręką. I przez cały czas to, co Ci tu przekazałem, jest w rzeczywistości poprawne. Jest to także całkiem niezła prezentacja potęgi traktowania funkcji jako danych, które mogą być przesyłane i zwracane z funkcji.

I to prowadzi nas do sedna tego epizodu. Teraz już możemy odpowiedzieć na pytanie postawione pod tytułem. Nazywamy ten styl programowania funkcyjnym, ponieważ to wszystko jest o traktowaniu funkcji jak cząstek danych, którymi manipuluje się w taki sam sposób jak znakami czy liczbami. Ludzie od programowania funkcyjnego odnoszą się do nich jako do typów pierwszoklasowych. Język funkcyjny jest językiem, który używa funkcji jako typów pierwszoklasowych, promuje przejrzystość referencyjną poprzez usuwanie przypisań, i zachowuje historię danych poprzez trwałe struktury danych.

Jak nauczymy się w następnych odcinkach, ta definicja nie jest ani pełna, ani w pełni adekwatna; ale na tę chwilę... wystarczy.

Powyższy tekst jest luźnym tłumaczeniem wpisu bloga Roberta Cecila "Wujka Boba" Martina z dnia 02 stycznia 2013 ze strony:

https://blog.cleancoder.com/uncle-bob/2013/01/02/FPBE2-Whys-it-called-functional.html

Proszę o komentarze, o ile ta luźność jest zbyt daleko posunięta.

[1] - Została dodana dopiero 18 marca 2014 roku wraz z 8. wersją Javy. [przyp. tłum.]

Idź do oryginalnego materiału