Cos'è la trasparenza referenziale?

36

L'ho visto nei paradigmi imperativi

f (x) + f (x)

potrebbe non essere lo stesso di:

2 * f (x)

Ma in un paradigma funzionale dovrebbe essere lo stesso. Ho cercato di implementare entrambi i casi in Python e Schema , ma per me sembrano piuttosto semplici allo stesso modo.

Quale sarebbe un esempio che potrebbe indicare la differenza con la funzione data?

    
posta asgard 24.08.2014 - 17:44
fonte

3 risposte

60

La trasparenza referenziale, riferita a una funzione, indica che è possibile determinare il risultato dell'applicazione di tale funzione solo osservando i valori dei suoi argomenti. Puoi scrivere funzioni referenzialmente trasparenti in qualsiasi linguaggio di programmazione, ad es. Python, Scheme, Pascal, C.

D'altra parte, nella maggior parte delle lingue è anche possibile scrivere funzioni trasparenti non referenziali. Ad esempio, questa funzione Python:

counter = 0

def foo(x):
  global counter

  counter += 1
  return x + counter

non è referenzialmente trasparente, infatti chiama

foo(x) + foo(x)

e

2 * foo(x)

produrrà valori diversi, per qualsiasi argomento x . Il motivo è che la funzione utilizza e modifica una variabile globale, quindi il risultato di ogni chiamata dipende da questo stato di modifica e non solo dall'argomento della funzione.

Haskell, un linguaggio puramente funzionale, separa rigorosamente valutazione dell'espressione in cui vengono applicate pure funzioni e che è sempre referenzialmente trasparente, da esecuzione di azioni (elaborazione di valori speciali), che non è referenzialmente trasparente, cioè l'esecuzione della stessa azione può avere ogni volta un risultato diverso.

Quindi, per qualsiasi funzione di Haskell

f :: Int -> Int

e qualsiasi intero x , è sempre vero che

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

Un esempio di un'azione è il risultato della funzione di libreria getLine :

getLine :: IO String

Come risultato della valutazione dell'espressione, questa funzione (in realtà una costante) produce innanzitutto un valore puro di tipo IO String . I valori di questo tipo sono valori come gli altri: puoi passarli in giro, inserirli in strutture di dati, comporli utilizzando funzioni speciali e così via. Ad esempio puoi creare un elenco di azioni in questo modo:

[getLine, getLine] :: [IO String]

Le azioni sono speciali in quanto puoi dire al runtime di Haskell di eseguirle scrivendo:

main = <some action>

In questo caso, quando il tuo programma Haskell viene avviato, il runtime passa attraverso l'azione associata a main e esegue , producendo probabilmente effetti collaterali. Pertanto, l'esecuzione dell'azione non è referenzialmente trasparente perché l'esecuzione della stessa azione due volte può produrre risultati diversi a seconda di ciò che il runtime ottiene come input.

Grazie al sistema di tipi di Haskell, un'azione non può mai essere utilizzata in un contesto dove è previsto un altro tipo e viceversa. Quindi, se vuoi trovare la lunghezza di una stringa, puoi utilizzare la funzione length :

length "Hello"

restituirà 5. Ma se vuoi trovare la lunghezza di una stringa letta dal terminale, non puoi scrivere

length (getLine)

perché si ottiene un errore di tipo: length si aspetta un input di tipo list (e una String è, infatti, una lista) ma getLine è un valore di tipo IO String (un'azione). In questo modo, il sistema di tipi garantisce che un valore di azione come getLine (la cui esecuzione viene eseguita al di fuori del linguaggio principale e che può essere trasparente non referenzialmente) non possa essere nascosto all'interno di un valore non di azione di tipo Int .

Modifica

Per rispondere a questa domanda, ecco un piccolo programma Haskell che legge una linea dalla console e ne stampa la lunghezza.

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

L'azione principale consiste di due sottoazioni che vengono eseguite in sequenza:

  1. getline di tipo IO String ,
  2. il secondo è costruito valutando la funzione putStrLn di tipo String -> IO () sul suo argomento.

Più precisamente, la seconda azione è costruita da

  1. vincolante line al valore letto dalla prima azione,
  2. valutazione delle funzioni pure length (lunghezza di calcolo come numero intero) e poi show (trasformare il numero intero in una stringa),
  3. costruire l'azione applicando la funzione putStrLn al risultato di show .

A questo punto, la seconda azione può essere eseguita. Se hai digitato "Ciao", verrà stampato "5".

Tieni presente che se ottieni un valore da un'azione utilizzando la notazione <- , puoi utilizzare tale valore solo all'interno di un'altra azione, ad es. non puoi scrivere:

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

perché show (length line) ha tipo String mentre la notazione richiede che un'azione ( getLine di tipo IO String ) sia seguita da un'altra azione (ad esempio putStrLn (show (length line)) di tipo IO () ).

EDIT 2

La definizione di trasparenza referenziale di Jörg W Mittag è più generale della mia (ho alzato la sua risposta). Ho usato una definizione limitata perché l'esempio nella domanda si concentra sul valore restituito delle funzioni e volevo illustrare questo aspetto. Tuttavia, RT in generale fa riferimento al significato dell'intero programma, comprese le modifiche allo stato globale e le interazioni con l'ambiente (IO) causate dalla valutazione di un'espressione. Quindi, per una definizione generale corretta, dovresti fare riferimento a quella risposta.

    
risposta data 24.08.2014 - 18:11
fonte
25
def f(x): return x()

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

Tuttavia, questo è non cosa significa trasparenza referenziale. RT significa che puoi sostituire qualsiasi espressione nel programma con il risultato di valutare quell'espressione (o viceversa) senza cambiare il significato del programma.

Prendi, ad esempio, il seguente programma:

def f(): return 2

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

Questo programma è referenzialmente trasparente. Posso sostituire una o entrambe le occorrenze di f() con 2 e funzionerà sempre allo stesso modo:

def f(): return 2

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

o

def f(): return 2

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

o

def f(): return 2

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

si comportano tutti allo stesso modo.

Beh, in realtà, ho imbrogliato. Dovrei essere in grado di sostituire la chiamata a print con il suo valore di ritorno (che non ha alcun valore) senza modificare il significato del programma. Tuttavia, chiaramente, se rimuovo solo le due dichiarazioni print , il significato del programma cambierà: prima, ha stampato qualcosa sullo schermo, dopo che non lo ha fatto. I / O non è referenzialmente trasparente.

La semplice regola empirica è: se è possibile sostituire qualsiasi espressione, sub-espressione o chiamata di subroutine con il valore di ritorno di tale espressione, sub-espressione o chiamata di subroutine in qualsiasi punto del programma, senza che il programma ne modifichi il significato, quindi hai trasparenza referenziale. E ciò significa che in pratica non si può avere alcun I / O, non si può avere uno stato mutabile, non si possono avere effetti collaterali. In ogni espressione, il valore dell'espressione deve dipendere esclusivamente dai valori delle parti costituenti dell'espressione. E in ogni chiamata di subroutine, il valore di ritorno deve dipendere esclusivamente dagli argomenti.

    
risposta data 24.08.2014 - 18:23
fonte
1

Parti di questa risposta sono prese direttamente da un tutorial non finito sulla programmazione funzionale , ospitato sul mio account GitHub:

A function is said to be referentially transparent if it, given the same input parameters, always produces the same output (return value). If one is looking for a raison d'être for pure functional programming, referential transparency is a good candidate. When reasoning with formulae in algebra, arithmetic, and logic, this property — also called substitutivity of equals for equals — is so fundamentally important that it is usually taken for granted...

Considera un semplice esempio:

x = 42

In un linguaggio funzionale puro, la parte sinistra e quella destra del segno di uguale sono sostituibili l'una per l'altra in entrambe le direzioni. Cioè, a differenza di un linguaggio come C, la notazione di cui sopra afferma veramente un'eguaglianza. Una conseguenza di ciò è che possiamo ragionare sul codice del programma proprio come le equazioni matematiche.

Da wiki Haskell :

Pure computations yield the same value each time they are invoked. This property is called referential transparency and makes possible to conduct equational reasoning on the code...

Per contrastare questo, il tipo di operazione eseguita da linguaggi di tipo C viene talvolta definito come assegnazione distruttiva .

Il termine puro è spesso usato per descrivere una proprietà di espressioni, rilevanti per questa discussione. Affinché una funzione sia considerata pura,

  • non è consentito mostrare effetti collaterali e
  • deve essere referenzialmente trasparente.

Secondo la metafora della scatola nera, trovata in numerosi libri di testo matematici, gli interni di una funzione sono completamente isolati dal mondo esterno. Un effetto collaterale è quando una funzione o un'espressione viola questo principio - cioè, la procedura è autorizzata a comunicare in qualche modo con altre unità di programma (ad esempio per condividere e scambiare informazioni).

In sintesi, la trasparenza referenziale è un must per le funzioni di comportarsi come true , funzioni matematiche anche nella semantica dei linguaggi di programmazione.

    
risposta data 24.08.2014 - 21:09
fonte

Leggi altre domande sui tag