Effets secondaires brisant la transparence référentielle

11

La programmation fonctionnelle dans Scala explique l'impact d'un effet secondaire sur la rupture de la transparence référentielle:

effet secondaire, ce qui implique une certaine violation de la transparence référentielle.

J'ai lu une partie du SICP , qui traite de l'utilisation du «modèle de substitution» pour évaluer un programme.

Comme je comprends à peu près le modèle de substitution avec transparence référentielle (RT), vous pouvez décomposer une fonction dans ses parties les plus simples. Si l'expression est RT, vous pouvez décomposer l'expression et obtenir toujours le même résultat.

Cependant, comme l'indique la citation ci-dessus, l'utilisation d'effets secondaires peut / cassera le modèle de substitution.

Exemple:

val x = foo(50) + bar(10)

Si fooet bar n'ont pas d'effets secondaires, l'exécution de l'une ou l'autre fonction renvoie toujours le même résultat à x. Mais, s'ils ont des effets secondaires, ils modifieront une variable qui perturbe / jette une clé dans le modèle de substitution.

Je me sens à l'aise avec cette explication, mais je ne la comprends pas complètement.

Veuillez me corriger et remplir tous les trous en ce qui concerne les effets secondaires brisant la RT, en discutant également les effets sur le modèle de substitution.

Kevin Meredith
la source

Réponses:

20

Commençons par une définition de la transparence référentielle :

Une expression est dite référentiellement transparente si elle peut être remplacée par sa valeur sans changer le comportement d'un programme (en d'autres termes, produire un programme qui a les mêmes effets et qui sort sur la même entrée).

Cela signifie que (par exemple) vous pouvez remplacer 2 + 5 par 7 dans n'importe quelle partie du programme, et le programme devrait toujours fonctionner. Ce processus est appelé substitution. La substitution est valable si, et seulement si, 2 + 5 peuvent être remplacés par 7 sans affecter aucune autre partie du programme .

Disons que j'ai une classe appelée Baz, avec les fonctions Fooet Baren elle. Par souci de simplicité, nous dirons simplement cela Fooet les Bardeux renvoient la valeur transmise. Donc Foo(2) + Bar(5) == 7, comme vous vous en doutez. La transparence référentielle garantit que vous pouvez remplacer l'expression Foo(2) + Bar(5)par l'expression 7n'importe où dans votre programme, et le programme fonctionnera toujours de manière identique.

Mais que faire si Foorenvoyé la valeur transmise, mais Barretourné la valeur transmise, plus la dernière valeur fournie à Foo? C'est assez facile à faire si vous stockez la valeur de Foodans une variable locale dans la Bazclasse. Eh bien, si la valeur initiale de cette variable locale est 0, l'expression Foo(2) + Bar(5)renverra la valeur attendue de 7la première fois que vous l'invoquerez, mais elle renverra 9la deuxième fois que vous l'invoquerez.

Cela viole la transparence référentielle de deux manières. Tout d'abord, on ne peut pas compter sur Bar pour renvoyer la même expression chaque fois qu'elle est appelée. Deuxièmement, un effet secondaire s'est produit, à savoir que l'appel de Foo influence la valeur de retour de Bar. Puisque vous ne pouvez plus garantir que Foo(2) + Bar(5)sera égal à 7, vous ne pouvez plus remplacer.

C'est ce que signifie la transparence référentielle dans la pratique; une fonction référentiellement transparente accepte une certaine valeur et renvoie une valeur correspondante, sans affecter d'autre code ailleurs dans le programme, et renvoie toujours la même sortie pour la même entrée.

Robert Harvey
la source
5
La rupture RTvous empêche donc d'utiliser le. substitution model.Le gros problème de ne pas pouvoir l'utiliser substitution modelest le pouvoir de l'utiliser pour raisonner sur un programme?
Kevin Meredith du
C'est exactement ça.
Robert Harvey
1
+1 réponse merveilleusement claire et compréhensible. Je vous remercie.
Racheet
2
De plus, si ces fonctions sont transparentes ou "pures", l'ordre dans lequel elles s'exécutent n'est pas important, peu importe si foo () ou bar () s'exécute en premier, et dans certains cas, elles peuvent ne jamais évaluer si elles ne sont pas nécessaires
Zachary K
1
Encore un autre avantage de RT est que les expressions référentiellement transparentes coûteuses peuvent être mises en cache (car les évaluer une ou deux fois devrait produire exactement le même résultat).
dcastro
3

Imaginez que vous essayez de construire un mur et que vous avez reçu un assortiment de boîtes de différentes tailles et formes. Vous devez remplir un trou en forme de L particulier dans le mur; devriez-vous chercher une boîte en forme de L ou pouvez-vous remplacer deux boîtes droites de la taille appropriée?

Dans le monde fonctionnel, la réponse est que l'une ou l'autre solution fonctionnera. Lors de la construction de votre monde fonctionnel, vous n'avez jamais à ouvrir les boîtes pour voir ce qu'il y a à l'intérieur.

Dans le monde impératif, il est dangereux de construire votre mur sans inspecter le contenu de chaque boîte et les comparer au contenu de toutes les autres:

  • Certains contiennent des aimants puissants et pousseront d'autres boîtes magnétiques hors du mur s'ils ne sont pas correctement alignés.
  • Certains sont très chauds ou froids et réagiront mal s'ils sont placés dans des espaces adjacents.

Je pense que je vais m'arrêter avant de perdre votre temps avec des métaphores plus improbables, mais j'espère que le point est fait; les briques fonctionnelles ne contiennent aucune surprise cachée et sont entièrement prévisibles. Parce que vous pouvez toujours utiliser des blocs plus petits de la bonne taille et de la bonne forme pour remplacer un plus grand et qu'il n'y a pas de différence entre deux boîtes de la même taille et de la même forme, vous disposez d'une transparence référentielle. Avec des briques impératives, il ne suffit pas d'avoir quelque chose de la bonne taille et de la bonne forme - il faut savoir comment la brique a été construite. Pas référentiellement transparent.

Dans un langage fonctionnel pur, tout ce que vous devez voir est la signature d'une fonction pour savoir ce qu'elle fait. Bien sûr, vous voudrez peut-être regarder à l'intérieur pour voir comment il fonctionne, mais vous n'avez pas besoin de regarder.

Dans un langage impératif, on ne sait jamais quelles surprises pourraient se cacher à l'intérieur.

itsbruce
la source
"Dans un langage purement fonctionnel, il suffit de voir la signature d'une fonction pour savoir ce qu'elle fait." - Ce n'est généralement pas vrai. Oui, dans l'hypothèse du polymorphisme paramétrique, nous pouvons conclure qu'une fonction de type (a, b) -> ane peut être que la fstfonction et qu'une fonction de type a -> ane peut être que la identityfonction, mais vous ne pouvez pas nécessairement dire quoi que ce soit à propos d'une fonction de type (a, a) -> a, par exemple.
Jörg W Mittag
2

Comme je comprends à peu près le modèle de substitution (avec transparence référentielle (RT)), vous pouvez décomposer une fonction dans ses parties les plus simples. Si l'expression est RT, vous pouvez décomposer l'expression et obtenir toujours le même résultat.

Oui, l'intuition a tout à fait raison. Voici quelques conseils pour être plus précis:

Comme vous l'avez dit, toute expression RT doit avoir un single"résultat". Autrement dit, étant donné une factorial(5)expression dans le programme, il devrait toujours donner le même "résultat". Donc, si un certain factorial(5)est dans le programme et qu'il donne 120, il devrait toujours donner 120 quel que soit "l'ordre des étapes", il est développé / calculé - quelle que soit l' heure .

Exemple: la factorialfonction.

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)

Il y a quelques considérations avec cette explication.

Tout d'abord, gardez à l'esprit que les différents modèles d'évaluation (voir ordre applicatif vs ordre normal) peuvent donner des "résultats" différents pour la même expression RT.

def first(y, z):
  return y

def second(x):
  return second(x)

first(2, second(3)) # result depends on eval. model

Dans le code ci-dessus, firstet secondsont référentiellement transparents, et pourtant, l'expression à la fin donne des "résultats" différents si elle est évaluée dans l'ordre normal et l'ordre d'application (sous ce dernier, l'expression ne s'arrête pas).

.... ce qui conduit à l'utilisation de "résultat" entre guillemets. Puisqu'il n'est pas nécessaire qu'une expression s'arrête, elle peut ne pas produire de valeur. Donc, utiliser "résultat" est un peu flou. On peut dire qu'une expression RT donne toujours la même chose computationsdans un modèle d'évaluation.

Troisièmement, il peut être nécessaire de voir deux foo(50)apparaitre dans le programme à des endroits différents comme des expressions différentes - chacune produisant ses propres résultats qui peuvent différer les uns des autres. Par exemple, si le langage autorise une portée dynamique, les deux expressions, bien que lexicalement identiques, sont différentes. En perl:

sub foo {
    my $x = shift;
    return $x + $y; # y is dynamic scope var
}

sub a {
    local $y = 10;
    return &foo(50); # expanded to 60
}

sub b {
    local $y = 20;
    return &foo(50); # expanded to 70
}

La portée dynamique induit en erreur car elle permet de penser facilement que xc'est la seule entrée pour foo, alors qu'en réalité, c'est xet y. Une façon de voir la différence est de transformer le programme en programme équivalent sans portée dynamique - c'est-à-dire en passant explicitement les paramètres, donc au lieu de définir foo(x), nous définissons foo(x, y)et passons yexplicitement dans les appelants.

Le fait est que nous sommes toujours dans un functionétat d'esprit: étant donné une certaine entrée pour une expression, nous recevons un "résultat" correspondant. Si nous donnons la même entrée, nous devrions toujours nous attendre au même "résultat".

Maintenant, qu'en est-il du code suivant?

def foo():
   global y
   y = y + 1
   return y

y = 10
foo() # yields 11
foo() # yields 12

La fooprocédure rompt RT car il y a des redéfinitions. Autrement dit, nous avons défini yen un point, et ce dernier sur, redéfini ce même y . Dans l'exemple perl ci-dessus, les ys sont des liaisons différentes bien qu'ils partagent le même nom de lettre "y". Ici, les ys sont en fait les mêmes. C'est pourquoi nous disons que la (ré) affectation est une méta- opération: vous changez en fait la définition de votre programme.

En gros, les gens décrivent généralement la différence comme suit: dans un environnement sans effets secondaires, vous avez une cartographie à partir de input -> output. Dans un cadre «impératif», vous avez input -> ouputdans le cadre d'un statequi peut évoluer dans le temps.

Maintenant, au lieu de simplement substituer des expressions à leurs valeurs correspondantes, il faut également appliquer des transformations stateà chaque opération qui l'exige (et bien sûr, les expressions peuvent les consulter statepour effectuer des calculs).

Donc, si dans un programme libre d'effets secondaires, tout ce que nous devons savoir pour calculer une expression est son entrée individuelle, dans un programme impératif, nous devons connaître les entrées et l'état entier, pour chaque étape de calcul. Le raisonnement est le premier à subir un gros coup (maintenant, pour déboguer une procédure problématique, il faut l'entrée et le core dump). Certaines astuces sont rendues impraticables, comme la mémorisation. Mais aussi, la concurrence et le parallélisme deviennent beaucoup plus difficiles.

Thiago Silva
la source
1
Ravi que vous mentionniez la mémorisation. Ceci peut être utilisé comme un exemple d'état interne qui n'est pas visible à l'extérieur: une fonction utilisant la mémorisation est toujours référentiellement transparente même si en interne elle utilise l'état et la mutation.
Giorgio