[Functional-programming] Cos'è la trasparenza referenziale?


Answers

La trasparenza referenziale, un termine comunemente usato nella programmazione funzionale, significa che data una funzione e un valore di input, si riceverà sempre lo stesso risultato. Vale a dire che non esiste uno stato esterno utilizzato nella funzione.

Ecco un esempio di una funzione trasparente referenziale:

int plusOne(int x)
{
  return x+1;
}

Con una funzione referenziale trasparente, dato un input e una funzione, è possibile sostituirla con un valore invece di chiamare la funzione. Quindi, invece di chiamare plusOne con un pareggiatore di 5, potremmo semplicemente sostituirlo con 6.

Un altro buon esempio è la matematica in generale. In matematica, data una funzione e un valore di input, si mapperà sempre allo stesso valore di output. f (x) = x + 1. Pertanto le funzioni matematiche sono referenzialmente trasparenti.

Questo concetto è importante per i ricercatori perché significa che quando si ha una funzione referentially trasparente, si presta a una facile parallelizzazione automatica e alla memorizzazione nella cache.

La trasparenza referenziale viene utilizzata sempre in linguaggi funzionali come Haskell.

-

Al contrario, c'è il concetto di opacità referenziale. Questo significa il contrario. Chiamare la funzione potrebbe non produrre sempre la stessa uscita.

//global G
int G = 10;

int plusG(int x)
{//G can be modified externally returning different values.
  return x + G;
}

Un altro esempio è una funzione membro in un linguaggio di programmazione orientato agli oggetti. Le funzioni membro operano normalmente sulle sue variabili membro e pertanto sarebbero opache referenziali. Ovviamente le funzioni per i membri possono essere referenzialmente trasparenti.

Ancora un altro esempio è una funzione che legge da un file di testo e stampa l'output. Questo file di testo esterno potrebbe cambiare in qualsiasi momento, quindi la funzione sarebbe opacizzante dal punto di vista referenziale.

Question

Che cosa significa il termine trasparenza referenziale ? Ho sentito dire che "significa che puoi sostituire gli uguali con gli uguali" ma questa sembra una spiegazione inadeguata.




Per quelli che hanno bisogno di una spiegazione concisa ne azzarderò uno (ma leggete la descrizione qui sotto).

La trasparenza referenziale in un linguaggio di programmazione promuove il ragionamento equo: maggiore è la trasparenza referenziale, più facile è ragionare in modo equo. Ad esempio con una definizione di funzione (pseudo),

fx = x + x,

la facilità con cui è possibile (in tutta sicurezza) sostituire f (foo) con foo + foo nell'ambito di questa definizione, senza avere troppi vincoli su dove è possibile eseguire questa riduzione, è una buona indicazione di quanta trasparenza referenziale il linguaggio di programmazione ha.

Ad esempio, se foo fosse x ++ nel senso di programmazione C, non potreste eseguire questa riduzione in modo sicuro (vale a dire, se doveste eseguire questa riduzione non finirebbe con lo stesso programma con cui avete iniziato).

Nei linguaggi di programmazione pratica non vedrete una trasparenza referenziale perfetta, ma i programmatori funzionali si preoccupano più di altri (cfr. Haskell, dove è un obiettivo centrale).

(Full disclosure: Sono un programmatore funzionale quindi dalla risposta più alta dovresti prendere questa spiegazione con un pizzico di sale.)




Nota che questo concetto di "significato" è qualcosa che accade nella mente dell'osservatore. Quindi, lo stesso "riferimento" può significare cose diverse per persone diverse. Quindi, per esempio, abbiamo una pagina di disambiguazione di Edimburgo su Wikipedia.

Un problema correlato che può presentarsi nel contesto della programmazione potrebbe essere il polimorfismo.

E forse dovremmo avere un nome per il caso speciale di polimorfismo (o forse anche di casting) dove per i nostri scopi i diversi casi polimorfici sono semanticamente equivalenti (al contrario del solo essere simili. Ad esempio, il numero 1 - che potrebbe essere rappresentato l'uso di un tipo intero o di un tipo complesso o di una varietà di altri tipi può essere trattato polimorficamente).




[Questo è un post sulla mia risposta del 25 marzo, nel tentativo di avvicinare la discussione alle preoccupazioni della programmazione funzionale / imperativa.]

L'idea dei programmatori funzionali di trasparenza referenziale sembra differire dalla nozione standard in tre modi:

  • Mentre i filosofi / logici usano termini come "riferimento", "denotazione", "designatum" e " bedeutung " (termine tedesco di Frege), i programmatori funzionali usano il termine "valore". (Questo non è del tutto il loro modo di agire. Osservo che Landin, Strachey ei loro discendenti usavano anche il termine "valore" per parlare di riferimento / denotazione. Potrebbe essere solo una semplificazione terminologica introdotta da Landin e Strachey, ma sembra fare un grande differenza se usato in modo ingenuo.)

  • I programmatori funzionali sembrano credere che questi "valori" esistano all'interno del linguaggio di programmazione, non all'esterno. Nel fare questo, si differenziano sia dai filosofi che dai semantici del linguaggio di programmazione.

  • Sembrano credere che questi "valori" dovrebbero essere ottenuti dalla valutazione.

Ad esempio, l'articolo di Wikipedia sulla trasparenza referenziale dice, questa mattina:

Si dice che un'espressione è referenzialmente trasparente se può essere sostituita con il suo valore senza modificare il comportamento di un programma (in altre parole, producendo un programma che ha gli stessi effetti e output sullo stesso input).

Ciò è completamente in disaccordo con ciò che dicono i filosofi / i logici. Dicono che un contesto è referenziale o referenzialmente trasparente se un'espressione in quel contesto può essere sostituita da un'altra espressione che si riferisce alla stessa cosa (un'espressione coreferential ). Chi sono questi filosofi / logici? Includono Frege , Russell , Whitehead , Carnap , Quine , Church e innumerevoli altri. Ognuno di loro è una figura imponente. Il potere intellettuale combinato di questi logici è a dir poco sconvolgente. Tutti sono unanimi nella posizione secondo cui i referenti / denotazioni esistono al di fuori del linguaggio formale e le espressioni all'interno del linguaggio possono solo parlarne. Quindi, tutto ciò che si può fare all'interno della lingua è sostituire un'espressione con un'altra espressione che si riferisce alla stessa entità. I referenti / denotazioni stessi non esistono all'interno della lingua. Perché i programmatori funzionali si discostano da questa tradizione consolidata?

Si potrebbe presumere che i semantici del linguaggio di programmazione potrebbero averli fuorviati. Ma loro no.

Landin :

(a) ogni espressione ha una struttura di sottoespressione di nidificazione, (b) ciascuna sottoespressione indica qualcosa (di solito un numero, un valore di verità o una funzione numerica) , (c) la cosa che l'espressione denota, cioè il suo "valore", dipende solo dal valori delle sue sottoespressioni, non su altre proprietà di esse. [Aggiunto enfasi]

Stoy :

L'unica cosa che conta su un'espressione è il suo valore, e qualsiasi sottoespressione può essere sostituita da qualsiasi altro valore uguale [enfasi aggiunta]. Inoltre, il valore di un'espressione è, entro certi limiti, lo stesso ogni volta che si verifica ".

Bird and Wadler :

il valore di un'espressione dipende solo dai valori delle sue espressioni costitutive (se ce ne sono) e queste sottoespressioni possono essere sostituite liberamente da altre che possiedono lo stesso valore [Enfasi aggiunta].

Quindi, in retrospettiva, gli sforzi di Landin e Strachey per semplificare la terminologia sostituendo "riferimento" / "denotazione" con "valore" potrebbero essere stati ingiustificati. Non appena si sente parlare di un "valore", si ha la tentazione di pensare a un processo di valutazione che porti ad esso. È ugualmente allettante pensare a qualunque cosa la valutazione produca come "valore", anche se potrebbe essere del tutto chiaro che quella non è la denotazione. Questo è ciò che racconto per essere successo al concetto di "trasparenza referenziale" agli occhi dei programmatori funzionali. Ma il "valore" di cui si parlava i primi semantisti non è il risultato di una valutazione o dell'output di una funzione o di una cosa del genere. È la denotazione del termine.

Una volta compreso il cosiddetto "valore" di un'espressione ("riferimento" o "denotazione" nel discorso dei filosofi classici) come un complesso oggetto matematico / concettuale, si aprono tutti i tipi di possibilità.

  • Strachey ha interpretato le variabili nei linguaggi di programmazione imperativi come valori L , come menzionato nella mia risposta del 25 marzo, che è un oggetto concettuale sofisticato che non ha una rappresentazione diretta all'interno della sintassi di un linguaggio di programmazione.
  • Ha anche interpretato i comandi in tali linguaggi come le funzioni stato-stato, un'altra istanza di un oggetto matematico complesso che non è un "valore" all'interno della sintassi.
  • Anche una chiamata di funzione con effetti collaterali in C ha un "valore" ben definito come un trasformatore di stato che mappa gli stati in coppie di stati e valori (la cosiddetta "monade" nella terminologia dei programmatori funzionali).

La riluttanza dei programmatori funzionali a chiamare tali linguaggi "referenzialmente trasparenti" implica semplicemente che sono riluttanti ad ammettere oggetti matematici / concettuali così complessi come "valori". D'altra parte, sembrano perfettamente disposti a chiamare un trasformatore di stato un "valore" quando viene inserito nella loro sintassi preferita e abbellito da una parola come "monade". Devo dire che sono del tutto incoerenti, anche se gli accordiamo che la loro idea di "trasparenza referenziale" ha una certa coerenza.

Un po 'di storia potrebbe far luce su come sono nate queste confusioni. Il periodo tra il 1962 e il 1967 fu molto intenso per Christopher Strachey. Tra il 1962 e il 1965, ha svolto un lavoro part-time come assistente di ricerca con Maurice Wilkes per progettare e implementare il linguaggio di programmazione che divenne noto come CPL. Si trattava di un linguaggio di programmazione imperativo, ma doveva avere anche potenti funzionalità di linguaggio di programmazione funzionale. Landin, che era un impiegato di Strachey nella sua società di consulenza, ha avuto un'enorme influenza sulla visione di Strachey dei linguaggi di programmazione. Nel famoso documento del 1965 " Landin ", Landin promuove sfacciatamente i linguaggi di programmazione funzionale (chiamandoli linguaggi denotativi ) e descrive i linguaggi di programmazione imperativi come la loro "antitesi". Nella discussione che segue, troviamo Strachey che mette in dubbio la posizione di forza di Landin.

... DLs formano un sottoinsieme di tutte le lingue. Sono un sottoinsieme interessante, ma che è scomodo da usare a meno che non ci si abitui. Ne abbiamo bisogno perché al momento non sappiamo come costruire prove con linguaggi che includono imperativi e salti. [Aggiunto enfasi]

Nel 1965, Strachey prese la posizione di un lettore a Oxford e sembra aver lavorato essenzialmente a tempo pieno sullo sviluppo di una teoria degli imperativi e dei salti. Nel 1967, era pronto con una teoria, che insegnò nel suo corso su " Concetti fondamentali nei linguaggi di programmazione " in una scuola estiva di Copenaghen. Gli appunti delle lezioni avrebbero dovuto essere pubblicati ma "sfortunatamente, a causa del montaggio dilatorio, i procedimenti non si sono mai materializzati, come gran parte del lavoro di Strachey a Oxford, tuttavia, il giornale ha avuto un'influente circolazione privata". ( Martin Campbell-Kelly )

La difficoltà di ottenere gli scritti di Strachey avrebbe potuto portare alla propagazione delle confusioni, con persone che si affidavano a fonti secondarie e dicerie. Ma ora che " Concetti fondamentali " sono facilmente disponibili sul Web, non è necessario ricorrere al lavoro di supposizione. Dovremmo leggerlo e prendere una decisione su cosa intendesse Strachey. In particolare:

  • Nella sezione 3.2, si occupa di "espressioni" in cui parla di "trasparenza referenziale a valore R".
  • La sua sezione 3.3 riguarda i "comandi" in cui parla di "trasparenza referenziale a valore L".
  • Nella sezione 3.4.5, parla di "funzioni e routine" e dichiara che "qualsiasi deviazione della trasparenza referenziale a valore R in un contesto di valore R dovrebbe essere eliminata decomprimendo l'espressione in più comandi e espressioni più semplici, oppure, se questo risulta essere difficile, oggetto di un commento. "

Qualsiasi discorso sulla "trasparenza referenziale" senza comprendere la distinzione tra valori L, valori R e altri oggetti complessi che popolano l'universo concettuale del programmatore imperativo è fondamentalmente sbagliato.




Una funzione referenzialmente trasparente è quella che agisce come una funzione matematica; dati gli stessi input, produrrà sempre le stesse uscite. Implica che lo stato passato non sia modificato e che la funzione non abbia uno stato proprio.