Pourquoi est-il difficile de déterminer si une fonction est pure?

StackOverflow https://stackoverflow.com/questions/1609303

Question

J'étais à la convention StackOverflow Dev Days hier, et l'un des intervenants parlait de Python. Il a montré une fonction Memoize et j'ai demandé s'il était possible de l'empêcher d'être utilisée sur une fonction non pure. Il a dit non, c'est en principe impossible, et si quelqu'un pouvait trouver un moyen de le faire, cela ferait une excellente thèse de doctorat.

Cela m’a un peu dérouté, car il ne semble pas très difficile pour un compilateur / interprète de résoudre récursivement. En pseudocode: 

function isPure(functionMetadata): boolean;
begin
   result = true;
   for each variable in functionMetadata.variablesModified
      result = result and variable.isLocalToThisFunction;
   for each dependency in functionMetadata.functionsCalled
      result = result and isPure(dependency);
end;

C'est l'idée de base. Évidemment, vous auriez besoin d'une sorte de vérification pour éviter une récursion infinie sur des fonctions qui dépendent l'une de l'autre, mais ce n'est pas trop difficile à configurer.

Les fonctions d'ordre supérieur qui prennent des pointeurs de fonction peuvent poser problème, car elles ne peuvent pas être vérifiées statiquement, mais ma question initiale présuppose que le compilateur ait une sorte de contrainte de langage pour indiquer que seul un pointeur de fonction pur peut être transmis. un certain paramètre. S'il en existait un, il pourrait être utilisé pour satisfaire à la condition.

Évidemment, cela serait plus facile dans un langage compilé que dans un langage interprété, car tout ce travail de calcul serait effectué avant l'exécution du programme et ne ralentirait donc rien, mais je ne vois pas vraiment de problèmes fondamentaux rendre impossible l'évaluation.

Quelqu'un ayant un peu plus de connaissances dans ce domaine sait-il ce qu'il me manque?

Était-ce utile?

La solution

C'est particulièrement difficile en Python. Puisque anObject.aFunc peut être modifié arbitrairement à l'exécution, vous ne pouvez pas déterminer au moment de la compilation quelle fonction appellera unObject.aFunc () ou même s'il s'agira d'une fonction. .

Autres conseils

Vous devez également annoter chaque appel système, chaque FFI, ...

Et en outre, la plus petite "fuite" a tendance à s'infiltrer dans la base de code entière.

Ce n’est pas un problème théoriquement insoluble, mais dans la pratique, il est très très difficile de le faire de manière à ce que le système ne se sente pas fragile.

En passant, je ne pense pas que cela constitue une bonne thèse de doctorat; Haskell en a effectivement déjà une version avec la monade IO.

Et je suis sûr que beaucoup de gens continuent à regarder cela "en pratique". (spéculation sauvage) Dans 20 ans, nous aurons peut-être ceci.

En plus des autres excellentes réponses proposées ici: votre pseudocode détermine uniquement si une fonction modifie des variables. Mais ce n'est pas vraiment ce que "pur" veux dire. " Pure " signifie généralement quelque chose de plus proche de "transparent par rapport aux référentiels". En d'autres termes, la sortie dépend complètement de l'entrée. Donc, quelque chose d'aussi simple que de lire l'heure actuelle et d'en faire un facteur dans le résultat (ou de lire une entrée, ou de lire l'état de la machine, ou ...) rend la fonction non pure, sans modifier aucune variable.

Vous pouvez également écrire un "pur" " fonction qui a modifié les variables.

Voici la première chose qui m'est venue à l'esprit lorsque j'ai lu votre question.

  

Hiérarchies de classes

Pour déterminer si une variable est modifiée, il faut creuser dans chacune des méthodes appelées pour déterminer si elle est en mutation. C'est ... un peu simple pour un type scellé avec une méthode non virtuelle.

Mais considérez les méthodes virtuelles. Vous devez rechercher chaque type dérivé et vérifier que chaque substitution de cette méthode ne mute pas en état. Déterminer ceci n’est tout simplement pas possible dans un langage / framework qui permet la génération de code dynamique ou est tout simplement dynamique (si cela est possible, c’est extrêmement difficile). La raison en est que l'ensemble des types dérivés n'est pas corrigé, car un nouveau peut être généré à l'exécution.

Prenons C # comme exemple. Rien ne m'empêche de générer une classe dérivée au moment de l'exécution qui remplace cette méthode virtuelle et modifie l'état. Une vérification statique ne serait pas en mesure de détecter ce type de modification et ne pourrait donc pas valider que la méthode soit pure ou non.

Je pense que le principal problème serait de le faire efficacement.

Le langage D a des fonctions pures mais vous devez les spécifier vous-même pour que le compilateur sache les vérifier. Je pense que si vous les spécifiez manuellement, il serait plus facile de le faire.

Décider si une fonction donnée est pure, en général, est plus facile à décider si un programme donné va s’arrêter - et il est bien connu que le problème de la suspension est le genre de problème qui ne peut pas être résolu efficacement.

Notez que la complexité dépend également de la langue. Pour les langages plus dynamiques, il est possible de tout redéfinir à tout moment. Par exemple, dans Tcl 

proc myproc {a b} {
    if { $a > $b } {
        return $a
    } else {
        return $b
    }
}

Chaque élément de celui-ci pourrait être modifié à tout moment. Par exemple:

  • le " if " La commande peut être réécrite pour utiliser et mettre à jour les variables globales
  • le " return " commande, dans le même sens, pourrait faire la même chose
  • the pourrait être une trace d'exécution sur la commande if que, quand "if". est utilisé, la commande de retour est redéfinie en fonction des entrées de la commande if

Certes, Tcl est un cas extrême; l'un des langages les plus dynamiques qui soient. Cela dit, cela met en évidence le problème selon lequel il peut être difficile de déterminer la pureté d'une fonction même une fois que vous l'avez entrée.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top