Czy sama zapamiętana funkcja czysta jest uważana za czystą?

47

Powiedzmy, że fn(x)jest to czysta funkcja, która robi coś kosztownego, na przykład zwraca listę głównych czynników x.

Powiedzmy, że tworzymy zapamiętaną wersję tej samej funkcji memoizedFn(x). Zawsze zwraca ten sam wynik dla danych wejściowych, ale zachowuje prywatny bufor poprzednich wyników w celu poprawy wydajności.

Formalnie rzecz biorąc, jest memoizedFn(x)uważany za czysty?

Czy może jest jakaś inna nazwa lub termin kwalifikacyjny używany w odniesieniu do takiej funkcji w dyskusjach dotyczących PR? (tj. funkcja z efektami ubocznymi, które mogą wpływać na złożoność obliczeniową kolejnych wywołań, ale mogą nie wpływać na zwracane wartości).

terminology pure-function kalus
źródło
24
Może nie jest czysty dla purystów, ale „wystarczająco czysty” dla pragmatycznych ludzi ;-)
Doc Brown
2
@DocBrown Zgadzam się, zastanawiam się tylko, czy istnieje bardziej formalny termin „wystarczająco czysty”
callum
13
Wykonanie czystej funkcji najprawdopodobniej zmodyfikuje pamięć podręczną instrukcji procesora, predyktory gałęzi itp. Ale to prawdopodobnie „wystarczy” również dla purystów - lub możesz całkowicie zapomnieć o czystych funkcjach.
gnasher729
10
@callum Nie, nie ma formalnej definicji „wystarczająco czystej”. Kłócąc się o czystość i semantyczną równoważność dwóch „referencyjnie przezroczystych” wywołań, zawsze musisz dokładnie określić, którą semantykę zamierzasz zastosować. Przy niskim poziomie szczegółowości implementacji zawsze się psuje i ma różne efekty pamięci lub czasy. Właśnie dlatego musisz być pragmatyczny: jaki poziom szczegółowości jest przydatny do rozumowania twojego kodu?
Bergi
3
Następnie, ze względu na pragmatyzm, powiedziałbym, że czystość zależy od tego, czy uwzględnisz czas obliczeń jako część wyniku. funcx(){sleep(cached_time--); return 0;}zwraca tę samą wartość za każdym razem, ale będzie działać inaczej
Mars

Odpowiedzi:

41

Tak. Zapamiętana wersja funkcji czystej jest również funkcją czystą.

Wszystko, na czym zależy dbałość o czystość funkcji, to wpływ, jaki parametry wejściowe na wartość zwracaną przez funkcję (przekazanie tego samego wejścia powinno zawsze dawać to samo wyjście) i wszelkie skutki uboczne istotne dla stanów globalnych (np. Tekst na terminal, interfejs użytkownika lub sieć) . Czas obliczeń i dodatkowe użycie pamięci nie mają znaczenia dla czystości funkcji.

Pamięci podręczne czystej funkcji są prawie niewidoczne dla programu; funkcjonalny język programowania może automatycznie optymalizować czystą funkcję do zapamiętywanej wersji funkcji, jeśli może stwierdzić, że będzie to korzystne. W praktyce automatyczne określenie, kiedy zapamiętywanie jest korzystne, jest w rzeczywistości dość trudnym problemem, ale taka optymalizacja byłaby ważna.

Lie Ryan
źródło
19

Wikipedia definiuje „czystą funkcję” jako funkcję, która ma następujące właściwości:

  • Zwracana wartość jest taka sama dla tych samych argumentów (bez zmian z lokalnymi zmiennymi statycznymi, zmiennymi nielokalnymi, zmiennymi argumentami referencyjnymi lub strumieniami wejściowymi z urządzeń I / O).

  • Jego ocena nie ma skutków ubocznych (brak mutacji lokalnych zmiennych statycznych, zmiennych nielokalnych, zmiennych argumentów referencyjnych lub strumieni We / Wy).

W efekcie czysta funkcja zwraca to samo wyjście przy tych samych danych wejściowych i nie wpływa na nic poza funkcją. Dla celów czystości nie ma znaczenia, w jaki sposób funkcja oblicza wartość zwracaną, o ile zwraca to samo wyjście przy tych samych danych wejściowych.

Funkcjonalnie czyste języki, takie jak Haskell, rutynowo używają zapamiętywania, aby przyspieszyć funkcję poprzez buforowanie wcześniej obliczonych wyników.

Robert Harvey
źródło
16
Mogę coś przeoczyć, ale jak zamierzasz zachować pamięć podręczną bez skutków ubocznych?
val
1
Trzymając go wewnątrz funkcji.
Robert Harvey
4
„brak mutacji lokalnej zmiennej statycznej” wydaje się wykluczać również lokalne zmienne trwałe między wywołaniami.
val
3
To tak naprawdę nie odpowiada na pytanie, nawet jeśli wydajesz się sugerować, że tak, to jest czyste.
Mars
6
@val Masz rację: ten warunek należy nieco złagodzić. Czysto funkcjonalne zapamiętywanie, do którego się odnosi, nie ma widocznej mutacji żadnych danych statycznych. To, co się dzieje, polega na tym, że wynik jest następnie obliczany i zapamiętywany przy pierwszym wywołaniu funkcji i zwraca tę samą wartość przy każdym wywołaniu. Wiele języków ma do tego idiom: static constzmienna lokalna w C ++ (ale nie C) lub leniwie oceniana struktura danych w Haskell. Jest jeszcze jeden warunek, którego potrzebujesz: inicjalizacja musi być bezpieczna dla wątków.
Davislor
7

Tak, zapamiętane funkcje czyste są powszechnie nazywane czystymi. Jest to szczególnie powszechne w językach takich jak Haskell, w których zapamiętywane, leniwie oceniane, niezmienne wyniki są wbudowaną funkcją.

Jest jedno ważne zastrzeżenie: funkcja zapamiętywania musi być bezpieczna dla wątków, w przeciwnym razie możesz uzyskać warunki wyścigu, gdy dwa wątki będą próbowały to nazwać.

Jednym z przykładów informatyków używających w ten sposób terminu „czysto funkcjonalny” jest post na blogu Conal Elliott na temat automatycznej zapamiętywania:

Być może, co zaskakujące, zapamiętywanie można wdrożyć prosto i czysto funkcjonalnie w leniwym języku funkcjonalnym.

Istnieje wiele przykładów w recenzowanej literaturze, i były one od dziesięcioleci. Na przykład w artykule z 1995 r. „Używanie automatycznej zapamiętywania jako narzędzia inżynierii oprogramowania w rzeczywistych systemach AI”, w bardzo podobnym języku w rozdziale 5.2 opisano, co dziś nazwalibyśmy czystą funkcją:

Zapamiętywanie działa tylko dla prawdziwych funkcji, a nie dla procedur. Oznacza to, że jeśli wynik funkcji nie jest całkowicie i deterministycznie określony przez parametry wejściowe, użycie zapamiętywania da nieprawidłowe wyniki. Liczba funkcji, które można z powodzeniem zapamiętać, zostanie zwiększona poprzez zachęcanie do stosowania funkcjonalnego stylu programowania w całym systemie.

Niektóre imperatywne języki mają podobny idiom. Na przykład static constzmienna w C ++ jest inicjowana tylko raz, przed użyciem jej wartości i nigdy się nie mutuje.

Davislor
źródło
3

To zależy od tego, jak to robisz.

Zwykle ludzie chcą zapamiętywać, mutując jakiś słownik pamięci podręcznej. Ma to wszystkie problemy związane z mutacją nieczystą, takie jak martwienie się o współbieżność, martwienie się o zbyt duży rozmiar pamięci podręcznej itp.

Możesz jednak robić notatki bez mutacji nieczystej pamięci. Jednym z przykładów jest ta odpowiedź , w której śledzę zapamiętane wartości zewnętrznie za pomocą lengthsargumentu.

W linku podanym przez Roberta Harveya zastosowano leniwą ocenę, aby uniknąć skutków ubocznych.

Inną techniką, którą czasem można zobaczyć, jest wyraźne oznaczenie zapamiętywania jako nieczystego efektu ubocznego w kontekście IOtypu, na przykład z funkcją zapamiętywania efektu kota .

Ten ostatni wskazuje na to, że czasem celem jest po prostu kapsułkowanie mutacji, a nie jej eliminowanie. Większość funkcjonalnych programistów uważa, że ​​jest „wystarczająco czysty”, aby zanieczyszczenie było wyraźne i zamknięte.

Jeśli chcesz, aby termin odróżniał go od naprawdę czystej funkcji, myślę, że wystarczy powiedzieć „zapamiętany ze zmiennym słownikiem”. Dzięki temu ludzie wiedzą, jak bezpiecznie z niego korzystać.

Karl Bielefeldt
źródło
Nie wydaje mi się, aby któreś z bardziej przejrzystych rozwiązań rozwiązało powyższe problemy: chociaż tracisz obawy o współbieżność, tracisz również szansę na dwa równolegle rozpoczynane połączenia typu collatz(100)i collatz(200). I IIUIC, problem ze zbyt dużym wzrostem pamięci podręcznej (choć Haskell może mieć w tym kilka fajnych sztuczek?).
maaartinus
Uwaga: IOjest czysty. Wszystkie nieczyste metody IOi Koty są nazywane unsafe. Async.memoizejest również czysty, więc nie musimy zadowolić się „czystością” :)
Samuel
2

Zwykle funkcja, która zwraca listę, nie jest wcale czysta, ponieważ wymaga alokacji pamięci i może przez to zawieść (np. Przez zgłoszenie wyjątku, który nie jest czysty). Język, który ma typy wartości i może reprezentować listę jako typ wartości o ograniczonym rozmiarze, może nie mieć tego problemu. Z tego powodu twój przykład prawdopodobnie nie jest czysty.

Zasadniczo, jeśli zapamiętywanie można wykonać w sposób wolny od błędów (np. Poprzez statycznie przydzielone miejsce na zapamiętane wyniki i wewnętrzną synchronizację w celu kontroli dostępu do nich, jeśli język dopuszcza wątki), uzasadnione jest rozważenie takiej funkcji czysty.

R ..
źródło
0

Za pomocą monady stanu możesz zaimplementować zapamiętywanie bez skutków ubocznych .

[Monada stanu] jest w zasadzie funkcją S => (S, A), gdzie S jest typem reprezentującym twój stan, a A jest wynikiem, który funkcja wywołuje - stanem kotów .

W twoim przypadku stanem będzie zapamiętana wartość lub nic (tj. Haskell Maybelub Scala Option[A]). Jeśli zapamiętana wartość jest obecna, jest zwracana jako A, w przeciwnym razie Ajest obliczana i zwracana zarówno jako stan przejściowy, jak i wynik.

Samuel
źródło