Un compilateur peut-il détecter automatiquement des fonctions pures sans les informations de type relatives à la pureté?

Question

Donc, je suis disputer avec mon ami qui prétend qu'un compilateur comme GCC est capable de détecter une fonction pure automatiquement sans aucune information de type. J'en doute.

Les langues, comme le D ou Haskell ont pureté dans leurs systèmes de type et d'un programmeur définit explicitement de la fonction qui est pur ou non. Une pure fonction n'a pas d'effets secondaires et peut donc très facilement être parallélisé.

La question est donc: Est-ce nécessaire ou pas? Pourrait un compilateur de détecter pureté, sans aucune méta ou des informations de type, juste en supposant que tout ce qui ne IO ou accède à des variables globales automatiquement n'est pas pur?

Answer 1

Bien sûr, vous pouvez détecter les fonctions pures dans certains cas. Par exemple,

int f(int x)
{
    return x*2;
}

peut être détecté comme pur, simple analyse statique. La difficulté est de faire cela en général, et la détection des interfaces qui utilisent "interne" de l'état, mais à l'extérieur pur est fondamentalement impossible.

GCC n'ont les options d'alerte -Wsuggest-attribute=pure et -Wsuggest-attribute=const, qui suggèrent des fonctions qui pourraient être candidats à l' pure et const attributs. Je ne suis pas sûr qu'il choisit d'être conservateur (c'est à dire s'il manque beaucoup de fonctions pures, mais jamais il suggère, pour un non-fonction pure) ou permet à l'utilisateur de décider.

Notez que GCC de la définition de l' pure est "dépendant uniquement sur des arguments et des variables globales":

De nombreuses fonctions ont pas d'effets à l'exception de la valeur de retour et leur valeur de retour ne dépend que des paramètres et/ou des variables globales. Une telle fonction peut être soumis à des courants sous-expression de l'élimination et de l'optimisation en boucle comme un opérateur arithmétique serait. Ces fonctions doivent être déclarés avec l'attribut pure.

- Manuel de GCC

Strictes de pureté, c'est à dire les mêmes résultats pour les mêmes arguments, en toutes circonstances, est représenté par l' const d'attribut, mais cette fonction ne peut pas même de déréférencement d'un pointeur passé à elle. Donc, la parallélisation des opportunités pour pure les fonctions sont limitées, mais beaucoup moins de fonctions peuvent être const par rapport à la pure fonctions que vous pouvez écrire dans une langue comme Haskell.

Par la voie, automatiquement parallelising fonctions pures n'est pas aussi facile que vous le pensez; la partie la plus difficile devient de décider ce que paralléliser. Paralléliser les calculs qui sont trop pas cher, et les frais généraux, le rend inutile. Ne pas paralléliser assez, et vous n'avez pas récolter les bénéfices. Je ne sais pas du tout pratique et fonctionnelle de la langue mise en œuvre qui ne la parallélisation automatique pour cette raison, et bien que les bibliothèques comme repa paralléliser de nombreuses opérations en arrière-plan sans parallélisme explicite dans le code de l'utilisateur.

Answer 2

Il y a un autre problème. Envisager

int isthispure(int i) {
   if (false) return getchar();
   return i + 42;
}

La fonction est effectivement pure, même si elle contient de l'impur code, mais ce code ne peut pas être atteint. Maintenant, supposons false est remplacé par g(i) , mais nous savons bien sûr que g(i) est fausse (par exemple, g peut vérifier si son argument est un nombre Lychrel). Pour prouver que isthispure est en effet pure, le compilateur aurait à prouver qu'aucun des numéros de Lychrel existent.

(J'avoue que c'est une réflexion théorique. On pourrait aussi décider que si une fonction contient toute impur code, il est lui-même impur. Mais ce n'est pas justifiée par le type C du système, à mon humble avis.)

Answer 3

Déterminer si une fonction est pur (même dans le sens limité utilisée par GCC) est équivalent au problème de l'arrêt, si la réponse est "pas de fonctions arbitraires." Il est possible de détecter automatiquement que certaines fonctions sont pures, les autres ne sont pas pures, et le drapeau le reste "inconnu", qui permet la parallélisation automatique dans certains cas.

Dans mon expérience, même les programmeurs ne sont pas très bon à trouver de telles choses, donc je veux que le type de système pour aider à garder une trace de celui-ci pour moi, pas seulement pour l'optimiseur.

Answer 4

J'ai découvert lors de l'écriture d'un article comparant C# et C++ performance que Visual C++ peut en effet détecter une pure fonction de complexité moyenne, alors que l'appel d'une fonction que le calcul d'un polynôme.

J'ai appelé le polynôme fonction dans une boucle de manger jusqu'à l'heure sur l'horloge. Le compilateur optimisé l'appel pour exécuter une fois avant la boucle commencée et ré-utiliser le résultat dans la boucle. Pour cela, il faut savoir qu'il n'y a pas d'effets secondaires.

Je dois dire cependant, c'est agréable d'être en mesure de garantir que le compilateur peut faire de l'optimisation, par le marquage d'une fonction pure, et il sert comme une forme de documents, de trop.