Zgodnie z Wikipedią:
W programowaniu komputerowym funkcję można opisać jako czystą, jeśli obie instrukcje dotyczące funkcji hold: Funkcja zawsze ocenia tę samą wartość wyniku, biorąc pod uwagę te same wartości argumentu. Wartość wyniku funkcji nie może zależeć od żadnych ukrytych informacji lub stanów, które mogą się zmieniać w trakcie wykonywania programu lub między różnymi wykonaniami programu, ani też nie może zależeć od jakichkolwiek zewnętrznych danych wejściowych z urządzeń I / O. Ocena wyniku nie powoduje semantycznie obserwowalnego efektu ubocznego lub wyjścia, takiego jak mutacja obiektów podlegających mutacji lub wyjście do urządzeń I / O.
Zastanawiam się, czy można napisać funkcję obliczającą, czy funkcja jest czysta, czy nie. Przykładowy kod w JavaScript:
function sum(a,b) {
return a+b;
}
function say(x){
console.log(x);
}
isPure(sum) // True
isPure(say) // False
if (rand(1000000)<2) return WRONG_ANSWER
, wielokrotne sprawdzanie funkcji pod kątem spójnego zachowania nie pomoże. Ale jeśli masz dostęp do definicji funkcji, dowód jest trywialny.say
wywołania,console.log
które są nieczyste, są zatemsay
również nieczyste.Odpowiedzi:
Tak, jest to możliwe, w zależności od języka.
W JavaScript możesz stwierdzić, czy funkcja jest czysta, według następujących kryteriów:
Czyta tylko parametry i mieszkańców;
Pisze tylko mieszkańców;
W przypadku nielokalnych wywołuje tylko funkcje czyste;
Wszystkie funkcje, które domyślnie wywołuje, są czyste, np
toString
.; iZapisuje właściwości miejscowych tylko wtedy, gdy nie aliasują nielokalnych.
Aliasingu nie można ustalić w JavaScript w ogólnym przypadku, ponieważ zawsze można dynamicznie wyszukiwać właściwości obiektu (
object["property"]
). Pod warunkiem, że nigdy tego nie robisz i masz źródło całego programu, myślę, że problem można rozwiązać. Potrzebne byłyby również informacje o tym, które natywne funkcje mają skutki uboczne, takie jakconsole.log
większość innych elementów związanych z DOM.Termin „czysty” mógłby również zawierać pewne wyjaśnienia. Nawet w silnie, statycznie typowanym, czysto funkcjonalnym języku programowania, w którym wszystkie funkcje są względnie przezroczyste, funkcja może nadal nie zostać zakończona. Kiedy więc mówimy
id :: a -> a
, tak naprawdę nie mówimy:Ale raczej:
Ponieważ poprawna implementacja
id
toerror "Not implemented!"
. Jak zauważa Peteris, ta nieotrzymalność może być postrzegana jako rodzaj zanieczyszczenia. Koka to funkcjonalny język programowania - ze składnią wzorowaną na JavaScript - który może wywnioskować możliwe efekty, takie jak rozbieżność (nieterminacja), przejrzystość referencyjna, zgłaszanie wyjątków i działania we / wy.źródło
toString
jest czysty dla dowolnego obiektu używanego jako ciąg.function a (o) { return o.method(); }
- nie możemy właściwie odpowiedzieć na to pytanie, ponieważ zależy to odo
przekazanego parametru . Ponadto nie możemy wyjaśnić, co się stanie, jeśli wcześniej certyfikowana funkcja zostanie zmieniona na implementację nieoczyszczoną, co zawsze stanowi potencjalny problem z javascript.Nie. Możesz łatwo sprawdzić, czy funkcja wykonuje tylko operacje „czysto bezpieczne”, jak opisano w odpowiedzi Jona Purdy'ego, ale to nie wystarczy IMO, aby odpowiedzieć na pytanie.
Rozważ tę funkcję:
Oczywiście, jeśli
someCheck
jest nieczyste, to takpossiblyPure
. Ale jeślisomeCheck
jest czyste i zwracatrue
każdą możliwą wartośćx
,possiblyPure
jest czyste, ponieważ nieczytelna ścieżka do kodu jest nieosiągalna!I tu pojawia się trudna część: ustalenie, czy
someCheck
zwraca wartość true dla każdego możliwego wkładu. Próba natychmiastowej odpowiedzi na to pytanie prowadzi do królestwa problemu zatrzymania i podobnych problemów nierozstrzygalnych.EDYCJA: Dowód, że jest to niemożliwe
Istnieje pewna niepewność, czy funkcja musi kończyć się na każdym możliwym wejściu. Ale w obu przypadkach problem zatrzymania można wykorzystać do wykazania, że sprawdzenie czystości jest niemożliwe.
Przypadek A) Jeśli czysta funkcja jest zobowiązany do wypowiedzenia się na każdy możliwy wkład, to mają do rozwiązania problemu stopu w celu ustalenia, czy funkcja ta jest czysta. Ponieważ wiadomo, że jest to niemożliwe, z tej definicji nie można obliczyć czystości.
Przypadek B) Jeśli na niektórych danych wejściowych może się nie kończyć funkcja czysta, możemy skonstruować coś takiego: Załóżmy, że
isPure(f)
oblicza, czyf
jest łańcuchem definiującym funkcję czystą.Teraz
isPure
musi ustalić, czyf
zatrzymuje się we własnym źródle jako dane wejściowe. Jeśli się zatrzyma,upf
jest nieczyste; jeśli się nie skończy,upf
to jest czyste ifff
jest czyste.Gdyby
isPure
działał zgodnie z oczekiwaniami (zwraca poprawne wyniki i kończy się na każdym wejściu), rozwiązalibyśmy problem zatrzymania (*)! Ponieważ wiadomo, że jest to niemożliwe,isPure
nie może istnieć.(*) dla funkcji czystego JavaScript, co jest wystarczające, aby rozwiązać to również dla maszyny Turinga.
źródło
W tym pytaniu dotyczącym przepełnienia stosu znajduje się odpowiednia odpowiedź yfeldblum. (I z jakiegoś powodu ma opinię negatywną, której nie mogę pojąć. Czy etykietowanie czegoś, co ma 3 lata, byłoby kiepską etykietą?) Daje dowód, że to, czy funkcja jest czysta, można w komentarzu zredukować do problemu zatrzymania.
Myślę, że z praktycznego punktu widzenia niektóre języki nie byłyby zbyt trudne, jeśli pozwolisz na powrót funkcji tak, nie, a może. Kilka dni temu oglądałem wideo o Clojure, a mówca wykonał wiele przypadków nieczystości w bazie kodu, szukając około 4 różnych ciągów (np. „Ref”). Ze względu na nacisk Clojure na czystość i segregację nieczystych rzeczy, było to trywialne, ale nie było dokładnie to, czego szukasz.
Więc teoretycznie niemożliwe, praktycznie możliwe, jeśli trochę poprawisz pytanie, i myślę, że to, jak trudne byłoby to w dużej mierze zależy od języka. Łatwiejsze / prostsze języki z naciskiem na niezmienność i dobre odbicie.
źródło
bottom
jest ważną wartością pierwszej klasy, nie zasługuje na dyskryminację w ten sposób.Świetne pytanie.
Najlepsze, co możesz zrobić w praktyce, zakładając brak możliwości słuchania działań we / wy w celu wywołania funkcji tyle razy, ile to możliwe. Następnie sprawdź, czy zwracana wartość jest spójna.
Ale ogólnie nie możesz tego zrobić. Prawdopodobnie programy, które nie zatrzymują się, nie są czyste i nie możemy rozstrzygnąć problemu zatrzymania.
źródło
void
funkcja byłaby „czysta”, co jest oczywiście fałszywe.Niemożliwe w ogólnym przypadku. Zobacz problem zatrzymania . W skrócie, nie można napisać programu, który przy dowolnej funkcji i danych wejściowych określa, czy program się zatrzyma, czy będzie działał na zawsze. Jeśli działa wiecznie, nie jest to czysta funkcja pasująca do podanej definicji.
źródło
bottom
wartości.