Zalety czystej funkcji

82

Dzisiaj czytałem o czystej funkcji, pomyliłem się z jej użyciem:

O funkcji mówi się, że jest czysta, jeśli zwraca ten sam zestaw wartości dla tego samego zestawu danych wejściowych i nie ma żadnych obserwowalnych skutków ubocznych.

np. strlen()jest czystą funkcją, podczas gdy rand()jest nieczysta.

http://ideone.com/33XJU

Powyższy program zachowuje się analogicznie jak w przypadku braku puredeklaracji.

Jakie są korzyści z zadeklarowania funkcji jako pure[jeśli nie ma zmiany w wyniku]?

Zielony Goblin
źródło
7
Tak - spójrz na wygenerowany zespół.
Philip Kendall
4
Nie sądzę, aby ta definicja czystości była poprawna - printfna przykład kwalifikowałaby się (dwukrotne wywołanie jej z tymi samymi argumentami daje tę samą wartość zwracaną), ale nie jest czysta.
tdammers
14
@tdammers: Rzeczywiście, brakuje jej ...and no side-effects...części.
Frerich Raabe
2
@Ben: skąd bierze się entropia? Mamy tu do czynienia z (teoretycznie) deterministycznymi maszynami, jedynym sposobem na uzyskanie w nich prawdziwej entropii są źródła zewnętrzne, co oznacza efekty uboczne. Oczywiście moglibyśmy pozwolić językom programowania na definiowanie niedeterministycznych funkcji, udając, że nie ma technicznych skutków ubocznych, a funkcje naprawdę są niedeterministyczne; ale jeśli to zrobimy, większość praktycznych korzyści płynących ze śledzenia czystości zostanie utracona.
tdammers
3
tdammers jest poprawna - podana powyżej definicja czystego jest niepoprawna. Czysty oznacza, że ​​dane wyjściowe zależą tylko od wejść funkcji; również nie może być żadnych obserwowalnych skutków ubocznych. „Te same dane wyjściowe dla tych samych danych wejściowych” to bardzo niedokładne podsumowanie tych wymagań. en.wikipedia.org/wiki/Pure_function
Dancrumb

Odpowiedzi:

145

pure pozwala kompilatorowi wiedzieć, że może dokonać pewnych optymalizacji dotyczących funkcji: wyobraź sobie kawałek kodu, na przykład

Dzięki czystej funkcji kompilator może wiedzieć, że musi przeprowadzić ocenę fun(10)raz i tylko raz, a nie 1000 razy. W przypadku złożonej funkcji to duża wygrana.

Philip Kendall
źródło
To znaczy, możesz bezpiecznie używać zapamiętywania
Joel Coehoorn
@mob Co masz na myśli? Dlaczego nie?
Konrad Rudolph
15
Ponieważ możesz modyfikować ciąg (sekwencję znaków zaczynających się od jakiegoś adresu) bez modyfikowania wejścia (wskaźnika do adresu, na którym zaczyna się ciąg), tj. Nie możesz go zapamiętać. Byłaby to tylko czysta funkcja w języku z niezmiennymi ciągami znaków (powiedzmy w Javie).
tłum
5
@KonradRudolph: Wyobraź sobie ciąg o długości 1000. Wezwij strlento. Potem znowu. To samo tak? Teraz zmodyfikuj drugi znak, który ma być \0. Czy strlennadal zwraca teraz 1000? Adres początkowy jest taki sam (wejście == jest takie samo), ale funkcja zwraca teraz inną wartość.
Mike Bailey
5
@mob To dobry zarzut, oczywiście masz rację. Zmylił mnie fakt, że nawet książki twierdzą, że strlen(w GCC / glibc) jest w rzeczywistości czyste. Ale spojrzenie na implementację glibc pokazało, że to błąd.
Konrad Rudolph
34

Kiedy mówisz, że funkcja jest „czysta”, gwarantujesz, że nie ma ona żadnych zewnętrznych efektów ubocznych (a jak mówi komentarz, jeśli kłamiesz, mogą się zdarzyć złe rzeczy). Świadomość, że funkcja jest „czysta”, przynosi korzyści kompilatorowi, który może wykorzystać tę wiedzę do wykonania pewnych optymalizacji.

Oto, co dokumentacja GCC mówi o pureatrybucie:

czysty

Wiele funkcji nie ma żadnych efektów poza wartością zwracaną, a ich wartość zwracana zależy tylko od parametrów i / lub zmiennych globalnych. Taka funkcja może podlegać zwykłej eliminacji podwyrażeń i optymalizacji pętli, tak jak byłby to operator arytmetyczny. Funkcje te należy zadeklarować z atrybutem pure. Na przykład,

Odpowiedź Philipa już pokazuje, jak wiedza o funkcji jest „czysta” może pomóc w optymalizacji pętli.

Oto jedno z typowych eliminacji podwyrażeń (podane foojest czyste):

Może zostać:

ArjunShankar
źródło
3
Nie jestem pewien, czy któryś to robi, ale czyste funkcje umożliwiają również kompilatorowi zmianę kolejności, gdy funkcja zostanie wywołana, jeśli uzna, że ​​zmiana kolejności byłaby korzystna. Gdy istnieje możliwość wystąpienia efektów ubocznych, kompilator musi być bardziej konserwatywny.
mpdonadio
@MPD - Tak, to brzmi rozsądnie. A ponieważ callinstrukcja jest wąskim gardłem dla superskalarnych procesorów, pomoc ze strony kompilatora może pomóc.
ArjunShankar
Mglisto przypominam sobie, jak kilka lat temu korzystałem z kompilatora DSP, który używałby tej techniki do uzyskania wartości zwracanych wcześniej / później. Pozwoliło to zminimalizować zatorów w rurociągach.
mpdonadio
1
Czy „foo (99)” może zostać obliczone wstępnie, ponieważ 99 jest stałą, a foo zawsze zwróci ten sam wynik? Może w jakiejś dwuetapowej kompilacji?
markwatson
1
@markwatson - nie jestem pewien. Mogą zdarzyć się sytuacje, gdy jest to po prostu niemożliwe. np. jeśli foojest częścią innej jednostki kompilacji (inny plik C) lub w wstępnie skompilowanej bibliotece. W obu przypadkach kompilator nie będzie wiedział, co foorobi i nie może wstępnie obliczyć.
ArjunShankar,
29

Oprócz możliwych korzyści w czasie wykonywania, czysta funkcja jest znacznie łatwiejsza do rozważenia podczas czytania kodu. Ponadto o wiele łatwiej jest przetestować czystą funkcję, ponieważ wiesz, że wartość zwracana zależy tylko od wartości parametrów.

Frerich Raabe
źródło
3
+1, twoja uwaga dotycząca testowania jest interesująca. Nie jest wymagana konfiguracja ani demontaż.
ArjunShankar
15

Nie czysta funkcja

jest jak rozszerzenie czystej funkcji

w którym oprócz jawnych argumentów funkcji x, y masz resztę wszechświata (lub cokolwiek, z czym twój komputer może się komunikować) jako niejawne potencjalne dane wejściowe. Podobnie, poza jawną wartością zwracaną w postaci liczby całkowitej, wszystko, do czego komputer może zapisać, jest niejawnie częścią wartości zwracanej.

Powinno być jasne, dlaczego wnioskowanie o czystej funkcji jest znacznie łatwiejsze niż o nieczystej.

Giorgio
źródło
1
+1: Wykorzystanie wszechświata jako potencjalnego wkładu jest bardzo dobrym sposobem wyjaśnienia różnicy między czystym a nieczystym.
ArjunShankar
w istocie taka jest idea monad.
Kristopher Micinski
7

Jako dodatek chciałbym wspomnieć, że C ++ 11 kodyfikuje pewne rzeczy za pomocą słowa kluczowego constexpr. Przykład:

Ograniczenia dotyczące użycia constexpr sprawiają, że funkcja jest dająca się udowodnić czystość. W ten sposób kompilator może bardziej agresywnie optymalizować (po prostu upewnij się, że używasz rekurencji ogonowej, proszę!) I oceniać funkcję w czasie kompilacji, a nie w czasie wykonywania.

A więc, odpowiadając na twoje pytanie, jeśli używasz C ++ (wiem, że powiedziałeś C, ale są one powiązane), napisanie czystej funkcji w odpowiednim stylu pozwala kompilatorowi robić różne fajne rzeczy z funkcją: -)

Robert Mason
źródło
4

Ogólnie rzecz biorąc, funkcje Pure mają 3 zalety w porównaniu z nieczystymi funkcjami, z których kompilator może skorzystać:

Buforowanie

Powiedzmy, że masz czystą funkcję, fktóra jest wywoływana 100000 razy, ponieważ jest deterministyczna i zależy tylko od jej parametrów, kompilator może obliczyć jej wartość raz i użyć jej w razie potrzeby

Równoległość

Czyste funkcje nie odczytują ani nie zapisują w żadnej pamięci współdzielonej i dlatego mogą działać w oddzielnych wątkach bez żadnych nieoczekiwanych konsekwencji

Przekazywanie przez odniesienie

Funkcja f(struct t)pobiera argument tprzez wartość, az drugiej strony kompilator może przekazać tprzez odwołanie do, fjeśli jest zadeklarowana jako czysta, gwarantując, że wartość tnie zmieni się i przyniesie wzrost wydajności


Oprócz kwestii związanych z czasem kompilacji, czyste funkcje można testować dość łatwo: wystarczy je wywołać.

Nie ma potrzeby tworzenia obiektów ani pozorowania połączeń z bazami danych / systemem plików.

Uri Goren
źródło