Czy czyste funkcje mogą przyjmować argumenty tylko przez wartość?

0

2019, prawie 2020, a ludzie dalej nie odróżniają funkcji czystych od pół czystych LOOOL

3

Moje rozumowanie obecnie jest takie, że (nadal) zgadzam się z definicją funkcji czystej podaną w moim pierwszym poście, a ponadto:

  1. Jak wspominał m.in. @twoj_stary_pijany, @LukeJL, @hauleth i @Wibowit, dany język może wymusić, że dana funkcja będzie czysta (np. języki czysto funkcyjne lub takie posiadające odpowiednie słowa kluczowe). Wniosek: w każdym języku trochę co innego może być funkcją czystą. Niemniej nadal niektóre (wszystkie?) języki mogą posiadać jakąś wspólną definicję funkcji czystej.
  2. Jak wspomniał m.in. @lion137, programista może funkcję napisać tak, by była lub nie była czysta. Jest to rzecz oczywista, niemniej godna odnotowania według mnie.
  3. Jak wspomnieli m.in. @katelx, @LukeJL i @Maciej Cąderek, rzeczywiście "czystość" danej funkcji nie zależy od tego, co robi się poza nią z obiektem przekazywanym do niej. Przykładowo, jeśli do funkcji min przekazuje się referencję do listy liczb, to dodając do owej listy liczbę między wywołaniami tej funkcji, burzy się być może jakiś inny paradygmat programowania funkcyjnego, ale nie "czystość" tej konkretnej funkcji.
  4. Jak wspomniał @LukeJL, czasami "czystość" można ocenić zależnie od tego, do czego nam ona "jest potrzebna".

Jeśli pominąłem kogoś, kto też pisał o powyższych punktach, przepraszam. Proszę wpisać się w komentarzu, to dodam.


UPDATE: Nadal więc, można powiedzieć, poszukuję definicji funkcji czystej wspólnej dla wszystkich języków programowania, ale coraz bardziej mam wrażenie, że jest to podróż w stronę końca tęczy.


UPDATE2: Zapomniałbym: jak wspomnieli @Wibowit i @Maciej Cąderek, z podanych przeze mnie w pierwszym poście kolokwialnych definicji cech funkcji czystej przynajmniej pierwsza jest błędna, patrząc ogólnie. Druga – nie jestem pewien, ale być może jest z tego samego powodu, co pierwsza. Niemniej wykreślę, żeby nie wprowadzać zamieszania.


UPDATE3: Co do pierwotnego problemu poruszanego przez wątek – przekazywanie argumentów. Nie jest to, jak obecnie myślę, istotne dla "czystości" funkcji. Dlaczego. Uznaję możliwości przekazania parametru za zależne od danego języka – a więc patrz punkt nr 1; wybór którejś możliwości podpada natomiast pod punkt nr 2.

4

@Silv:
Czystość funkcyjną trzeba rozważać też w kontekście konsekwencji tej czystości. Weźmy pod uwagę taki kod:

val a = new java.lang.Integer(5)
val b = new java.lang.Integer(5)

val result1 = method(a, a)
val result2 = method(a, b)

Spodziewamy się iż zawsze result1 == result2 ale czy będzie tak gdy method będzie porównywać referencje? Nie. Przy takiej definicji:

def method(a: java.lang.Integer, b: java.lang.Integer): Boolean =
  a eq b // odpowiednik Javowego: a == b

result1 będzie true, a result2 będzie false.

Powyższe zachowanie sprawia, że podstawowa optymalizacja (common subexpression elimination - tutaj tym wspólnym wyrażeniem jest new Integer(5)) która miała zawsze działać w czystym funkcyjnie kodzie nagle przestała działać. Stąd po prostu trzeba założyć, że w czystej funkcji nie ma porównywania referencji. Dla przykładu porównywania referencji wprost nie ma w Haskellu czy Clojure (można się dobrać do nich za pomocą IO i innych trików, ale to już jest mieszanie kodu czysto funkcyjnego z imperatywnym).

Jeżeli założymy, że nie możemy porównywać referencji (a przynajmniej, że porównywanie referencji nie może być obserwowalne z zewnątrz) to samo przekazywanie referencji do funkcji bez możliwości sprawdzania dokąd prowadzą nie miałoby sensu. Nic by się nie dało z takimi referencjami zrobić co by mogło wpłynąć na wynik. Stąd trzeba tych referencji użyć by dostać się do składowych obiektu (idąc dalej: składowych całego grafu obiektów osiągalnego zaczynając od tej referencji). Wszystkie te składowe to de facto argumenty funkcji zgrupowane w obiekt.

Mówiąc inaczej w czystym funkcyjnie kodzie wartość x powinna być nieodróżnialna od x.clone() (przy założeniu poprawności metody clone()). Stąd w zasadzie można wywnioskować, że sposób przekazywania argumentów (przez wartość czy przez referencję) nie powinien niczego zmieniać. Przekazywanie argumentu przez wartość to jest taki mniej więcej x.clone(), tyle że sklonowany obiekt ląduje w nowej ramce stosu (tzn w ramce stosu odpowiadającej wywołaniu funkcji, której przekazujemy x), a nie na stercie.

3

Czystość funkcji jest powiązana z formalną analizą semantyki programów, w której przydatną własnością jest Referential Transparency bez której w dowodach własności programów musiałbyś analizować każde wywołanie funkcji oddzielnie i nie można by wykorzystać podejścia indukcyjnego. Czystość funkcji jest tutaj warunkiem koniecznym dla RT, ale nie wystarczającym (Purity vs RT). W dodatku w środowisku naukowym nie ma do końca konsensusu w kwestii formalnej definicji czystości i chociaż na Wiki można znaleźć całkiem sensowną definicję to pozostawia ona jednak trochę do interpretacji:

In computer programming, a pure function is a function that has the following properties:

  1. Its return value is the same for the same arguments (no variation with local static variables, non-local variables, mutable reference arguments or input streams from I/O devices).
  2. Its evaluation has no side effects (no mutation of local static variables, non-local variables, mutable reference arguments or I/O streams).
  • (1) mówi o tym, że wyniki dla tych samych argumentów mają być równe. To implikuje 2 rzeczy. Po pierwsze jest tu przemycona implicite relacja równości i jak słusznie zauważył @Wibowit inne będą skutki przyjęcia równości strukturalnej, która dominuje w językach funkcyjnych, inna równości referencji, a takie potworki jak JS-owy (==) w ogóle się tutaj nie nadają, bo nawet nie spełniają kryterium relacji równoważności. Drugą sprawa jest, że ta definicja oznacza, że wszystkie zmienne od których zależy wynik funkcji muszą być przekazana explicite jako argumenty tej funkcji. I teraz możemy sobie wyobrazić, że w języku który pozwalałby np. wstrzyknąć inną definicje operatora w określonym kontekście funkcja function add(x, y) { return x + y; } nie byłaby czysta bo (+) jest potencjalnie zmienną, co zawęża właściwie czyste funkcje do lambda termów, co przy analizie praktycznych języków nie jest zbyt pomocne. Tak samo sprawa wygląda z obiektami które są współdzielone przez kilka wątków, bo nawet jeśli w takim C++ mamy referencje na constowy obiekt, to to jeszcze nie oznacza, że inny wątek nie wykonuje w tym momencie funkcji, która ten obiekt może modyfikować, żeby radzić sobie z takimi sytuacjami Rust ma całą masę innych mechanizmów jak ownership, borrowing, czy life scope'y.
  • (2) też jest kontrowersyjna. No bo czy mówimy o jakichkolwiek efektach ubocznych czy tylko o tych obserwowalnych z zewnątrz, to znaczy, czy jeśli mutuje lokalną strukturę w funkcji to czy to wciąż jest czysta funkcja? Tym razem z punktu czystości jako narzędzia do analizy formalnej jak najbardziej tak, ale są puryści (hehe), którzy twierdzą, że nie.

Inna kwestia, którą poruszał @Silv to czy na podstawie sygnatury funkcji można stwierdzić czy funkcja jest czysta. No i w 99% języków programowania nie można. Nawet w takim Elmie, który jest funkcyjny i niemutowalny możesz użyć loggera korzystając z konstrukcji let _ = Debug.log something in x, czyli potencjalnie każda funkcja jest nieczysta (inna sprawa czy taka nieczystość, to rzeczywiście problem). W takim D, który niby ma adnotację pure, to daje ona tylko gwarancję tzw. "weak purity" - docs. Żeby sygnatura na prawdę przekazywała jakieś informacje o czystości funkcji to musimy informację o efektach ubocznych zawrzeć explicite w sytemie typów i jeszcze zadbać o to żeby wszystkie nieczyste funkcje (które najczęściej są wrapperami na syscalle) były dobrze otypowane tak jak Haskellu. To co natomiast można zrobić to można na podstawie generycznej sygnatury funkcji, znaleźć jedyne możliwe czyste implementacje - Theorems for free.

tl;dr; Pojęcie czystości funkcji nie jest precyzyjne i ludzie piszący lub badający różne języki pewnie będą szczegóły rozpatrywali inaczej. Ogólna idea jest dobrze wyrażona w definicji z Wikipedii.

3

I teraz możemy sobie wyobrazić, że w języku który pozwalałby np. wstrzyknąć inną definicje operatora w określonym kontekście funkcja function add(x, y) { return x + y; } nie byłaby czysta bo (+) jest potencjalnie zmienną, co zawęża właściwie czyste funkcje do lambda termów, co przy analizie praktycznych języków nie jest zbyt pomocne. Tak samo sprawa wygląda z obiektami które są współdzielone przez kilka wątków, bo nawet jeśli w takim C++ mamy referencje na constowy obiekt, to to jeszcze nie oznacza, że inny wątek nie wykonuje w tym momencie funkcji, która ten obiekt może modyfikować, żeby radzić sobie z takimi sytuacjami Rust ma całą masę innych mechanizmów jak ownership, borrowing, czy life scope'y.

Wstrzykiwanie + czy mutowanie z innych wątków to wciąż mutowanie stanu na którym operuje funkcja, więc łamie zasady podane w wiki. Z drugiej strony czytanie z niemutowalnego stanu nie będącego argumentami funkcji nie łamie tej definicji. Nie bardzo widzę jak mechanizmy z C++ czy Rusta cokolwiek tu zmieniają.

No bo czy mówimy o jakichkolwiek efektach ubocznych czy tylko o tych obserwowalnych z zewnątrz, to znaczy, czy jeśli mutuje lokalną strukturę w funkcji to czy to wciąż jest czysta funkcja?

Wg definicji z wiki tak, jest czysta. Tworzenie świeżego, prywatnego, mutowalnego stanu na czas wywołania funkcji nie łamie żadnej z tych zasad: no mutation of local static variables, non-local variables, mutable reference arguments or I/O streams.

Moim zdaniem można by rozróżnić czystą funkcję od czystej implementacji. Na najniższym poziomie (czyli procesora) czystości funkcyjnej nie ma, gdyż wszystkie procesory opierają się na efektach ubocznych. Zawsze jakiś rejestr procesora albo komórka pamięci zostanie zamazana. Z poziomu kodu jednak nie da się stwierdzić nieczystości funkcji np Math.max. Stąd można założyć iż jest zewnętrznie czysta, tzn jest czysta z punktu widzenia wołającego tę funkcję (= klienta).

1

@Wibowit Z wstrzykiwaniem kontekstu i wątkami chodziło mi o to, że jeśli jesteś odpowiednio skrupulatny, to okaże się, że czyste są tylko funkcje które są zapisem lambda termów (operują tylko na swoich argumentach, które są niemutowalne, niektórzy nawet definiują czystość nie na poziomie funkcji, ale całego języka - paper), ale w praktyce to oznacza, że takie pojęcie czystości byłoby nieprzydatne, bo 99,9% funkcji takie nie jest. Dlatego raczej zakłada się bardziej pragmatyczne podejście i czystość danej funkcji rozważa się w kontekście konkretnego programu lub zastosowań i nie przejmujesz się tym czy ktoś w runtimie podmieni implementację biblioteki standardowej. Twoja "zewnętrzna czystość" to w sumie właśnie takie podejście.

Z Rustem chodziło o to, że możesz wyrazić w systemie typów, że dana referencja może być dostępna na raz tylko dla jednego callera (wątku) i kompilator to Ci zagwarantuje. W C++ żeby to uzyskać musisz się synchronizować, co w oczywisty sposób jest nieczyste. Inaczej mówiąc Rust daje więcej narzędzi do zagwarantowania pełnej czystości funkcji, nawet w środowisku wielowątkowym. Jest to rozwinięcie ideii typów/logiki liniowej

0

Poczytałem trochę o tych super czystych językach. Założenie, że funkcja (jak i cała reszta programu) ma działać tak samo jeśli przeniesie się ją w dowolne inne miejsce bez żadnych zmian jest absurdalne. Zysk jest praktycznie zerowy, a strata w ekspresyjności ogromna. Porządne IDE dzięki statycznej analizie bez problemu radzi sobie z zasięgami zmiennych, przesłanianiem, przeciążaniem, nadpisywaniem, dziedziczeniem, nawigacją, refaktorem itd w statycznie typowanych językach. Nie popadajmy w skrajności.

0

Jeśli już jesteśmy przy Referential Transparency to oprócz przekazywania przez wartość w dobrych językach funkcyjnych jest jeszcze przekazywanie przez nazwę. Ma to Scala. W Haskellu chyba wszystkie argumenty są przekazywane przez nazwę.

1 użytkowników online, w tym zalogowanych: 0, gości: 1