Co to jest przejrzystość referencyjna?

38

Widziałem to w paradygmatach imperatywnych

f (x) + f (x)

może nie być taki sam jak:

2 * f (x)

Ale w paradygmacie funkcjonalnym powinno być tak samo. Próbowałem zaimplementować oba przypadki w Pythonie i Scheme , ale dla mnie wyglądają tak samo prosto.

Jaki byłby przykład, który mógłby wskazać różnicę w stosunku do danej funkcji?

asgard
źródło
7
Możesz i często robisz pisać referencyjnie przezroczyste funkcje w Pythonie. Różnica polega na tym, że język tego nie wymusza.
Karl Bielefeldt
5
w C i podobnie: f(x++)+f(x++)może nie być tym samym, co 2*f(x++)(w C jest szczególnie piękny, gdy takie rzeczy są ukryte w makrach - czy złamałem sobie nos na tym? założycie się)
gnat
W moim rozumieniu przykładem @ gnat jest to, dlaczego języki funkcjonalnie zorientowane, takie jak R, wykorzystują przekazywanie referencji i jawnie unikają funkcji modyfikujących ich argumenty. Przynajmniej w języku R może być trudne omijanie tych ograniczeń (przynajmniej w stabilny, przenośny sposób) bez zagłębiania się w skomplikowany system środowisk, przestrzeni nazw i ścieżek wyszukiwania w języku.
shadowtalker
4
@ssdecontrol: W rzeczywistości, gdy masz przejrzystość referencyjną, wartość pass-by-pass i pass-by-referencja zawsze dają dokładnie ten sam wynik, więc nie ma znaczenia, którego używa język. Języki funkcjonalne są często określane za pomocą czegoś podobnego do parametru pass-by-value dla przejrzystości semantycznej, ale ich implementacje często używają pass-by-referencji dla wydajności (lub nawet obu, w zależności od tego, który jest szybszy dla danego kontekstu).
Jörg W Mittag,
4
@gnat: W szczególności f(x++)+f(x++)może być absolutnie wszystkim, ponieważ wywołuje niezdefiniowane zachowanie. Ale to nie jest tak naprawdę związane z przejrzystością referencyjną - co nie pomogłoby w tym wywołaniu, jest „niezdefiniowane” dla referencyjnie przejrzystych funkcji, jak sin(x++)+sin(x++)również w. Może mieć 42 lata, może sformatować dysk twardy, demony wylatują z nosa użytkownika…
Christopher Creutzig

Odpowiedzi:

62

Przezroczystość referencyjna, odnosząca się do funkcji, wskazuje, że wynik zastosowania tej funkcji można określić tylko na podstawie wartości jej argumentów. Możesz pisać referencyjnie przezroczyste funkcje w dowolnym języku programowania, np. Python, Scheme, Pascal, C.

Z drugiej strony, w większości języków możesz także pisać funkcje nie referencyjnie przejrzyste. Na przykład ta funkcja Pythona:

counter = 0

def foo(x):
  global counter

  counter += 1
  return x + counter

nie jest referencyjnie przejrzysty, w rzeczywistości dzwoni

foo(x) + foo(x)

i

2 * foo(x)

wygeneruje różne wartości dla każdego argumentu x. Powodem tego jest to, że funkcja używa i modyfikuje zmienną globalną, dlatego wynik każdego wywołania zależy od tego zmieniającego się stanu, a nie tylko od argumentu funkcji.

Haskell, język czysto funkcjonalny, ściśle oddziela ocenę wyrażeń, w której stosowane są funkcje czyste i która zawsze jest referencyjnie przejrzysta, od wykonania akcji (przetwarzanie wartości specjalnych), która nie jest referencyjnie przejrzysta, tj. Wykonanie tej samej akcji może mieć za każdym razem inny wynik.

Tak więc dla dowolnej funkcji Haskell

f :: Int -> Int

i dowolną liczbą całkowitą x, zawsze tak jest

2 * (f x) == (f x) + (f x)

Przykładem akcji jest wynik funkcji biblioteki getLine:

getLine :: IO String

W wyniku oceny wyrażenia ta funkcja (właściwie stała) przede wszystkim generuje czystą wartość typu IO String. Wartości tego typu są wartościami jak każda inna: możesz je przekazywać, umieszczać w strukturach danych, komponować je za pomocą specjalnych funkcji i tak dalej. Na przykład możesz zrobić listę takich akcji:

[getLine, getLine] :: [IO String]

Działania są wyjątkowe, ponieważ można powiedzieć środowisku wykonawczemu Haskell, aby je wykonał, pisząc:

main = <some action>

W takim przypadku, po uruchomieniu programu Haskell, środowisko wykonawcze przechodzi przez akcję związaną z nią maini wykonuje ją, prawdopodobnie powodując efekty uboczne. Dlatego wykonywanie akcji nie jest względnie przejrzyste, ponieważ dwukrotne wykonanie tej samej akcji może dać różne wyniki w zależności od tego, co środowisko wykonawcze otrzymuje jako dane wejściowe.

Dzięki systemowi typów Haskell nigdy nie można użyć akcji w kontekście, w którym oczekiwany jest inny typ, i odwrotnie. Jeśli więc chcesz znaleźć długość łańcucha, możesz użyć lengthfunkcji:

length "Hello"

zwróci 5. Ale jeśli chcesz znaleźć długość ciągu odczytywanego z terminala, nie możesz pisać

length (getLine)

ponieważ pojawia się błąd typu: lengthoczekuje wprowadzenia listy typów (a String jest rzeczywiście listą), ale getLinejest wartością typu IO String(akcja). W ten sposób system typów zapewnia, że ​​wartość akcji podobna getLine(której wykonanie odbywa się poza językiem podstawowym i która może być niereferencyjnie przezroczysta) nie może być ukryta wewnątrz wartości typu non-action Int.

EDYTOWAĆ

Aby odpowiedzieć na pytanie exizt, oto mały program Haskell, który odczytuje wiersz z konsoli i drukuje jego długość.

main :: IO () -- The main program is an action of type IO ()
main = do
          line <- getLine
          putStrLn (show (length line))

Główna akcja składa się z dwóch podgrup, które są wykonywane sekwencyjnie:

  1. getlinetypu IO String,
  2. drugi konstruuje się, oceniając funkcję putStrLntypu String -> IO ()na podstawie jej argumentu.

Dokładniej, druga akcja jest zbudowana przez

  1. powiązanie linez wartością odczytaną przez pierwszą akcję,
  2. ocena funkcji czystych length(oblicz długość jako liczba całkowita), a następnie show(zamień liczbę całkowitą na ciąg znaków),
  3. budowanie akcji poprzez zastosowanie funkcji putStrLndo wyniku show.

W tym momencie można wykonać drugą akcję. Jeśli wpiszesz „Cześć”, wyświetli się „5”.

Zauważ, że jeśli otrzymujesz wartość z akcji za pomocą <-notacji, możesz użyć tej wartości tylko w innej akcji, np. Nie możesz napisać:

main = do
          line <- getLine
          show (length line) -- Error:
                             -- Expected type: IO ()
                             --   Actual type: String

ponieważ show (length line)ma typ, Stringpodczas gdy notacja wymaga, aby po akcji ( getLinetypu IO String) następowała kolejna akcja (np. putStrLn (show (length line))typu IO ()).

EDYCJA 2

Definicja przejrzystości referencyjnej Jörga W. Mittaga jest bardziej ogólna niż moja (poparłem jego odpowiedź). Użyłem ograniczonej definicji, ponieważ przykład w pytaniu koncentruje się na wartości zwracanej funkcji i chciałem zilustrować ten aspekt. Jednak RT ogólnie odnosi się do znaczenia całego programu, w tym zmian stanu globalnego i interakcji ze środowiskiem (IO) spowodowanych oceną wyrażenia. Tak więc, aby uzyskać poprawną, ogólną definicję, należy odnieść się do tej odpowiedzi.

Giorgio
źródło
10
Czy downvoter może zasugerować, jak mogę poprawić tę odpowiedź?
Giorgio
Jak zatem uzyskać długość łańcucha odczytywanego z terminala w Haskell?
sbichenko
2
Jest to wyjątkowo pedantyczne, ale ze względu na kompletność, to nie system typowy Haskella zapewnia, że ​​działania i czyste funkcje się nie mieszają; to fakt, że język nie zapewnia żadnych nieczystych funkcji, które można wywoływać bezpośrednio. Możesz właściwie zaimplementować IOtyp Haskella dość łatwo w dowolnym języku za pomocą lambd i generycznych, ale ponieważ każdy może wywoływać printlnbezpośrednio, implementacja IOnie gwarantuje czystości; to byłaby tylko konwencja.
Doval
Miałem na myśli, że (1) wszystkie funkcje są czyste (oczywiście są one czyste, ponieważ język nie zapewnia żadnych nieczystych, mimo że o ile wiem, istnieją pewne mechanizmy do obejścia tego), oraz (2) funkcje czyste i nieczyste działania mają różne typy, więc nie można ich mieszać. BTW, co rozumiesz przez bezpośrednie połączenie ?
Giorgio
6
Twoje twierdzenie o getLinebraku przejrzystości referencyjnej jest błędne. Prezentujesz getLinetak, jakby oceniał lub redukował do jakiegoś ciągu, którego określony ciąg zależy od danych wejściowych użytkownika. To jest niepoprawne. IO Stringnie zawiera ciągu znaków więcej niż Maybe String. IO Stringjest receptą na być może uzyskanie Sznurka, a co więcej, jest tak czysty, jak każdy inny w Haskell.
LuxuryMode,
25
def f(x): return x()

from random import random
f(random) + f(random) == 2*f(random)
# => False

Jednak nie to oznacza przejrzystość referencyjna. RT oznacza, że ​​możesz zastąpić dowolne wyrażenie w programie wynikiem oceny tego wyrażenia (lub odwrotnie) bez zmiany znaczenia programu.

Weźmy na przykład następujący program:

def f(): return 2

print(f() + f())
print(2)

Ten program jest względnie przejrzysty. Mogę wymienić jeden lub oba wystąpień f()z 2i nadal będzie ona działać tak samo:

def f(): return 2

print(2 + f())
print(2)

lub

def f(): return 2

print(f() + 2)
print(2)

lub

def f(): return 2

print(2 + 2)
print(f())

wszyscy będą zachowywać się tak samo.

Właściwie to oszukiwałem. Powinienem być w stanie zastąpić wywołanie do printwartością zwracaną (która w ogóle nie jest wartością) bez zmiany znaczenia programu. Jednak wyraźnie, jeśli po prostu usunę te dwie printinstrukcje, znaczenie programu ulegnie zmianie: wcześniej wypisał coś na ekranie, a potem nie. We / wy nie jest względnie przejrzyste.

Prosta zasada brzmi: jeśli możesz zastąpić dowolne wywołanie wyrażenia, podwyrażenia lub podprogramu wartością zwracaną tego wyrażenia, podwyrażenia lub wywołania podprogramu w dowolnym miejscu programu, bez zmiany jego znaczenia, wówczas masz odniesienie przezroczystość. A to oznacza, że ​​praktycznie nie możesz mieć żadnego wejścia / wyjścia, nie możesz mieć żadnego stanu zmiennego, nie może mieć żadnych skutków ubocznych. W każdym wyrażeniu wartość wyrażenia musi zależeć wyłącznie od wartości składowych wyrażenia. I w każdym wywołaniu podprogramu wartość zwracana musi zależeć wyłącznie od argumentów.

Jörg W Mittag
źródło
4
„nie może mieć żadnego stanu zmiennego”: Cóż, możesz go mieć, jeśli jest ukryty i nie wpływa na obserwowalne zachowanie twojego kodu. Pomyśl np. O zapamiętywaniu.
Giorgio
4
@Giorgio: Być może jest to subiektywne, ale twierdzę, że wyniki w pamięci podręcznej nie są tak naprawdę „stanem zmiennym”, jeśli są ukryte i nie mają zauważalnych efektów. Niezmienność jest zawsze abstrakcją zaimplementowaną na zmiennym sprzęcie; często jest dostarczany przez język (dając abstrakcję „wartości”, nawet jeśli wartość może przemieszczać się między rejestrami a lokalizacjami pamięci podczas wykonywania i może zniknąć, gdy się dowie, że nigdy nie będzie ponownie używana), ale nie mniej ważna, gdy jest dostarczone przez bibliotekę lub coś w tym stylu. (Oczywiście przy założeniu, że jest poprawnie zaimplementowany).
ruakh
1
+1 Naprawdę podoba mi się ten printprzykład. Być może jednym ze sposobów, aby to zobaczyć, jest to, że to, co jest drukowane na ekranie, jest częścią „wartości zwracanej”. Jeśli możesz zastąpić printjego funkcją wartością zwracaną i równoważnym zapisem na terminalu, przykład działa.
Pierre Arlaud,
1
@Giorgio Wykorzystanie przestrzeni / czasu nie może być uważane za efekt uboczny dla celów przejrzystości odniesienia. Która stałaby 4i 2 + 2non-wymienny, ponieważ mają różne czasy pracy, a cała punktem referencyjnym przejrzystości jest to, że można zastąpić wyraz z tym, co ocenia się. Ważną kwestią byłoby bezpieczeństwo wątku.
Doval
1
@overexchange: Referential Transparency oznacza, że ​​możesz zastąpić każde podwyrażenie jego wartością bez zmiany znaczenia programu. listOfSequence.append(n)powraca None, więc powinieneś być w stanie zastąpić każdą rozmowę, aby listOfSequence.append(n)z Nonenie zmieniając sens swojego programu. Możesz to zrobić? Jeśli nie, to nie jest referencyjnie przejrzysty.
Jörg W Mittag
1

Części tej odpowiedzi pochodzą bezpośrednio z niedokończonego samouczka na temat programowania funkcjonalnego , hostowanego na moim koncie GitHub:

Mówi się, że funkcja jest referencyjnie przezroczysta, jeśli przy tych samych parametrach wejściowych zawsze daje takie same dane wyjściowe (wartość zwracana). Jeśli ktoś szuka racji bytu wyłącznie programowania funkcjonalnego, dobrym wyborem jest przejrzystość referencyjna. Podczas wnioskowania za pomocą formuł w algebrze, arytmetyce i logice, ta właściwość - zwana także substytucyjnością równości dla równości - jest tak fundamentalnie ważna, że ​​zwykle uważa się ją za coś oczywistego ...

Rozważ prosty przykład:

x = 42

W czysto funkcjonalnym języku lewa i prawa strona znaku równości są wzajemnie zastępowalne na oba sposoby. Oznacza to, że w przeciwieństwie do języka takiego jak C powyższa notacja naprawdę zapewnia równość. Konsekwencją tego jest to, że możemy rozumować o kodzie programu tak samo jak równania matematyczne.

Z Haskell wiki :

Czyste obliczenia dają tę samą wartość za każdym razem, gdy są wywoływane. Ta właściwość nazywa się przejrzystością referencyjną i umożliwia prowadzenie równego rozumowania w kodzie ...

Dla kontrastu, rodzaj operacji wykonywanej przez języki podobne do C jest czasami określany jako destrukcyjne zadanie .

Termin czysty jest często używany do opisania właściwości wyrażeń związanych z tą dyskusją. Aby funkcję można było uznać za czystą,

  • nie wolno wykazywać żadnych skutków ubocznych, oraz
  • musi być referencyjnie przejrzysty.

Według metafory czarnej skrzynki, znajdującej się w wielu podręcznikach matematycznych, elementy wewnętrzne funkcji są całkowicie odcięte od świata zewnętrznego. Efektem ubocznym jest sytuacja, gdy funkcja lub wyrażenie narusza tę zasadę - oznacza to, że procedura może w jakiś sposób komunikować się z innymi jednostkami programu (np. W celu udostępniania i wymiany informacji).

Podsumowując, przejrzystość referencyjna jest niezbędna, aby funkcje zachowywały się jak prawdziwe , matematyczne funkcje również w semantyce języków programowania.

yesthisisuser
źródło
wydaje się, że otwiera się to po skopiowaniu stąd słowo po słowie : „Mówi się, że funkcja jest względnie przezroczysta, jeśli przy tych samych parametrach wejściowych zawsze daje takie same dane wyjściowe ...” Wymiana stosu ma reguły dotyczące plagiatu , wiesz o tym? „Plagiat jest bezdusznym kopiowaniem fragmentów czyjejś pracy, uderzaniem w nią swoim imieniem i podawaniem się za oryginalnego autora ...”
gnat
3
Napisałem tę stronę.
yesthisisuser
jeśli tak jest, zastanów się nad tym, żeby nie wyglądało to na plagiat - ponieważ czytelnicy nie mają sposobu, aby powiedzieć. Czy wiesz jak to zrobić w SE? 1) Odwołujesz się do źródła oryginałów, takiego jak „Jak (napisałem) [here](link to source)...”, po którym następuje 2) właściwe formatowanie cytatu (użyj znaków cudzysłowu lub, jeszcze lepiej, > symbolu). Nie zaszkodzi również, jeśli oprócz ogólnych wskazówek, odpowiesz na konkretne pytanie, w tym przypadku o f(x)+f(x)/ 2*f(x), zobacz Jak odpowiedzieć - w przeciwnym razie może się wydawać, że po prostu reklamujesz swoją stronę
gnat
1
Teoretycznie zrozumiałem tę odpowiedź. Ale praktycznie przestrzegając tych zasad, muszę zwrócić listę sekwencji gradobicia w tym programie . Jak mam to zrobic?
nadmierna wymiana