Qu'est-ce que la transparence référentielle?

38

J'ai vu cela dans des paradigmes impératifs

f (x) + f (x)

pourrait ne pas être la même chose que:

2 * f (x)

Mais dans un paradigme fonctionnel, cela devrait être la même chose. J'ai essayé d'implémenter les deux cas en Python et Scheme , mais pour moi, ils ont l'air assez simples.

Quel serait un exemple qui pourrait indiquer la différence avec la fonction donnée?

Asgard
la source
7
Vous pouvez, et vous le faites souvent, écrire des fonctions référentiellement transparentes en python. La différence est que la langue ne l'applique pas.
Karl Bielefeldt
5
en C et similaires: f(x++)+f(x++)peut-être pas la même chose que 2*f(x++)(en C, c'est particulièrement beau quand des choses comme celles-là sont cachées dans des macros - est-ce que je me suis cassé le nez là-dessus? pariez-vous)
gnat
D'après ma compréhension, l'exemple de @ gnat est la raison pour laquelle les langages à fonctionnalité orientée tels que R utilisent la méthode de référence par passe et évitent explicitement les fonctions qui modifient leurs arguments. En R, du moins, il peut être difficile de contourner ces restrictions (du moins, de manière stable et portable) sans plonger dans le système complexe d'environnements de noms, d'espaces de noms et de chemins de recherche du langage.
shadowtalker
4
@ssdecontrol: En fait, lorsque vous avez une transparence référentielle, pass-par-value et pass-by-reference, vous obtenez toujours le même résultat, donc peu importe le langage utilisé. Les langages fonctionnels sont souvent spécifiés avec quelque chose qui s'apparente pass-par-valeur pour la clarté sémantique, mais leurs implémentations utilisent souvent la performance par référence pour les performances (ou même les deux, selon celle qui est la plus rapide pour le contexte donné).
Jörg W Mittag
4
@gnat: En particulier, f(x++)+f(x++)peut être absolument n'importe quoi, puisqu'il invoque un comportement indéfini. Mais cela n’est pas vraiment lié à la transparence référentielle - ce qui n’aiderait pas cet appel, il est «indéfini» pour les fonctions référentiellement transparentes comme dans le cas sin(x++)+sin(x++)contraire. Pourrait être 42, pourrait formater votre disque dur, pourrait avoir des démons voler sur le nez des utilisateurs…
Christopher Creutzig

Réponses:

62

La transparence référentielle, associée à une fonction, indique que vous pouvez déterminer le résultat de l'application de cette fonction uniquement en consultant les valeurs de ses arguments. Vous pouvez écrire des fonctions référentiellement transparentes dans n’importe quel langage de programmation, par exemple Python, Scheme, Pascal, C.

Par ailleurs, dans la plupart des langues, vous pouvez également écrire des fonctions non transparentes par référentiel. Par exemple, cette fonction Python:

counter = 0

def foo(x):
  global counter

  counter += 1
  return x + counter

n'est pas référentiellement transparent, appelant en fait

foo(x) + foo(x)

et

2 * foo(x)

produira des valeurs différentes, pour tout argument x. La raison en est que la fonction utilise et modifie une variable globale. Par conséquent, le résultat de chaque invocation dépend de cet état changeant, et pas seulement de l'argument de la fonction.

Haskell, un langage purement fonctionnel, sépare strictement l' évaluation de l'expression dans laquelle des fonctions pures sont appliquées et qui est toujours transparente de manière référentielle, de l' exécution de l' action (traitement des valeurs spéciales), qui n'est pas transparente de manière référentielle, c'est-à-dire que l'exécution de la même action peut avoir à chaque fois une résultat différent.

Donc, pour toute fonction Haskell

f :: Int -> Int

et tout entier x, il est toujours vrai que

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

Un exemple d'action est le résultat de la fonction de bibliothèque getLine:

getLine :: IO String

À la suite de l'évaluation de l'expression, cette fonction (en fait une constante) produit tout d'abord une valeur pure de type IO String. Les valeurs de ce type sont des valeurs comme les autres: vous pouvez les transmettre, les placer dans des structures de données, les composer à l'aide de fonctions spéciales, etc. Par exemple, vous pouvez faire une liste d'actions comme ceci:

[getLine, getLine] :: [IO String]

Les actions ont ceci de particulier que vous pouvez demander à l'exécution de Haskell de les exécuter en écrivant:

main = <some action>

Dans ce cas, lorsque votre programme Haskell est démarré, le moteur d'exécution parcourt l'action qui lui est liée mainet l' exécute , produisant éventuellement des effets secondaires. Par conséquent, l'exécution de l'action n'est pas transparente de manière référentielle, car l'exécution de la même action à deux reprises peut produire des résultats différents selon ce que le moteur d'exécution obtient en entrée.

Grâce au système de types de Haskell, une action ne peut jamais être utilisée dans un contexte où un autre type est attendu, et inversement. Donc, si vous voulez trouver la longueur d'une chaîne, vous pouvez utiliser la lengthfonction:

length "Hello"

retournera 5. Mais si vous voulez trouver la longueur d'une chaîne lue depuis le terminal, vous ne pouvez pas écrire

length (getLine)

parce que vous obtenez une erreur de type: lengthattend une entrée de type list (et une chaîne est, en réalité, une liste) mais getLineune valeur de type IO String(une action). De cette manière, le système de types garantit qu'une valeur d'action telle que getLine(dont l'exécution est exécutée en dehors du langage principal et qui peut être transparente de manière non référentielle) ne peut pas être cachée à l'intérieur d'une valeur de type non-action Int.

MODIFIER

Pour répondre à cette question, voici un petit programme Haskell qui lit une ligne à partir de la console et en imprime la longueur.

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

L'action principale consiste en deux sous-actions exécutées séquentiellement:

  1. getlinede type IO String,
  2. la seconde est construite en évaluant la fonction putStrLnde type String -> IO ()sur son argument.

Plus précisément, la deuxième action est construite par

  1. liant lineà la valeur lue par la première action,
  2. évaluer les fonctions pures length(calculer la longueur sous forme d'entier) puis show(transformer l'entier en chaîne),
  3. construire l'action en appliquant une fonction putStrLnau résultat de show.

À ce stade, la deuxième action peut être exécutée. Si vous avez tapé "Bonjour", "5" sera imprimé.

Notez que si vous obtenez une valeur d'une action en utilisant la <-notation, vous ne pouvez utiliser cette valeur que dans une autre action, par exemple, vous ne pouvez pas écrire:

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

car show (length line)a le type Stringalors que la notation do nécessite qu'une action ( getLinede type IO String) soit suivie d'une autre action (par exemple putStrLn (show (length line))de type IO ()).

EDIT 2

La définition de la transparence référentielle de Jörg W Mittag est plus générale que la mienne (j'ai voté pour sa réponse). J'ai utilisé une définition restreinte parce que l'exemple de la question porte sur la valeur de retour des fonctions et je voulais illustrer cet aspect. Cependant, RT fait généralement référence à la signification de l'ensemble du programme, y compris les changements d'état global et les interactions avec l'environnement (IO) provoqués par l'évaluation d'une expression. Donc, pour une définition correcte et générale, vous devriez vous référer à cette réponse.

Giorgio
la source
10
Le votant inférieur peut-il suggérer comment je peux améliorer cette réponse?
Giorgio
Alors, comment peut-on obtenir la longueur d’une chaîne lue à partir d’un terminal en Haskell?
Sichicho
2
C’est extrêmement pédant, mais par souci d’exhaustivité, ce n’est pas le système de types de Haskell qui assure que les actions et les fonctions pures ne se mélangent pas; c'est le fait que le langage ne fournit aucune fonction impure que vous pouvez appeler directement. Vous pouvez réellement implémenter le IOtype Haskell assez facilement dans n'importe quelle langue avec lambdas et génériques, mais comme tout le monde peut appeler printlndirectement, la mise en œuvre IOne garantit pas la pureté; ce serait simplement une convention.
Doval
Je voulais dire que (1) toutes les fonctions sont pures (bien sûr, elles sont pures parce que le langage ne fournit pas d’impures, même si, autant que je sache, certains mécanismes permettent de contourner cela), et (2) des fonctions pures et Les actions impures ont différents types, elles ne peuvent donc pas être mélangées. BTW, qu'entendez-vous par appel directement ?
Giorgio
6
Votre remarque sur le fait de getLinene pas être référentiellement transparent est incorrecte. Vous présentez getLinecomme si elle évaluait ou réduisait à une chaîne, dont la chaîne particulière dépend de l'entrée de l'utilisateur. Ceci est une erreur. IO Stringne contient pas plus de chaîne que Maybe Stringne le fait. IO Stringest une recette pour peut-être, éventuellement, obtenir une chaîne et, en tant qu’expression, aussi pure que toute autre en Haskell.
LuxuryMode
25
def f(x): return x()

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

Cependant, ce n'est pas ce que signifie la transparence référentielle. RT signifie que vous pouvez remplacer n’importe quelle expression dans le programme par le résultat de l’évaluation de cette expression (ou inversement) sans modifier la signification du programme.

Prenons, par exemple, le programme suivant:

def f(): return 2

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

Ce programme est référentiellement transparent. Je peux remplacer une ou les deux occurrences de f()avec 2et cela fonctionnera toujours de la même manière:

def f(): return 2

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

ou

def f(): return 2

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

ou

def f(): return 2

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

se comportera tous de la même manière.

En fait, j'ai triché. Je devrais être capable de remplacer l'appel à printavec sa valeur de retour (qui n'est aucune valeur) sans changer la signification du programme. Cependant, il est clair que si je supprime simplement les deux printdéclarations, la signification du programme changera: auparavant, il imprimait quelque chose à l'écran, après cela, pas du tout. Les E / S ne sont pas référentiellement transparentes.

La règle de base est la suivante: si vous pouvez remplacer une expression, une sous-expression ou un appel de sous-routine par la valeur de retour de cette expression, sous-expression ou appel de sous-routine n’importe où dans le programme, sans que le programme en change le sens, vous avez alors un référentiel. transparence. Et ce que cela signifie, pratiquement, c'est que vous ne pouvez avoir aucun I / O, aucun état mutable, aucun effet secondaire. Dans chaque expression, la valeur de l'expression doit dépendre uniquement des valeurs des parties constitutives de l'expression. Et dans chaque appel de sous-routine, la valeur de retour doit dépendre uniquement des arguments.

Jörg W Mittag
la source
4
"ne peut avoir aucun état mutable": vous pouvez l'avoir s'il est caché et n'influence pas le comportement observable de votre code. Pensez par exemple à la mémorisation.
Giorgio
4
@Giorgio: C'est peut-être subjectif, mais je dirais que les résultats mis en cache ne sont pas vraiment des "états mutables" s'ils sont cachés et n'ont aucun effet observable. L’immuabilité est toujours une abstraction implémentée au dessus d’un matériel mutable; il est souvent fourni par le langage (donnant l'abstraction de "une valeur" même si la valeur peut se déplacer entre les registres et les emplacements de mémoire pendant l'exécution, et peut disparaître une fois que l'on sait qu'elle ne sera plus jamais utilisée), mais ce n'est pas moins valable quand c'est fourni par une bibliothèque ou quoi. (En supposant que son implémentation soit correcte, bien sûr.)
ruakh
1
+1 J'aime beaucoup l' printexemple. Une façon de voir cela est peut-être que ce qui est imprimé à l'écran fait partie de la "valeur de retour". Si vous pouvez remplacer printpar la valeur de retour de la fonction et l’écriture équivalente sur le terminal, l’exemple fonctionne.
Pierre Arlaud
1
@Giorgio L'utilisation de l'espace / du temps ne peut être considérée comme un effet secondaire aux fins de la transparence référentielle. Cela rendrait 4et 2 + 2non interchangeable, car ils ont des temps d'exécution différents, et le point essentiel de la transparence référentielle est que vous pouvez remplacer une expression par ce qu'elle évalue. La considération importante serait la sécurité du fil.
Doval
1
@overexchange: La transparence référentielle signifie que vous pouvez remplacer chaque sous-expression par sa valeur sans changer le sens du programme. listOfSequence.append(n)retourne None, vous devriez donc pouvoir remplacer chaque appel listOfSequence.append(n)par Nonesans changer le sens de votre programme. Peux-tu faire ça? Si ce n'est pas le cas, alors ce n'est pas transparent par référence.
Jörg W Mittag
1

Certaines parties de cette réponse proviennent directement d’un tutoriel inachevé sur la programmation fonctionnelle , hébergé sur mon compte GitHub:

Une fonction est dite référentiellement transparente si, avec les mêmes paramètres d'entrée, elle produit toujours la même sortie (valeur de retour). Si on cherche une raison d'être pour une programmation purement fonctionnelle, la transparence référentielle est un bon candidat. Lorsque l'on raisonne avec des formules en algèbre, en arithmétique et en logique, cette propriété - appelée également substitutivité d'égaux pour égaux - est si fondamentalement importante qu'elle est généralement considérée comme acquise ...

Prenons un exemple simple:

x = 42

Dans un langage purement fonctionnel, les côtés gauche et droit du signe égal sont substituables l'un à l'autre. C'est-à-dire que, contrairement à un langage comme C, la notation ci-dessus affirme véritablement une égalité. Une conséquence de ceci est que nous pouvons raisonner à propos du code de programme, tout comme les équations mathématiques.

De Wiki Haskell :

Les calculs purs donnent la même valeur chaque fois qu'ils sont appelés. Cette propriété est appelée transparence référentielle et permet de conduire un raisonnement équationnel sur le code ...

À l'opposé, le type d'opération exécuté par les langages de type C est parfois appelé une affectation destructive .

Le terme pur est souvent utilisé pour décrire une propriété d'expressions pertinente pour la discussion. Pour qu'une fonction soit considérée pure,

  • il n'est pas permis de présenter des effets secondaires, et
  • il doit être référentiellement transparent.

Selon la métaphore de la boîte noire, que l'on retrouve dans de nombreux manuels de mathématiques, les fonctions internes d'une fonction sont complètement isolées du monde extérieur. Un effet secondaire survient lorsqu'une fonction ou une expression enfreint ce principe. En d'autres termes, la procédure est autorisée à communiquer d'une manière ou d'une autre avec d'autres unités de programme (par exemple, pour partager et échanger des informations).

En résumé, la transparence référentielle est indispensable pour que les fonctions se comportent comme de vraies fonctions mathématiques, y compris dans la sémantique des langages de programmation.

yesthisisuser
la source
cela semble s'ouvrir avec une copie mot à mot prise à partir d'ici : "Une fonction est dite référentiellement transparente si, avec les mêmes paramètres d'entrée, elle produit toujours la même sortie ..." Stack Exchange a des règles de plagiat , vous êtes au courant de cela? "Le plagiat est l'acte sans âme qui consiste à copier des morceaux du travail de quelqu'un d'autre, à taper votre nom dessus et à se faire passer pour l'auteur original ..."
gnat
3
J'ai écrit cette page.
Yesthisisuser
Si tel est le cas, envisagez de réduire le plagiat, car les lecteurs n'ont aucun moyen de le savoir. Savez-vous comment faire cela chez SE? 1) Vous faites référence à la source d'origine, telle que "Comme (je l'ai) écrit [here](link to source)..." suivie de 2) le formatage approprié des guillemets (utilisez les guillemets, ou mieux encore, le > symbole correspondant). Il ne serait pas aussi mal si en plus de donner des directives générales, les adresses de réponse question concrète posé des questions sur, dans ce cas à propos de f(x)+f(x)/ 2*f(x), voir Comment répondre - sinon il peut ressembler à vous simplement la publicité de votre page
moucheron
1
Théoriquement, j'ai compris cette réponse. Mais, suivant pratiquement ces règles, je dois retourner la liste de séquences de grêle dans ce programme . Comment puis-je faire cela?
échange