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

transparence référentielle, un terme couramment utilisé dans la programmation fonctionnelle, signifie qu'avec une fonction et une valeur d'entrée, vous recevrez toujours la même sortie. C'est-à-dire qu'il n'est pas extérieure de l'état utilisé dans la fonction.

voici un exemple de fonction transparente référentielle:

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

avec une fonction transparente référentielle, avec une entrée et une fonction, vous pouvez la remplacer par une valeur au lieu d'appeler la fonction. Donc au lieu d'appeler plusOne avec un paramètre de 5, nous pourrions juste remplacer cela par 6.

un autre bon exemple est les mathématiques en général. En mathématiques étant donné une fonction et une valeur d'entrée, il sera toujours la même valeur de sortie. f (x) = x + 1. Par conséquent, les fonctions en mathématiques sont référentiellement transparentes.

ce concept est important pour les chercheurs car il signifie que lorsque vous avez une fonction de transparence référentielle, il se prête facilement à la parallélisation et à la mise en cache automatiques.

transparence référentielle est toujours utilisé dans les langues fonctionnelles comme Haskell.

--

En revanche il y a le concept de l'opacité référentielle. Cela signifie le contraire. Appeler la fonction ne produit pas toujours la même sortie.

//global G
int G = 10;

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

un autre exemple, est une fonction membre dans un langage de programmation orienté objet. Les fonctions de membre opèrent généralement sur ses variables de membre et serait donc opaque référentiel. Les fonctions des membres peuvent bien sûr être référentiellement transparentes.

Encore un autre exemple est une fonction qui lit un fichier texte et imprime le résultat. Ce fichier texte externe pourrait changer à tout moment de sorte que la fonction serait référentiellement opaque.

une fonction de transparence référentielle est une fonction qui ne dépend que de son entrée.

[Ceci est un post-scriptum à ma réponse à partir du 25 Mars, dans un effort pour amener la discussion plus près des préoccupations de la fonctionnelle/programmation impérative.]

l'idée des programmeurs fonctionnels de transparence référentielle semble différer de la notion standard de trois façons:

• alors que les philosophes / logiciens utilisent des termes comme "référence", "dénotation", "designatum" et " bedeutung " (Terme allemand de Frege), les programmeurs fonctionnels utilisent le terme "valeur". (Ce n'est pas entièrement de leur faire. Je remarque que Landin, Strachey et leurs descendants ont aussi utilisé le terme "valeur" pour parler de référence/dénotation. Ce n'est peut-être qu'une simplification terminologique introduite par Landin et Strachey, mais elle semble faire une grande différence lorsqu'elle est utilisée d'une manière naïve.)

• les programmeurs fonctionnels semblent croire que ces "valeurs" existent à l'intérieur le langage de programmation, pas à l'extérieur. Ce faisant, ils diffèrent à la fois des philosophes et des sémantiques du langage de programmation.

• ils semblent croire que ces" valeurs " sont supposées être obtenues par évaluation.

par exemple, L'article de Wikipedia sur transparence référentielle dit, ce matin:

une expression est dit transparent référentiellement s'il peut être remplacé par sa valeur sans changer le comportement d'un programme (en d'autres termes, donnant un programme qui a les mêmes effets et sortie sur la même entrée).

cela est complètement en contradiction avec ce que disent les philosophes/logiciens. Ils disent qu'un contexte est référentiel ou référentiellement transparent si une expression dans ce contexte peut être remplacée par une autre expression Cela fait référence à la même chose (une expression coréférentielle ). Qui sont ces philosophes/logiciens? Ils comprennent Frege , Russell , Whitehead , Carnap , Quine , Eglise et d'innombrables autres. Chacun d'eux est une figure emblématique. Le pouvoir intellectuel combiné de ces logiciensest bouleversant à dire le moins. Tous sont unanimes dans la position que les référents/dénotations existent en dehors de la langue formelle et les expressions dans la langue ne peut parler à propos de eux. Ainsi, tout ce que l'on peut faire dans la langue est de remplacer une expression par une autre qui se réfère à la même entité. Les référents/dénotations eux-mêmes n'existent pas dans la langue. Pourquoi les programmeurs fonctionnels s'écartent-ils de cette la tradition?

on pourrait présumer que les sémantiques du langage de programmation les ont induits en erreur. Mais ils ne l'ont pas fait.

Landin :

(a) chaque expression a structure de la sous-expression de nidification, (b) chaque sous-expression dénote quelque chose (habituellement un nombre, une valeur de vérité ou fonction numérique) , (c) la chose qu'une expression dénote, c'est à dire, sa "valeur", dépend uniquement de la valeur de son- des expressions, pas sur les autres propriétés. [C'est nous qui soulignons]

Stoy :

la seule chose qui importe au sujet d'une expression est sa valeur, et n'importe quelle sous-expression peut être remplacé par toute autre valeur égale [italique ajouté]. En outre, la valeur d'une expression est, dans certaines limites, la même chaque fois qu'il se produit".

l'Oiseau et de Wadler :

la valeur d'une expression dépend seulement des valeurs de son constituant les expressions (le cas échéant) et ces sous-expressions peuvent être librement remplacées par autres ayant la même valeur [c'est nous qui soulignons].

ainsi, rétrospectivement, les efforts de Landin et Strachey pour simplifier la terminologie en remplaçant "référence" / "dénotation" avec "valeur" aurait pu être malavisée. Dès que l'on entend parler d'une "valeur", on est tenté de penser à un processus d'évaluation qui conduit à lui. Il est tout aussi tentant de penser à ce que l'évaluation produit comme "valeur", même s'il est assez clair que ce n'est pas la dénotation. C'est ce qui est arrivé, je crois, au concept de "transparence référentielle" aux yeux des programmeurs fonctionnels. Mais la "valeur" dont on parlait par les premiers sémanticiens est pas le résultat d'une évaluation ou la sortie d'une fonction ou une telle chose. C'est la dénotation du terme.

une fois que nous comprenons la soi-disant "valeur" d'une expression ("référence" ou "dénotation" dans le discours des philosophes classiques) comme un objet mathématique/conceptuel complexe, toutes sortes de possibilités s'ouvrent.

• Strachey interprété variables en impératif langages de programmation comme l-values , comme mentionné dans ma réponse du 25 Mars, qui est un objet conceptuel sophistiqué qui n'a pas une représentation directe dans la syntaxe d'un langage de programmation.
• il a également interprété des commandes dans des langues telles que les fonctions État-à-état, une autre instance d'un objet mathématique complexe qui n'est pas une" valeur " dans la syntaxe.
• même un appel de fonction à effet latéral en C A une "valeur" bien définie comme un transformateur d'état qui établit une correspondance entre des États et des paires d'États et de valeurs (la soi-disant "monade" dans la terminologie des programmeurs fonctionnels).

la réticence des programmeurs fonctionnels à appeler de tels langages" référentiellement transparents "implique simplement qu'ils sont réticents à admettre des objets mathématiques/conceptuels aussi complexes que des"valeurs". D'autre part, ils semblent parfaitement disposés à appeler un transformateur d'état une "valeur" quand il est mis dans leur syntaxe préférée et habillé avec un mot à la mode comme "monad". Je dois dire qu'ils sont tout à fait incohérents, même si nous leur accordons une certaine cohérence dans leur idée de "transparence référentielle".

Un peu d'histoire peut jeter une certaine lumière sur la façon dont ces confusions. La période de 1962 à 1967 fut très intense pour Christopher Strachey. De 1962 à 1965, il occupe un poste à temps partiel D'assistant de recherche à Maurice Wilkes de concevoir et de mettre en œuvre le langage de programmation qui est venu à être connu sous le nom de CPL. Il s'agissait d'un langage de programmation impératif, mais il devait aussi posséder de puissantes capacités de langage de programmation fonctionnel. Landin, qui était un employé de Strachey dans sa société de conseil, a eu une influence énorme sur la vision de Strachey des langages de programmation. Dans le repère 1965 papier " à Côté de 700 langages de programmation ", Landin sans vergogne favorise la programmation fonctionnelle les langages (les appelant dénotatifs ) et décrit les langages de programmation impératifs comme leur "antithèse". Dans la discussion qui suit, Nous trouvons Strachey soulevant des doutes sur la position forte de Landin.

... DLs forme un sous-ensemble de toutes les langues. Ils sont un sous-ensemble intéressant, mais un ce qui n'est pas pratique à utiliser à moins d'y être habitué. Nous avons besoin de ils parce que à l'heure actuelle nous ne savons pas comment construire des épreuves avec des langages qui incluent des impératifs et des sauts. [C'est nous qui soulignons]

en 1965, Strachey a pris la position d'un lecteur à Oxford et semble avoir travaillé essentiellement à temps plein sur le développement d'une théorie des impératifs et des sauts. En 1967, il est prêt avec une théorie, qu'il a enseigné dans son cours sur " concepts fondamentaux dans les langages de programmation " dans une école D'été de Copenhague. Les notes de conférence étaient supposées avoir été publiée, mais "malheureusement, en raison de dilatoire la rédaction, le procès ne s'est jamais concrétisé; comme une grande partie du travail de Strachey à Oxford, cependant, le le journal avait une diffusion privée influente."( Martin Campbell-Kelly )

la difficulté d'obtenir les écrits de Strachey pourrait avoir conduit à la propagation des confusions, avec des gens qui s'appuient sur des sources secondaires et des ouï-dire. Mais, maintenant que" concepts fondamentaux " est facilement disponible sur le web, il n'est pas nécessaire de recourir à des approximations. Nous devrions le lire et décider de ce que Strachey veut dire. En particulier:

• dans la section 3.2, il traite des "expressions"où il parle de" transparence référentielle de la valeur R".
• sa section 3.3 traite des" commandes "où il parle de"transparence référentielle de la valeur L".
• dans la section 3.4.5, il parle à propos de "fonctions et routines" et déclare que " toute déviation de la transparence référentielle de valeur R dans un contexte de valeur R devrait soit être éliminé en décomposant l'expression en plusieurs commandes et plus simple expressions, ou, si cela s'avère difficile, l'objet d'un commentaire."

toute discussion de "transparence référentielle" sans comprendre la distinction entre l-values, R-values et d'autres objets complexes qui peuplent l'impératif l'univers conceptuel du programmeur est fondamentalement erroné.

une expression est transparente référentiellement si elle peut être remplacée par sa valeur, sans changer l'algorithme, donnant un algorithme qui a les mêmes effets et sortie sur la même entrée.

une fonction transparente référentiellement est une fonction qui agit comme une fonction mathématique; avec les mêmes entrées, elle produira toujours les mêmes sorties. Cela implique que l'etat passe n'est pas modifié, et que la fonction n'a pas d'état de son propre.

Si vous êtes intéressé par l'étymologie (ie. pourquoi ce concept a-t-il ce nom particulier), jetez un oeil à mon blog post sur le sujet. La terminologie vient de la Quine philosophe/logicienne.

pour ceux qui ont besoin d'une explication concise, je mets en danger un (mais lisez la divulgation ci-dessous).

la transparence référentielle dans un langage de programmation favorise le raisonnement équationnel -- plus la transparence référentielle est grande, plus il est facile de faire un raisonnement équationnel. Par exemple: avec une définition de fonction (pseudo),

f x = x + x,

la facilité avec laquelle vous pouvez(en toute sécurité) remplacer f (foo) par foo + foo dans le cadre de cette définition, sans avoir trop de contraintes sur l'endroit où vous pouvez effectuer cette réduction, est une bonne indication de la transparence référentielle de votre langage de programmation.

par exemple, si foo était x++ dans le sens de programmation C, alors vous ne pourriez pas effectuer cette réduction en toute sécurité (ce qui veut dire que si vous deviez effectuer cette réduction, vous ne finiriez pas avec le même programme que celui avec lequel vous avez commencé).

dans les langages de programmation pratiques vous ne verrez pas une transparence référentielle parfaite, mais les programmeurs fonctionnels s'en soucient plus que la plupart des autres (cf. Haskell, où c'est un objectif central).

(divulgation complète: je suis un programmeur fonctionnel donc par la réponse supérieure vous devriez prendre cette explication avec un grain de sel.)

1. Denotational-sémantique est basée sur la modélisation des langues par la construction de domaines qui constituent denotable valeurs .
2. Fonctionnelle Programmeurs utilisent le terme valeur pour décrire la convergence d'un calcul basé sur les règles de réécriture de la langue ie. sa sémantique opérationnelle.

en 1 Il y a une clarté de deux langues en question:

• un être modélisées, la langue d'objet
• la langue de la modélisation, le méta-langage

en 2, grâce à la proximité de l'objet et des langues métalliques, ils peuvent être confondus.

en tant qu'exécuteur de langue, je trouve que je dois constamment me souvenir de cette distinction.

Donc, le prof. Reddy je te paraphraser ainsi :-)

dans les contextes de programmation fonctionnelle et sémantique, le terme référentiel Transparence n'est pas référentiellement transparent.

Notez que cette notion de "sens" est quelque chose qui se passe dans l'esprit de l'observateur. Ainsi, le même "de référence" peut signifier différentes choses pour différentes personnes. Ainsi, par exemple, nous avons une page de désambiguïsation D'Edimbourg dans Wikipedia.

Une question connexe qui peut apparaître dans le contexte de la programmation pourrait être le polymorphisme.

et peut-être que nous devrions avoir un nom pour le cas spécial de polymorphisme (ou peut-être même casting) où pour nos besoins, les différents cas polymorphiques sont sémantiquement équivalents (au lieu d'être simplement similaires). Par exemple, le nombre 1 -- qui pourrait être représenté par un type entier, ou un type complexe ou n'importe lequel d'une variété d'autres types -- peut être traité polymorphiquement).

la réponse suivante, je l'espère, ajoute et qualifie le controversé 1er et 3 réponse.

admettons qu'une expression désigne certains référent. Cependant, la question Est de savoir si ces références peuvent être codées de manière isomorphique dans le cadre d'expressions elles-mêmes, appelant ces expressions "valeurs". Par exemple, le nombre littéral valeurs sont un sous-ensemble de l'ensemble des expressions arithmétiques, la vérité, les valeurs sont un sous-ensemble de l'ensemble d'expressions booléennes, etc. L'idée est d'évaluer une expression à sa valeur (si elle en a un). Ainsi, le mot "valeur" peut renvoyer à une dénotation ou à un élément distinct de l'ensemble des expressions. Mais s'il y a un isomorphisme (bijection) entre le référent et la valeur nous peut dire qu'ils sont la même chose. (Ceci dit, il faut être prudent de définir les référents et l'isomorphisme, comme le prouve le domaine de la dénotationalisation sémantique. Pour mettre un exemple mentionné par les réponses à la troisième réponse, le de données algébriques la définition de type data Nat = Zero | Suc Nat ne s'applique pas correspondent, comme prévu, à l'ensemble des nombres naturels.)

écrivons E[·] pour une expression avec un trou, également connu dans certains quartiers en tant que "contexte". Deux exemples de contexte pour les expressions de type C sont [·]+1 et [·]++ .

écrivons [[·]] pour la fonction qui prend une expression (sans trou) et délivre son sens (référent, dénotation, etc.) certaines sens-fournir univers. (J'emprunte de la notation sur le terrain de sémantique dénotationnelle.)

adaptons la définition de Quine un peu formellement comme suit: un contexte E[·] est référentiellement transparent iff compte tenu de deux expressions E1 et E2 (pas de trous il s'agit de [[E1]] = [[E2]] (c'est-à-dire que les expressions dénotent/renvoient à la même référent) alors il est le cas que [[E[E1]]] = [[E[E2]]] (c.-à-d. remplissage le trou avec les résultats E1 ou E2 dans des expressions qui dénotent aussi la même référent.)

la règle de Leibniz de substituer des égaux pour des égaux est généralement exprimée comme " si E1 = E2 puis E[E1] = E[E2] ', qui dit que E[·] est une fonction. Fonction (ou d'ailleurs un programme calculant la fonction) est un mappage à partir d'un source vers une cible de sorte qu'il existe au plus un élément cible pour chaque source élément. Les fonctions non déterministes sont des misnomères, ce sont soit des relations, fonction livraison de décors, etc. Si dans la règle de Leibniz l'égalité = est denotational puis les doubles-crochets sont simplement pris pour acquis et élidés. Ainsi, un contexte référentiellement transparent est une fonction. Et la règle de Leibniz est le principal ingrédient du raisonnement équationnel, donc le raisonnement équationnel est certainement lié à la transparence référentielle.

bien que [[·]] soit une fonction des expressions aux dénotations, elle pourrait être fonction des expressions à des "valeurs" compris comme un sous-ensemble restreint de les expressions, et [[·]] peuvent être considérées comme une évaluation.

maintenant, si E1 est une expression et E2 est une valeur nous avons ce que je pense est signifié par la plupart des gens en définissant la transparence référentielle en termes d'expressions, de valeurs, et d'évaluation. Mais comme le montrent les première et troisième réponses de cette page, il s'agit là d'une définition imparfaite.

Le problème avec les contextes tels que [·]++ n'est pas l'effet secondaire, mais sa valeur n'est pas définie au sens c isomorphe. Les fonctions sont pas les valeurs (bien, les pointeurs vers les fonctions sont) alors que dans les langages de programmation fonctionnelle elles le sont. Landin, Strachey, et les pionniers de la sémantique dénotationnelle étaient assez intelligents dans utiliser des mondes fonctionnels pour donner un sens.

Pour d'impérieuses C-comme les langues que nous pouvons (à peu près) de fournir une sémantique pour expressions utilisant la fonction [[·]] : Expression -> (State -> State x Value) .

Value est un sous-ensemble de Expression . State contient des paires (identificateur,valeur). La fonction sémantique prend une expression et sa signification une fonction de l'état courant à la paire avec la mise à jour de l'état et d'une valeur. Par exemple, [[x]] est la fonction de l'état actuel la paire dont le premier est celui de l'état actuel et dont le second component est la valeur de X. En revanche, [[x++]] est la fonction de le état actuel de la paire dont le premier composant est un état dans lequel la valeur de x est incrémenté, et dont le deuxième composant est cette même valeur. Dans ce sense, le contexte [·]++ est référentiellement transparent iff il satisfait les définition donnée ci-dessus.

je pense que les programmeurs fonctionnels ont le droit d'utiliser la transparence référentielle dans le sentiment qu'ils récupèrent naturellement [[·]] comme une fonction des expressions aux valeurs. Les fonctions sont de première classe les valeurs et l'état peuvent également être une valeur, pas une la dénotation. L'état monade est (en partie) un mécanisme propre pour passer (ou threading) de l'état.

dans la programmation fonctionnelle, la transparence référentielle est généralement définie comme le fait qu'une expression, dans une émission, peut être remplacée par sa valeur (ou toute autre chose ayant la même valeur) sans changer le résultat de l'émission. Cela implique que les méthodes doivent toujours retourner la même valeur pour un argument donné, sans avoir aucun autre effet. Ce concept de programmation fonctionnelle s'applique également à la programmation impérative, et peut vous aider à rendre votre code plus clair.

Transparence Référentielle

l'expression transparence référentielle est utilisée dans divers domaines, tels que les mathématiques, la logique, la linguistique, la philosophie et la programmation. Il a une signification différente dans chacun de ces domaines. Ici, nous ne traiterons que des programmes informatiques, bien que nous montrerons l'analogie avec les mathématiques (mathématiques simples, ne vous inquiétez pas). Notons, cependant, que les informaticiens ne sont pas d'accord sur la signification de référentiel transparence dans la programmation. Ce que nous allons étudier est la transparence référentielle, puisqu'il est utilisé par des programmeurs.

transparence référentielle en mathématiques En mathématiques, la transparence référentielle est la propriété des expressions qui peuvent être remplacés par d'autres expressions ayant la même valeur sans changer le résultat. Prenons l'exemple suivant:

x = 2 + (3 * 4)

nous pouvons remplacer la sous-expression (3 * 4) par toute autre expression ayant la même valeur sans changer le résultat (la valeur de x). L'expression la plus évidente à utiliser est bien sûr 12:

x = 2 + 12

toute autre expression ayant la valeur 12 (peut-être (5 + 7)) peut être utilisée sans changer le résultat. En conséquence, la sous-expression (3 * 4) est référentiellement transparente.

nous pouvons aussi remplacer l'expression 2 + 12 par une autre expression ayant la même valeur sans changer la valeur de x, donc elle est référentiellement transparent:

x = 14

vous pouvez facilement voir l'avantage de la transparence référentielle: elle permet le raisonnement. Sans elle, nous ne pourrions résoudre aucune expression sans tenir compte d'autres éléments.

transparence référentielle dans la programmation Dans la programmation, la transparence référentielle s'applique aux programmes. Étant donné que les programmes sont composés de sous-programmes, qui sont eux-mêmes des programmes, ils s'appliquent également à ces sous-programmes. Sous-programmes peuvent être représentés, entre autres, par des méthodes. Cela signifie que la méthode peut être référentiellement transparente, ce qui est le cas si un appel à cette méthode peut être remplacé par sa valeur de retour:

int add(int a, int b) {
        return a + b
    }

int mult(int a, int b) {
        return a * b;
    }

int x = add(2, mult(3, 4));

dans cet exemple, la méthode mult est transparente référentiellement parce que tout appel à elle peut être remplacé par la valeur de retour correspondante. Ceci peut être observé en remplaçant mult (3, 4) par 12:

int x = add(2, 12)

De la même manière, ajouter(2, 12) peut être remplacé avec la valeur de retour correspondante, 14:

int x = 14;

aucun de ces remplacements ne changera le résultat du programme, quoi qu'il fasse. Notez que nous pourrions utiliser toute autre expression ayant la même valeur, ce qui est utile lors du remaniement.

d'autre part, considérer le programme suivant:

int add(int a, int b) {
    int result = a + b;
    System.out.println("Returning " + result);
    return result;
}

remplacer un appel à la méthode add avec la valeur de retour correspondante changera le résultat du programme, puisque le message ne sera plus imprimé. Dans ce cas, il supprimerait seulement l'effet secondaire mais dans d'autres cas, il pourrait changer la valeur retournée par la méthode:

public static void main(String... args) {
    printFibs(10);
}

public static void printFibs(int limit) {
    Fibs fibs = new Fibs();
    for (int i = 0; i < limit; i++) {
        System.out.println(fibs.next());
    }
}

static class Fibs {
    private int previous = -1;
    private int last = 1;

    public Integer next() {
        last = previous + (previous = last);
        return previous + last;
    }
}

ici, la méthode suivante ne peut pas être remplacée par quelque chose ayant la même valeur, puisque la méthode est conçue pour retourner une valeur différente sur chaque appel.

L'utilisation de telles méthodes non-référentiellement transparentes exige une discipline forte afin de ne pas partager le mutable de l'état impliqués dans le calcul. Le style fonctionnel évite de telles méthodes en faveur de versions référentiellement transparentes.

transparence référentielle dans la programmation impérative La programmation impérative et fonctionnelle utilise des fonctions. Bien que la programmation fonctionnelle n'utilise que des fonctions, la programmation impérative utilise:

• fonctions pures: méthodes retournant des valeurs et n'ayant pas d'autres effets
• effets purs: méthodes ne rien rendre mais changer quelque chose en dehors d'eux)
• fonctions avec des effets secondaires: méthodes à la fois retourner une valeur et changer quelque chose

comme nous le savons tous, il est de bonne pratique d'éviter les fonctions avec des effets secondaires. Cela laisse des programmeurs impératifs avec des fonctions pures et des effets purs. La transparence référentielle est alors un outil puissant pour les programmeurs impératifs pour rendre leurs programmes plus faciles à raisonner, et plus faciles à test.