Oblicz, jeśli funkcja jest czysta

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

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.

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.

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.

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

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.