Calculer si une fonction est pure

11

Selon Wikipedia:

En programmation informatique, une fonction peut être décrite comme pure si ces deux déclarations sur la fonction sont valables: La fonction évalue toujours la même valeur de résultat pour la ou les mêmes valeurs d'argument. La valeur de résultat de la fonction ne peut dépendre d'aucune information ou état caché susceptible de changer au cours de l'exécution du programme ou entre différentes exécutions du programme, ni de toute entrée externe provenant de périphériques d'E / S. L'évaluation du résultat ne provoque aucun effet secondaire ou sortie sémantiquement observable, comme une mutation d'objets mutables ou une sortie vers des dispositifs d'E / S.

Je me demande s'il est possible d'écrire une fonction qui calcule si une fonction est pure ou non. Exemple de code en Javascript:

function sum(a,b) {
    return a+b;
}

function say(x){
    console.log(x);
}

isPure(sum) // True
isPure(say) // False
Oni
la source
7
Cela pourrait être candidat pour le Computer Science Stack Exchange . Cela tend plus vers le domaine de la théorie ("possible") que vers le pratique et le design ... C'est un peu au-delà de mon ken.
... et même si c'est "possible" et "théorique", il y a très probablement une vraie réponse (un bon ajustement pour les questions et réponses) qui peut même impliquer une preuve ... qui le ramène à nouveau dans le monde de l'informatique .
Je pense que vous pouvez déterminer si une fonction est pure en regardant le type de fonctions qui sont invoquées dans sa définition. Je veux dire, vous pouvez définir la pureté par induction sur la structure des fonctions.
Giorgio
7
Il n'est pas possible de se passer de hacks de réflexion spécifiques à la plate-forme. Si une fonction est une boîte noire, aucune expérience ne peut prouver qu'elle est pure. Par exemple, s'il y a quelque chose comme if (rand(1000000)<2) return WRONG_ANSWER, sonder la fonction plusieurs fois pour un comportement cohérent n'aidera pas. Mais, si vous avez accès à la définition de fonction, la preuve est triviale.
SK-logic
1
@ user470365 De la définition d'une fonction pure - "L'évaluation du résultat ne provoque aucun effet secondaire ou sortie sémantiquement observable, comme une mutation d'objets mutables ou une sortie vers des dispositifs d'E / S." - Tout ce qui écrit sur IO est par définition impur. Dans l'exemple, les sayappels console.logqui sont donc sayimpurs le sont aussi.

Réponses:

17

Oui, c'est possible, selon la langue.

En JavaScript, vous pouvez savoir si une fonction est pure selon les critères suivants:

  • Il ne lit que les paramètres et les sections locales;

  • Il n'écrit que des locaux;

  • Sur les non-locaux, il n'appelle que des fonctions pures;

  • Toutes les fonctions qu'il appelle implicitement sont pures, par exemple toString; et

  • Il écrit uniquement les propriétés des locaux s'ils n'aliasent pas les non-locaux.

L'aliasing n'est pas possible de déterminer en JavaScript dans le cas général, car vous pouvez toujours rechercher dynamiquement les propriétés d'un objet ( object["property"]). Pourvu que vous ne fassiez jamais cela et que vous ayez la source de tout le programme, je pense que le problème est traitable. Vous auriez également besoin d'informations sur les fonctions natives qui ont des effets secondaires, comme console.logou presque tout ce qui concerne le DOM.

Le terme «pur» pourrait également utiliser quelques éclaircissements. Même dans un langage de programmation purement fonctionnel fortement typé statiquement, où toutes les fonctions sont référentiellement transparentes, une fonction peut toujours échouer. Donc, quand nous parlons id :: a -> a, ce que nous disons vraiment n'est pas:

Étant donné une certaine valeur de type a, la fonction idproduit une valeur de type a.

Mais plutôt:

Étant donné une certaine valeur de type a, la fonction idne produit pas une valeur qui n'est pas de type a.

Parce qu'une implémentation valide de idis error "Not implemented!". Comme le souligne Peteris, cette non-totalité pourrait être considérée comme une sorte d'impureté. Koka est un langage de programmation fonctionnel - avec une syntaxe modelée sur JavaScript - qui peut déduire des effets possibles tels que la divergence (non-terminaison), la transparence référentielle, le lancement d'exceptions et les actions d'E / S.

Jon Purdy
la source
+1 - Étant donné la réponse de Peteris, il y a eu tellement de votes positifs .....
mattnz
Je suppose que vous auriez besoin d'ajouter "Il n'appelle que des fonctions pures" à la liste des critères.
Greg Hewgill
1
@GregHewgill: Bonne capture. J'ai mis à jour la réponse en conséquence. C'est bien d'appeler des fonctions de mutation sur les locaux, tant qu'ils ne sont pas autrement efficaces. «Pure» est un terme trop surchargé…
Jon Purdy
Vous devez également vérifier si toStringest pur pour tout objet que vous utilisez comme chaîne.
Oleg V. Volkov
Je ne pense pas que cette réponse soit correcte, car il n'y a qu'un sous-ensemble de circonstances où vous pouvez réellement faire ces déterminations. Considérez: cette fonction est-elle pure? function a (o) { return o.method(); }- nous ne pouvons pas réellement répondre à cette question, car cela dépend du paramètre opassé. De plus, nous ne pouvons pas expliquer ce qui se passe si une fonction précédemment certifiée pure est remplacée par une implémentation non pure, ce qui est toujours un problème potentiel avec javascript.
Jules
11

Non. Vous pouvez facilement vérifier si une fonction ne fait que des opérations "pure-safe", comme décrit dans la réponse de Jon Purdy, mais cela n'est pas suffisant pour répondre à la question.

Considérez cette fonction:

function possiblyPure(x) {
    if (someCheck(x)) {
        return x+1; // pure code path
    }
    else {
        console.log("I'm so unpure..."); // unpure code path
    }
}

De toute évidence, si someCheckn'est pas pur, il en est de même possiblyPure. Mais, si someCheckest pur et renvoie truepour chaque valeur possible de x, possiblyPureest pur, car le chemin de code non pur est inaccessible!

Et voici la partie difficile: déterminer si oui ou non someCheckretourne vrai pour chaque entrée possible. Essayer de répondre à cette question vous conduit immédiatement dans le domaine du problème d'arrêt et des problèmes similaires indécidables.

EDIT: Preuve qu'il est impossible

Il existe une certaine incertitude quant à savoir si une fonction pure doit se terminer sur chaque entrée possible. Mais dans les deux cas, le problème d'arrêt peut être utilisé pour montrer que le contrôle de pureté est impossible.

Cas A) Si une fonction pure doit se terminer sur chaque entrée possible, vous devez résoudre le problème d'arrêt pour déterminer si la fonction est pure ou non. Comme cela est connu pour être impossible, par cette définition, la pureté ne peut pas être calculée.

Cas B) Si une fonction pure est autorisée à ne pas se terminer sur certaines entrées, nous pouvons construire quelque chose comme ça: Supposons que isPure(f)calcule si fest une chaîne définissant une fonction pure.

function halts(f) {
   var fescaped = f.replace(/\"/g, '\\"');
   var upf = 'function() { '+f+'("'+fescaped+'\); console.log("unpure"); }';
   return isPure(upf);
}

Il isPurefaut maintenant déterminer si elle fs'arrête ou non sur sa propre source en entrée. Si ça s'arrête, upfc'est impur; s'il ne se termine pas, upfest pur ssi fest pur.

Si cela avait isPurefonctionné comme prévu (retourne des résultats corrects et se termine à chaque entrée), nous aurions résolu le problème d'arrêt (*)! Puisque cela est connu pour être impossible, isPurene peut pas exister.

(*) pour les fonctions JavaScript pures, ce qui est suffisant pour le résoudre également pour la machine de turing.

user281377
la source
3
Vrai. Il est toujours possible de faire une analyse prudente - pour vérifier si une fonction est définitivement pure, mais pas possible de vérifier si elle n'est certainement pas pure.
SK-logic
De nombreux cas sont trivialement décidables - ces fonctions pures décrites par Jon Purdy ou les fonctions impures qui font inconditionnellement quelque chose de sale; mais en général, on peut construire des cas indécidables.
user281377
1

Cette question de stackoverflow a une réponse de yfeldblum qui est pertinente ici. (Et a un downvote pour une raison que je ne peux pas comprendre. Serait-ce une mauvaise étiquette de voter pour quelque chose qui a 3 ans?) Il donne une preuve que si une fonction est pure est réductible au problème d'arrêt dans un commentaire.

Je pense que d'un point de vue pratique, ce ne serait pas trop difficile pour certaines langues si vous laissez la fonction retourner oui, non ou peut-être. J'étais en train de regarder une vidéo sur Clojure il y a quelques jours, et le locuteur avait fait un compte d'instances d'impuretés dans une base de code en recherchant environ 4 chaînes différentes (comme "ref"). En raison de l'accent mis par Clojure sur la pureté et la ségrégation des choses impures, c'était trivial, mais ce n'était pas exactement ce que vous recherchiez.

Donc, théoriquement impossible, pratiquement possible si vous ajustez un peu la question, et je pense que la difficulté dépendrait beaucoup de la langue. Des langages plus simples / plus propres mettant l'accent sur l'immuabilité et une bonne réflexion seraient plus faciles.

Michael Shaw
la source
Je pense que cela avait été rejeté parce que c'est faux. bottomest une valeur valide de première classe, elle ne mérite pas d'être discriminée de cette façon.
SK-logic
0

Grande question.

Le mieux que vous pouvez faire dans la pratique, en supposant qu'aucune capacité d'écoute des actions d'E / S pour appeler la fonction autant de fois que possible. Vérifiez ensuite si la valeur de retour est cohérente.

Mais vous ne pouvez pas faire cela en général. On peut soutenir que les programmes sans interruption ne sont pas purs et nous ne pouvons pas décider du problème de l’arrêt.

Peter est
la source
1
-1: Il serait plus que trivial d'écrire une fonction qui passe ce test et est tout sauf pure.
mattnz
3
Selon cette logique, toute voidfonction serait "pure", ce qui est clairement faux.
Greg Hewgill
1
@Greg: Par extension, void foo (void) devrait également être pur.
mattnz
0

Pas possible dans le cas général. Voir problème d'arrêt . En bref, il est impossible d'écrire un programme qui, étant donné une fonction et une entrée arbitraires, détermine si le programme s'arrêtera ou s'exécutera pour toujours. S'il s'exécute pour toujours, ce n'est pas une fonction pure qui correspond à la définition que vous avez donnée.

dbkk
la source
5
Courir pour toujours ne semble pas exclure une fonction de l'adaptation de ses critères à une fonction pure.
whatsisname
+1: Il est implicitement nécessaire que la fonction se termine par "La fonction évalue toujours la même valeur de résultat donne ...."
mattnz
2
Un fonctionnement constant pour toujours sans modifier aucun état est parfaitement "pur". Mais, bien sûr, c'est un problème de terminologie ici.
SK-logic
@mattnz, une telle fonction sera toujours évaluée à la bottomvaleur.
SK-logic
1
Je peux voir où le problème de terminologie entre en jeu. Dans certaines interprétations, une fonction "pure" est une fonction qui est déterministe et ne communique jamais aucun état ou valeur avec l'extérieur pendant son exécution. Dans d'autres interprétations, l'arrêt est ajouté aux exigences. Avec la première interprétation, il est facile de déterminer si une fonction est pure: une machine qui exécute un langage particulier devrait pouvoir déterminer si un programme dans ce langage établit une communication avec l'extérieur.
rwong