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

Odpowiedz Nowy wątek
2019-08-16 17:04
2

Przejrzałem internet i obecnie mam następującą definicję czystej funkcji (niezależnie od języka programowania):

  1. Zwracana wartość (jeśli ją ma?) zależy wyłącznie od jej argumentów. — Mówiąc kolokwialnie, nie czyta z obiektu dostępnego z zewnątrz. [wykreślone, bo błędne]
  2. Nie posiada skutków ubocznych (side effects). — Mówiąc kolokwialnie, nie pisze do obiektu dostępnego z zewnątrz. [wykreślone, bo być może błędne]

Jednak zastanawia mnie pewna rzecz: z uwagi na punkt nr 1 wszystkie funkcje, które przyjmują argumenty przez referencję, nie będą czyste.

Dedukując, za czystą można uważać jedynie funkcję przyjmującą argumenty przez wartość.

Dobrze myślę?


UPDATE: Przykład w języku JavaScript:

// Funkcja, która moim zdaniem jest czysta według powyższej definicji
//    - liczby przekazywane są przez wartość *
function(someNumber) {
    return someNumber + 1;
}

// Funkcja, która moim zdaniem nie jest czysta według powyższej definicji
//    - obiekty przekazywane są przez referencję *
function(someObject) {
    return someObject.someProperty;
}

UPDATE2: * W języku JavaScript funkcje generalnie uznawane są za takie, które przyjmują argumenty przez wartość (np. według tej dokumentacji MDN), ale najpewniej nie o takie rozróżnienie mi chodzi. MDN podaje, że "object references are values". Dlatego też pominąłem to rozróżnienie wyżej.


edytowany 13x, ostatnio: Silv, 2019-08-17 00:50

Pozostało 580 znaków

2019-08-17 00:44
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.


edytowany 10x, ostatnio: Silv, 2019-08-17 00:56

Pozostało 580 znaków

2019-08-17 10:14
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.


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.
edytowany 2x, ostatnio: Wibowit, 2019-08-17 10:15
A co jeżeli w trakcie wykonywania funkcji ktoś z innego wątku zmodyfikuje obiekt, który jest mutable? Czy to też wpływa na myślenie o czystości funkcji? - twoj_stary_pijany 2019-08-17 10:34
Jeśli ten obiekt jest dostępny tylko poprzez argument funkcji to nie wpływa. Generalnie nie ma znaczenia czy argument funkcji to mutable.Seq czy immutable.Seq jeżeli rozważana funkcja go nie zmienia. Z drugiej strony ktoś może kombinować - w rozważanej funkcji odpalamy wątek, który modyfikuje zawartość któregoś argumentu. To oczywiście sprawia, że cała ta funkcja przestaje być czysta funkcyjnie. - Wibowit 2019-08-17 10:45
w JS często właśnie porównuje się referencje niemutowalnych obiektów po to, żeby zobaczyć czy coś się zmieniło od ostatniego sprawdzania (np. czy się nie zmienił stan od ostatniego renderingu). I jeśli nowa referencja do stanu jest identyczna ze starą, czyli jest to ten sam obiekt object1 === object2 to wiemy, że nie zaszły żadne zmiany. No bo obiekty są niemutowalne. Natomiast jeśli referencje są nieidentyczne object1 !== object2 to jest możliwość (chociaż nie pewność), że zaszła jakaś zmiana i trzeba np. przerenderować komponent. - LukeJL 2019-08-17 15:29
Dlatego napisałem 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). Jeśli relacja === pociąga za sobą obserwowalną równość to można użyć === jako wstępnego sprawdzenia do przyspieszenia wykonania programu. - Wibowit 2019-08-17 15:32
chociaż można w sumie nawet tak pisać kod, żeby była pewność (czyli nigdy nie wykonywać kopii obiektów zanim faktycznie się nie zmienią - dopiero potem zrobić copy on writing). Wtedy zawsze jeśli object1 !== object2 to będziemy mieć pewność, że zaszły zmiany (bo wynika to z naszej dyscypliny pisania kodu - tak jak z dyscypliny pisania kodu może wynikać, że równe referencje są tożsame z brakiem zmiany. Bo JS sam z siebie nie wymusza niemutowalności) - LukeJL 2019-08-17 15:33
dokładnie. Szybciej jest zrobić jedno porównanie === niż sprawdzać cały obiekt strukturalnie czy wszystko ma wśrodku takie samo. - LukeJL 2019-08-17 15:33

Pozostało 580 znaków

2019-08-17 19:06
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.

edytowany 1x, ostatnio: Kalrais, 2019-08-17 19:07

Pozostało 580 znaków

2019-08-17 19:36
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).


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.

Pozostało 580 znaków

2019-08-18 00:47
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

Pozostało 580 znaków

2019-08-18 10:54
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.


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.
Pokaż pozostałe 3 komentarze
Ale wymienione przez ciebie rzeczy to głównie refactoring czysto syntaktyczny. Popatrz na rzeczy w stylu wykrywania duplikatów, albo type migration i w jak bardzo ograniczonych sytuacjach działają. - Kalrais 2019-08-18 12:45
Właśnie o refaktoring syntaktyczny mi chodziło. Skoro refaktoring syntaktyczny działa dobrze to po co kaleczyć składnię, by uprościć tenże refaktoring? Gdyby solidność refaktoringu Javy znaną z IntelliJa przenieść do Haskella (który solidnie abstrahuje efekty uboczne czasu wykonania) to czego by wtedy brakowało do tego świętego Graala? W Haskellu można bezproblemowo zrobić wykrywanie duplikatów i deduplikację (poza kodem zapakowanym w IO przynajmniej). - Wibowit 2019-08-18 12:52
Chyba się trochę zgubiłem, bo nie wiem co masz na myśli z kaleczeniem składni. Co do tego że Haskell poza IO to Święty Graal to zgoda, z tym, że w Haskellu w IO pisze się więcej kodu niż by się mogło wydawać. - Kalrais 2019-08-18 13:21
No chodzi o to, że funkcja może operować tylko na tym co dostała jako argumenty. Żadnego stanu poza argumentami, żadnych funkcji oprócz tych przekazanych przez parametry. W innym przypadku jest zależna od miejsca w kodzie w którym się znajduje, czyli jest jakaś tam super czysta. - Wibowit 2019-08-18 13:25
Ah, ok. Jeśli masz curring, to nie jest to takie straszne jakby się mogło wydawać w Haskellu możesz o tym myśleć jak zamiast add x y =x + y miałbyś coś w stylu binOp op x y = op x y i add = binOp (+) może ten przykład jest zbyt trywialny, ale w praktyce się tak dosyć często pisze, choćby ze względu na testy. - Kalrais 2019-08-18 13:38

Pozostało 580 znaków

2019-08-18 22:10
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ę.


To się ogólnie nazywa "leniwą ewaluacją". - hauleth 2019-08-19 14:12
hm, na wikipedii nazwali to Non-strict evaluation i podzielili na Call-by-name i Call-by-need (i jeszcze jakie przez makro). Różnica jest taka, że Call-by-need cache'uje wyniki (jest to prawdziwe lazy) a Call-by-name - nie i jest to ładniejszy zapis lambdy typu Function0<r> - Kamil Żabiński 2019-08-20 11:33
To Haskell byłby call-by-need a nie call-by-name. - hauleth 2019-08-20 12:55

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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