Calculer si une fonction est pure

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

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.

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.

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.

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.

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.