Examiner les types et les preuves dans les langages de programmation
Un aperçu des types, contextes et preuves dans les langages de programmation.
Kelvin Qian, Scott Smith, Brandon Stride, Shiwei Weng, Ke Wu
― 6 min lire
Table des matières
- Types dans les Langages de Programmation
- Définir les Types
- Taille des Types
- Le Langage de Base
- Syntaxe
- Sémantique Opérationnelle
- Preuves dans le Langage de Base
- Cas de Base
- Étape Inductive
- Contextes et Substitution
- Contextes
- Substitution
- Fonctionnalités Étendues du Langage
- Raffinements
- Polymorphisme
- Preuves pour le Langage Étendu
- Complétude
- Validité
- Conclusion
- Source originale
- Liens de référence
Dans cet article, on va parler d'un langage de programmation de base et de ses extensions. On va surtout se concentrer sur comment on définit les Types, comment ces types se relient entre eux, et les règles qui régissent le langage. On va expliquer la structure de ce langage, le concept de types et comment ils interagissent dans notre système.
Types dans les Langages de Programmation
Les types sont super importants dans les langages de programmation. Ils garantissent que les variables contiennent le bon type d'information. Par exemple, une variable censée stocker des chiffres ne devrait pas prendre une chaîne de caractères comme valeur. Dans cet article, on va définir différents types et comment ils sont utilisés.
Définir les Types
On a plusieurs types dans notre langage. On peut avoir des types de base comme les entiers et les booléens, et on peut aussi avoir des types plus complexes comme les fonctions et les enregistrements. Chaque type a ses propres règles sur les types de valeurs qu'il peut contenir.
Types de Base
- Entiers : Ce sont des nombres entiers, comme 1, 2 ou -3.
- Booléens : Ce sont des valeurs de vérité, soit vrai soit faux.
Types Complexes
- Fonctions : Les fonctions sont des blocs de code qui peuvent prendre des entrées et produire des sorties. Elles sont définies avec des paramètres.
- Enregistrements : Les enregistrements sont des collections de paires clé-valeur. Ils nous permettent de regrouper des informations liées.
Taille des Types
La taille d'un type peut dépendre de sa structure. Par exemple, un simple entier a une taille de 1, tandis qu'un enregistrement peut avoir une taille qui dépend du nombre de champs qu'il contient. Comprendre la taille des types est important pour la gestion de la mémoire.
Le Langage de Base
Le langage de base est la fondation sur laquelle tout le reste est construit. Il introduit une syntaxe de base et des règles pour écrire des programmes. On va discuter de comment ce langage fonctionne.
Syntaxe
La syntaxe de notre langage de base se compose de divers éléments comme des déclarations, des expressions et des instructions. Un programme typique pourrait déclarer des variables puis effectuer des calculs ou appeler des fonctions.
Sémantique Opérationnelle
La sémantique opérationnelle décrit comment les instructions dans notre langage affectent l'exécution du programme. Chaque opération entraîne un changement dans l'état du programme, ce qui est essentiel pour comprendre comment les programmes fonctionnent.
Preuves dans le Langage de Base
Les preuves jouent un rôle crucial dans l'assurance que notre langage fonctionne comme prévu. En montrant que certaines propriétés sont vraies, on peut garantir l'intégrité des opérations dans le langage.
Cas de Base
Dans les preuves, on commence souvent par un cas de base. C'est le scénario le plus simple où les règles s'appliquent sans conditions compliquées. On peut montrer que certaines propriétés sont vraies pour des constructions de base d'abord.
Étape Inductive
Après avoir prouvé le cas de base, on passe à l'étape inductive. Ici, on suppose que notre propriété est vraie pour des tailles plus petites ou des cas plus simples, puis on montre qu'elle doit aussi être vraie pour des cas plus grands ou plus complexes. Cette méthode est utile pour prouver le comportement des fonctions ou des structures récursives.
Contextes et Substitution
Un des points sur lesquels on se concentre, c'est comment fonctionnent les contextes et les Substitutions dans notre langage. Quand on parle de contextes, on parle des environnements dans lesquels les expressions sont évaluées. La substitution fait référence au remplacement de parties des expressions par d'autres expressions ou valeurs.
Contextes
Les contextes peuvent contenir des espaces réservés pour des variables ou des valeurs. Par exemple, un contexte peut être configuré pour attendre une valeur entière à un endroit spécifique. Quand on substitue une valeur, on change le contexte pour s’adapter à la nouvelle valeur.
Substitution
Quand une valeur est substituée dans une expression, elle doit respecter les règles des types. Si on substitue un entier là où un booléen est attendu, ça va produire une erreur.
Fonctionnalités Étendues du Langage
En développant notre langage de base, on introduit des extensions qui permettent des tâches de programmation plus complexes. Ces extensions ajoutent de nouveaux types et opérations, permettant plus de flexibilité et de puissance.
Raffinements
Les raffinements sont un moyen de garantir que certaines conditions sont respectées lors de l'utilisation des types. Ils précisent qu'une valeur doit non seulement être d'un certain type mais aussi répondre à des critères supplémentaires. Par exemple, un nombre pourrait devoir être positif.
Polymorphisme
Le polymorphisme permet aux fonctions d'opérer sur différents types de valeurs tout en maintenant la sécurité des types. Ça veut dire qu'une seule fonction peut gérer différents types, comme des entiers ou des booléens, sans conflit.
Preuves pour le Langage Étendu
Tout comme pour le langage de base, on doit établir des preuves pour les fonctionnalités étendues. Ça garantit que les nouvelles parties du langage fonctionnent correctement.
Complétude
La complétude signifie que si on peut dériver un certain type, on peut aussi trouver un moyen de l'utiliser dans notre langage. Si on prétend qu'un certain type peut être généré, on doit aussi pouvoir l'utiliser correctement dans tous les contextes.
Validité
La validité est l'opposé de la complétude. Elle garantit que si un type passe nos vérifications dans notre système, il ne va pas causer d'erreurs pendant l'exécution. Cette propriété aide à maintenir l'intégrité des programmes écrits dans le langage.
Conclusion
En résumé, on a exploré les aspects fondamentaux d'un langage de programmation et de ses extensions. Les types, les contextes et les preuves sont essentiels pour comprendre comment fonctionne le langage. En construisant sur ces concepts, on introduit des fonctionnalités plus complexes qui permettent aux programmeurs de créer des applications robustes et flexibles. En garantissant à la fois la complétude et la validité dans notre système, on offre un cadre fiable pour les développeurs.
Titre: Semantic-Type-Guided Bug Finding
Résumé: In recent years, there has been an increased interest in tools that establish \emph{incorrectness} rather than correctness of program properties. In this work we build on this approach by developing a novel methodology to prove incorrectness of \emph{semantic typing} properties of functional programs, extending the incorrectness approach to the model theory of functional program typing. We define a semantic type refuter which refutes semantic typings for a simple functional language. We prove our refuter is co-recursively enumerable, and that it is sound and complete with respect to a semantic typing notion. An initial implementation is described which uses symbolic evaluation to efficiently find type errors over a functional language with a rich type system.
Auteurs: Kelvin Qian, Scott Smith, Brandon Stride, Shiwei Weng, Ke Wu
Dernière mise à jour: 2024-09-20 00:00:00
Langue: English
Source URL: https://arxiv.org/abs/2409.13896
Source PDF: https://arxiv.org/pdf/2409.13896
Licence: https://creativecommons.org/licenses/by/4.0/
Changements: Ce résumé a été créé avec l'aide de l'IA et peut contenir des inexactitudes. Pour obtenir des informations précises, veuillez vous référer aux documents sources originaux dont les liens figurent ici.
Merci à arxiv pour l'utilisation de son interopérabilité en libre accès.
Liens de référence
- https://archive.softwareheritage.org/swh:1:cnt:6b61de06aa8d945714c9a31cdd4fd0b17f1d0f6a;origin=
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/lang-jayil/ast.ml
- https://archive.softwareheritage.org/swh:1:cnt:9079b3d3ddd04c930645e94fc4bfbe6b41436bef;origin=
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/concolic/evaluator.ml;lines=75
- https://archive.softwareheritage.org/swh:1:cnt:54694433d1e7c0bd80916a0b2c849e975a51b702;origin=
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src-vendor/sudu/z3_api.ml;lines=82-85
- https://archive.softwareheritage.org/swh:1:cnt:09f8afbc874ac8f6108bd78ba6f293a1091a92f8;origin=
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/from_dbmc/solve/riddler.ml;lines=11-84
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/from_dbmc/solve/riddler.ml;lines=280-305
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/from_dbmc/solve/riddler.ml;lines=97-135
- https://archive.softwareheritage.org/swh:1:cnt:d7daef5e3497108f8e4f8115be9ef37de4c84556;origin=
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/concolic/structure/concolic_key.ml
- https://archive.softwareheritage.org/swh:1:cnt:f3037b9e2b16697538dac8e248a86a66d06594ab;origin=
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/concolic/session.ml;lines=147-151
- https://archive.softwareheritage.org/swh:1:cnt:227eaae664f89cca38bf5497ddcf4d26d69565b8;origin=
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/concolic/structure/path_tree.mli
- https://archive.softwareheritage.org/swh:1:cnt:074a434052dae6b7480806c5a60199bee440e3b6;origin=
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/concolic/structure/path_tree.ml;lines=173
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/concolic/structure/path_tree.ml;lines=306-310
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/concolic/structure/path_tree.ml;lines=121
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/concolic/structure/path_tree.ml;lines=242
- https://archive.softwareheritage.org/swh:1:cnt:897738a3ab8aea12cc16d0b20930e9dd779a7e84;origin=
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/concolic/structure/target.ml
- https://archive.softwareheritage.org/swh:1:cnt:291d602ef65d8c9e74b06fc54cddd971cdac3450;origin=
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/concolic/structure/target_queue.ml;lines=162
- https://archive.softwareheritage.org/swh:1:cnt:e197f8b7eb409c418809d912562dd567082c337a;origin=
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/concolic/symbolic_session.ml;lines=71-105
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/concolic/structure/path_tree.ml;lines=334
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/concolic/session.ml;lines=10
- https://archive.softwareheritage.org/swh:1:cnt:b6ee1c07f731325af6eacf974c7149f4b96604fa;origin=
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/concolic/symbolic_session.mli
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/concolic/session.ml;lines=69-177
- https://archive.softwareheritage.org/swh:1:cnt:23ea05d9ac6d359a439a8f6905bbd0f5d49d81a9;origin=
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:81fd6589252aaad05bc3c267a92ae267cb1757f9;anchor=swh:1:rev:50074785b0709bdac21cc4dd4acc9eea7b159d76;path=/src/dbmc/concolic/concolic_driver.ml;lines=54
- https://archive.softwareheritage.org/swh:1:cnt:6309abee6f2a3d2711c4e72dd54fe9b1f79c3384;origin=
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/concolic/driver.mli;lines=21
- https://archive.softwareheritage.org/swh:1:cnt:008d588a1586fe2b546e49167e7ae89a99786b8c;origin=
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/concolic/options.ml;lines=5
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/concolic/options.ml;lines=20
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/concolic/options.ml;lines=48-95
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/concolic/evaluator.ml;lines=324
- https://archive.softwareheritage.org/swh:1:cnt:26396b1f23ecffce5c8f579c6f227b16fae20f7a;origin=
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src-test/concolic/test_concolic.ml;lines=13
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/src/concolic/symbolic_session.ml;lines=288
- https://archive.softwareheritage.org/swh:1:cnt:a8776bcbcd5da0f645b952dfb8a316875422db0e;origin=
- https://github.com/JHU-PL-Lab/jaylang;visit=swh:1:snp:d10322f66a3531ab7251120395770910fe5980dd;anchor=swh:1:rev:54ef2e63cefcaecab809bf1fe73ff5e1795e6f29;path=/benchmark/concolic/cbenchmark.ml;lines=62-118