Verification of a DPLL Transition System in Rocq

Imaginez un monde où les ordinateurs jouent constamment à un jeu de « Vrai ou Faux » à enjeux élevés. Dans ce jeu, l'ordinateur reçoit un nœud géant et emmêlé d'énoncés logiques — comme une recette qui dirait : « Si vous ajoutez du sucre, vous devez aussi ajouter de la farine, mais si vous ajoutez de la farine, vous ne pouvez pas ajouter de sel. » L'objectif est de trouver un moyen de suivre la recette sans enfreindre aucune règle. C'est le problème de la satisfaisabilité (SAT). C'est l'équivalent numérique de tenter de faire entrer un million de pièces de puzzle différentes dans une boîte où certaines pièces sont rouges, d'autres sont bleues, et les instructions disent : « Pas de rouge à côté du bleu. »

Pourquoi est-ce important ? Parce qu'il ne s'agit pas seulement d'un puzzle logique ; c'est le moteur derrière presque tout ce qui est complexe en informatique. De la conception de micropuces à la preuve qu'un théorème mathématique est vrai, les ordinateurs utilisent des solveurs SAT pour naviguer dans ces labyrinthes logiques massifs. Mais voici le hic : ces solveurs sont incroyablement complexes. Si un minuscule bug se cache dans le code, l'ordinateur pourrait vous affirmer avec assurance qu'une preuve est valide alors qu'elle est en fait absurde. C'est pourquoi les mathématiciens et les informaticiens sont obsédés par la vérification formelle. Considérez cela comme la construction d'un filet de sécurité spécial, ultra-strict et incassable. Au lieu de simplement espérer que l'ordinateur fonctionne, ils utilisent un type spécial de « microscope mathématique » (appelé assistant de preuve) pour vérifier chaque étape de la logique, garantissant que la machine ne puisse jamais mentir sur la réponse.

La grande aventure du papier : Construire une machine logique digne de confiance

Dans cet article, Julia Dijkstra et Benedikt Ahrens font un pas de géant vers la création de ces machines logiques dignes de confiance. Ils n'ont pas seulement écrit un programme ; ils ont construit un squelette mathématiquement prouvé d'une méthode de résolution logique célèbre appelée DPLL (Davis-Putnam-Logemann-Loveland) à l'intérieur d'un outil appelé Rocq.

Considérez la méthode DPLL non pas comme un robot rigide suivant un script, mais comme un jeu de « Changement d'état ». Imaginez un détective essayant de résoudre un mystère. Le détective commence avec un carnet vide (sans indices). Il possède un ensemble de règles pour mettre à jour son carnet :

1. La règle du « Oh, je vois ! » (Propagation d'unité) : Si un indice dit « Le majordome l'a fait OU la domestique l'a fait », et que le détective sait déjà que la domestique est innocente, le carnet doit se mettre à jour pour dire « Le majordome l'a fait ». Le détective n'a pas le choix, la logique impose le mouvement.
2. La règle de la « Pure supposition » (Littéral pur) : Si le détective voit un indice concernant « Le jardinier » mais ne voit jamais d'indice sur le fait que « Le jardinier ne l'a pas fait », il peut supposer en toute sécurité que le jardinier est impliqué sans crainte de contradiction.
3. La règle de la « Bifurcation » (Décision) : Si le détective est bloqué, il choisit un indice au hasard (comme « Le majordome l'a fait ») et l'inscrit comme une décision. C'est une fourche dans le chemin.
4. La règle du « Oups, mauvais tournant » (Backtrack/Retour en arrière) : Si le détective inscrit une décision et trouve plus tard une contradiction (un indice qui dit « Le majordome ne l'a pas fait »), il doit effacer tout ce qui s'est passé après cette décision, inverser la décision (maintenant le majordome ne l'a pas fait) et réessayer.
5. La règle du « Fin de partie » (Échec) : S'il efface tout, inverse la dernière décision, et rencontre toujours une contradiction, la partie est terminée. Le mystère est insoluble.

La principale réussite des auteurs est d'avoir pris tout ce jeu et de l'avoir consigné dans un langage que l'assistant de preuve Rocq peut lire et vérifier. Ils n'ont pas seulement dit : « Cela semble correct. » Ils ont prouvé trois choses massives :

• Correctness (Correction) : Si le jeu se termine par une solution, cette solution est définitivement réelle. L'ordinateur ne va pas halluciner un modèle.
• Completeness (Complétude) : Si une solution existe, le jeu trouvera la solution. L'ordinateur ne restera pas bloqué ou n'abandonnera pas quand il ne le devrait pas.
• Termination (Terminaison) : Le jeu ne tournera jamais indéfiniment. Il est mathématiquement garanti de s'arrêter, soit avec une solution, soit avec un « Fin de partie ».

Ajouter un nouveau tour de magie : La règle « Pure »

L'une des contributions intéressantes de l'article est qu'ils ont ajouté une règle spécifique à leur jeu que certaines versions précédentes de cette théorie avaient omise : la Règle du Littéral Pur. Dans l'analogie du détective, c'est le moment où le détective réalise : « Hé, je n'ai jamais vu de preuve contre le jardinier, donc je vais simplement supposer que le jardinier est le coupable. » Les auteurs ont prouvé que l'ajout de cette règle rend le jeu plus rapide sans briser les garanties de sécurité. Ils ont montré que même avec ce raccourci supplémentaire, la logique reste parfaitement étanche.

De la théorie à un vrai (mais simple) robot

Après avoir prouvé que les règles du jeu fonctionnent parfaitement en théorie, les auteurs se sont demandé : « Pouvons-nous réellement construire un robot qui joue à ce jeu ? » Ils ont créé une stratégie — un ensemble d'instructions pour le détective sur le choix de la prochaine règle à utiliser. Ils ont construit une version concrète de cette stratégie dans Rocq, puis ont utilisé un outil magique appelé extraction pour transformer leur preuve mathématique en un véritable programme informatique écrit en OCaml.

Ils ont testé ce nouveau robot sur des puzzles simples. Ça a fonctionné ! Il a résolu des problèmes correctement, y compris un puzzle appelé zebra.cnf avec 155 variables et 1 135 clauses. Cependant, les auteurs sont très honnêtes quant aux limites de leur robot. C'est comme une voiture miniature de démonstration : elle roule parfaitement et prouve que le moteur fonctionne, mais ce n'est pas encore une voiture de Formule 1. Elle est lente car elle utilise des listes simples pour mémoriser les indices, alors que les voitures de course du monde réel utilisent une mémoire à haute vitesse. Les auteurs admettent que cette version n'est pas prête à battre les géants industriels utilisés par les entreprises aujourd'hui, mais c'est un noyau vérifié. C'est une petite fondation incassable sur laquelle des solveurs futurs, plus rapides et plus intelligents, peuvent être bâtis.

Ce que cela signifie pour l'avenir

L'article ne prétend pas avoir résolu le problème de la création du solveur SAT le plus rapide du monde. À la place, il prétend avoir construit le plan le plus sûr possible. En prouvant les règles abstraites dans Rocq, ils ont créé un « noyau de confiance ». Les futurs chercheurs pourront désormais prendre ce plan et y ajouter les fonctionnalités sophistées des solveurs modernes — comme « l'apprentissage par l'erreur » (apprentissage de clauses) ou le « saut de plusieurs étapes en arrière » (backtracking non chronologique) — avec la certitude que la logique sous-jacente est toujours saine.

En résumé, Dijkstra et Ahrens n'ont pas seulement construit une meilleure voiture ; ils ont construit le plan d'une voiture qui ne peut jamais s'écraser, prouvant que la logique derrière les roues est mathématiquement parfaite. C'est une petite étape vérifiée qui ouvre la voie à des machines logiques beaucoup plus grandes, plus complexes et dignes de confiance à l'avenir.