Je m'intéresse aux compilateurs vérifiés formalisés en théorie de type Martin-Löf, c'est-à-dire Coq / Agda. En ce moment, j'ai écrit un petit exemple de jouet. Ainsi, je peux prouver que mes optimisations sont correctes. Par exemple, les ajouts avec zéro peuvent être éliminés, c'est-à-dire des expressions comme "x + 0".
Y a-t-il des optimisations difficiles à réaliser avec un compilateur classique, qui pourraient servir de bon exemple? Est-il possible de prouver certaines propriétés d'un programme qui permettent des optimisations impossibles à réaliser avec un compilateur classique? (c'est-à-dire sans l'inférence qui est possible avec un prouveur de théorème)
Je serais intéressé par des idées ou des exemples et aussi des références sur le sujet.
Une question connexe: preuves d'exactitude du compilateur
edit: Comme Tsuyoshi l'a bien dit dans les commentaires: je recherche des techniques d'optimisation difficiles à implémenter si un compilateur est écrit en (disons) C mais plus faciles à implémenter si un compilateur est écrit en (disons) Coq. Comme Agda compile en C (via haskell), il est possible de faire tout ce qui est possible dans Agda également en C. Probablement le seul avantage des prouveurs de théorèmes comme Coq / Agda est que le compilateur et les optimisations peuvent être vérifiés.
edit2: Comme suggéré par Vijay DI, écrivez ce que j'ai lu jusqu'à présent. Je me suis principalement concentré sur Xavier Leroy et le projet CompCert à l'INRIA (il y a un papier de 80 pages qui est une bonne lecture, je pense). Un deuxième intérêt était dans le travail d'Anton Setzer sur les programmes interactifs. Je pensais que peut-être son travail pourrait être utilisé pour prouver les propriétés des programmes IO et la bisimulation des programmes IO. Merci d'avoir mentionné Sewell. J'ai entendu son discours "Contes de la jungle" à l'ICFP et lu peut-être 2 à 3 de ses articles. Mais je n'ai pas spécifiquement regardé son travail et celui de ses co-auteurs.
Je ne savais pas encore par où commencer ni chercher des articles sur l'optimisation des compilateurs; par exemple, quelles optimisations seraient intéressantes à examiner dans le cadre d'un compilateur vérifié.
Réponses:
cet article d'Yves Bertot, de Benjamin Grégoire et de Xavier Leroy construit un compilateur d'optimisation pour un langage de type C basé uniquement sur la spécification Coq. une partie de cette technologie est apparemment utilisé dans le compilateur C CompCert .
Une approche structurée pour prouver les optimisations du compilateur basée sur l'analyse du flux de données
il considère l'exactitude de deux optimisations, la propagation constante (CP) et l'élimination de la sous-expression commune (CSE), section 4. ces optimisations sont plus avancées que celles qui sont associées aux compilateurs non basés sur Coq pour le même langage. voir par exemple ce graphique de référence par rapport à gcc. (le compilateur basé sur Coq est probablement plus lent à compiler, bien que cela soit rarement mentionné!)
cependant, à la fin de l'article, ils notent qu'il existe certaines optimisations de compilateur dans de vrais compilateurs qui ne peuvent pas être modélisées dans leur cadre.
l'amélioration optimisée n'est pas le seul élément à prendre en compte ici, un autre aspect est que la logique d'optimisation du compilateur peut être sujette à des défauts subtils, notamment en raison de sa nature complexe. au fil des ans, gcc s'est avéré avoir des bogues dans ses nombreuses routines de logique d'optimisation. par exemple, bug gcc?
la source
Cela équivaut à étendre le vérificateur de type pour fournir certaines propriétés d'un programme à l'optimiseur. Je crois que Tsuyoshi Ito a raison et vous pouvez être peu mal orienté à propos de Coq. C'est un excellent outil pour fournir un compilateur sans bogue, mais dans le cas que vous décrivez, il ne fournit pas plus de puissance aux analyses statiques.
La seule chose que je peux penser au renforcement des analyses statiques avec Coq, est d'équiper votre langage d'assertions contenant des preuves écrites par l'utilisateur. - Si le compilateur lui-même était traduit dans un langage comprenant une plume pour la vérification typographique dynamique, et si les preuves écrites par l'utilisateur pouvaient être converties en fonctions, alors il serait possible d'appliquer ces fonctions en tant que propriétés prérequises pour certains sous-types ou optimisations. - Cela fournirait en effet plus de puissance au compilateur.
Cependant, pour autant que je puisse voir, ce serait plutôt utile pour renforcer le sous-typage. - Il est difficile de faire savoir à un programmeur quelle propriété à quel endroit serait utile pour l'optimiseur.
la source