Oblicz, jeśli funkcja jest czysta

11

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
Oni
źródło
7
Może to być kandydat na Computer Stack Stack Exchange . To raczej dotyczy dziedziny teorii („możliwej”) niż praktycznej i projektowej… To trochę poza moim zasięgiem.
... i chociaż jest to „możliwe” i „teoria”, istnieje bardzo prawdopodobne, że istnieje na to prawdziwa odpowiedź (dobre dopasowanie do pytań i odpowiedzi), która może nawet obejmować dowód ... który ponownie przenosi ją do świata informatyki .
Myślę, że można ustalić, czy funkcja jest czysta, patrząc na typ funkcji wywoływanych w jej definicji. Chodzi mi o to, że można zdefiniować czystość poprzez indukcję struktury funkcji.
Giorgio
7
Nie da się obejść bez specyficznych dla platformy hacków refleksyjnych. Jeśli funkcja jest czarną skrzynką, żaden eksperyment nie może udowodnić, że jest czysta. Na przykład, jeśli istnieje coś takiego 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.
SK-logic
1
@ user470365 Zgodnie z definicją czystej funkcji - „Ocena wyniku nie powoduje żadnych semantycznie obserwowalnych skutków ubocznych lub wyników, takich jak mutacja obiektów podlegających mutacji lub danych wyjściowych w urządzeniach I / O”. - Wszystko, co pisze do IO, jest z definicji nieczyste. W tym przykładzie saywywołania, console.logktóre są nieczyste, są zatem sayrównież nieczyste.

Odpowiedzi:

17

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.; i

  • Zapisuje 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 jak console.logwię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:

Biorąc pod uwagę pewną wartość typu a, funkcja idgeneruje wartość typu a.

Ale raczej:

Biorąc pod uwagę pewną wartość typu afunkcja idma nie wytwarzają wartość, która jest nie typu a.

Ponieważ poprawna implementacja idto error "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.

Jon Purdy
źródło
+1 - Biorąc pod uwagę odpowiedź Peterisa, otrzymano tyle głosów poparcia .....
mattnz
Przypuszczam, że trzeba by dodać „Wywołuje tylko funkcje czyste” do listy kryteriów.
Greg Hewgill
1
@GregHewgill: Dobry połów. Odpowiednio zaktualizowałem odpowiedź. Można wywoływać funkcje mutacji u miejscowych, o ile nie wywołują one skutków ubocznych. „Czysty” to zbyt przeciążony termin…
Jon Purdy
Musisz także sprawdzić, czy toStringjest czysty dla dowolnego obiektu używanego jako ciąg.
Oleg V. Volkov
Nie sądzę, aby ta odpowiedź była poprawna, ponieważ istnieje tylko podzbiór okoliczności, w których można faktycznie dokonać tych ustaleń. Zastanów się: czy ta funkcja jest czysta? function a (o) { return o.method(); }- nie możemy właściwie odpowiedzieć na to pytanie, ponieważ zależy to od oprzekazanego 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.
Jules
11

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ę:

function possiblyPure(x) {
    if (someCheck(x)) {
        return x+1; // pure code path
    }
    else {
        console.log("I'm so unpure..."); // unpure code path
    }
}

Oczywiście, jeśli someCheckjest nieczyste, to tak possiblyPure. Ale jeśli someCheckjest czyste i zwraca truekażdą możliwą wartość x, possiblyPurejest czyste, ponieważ nieczytelna ścieżka do kodu jest nieosiągalna!

I tu pojawia się trudna część: ustalenie, czy someCheckzwraca 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, czy fjest łańcuchem definiującym funkcję czystą.

function halts(f) {
   var fescaped = f.replace(/\"/g, '\\"');
   var upf = 'function() { '+f+'("'+fescaped+'\); console.log("unpure"); }';
   return isPure(upf);
}

Teraz isPuremusi ustalić, czy fzatrzymuje się we własnym źródle jako dane wejściowe. Jeśli się zatrzyma, upfjest nieczyste; jeśli się nie skończy, upfto jest czyste iff fjest czyste.

Gdyby isPuredział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, isPurenie może istnieć.

(*) dla funkcji czystego JavaScript, co jest wystarczające, aby rozwiązać to również dla maszyny Turinga.

użytkownik 281377
źródło
3
Prawdziwe. Zawsze można przeprowadzić konserwatywną analizę - aby sprawdzić, czy funkcja jest zdecydowanie czysta, ale nie można sprawdzić, czy zdecydowanie nie jest czysta.
SK-logic
Wiele przypadków można rozstrzygać w sposób trywialny - te czyste funkcje opisane przez Jona Purdy'ego lub nieczyste funkcje, które bezwarunkowo robią coś brudnego; ale ogólnie można konstruować przypadki nierozstrzygalne.
user281377,
1

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.

Michael Shaw
źródło
Sądzę, że został odrzucony, ponieważ jest zły. bottomjest ważną wartością pierwszej klasy, nie zasługuje na dyskryminację w ten sposób.
SK-logic
0

Ś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.

Piotr jest
źródło
1
-1: Napisanie funkcji, która przejdzie ten test i nie jest niczym innym, jak nie byłoby trywialne.
mattnz
3
Zgodnie z tą logiką każda voidfunkcja byłaby „czysta”, co jest oczywiście fałszywe.
Greg Hewgill
1
@Greg: Zasadniczo void foo (void) musiałoby być również czyste.
mattnz
0

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.

dbkk
źródło
5
Wydaje się, że ciągłe działanie nie wyklucza funkcji spełniającej kryteria czystej funkcji.
whatsisname
+1: Domyślnie wymagane jest, aby funkcja kończyła się słowami „Funkcja zawsze ocenia tę samą wartość wyniku daje ....”
mattnz
2
Konsekwentne działanie wieczne bez zmiany jakiegokolwiek stanu jest całkowicie „czyste”. Ale oczywiście jest to kwestia terminologii.
SK-logic
@mattnz, taka funkcja zawsze będzie oceniać do bottomwartości.
SK-logic
1
Widzę, gdzie pojawia się problem z terminologią. W niektórych interpretacjach „czysta” funkcja jest funkcją deterministyczną, która nigdy nie komunikuje żadnego stanu ani wartości z zewnątrz podczas jej wykonywania. W innych interpretacjach do wymagań dodano zatrzymanie. Dzięki pierwszej interpretacji łatwo jest ustalić, czy funkcja jest czysta: maszyna wykonująca określony język powinna być w stanie ustalić, czy program w tym języku komunikuje się z otoczeniem.
rwong