Principles of program verification for arbitrary monadic effects
Principes de la vérification de programmes à effets monadique arbitraires
Résumé
Computational monads are a convenient algebraic gadget to uniformly represent side-effects in programming languages, such as mutable state, divergence, exceptions, or non-determinism. Various frameworks for specifying programs and proving that they meet their specification have been proposed that are specific to a particular combination of side-effects. For instance, one can use Hoare logic to verify the functional correctness of programs with mutable state with respect to pre/post-conditions specifications, which are predicates on states. The goal of this thesis is to devise a principled semantic framework for verifying programs with arbitrary monadic effects in a generic way with respect to such rich specifications. One additional challenge is supporting various interpretations of effects, for instance total vs partial correctness, or angelic vs demonic nondeterminism. Finally, the framework should also accommodate relational verification, for properties such as program equivalence.
Les effets de bord présent dans les langages de programmation tel que l'état mutable, la divergence ou le non-déterminisme sont capturés de manière élégante par des monades. Plusieurs systèmes ont été proposés pour spécifier et prouver que des programmes manipulant une certaine combinaison d'effets respectent leur spécification. Par exemple, la logique de Hoare permet de vérifier la correction de programmes manipulant la mémoire en stipulant des prédicats sur les états initiaux et finaux. Le but de cette thèse est de définir un cadre sémantique générique pour vérifier que des programmes avec des effets monadique arbitraire respectent de telles spécifications. Les interprétations diverses des effets tels que la correction totale ou partielle, ou encore le non-déterminisme angélique ou démonique, introduisent un défi supplémentaire. Ce cadre sémantique devra aussi considérer la vérification de propriétés relationnelles, par exemple la simulation ou l'équivalence de programmes.
Origine : Version validée par le jury (STAR)