J'étais à la convention de Stackoverflow Dev Days Hier et l'une des orateurs parlait de Python. Il a montré une fonction Memoize et j'ai demandé s'il y avait un moyen de le garder d'être utilisé sur une fonction non pure. Il a dit non, c'est essentiellement impossible, et si quelqu'un pouvait trouver un moyen de le faire, cela ferait une bonne thèse de doctorat.
Ce genre de confus me confuse, car il ne semble pas tout ce qui est difficile pour un compilateur / interprète résoudre de manière récursive. Dans pseudocode: P>
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;
7 Réponses :
Voici la première chose à laquelle je suis tombé dans mon esprit lorsque j'ai lu votre question.
Hiérarchies de classe
Déterminer si une variable est modifiée inclut l'acte de creuser à travers chaque méthode qui est appelée la variable pour déterminer s'il est muté. C'est ... un peu tout droit vers l'avant pour un type scellé avec une méthode non virtuelle.
mais envisager des méthodes virtuelles. Vous devez trouver chaque type dérivé et vérifier que chaque dérogation de cette méthode ne ménage pas l'état. Déterminer cela n'est tout simplement pas possible dans une langue / un cadre qui permet une génération de code dynamique ou est simplement dynamique (si c'est possible, c'est extrêmement difficile). La raison pour laquelle l'ensemble de types dérivés n'est pas corrigé car un nouveau peut être généré au moment de l'exécution.
prendre 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 pouvait donc pas valider la méthode était pure ou non.
Oh, bon point. Le polymorphisme compliquerait définitivement les choses. Bien que cela puisse être corrigé en mettant une "contrainte pure" sur la fonction virtuelle de base.
Vous devez également annoter chaque appel système, chaque FFI, ...
et en outre, la «fuite» la plus tente a tendance à fuir dans toute la base de code.
Ce n'est pas un problème théoriquement intraitable, mais en pratique, il est très difficile de faire de manière à ce que tout le système ne se sent pas fragile.
comme un de côté, je ne pense pas que cela fait une bonne thèse de doctorat; Haskell a déjà déjà (une version de) ceci, avec l'Io Monad.
Et je suis sûr que beaucoup de gens continuent à regarder cette "pratique". (spéculation sauvage) dans 20 ans, nous pouvons avoir ceci.
L'ordinateur AI n'est-ce que de 4-6 ans seulement et est sûr qu'il sera capable de résoudre ce problème pour nous :)
À Haskell, chaque fonction est pure. io ne change pas cela. Eh bien, sauf à ceux qui font Unsafeperformio .
L'anootage de toute la classe système est que .NET fait pour leurs contrats de code. En cas de doute, il suppose que la méthode n'est pas pure.
Jared: L'ordinateur n'a-t-il pas été "de seulement 4 à 6 ans" depuis 30 ans ou plus? : P
@ Mason ou peut-être même 50 ans ou plus%)
@ Mason - Je pense que Jared est plaisante.
Il est particulièrement difficile en python. Étant donné que anoObject.func1 / code> peut être modifié arbitrairement au moment de l'exécution, vous ne pouvez pas déterminer au moment de la compilation quelle fonction fonctionnera anObject.func () appel ou même s'il s'agira du tout. .
Aie! D'accord, je peux voir comment cela rendrait cela plus difficile.
Il y a plus - Eval, Setattr (), GetTattr () Faire des choses étranges, etc. Des fonctionnalités comme celle-ci font des langues difficiles à analyser statiquement.
En plus des autres excellentes réponses ici: Votre pseudocode ne regarde que si une fonction modifie des variables. Mais ce n'est pas vraiment ce que "pur" signifie. "Pure" signifie généralement quelque chose de plus proche de "transparent de manière transparente." 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 de faire un facteur dans le résultat (ou de la lecture de l'entrée, ou de lire l'état de la machine, ou ...) rend la fonction non pure sans modifier aucune variables.
Aussi, vous pouvez écrire une fonction "pure" qui modifie des variables.
+1 Étant donné que l'effet secondaire ne signifie pas utiliser uniquement des valeurs immuables.
Je pense que le problème principal le ferait efficacement.
La langue D a des fonctions pures, mais vous devez les spécifier vous-même, de sorte 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 réductible pour décider si un programme donné s'arrêtera - et il est bien connu que le problème d'arrêt est le type de problème qui ne peut pas être résolu efficacement.
Je sais sur le problème d'arrêt, mais pourquoi dites-vous que c'est équivalent?
Supposons que j'écris un programme P qui simule l'exécution d'une fonction d'entrée F (I.e. p est un interprète). Supposons que P soit écrit de sorte qu'il s'arrête à une évaluation complète de F et immédiatement après avoir exécuté toute étape impure de F (avec une sortie indiquant pourquoi elle s'est arrêtée). Parce que certains F pourraient avoir la forme fa = fa - Syntaxe HASKELL pour une fonction avec un argument qui appelle simplement le même argument de l'infinitum, il y a certains f pour lesquels p pour lesquels P est n'ayant pas arrêté . Ainsi, la question de l'OP est réductible au problème d'arrêt.
Notez que dans HASKELLL, si nous nous débarrassons des échappatoires de la langue permettant un code impur intérieur autrement pur, le compilateur peut facilement déterminer quel code est purement pur et quel code n'est pas purement pur simplement en regardant les types. Haskell représente l'impureté au niveau de type.
D'une manière générale, les fonctions pures dans l'informatique n'excluent pas de fonctions de non-résiliation (ou de terminaison exceptionnellement) pour cette raison même. Haskell définit réellement la non-détermination d'être un type de valeur de retour spécial (le «fond») qui poisons efficacement toute opération qui tente de l'inspecter.
Notez que la complexité dépend également de la langue. Pour les langues les plus dynamiques, il est possible de redéfinir n'importe quoi à tout moment. Par exemple, dans TCL
proc myproc {a b} {
if { $a > $b } {
return $a
} else {
return $b
}
}
Certes, TCL est un cas extrême; L'une des langues les plus dynamiques est. Cela étant dit, il met en évidence le problème qu'il peut être difficile de déterminer la pureté d'une fonction même une fois que vous l'avez entrée. P> p>
Ce serait des variables accessibles qui doivent être locales, pas seulement modifiées. Une fonction dont le résultat dépend de la valeur actuelle d'un global, même si elle ne modifie pas que global, n'est clairement pas pure.
La question évidente: la journalisation affecte-t-elle la pureté? Je dirais que, au contraire, modifier en réalité une valeur globale (si cela ne peut pas lancer), n'affecte pas le résultat de votre méthode et permet ainsi de la mémoisation même si elle n'est clairement pas pure!