Pure functions i programowanie funkcyjne

16 marca
Denys Dushyn
Pure functions i programowanie funkcyjne
Programowanie funkcyjne jest obecnie popularnym zagadnieniem, wiele mówi się o związanych z nim pojęciach i jego praktycznych zastosowaniach. W artykule podsumowuję moje podejście do tematu oraz dzielę się wiedzą na temat funkcji, “czystych” funkcji (en. pure functions) i pokazuję, dlaczego warto z nich korzystać.

Matematyka

“Funkcja (łac. functio, -onis „odbywanie, wykonywanie, czynność”) – dla danych dwóch zbiorów X i Y przyporządkowanie każdemu elementowi zbioru X dokładnie jednego elementu zbioru Y. Oznacza się ją na ogół f, g, h itd.” (źródło: Wikipedia)

Podstawowym celem funkcji jest, że przypisanie każdemu elementowi danego zbioru tylko jednego elementu drugiego zbioru.

Istnieją różne notacje funkcji:

  • Zapis funkcyjny

y = f(x) 

Jest odczytywany jako: y równa się f od x.

Inną reprezentacją zapisu funkcjonalnego jest zbiór przyporządkowań zgodnie z definicją funkcji:

{(x, y) } {(x, f(x)) }

  • Definicja za pomocą strzałki

f: X → Y

Wszystkie definicje odzwierciedlają istnienie połączenia pomiędzy wartościami, a każda wartość wejściowa otrzymuje tylko jedną wartość wyjściową. “Czyste” funkcje, czyli pure functions, tak samo zachowują się w informatyce.

Informatyka

Funkcja jest nazywana “czystą”, jeśli odpowiada funkcji w sensie matematycznym: łączy każdą możliwą wartość wejściową z wartością wyjściową, tyle. W szczególności:

  • nie zawiera żadnych innych obliczeń (zazwyczaj efekty, obliczenia są widoczne). To znaczy, że wywołanie funkcji nie daje żadnego zauważalnego efektu, z wyjątkiem zwracanego wyniku; nie może również, na przykład, rejestrować na dysku lub wyświetlać danych, łączyć się z bazą danych, odczytywać plików lub wysyłać pakietów przez sieć.
  • nie zależy od niczego poza swoimi parametrami. Oznacza to, że jej wywołanie w innym kontekście lub w innym czasie z tymi samymi argumentami przyniesie ten sam rezultat.

Zdefiniujmy te twierdzenia jako właściwości:

  • Funkcja zwraca tylko jedną wartość;
  • Funkcja zwraca dokładnie taki sam wynik, gdy jest wywoływana z tą samą listą argumentów;
  • Funkcja nie cechuje się stanem, ani dostępem do stanu zewnętrznego. Za każdym wywołaniem funkcji wynik będzie taki sam z tą samą listą argumentów.
  • Brak zależności od kontekstu. Nie ma znaczenia, ile razy zostanie funkcja wywołana i w jakim kontekście, będzie ona dawała ten sam wynik w różnych kontekstach.

Podsumowując: informatyka dąży do wykorzystania wszystkich właściwości funkcji z matematyki.

Dlaczego “czyste” funkcje

1. Kompozycja

Jeśli posiadasz kilka funkcji, możesz je złożyć i otrzymać kolejną funkcję. "Czyste" funkcje nadają są do kompozycji, która pozwala na zapisywanie minimalnych funkcji i komponowanie ich w większe, w celu uzyskania niezbędnych obliczeń. W przeciwieństwie do funkcji, efektów nie da się składać. Efekty są niedeterministyczne i nie zwracają wartości, więc nie ma wartości, która może być przekazana do kolejnego efektu.

2. Niezmienne struktury danych

Aby napisać “czystą funkcję” o złożonej strukturze i opisać jej zachowanie, potrzebujesz niezmiennej struktury danych (EN: immutable data structure). Jeśli struktura danych jest niezmienna, to znacznie łatwiej będzie udowodnić właściwości nowej funkcji.

3. Indukcja strukturalna

Wiele struktur w informatyce jest definiowanych cyklicznie. Ich części mają te same cechy i te same właściwości, co całe konstrukcje.

Aby formalnie mówić o takiej strukturze i udowodnić jej właściwości, można użyć uogólnienia indukcji z pola logicznego, tzw. indukcji strukturalnej. Indukcja strukturalna (EN: structural induction) jest techniką dowodową podobną do indukcji matematycznej, tylko że zamiast działania w polu liczb całkowitych dodatnich ℕ, działa w polu takich rekurencyjnie zdefiniowanych struktur.

Przykłady takich struktur:

  • drzewa binarne,
  • zestawy (tak, można definiować zestawy rekurencyjnie).

4. Przejrzystość referencyjna

Przejrzystość referencyjna (EN: referential transparency) oznacza, że funkcja może być zastąpiona jego wartością bez zmiany zachowania programu. Z definicji, każda czysta funkcja jest przejrzysta referencyjnie. Każda kompozycja “czystych” funkcji jest domyślnie “czysta” i przejrzysta. Kompozycja funkcji matematycznych jest również matematyczna i zachowuje przejrzystość referencji.

Przejrzystość referencyjna jest właściwością funkcji, która jest niezależna od kontekstu. Odgrywa on znaczącą rolę w optymalizacji programu. Oto przykłady technik:

  • Memoizacja;
  • Stałe zestawianie w kompilatorach JIT (i inne zasady przepisywania);
  • Zasady przepisywania dla obiektów kategorycznych (monoidy, funktory);
  • Obliczenia równoległe.

Podsumowanie

Paradygmat programowania funkcyjnego dąży do traktowania każdego programu jako “czystej” funkcji. Pozwala nam to spojrzeć na rozwój programów i algorytmów z nowej perspektywy - każda funkcja posiada właściwości. W związku z tym, każdy program jest przedmiotem dowodu matematycznego.

A nawet weryfikacja programu, zamiast prostych testów jednostkowych, staje się procesem semi-formalnym. Jeśli program jest funkcją, posiada właściwości, które można zweryfikować poprzez testy i dowody matematyczne.