Outil de prototypage de sémantique de langage de programmation

11

Existe-t-il un outil pour prototyper la sémantique et le système de type d'un langage de programmation et qui permet également une sorte de vérification du modèle des propriétés standard, comme la solidité du type?

Je pose cette question, car je lis un livre sur Alloy et il fournit la fonctionnalité exacte que je veux, mais pour les modèles exprimés en utilisant la logique relationnelle.

Je connais Ott , mais il n'a pas ce genre de capacité de "vérification de modèle", car il se concentre sur la génération de code pour les systèmes d'assistant de preuve.

Toute référence sur l'existence d'un tel outil serait bien.

Rodrigo Ribeiro
la source
1
Ott est la première étape, puis vous effectuez la vérification du modèle dans votre assistant de preuve préféré.
Gilles 'SO- arrête d'être méchant'
@Gilles: D'accord, mais un point fort d'un outil de vérification de modèle est qu'il génère tout un ensemble d'éléments d'une taille donnée afin de vérifier si la propriété est bien valable pour eux. De cette façon, je devrai coder cette partie de génération pour chaque langage défini. Saviez-vous s'il existe un moyen d'automatiser cette étape de génération?
Rodrigo Ribeiro
Techniquement, vous pouvez le faire dans un assistant de preuve (au moins dans un tel que Coq) mais ce sera probablement très lent. Les assistants d'épreuve sont orientés vers les épreuves assistées par l'homme plutôt que d'essayer automatiquement des millions de façons de résoudre le problème. Si vous souhaitez réutiliser Ott, vous pouvez ajouter un backend pour votre vérificateur de modèle préféré.
Gilles 'SO- arrête d'être méchant'

Réponses:

8

Bien qu'il existe des cadres créés spécifiquement dans le but de prototyper les langages de programmation (y compris leur sémantique, les systèmes de types, l'évaluation et la vérification des propriétés les concernant), le meilleur choix dépend de votre cas particulier et de vos besoins spécifiques.

Cela dit, il existe plusieurs alternatives (peut-être pas si distinctes) que vous pourriez prendre (y compris celles que vous avez déjà mentionnées):

  • en utilisant un langage / framework spécifique conçu pour créer et prototyper de nouveaux langages: par exemple, Redex [1], un langage spécifique au domaine intégré dans Racket pour spécifier et vérifier la sémantique (opérationnelle) des langages de programmation, qui, étant donné une définition d'un langue, facilite la gestion des tâches telles que la composition (en Latex), l'inspection des traces de réduction, les tests unitaires et les tests aléatoires (par exemple pour vérifier la frappe)
  • utiliser des langages de modélisation généraux qui permettent de définir et d'effectuer facilement certaines analyses, à condition qu'ils puissent capturer le langage spécifique à portée de main dans la mesure nécessaire; L'alliage [2] est un exemple d'une telle approche: quoique assez généraux et flexibles, les langages peuvent être modélisés comme des relations entre états, tandis que le support pour la vérification de modèle (par exemple l'évaluation dans un tel langage) est gratuit après que la sémantique soit exprimée avec un modèle de relation (par exemple, quelques idées pour modéliser la sémantique d'un langage peuvent être trouvées dans [3])
  • incorporer le langage pour vérifier ses propriétés à l'aide d'un prouveur de théorème; un exemple définirait le langage ainsi que sa sémantique en l'intégrant dans un système de preuve comme Coq [4] (plus de détails sur cette approche, ainsi que la discussion et la démonstration de la différence entre l'intégration profonde et superficielle dans Coq sont donnés dans [ 5])
  • en utilisant Ott (comme déjà mentionné, avec un esprit similaire à Redex, mais en fournissant un nouveau langage de définition plutôt que d'être intégré); Ott vous permet de définir le langage de programmation dans une notation pratique, et de produire la composition et les définitions dans un système de preuve (généralement avec une intégration profonde), où la plupart des vérifications (c'est-à-dire la preuve) doivent être effectuées manuellement
  • développer le langage et sa sémantique, ainsi que des vérifications appropriées (par exemple en tant que tests) "à partir de zéro" dans un langage de programmation à usage général et la traduction dans d'autres systèmes si nécessaire, à des fins de vérification (certaines langues, comme Leon [6], inclure des vérificateurs intégrés, qui permettent de prouver automatiquement certaines propriétés et rendent cette approche similaire à l'intégration dans un système de preuve)

Notez qu'il y a un compromis entre la facilité d'utilisation du cadre / outil (par exemple aussi simple que la présentation de la définition sur papier ou en Latex) et la puissance des mécanismes de vérification des propriétés du langage (par exemple, l'intégration de la dans un prouveur de théorèmes peut permettre de vérifier des propriétés très élaborées).

[1] Casey Klein, John Clements, Christos Dimoulas, Carl Eastlund, Matthias Felleisen, Matthew Flatt, Jay A. McCarthy, Jon Rafkind, Sam Tobin-Hochstadt et Robert Bruce Findler. Exécutez vos recherches: sur l'efficacité de la mécanisation légère. POPL, 2012.

[2] Daniel Jackson. Alliage: une notation de modélisation d'objet légère. TOSEM, 2002.

[3] Greg Dennis, Felix Chang, Daniel Jackson. Vérification modulaire du code avec SAT. ISSTA, 2006

[4] Système formel de gestion des preuves Coq

[5] Raisonnement formel sur les programmes. Adam Chlipala, 2016

[6] Système automatisé Leon pour vérifier, réparer et synthétiser les programmes Scala fonctionnels

ivcha
la source