Execution models for Constraint Programming: kernel language design through semantics equivalence.

PhD Thesis, Thierry Martinez.

Download (PDF). Abstract. Résumé en français. (The defense has been held in English.)

Defense feedback

Some photos taken during the defense.

Recipes:

Defense at 4pm, Seminar at 2pm, Pot de thèse! at 7pm.

Université Paris Diderot, Halle aux farines. (Google Maps)

Salle des thèses, Hall F, 5th floor (access through hall E, allée paire, lift F).

9 esplanade Pierre Vidal-Naquet 75013 Paris / 10 rue Françoise Dolto 75013 Paris.

M14/RER C, Bibliothèque François Mitterrand (vianavigo).

14.00–15.45 Lifeware Public Seminar.

More informations on the seminar web page.

14.00–14.45 Jean Goubault-Larrecq, ENS Cachan Categorical models of Multiplicative-Additive Linear Logic
14.45–15.15 Frank Valencia, LIX Palaiseau Algebraic Structures for Space/Belief and Extrusion/Utterances
15.15–15.45 Tom Schrijvers, KUL Leuven From monoids to near-semirings: the essence of MonadPlus and Alternative

16.00 Defense.

19.00 Pot de thèse!

Thesis committee.

M. Roberto Di Cosmo Professeur des universités
Université Paris 7
Président du jury
M. François Fages Directeur de recherche
Inria
Directeur de thèse
M. Tom Schrijvers Professeur
Katholieke Universiteit Leuven
Rapporteur
M. Maurizio Gabbrielli Professeur
Universita’ di Bologna
Rapporteur
M. Jean Goubault-Larrecq Professeur
École normale supérieure de Cachan
Examinateur
M. Frank Valencia Chargé de recherche
CNRS
Examinateur

Abstract.

Logic programming and constraint programming are two declarative programming paradigms which rely on the identification of programs to theories, and programming to modeling. Execution models result from the operational interpretation of logical provability in logic programming, and of constraint propagation in constraint programming. However, the control of execution is crucial for the practicability of these schemes and extra-logical traits are thus added in those programming systems, with the classical slogans "logic program = logical theory + control", "constraint program = constraint model + search".

This thesis investigates execution models in which control and search can be shifted into the logic or the constraint model, while preserving the semantics. The three parts of the thesis correspond to the three semantics equivalence that are showed: the first between two committed-choice forward-chaining logic languages, the second between constraint logic programs and constraint models, and the third between guard semantics in angelic settings. Each of these equivalence is constructive in the sense that there exists an encoding that enables the compilation from one of the paradigm to the other.

First, we show that simple program transformations exist back and forth between Constraint Handling Rules (CHR) and Linear Logic Concurrent Constraint (LLCC) languages, making them semantically equivalent even if syntactically different, which closes the question of implementing a committed-choice semantics for LLCC by using CHR as kernel language.

Secondly, we show that a wide variety of search procedures can be internalized in the constraint model with a fixed enumeration strategy. Transforming search procedures into constraint satisfaction problems presents several advantages: (1) it makes search strategies declarative and modeled as constraint satisfaction problems; (2) it makes it possible to express search strategies in existing front-end modeling languages without any extension; (3) it opens up constraint propagation algorithms to search constraints and to the implementation of novel search procedures based on constraint propagation. This is illustrated with the design of the ClpZinc modeling language, with an angelic interpretation of Horn clauses which allows compilation to a reification-based constraint kernel.

Finally, in concurrent constraint logic programming, committed-choice semantics create a hierarchy of non-equivalent semantics axed on the expressive power of synchronization mechanism. We show that the hierarchy of guard semantics collapses with angelic semantics, allowing the most primitive synchronization mechanism to encode all the others. The main consequence of this collapse is the identification of a kernel language, with a primitive synchronization mechanism and an elementary constraint system which are sufficient to reconstruct the other forms of synchronizations and other constraint systems as modules, in the software engineering sense.

Résumé en français.

(The defense will be held in English.)

La programmation logique et la programmation par contraintes sont deux paradigmes de programmation déclaratifs qui reposent sur l'identification entre programmes et théories logiques d'une part, et entre programmation et modélisation d'autre part. Les modèles d'exécution résultent de l'interprétation opérationnelle de la prouvabilité logique en programmation logique, et de la propagation des contraintes en programmation par contraintes. Cependant, le contrôle de l'exécution est crucial pour rendre ces paradigmes utilisables en pratique et des traits extra-logiques sont ajoutés à cette fin dans ces systèmes de programmations, avec les slogans classiques « programmation logique = théorie logique + contrôle » et « programmation par contraintes = modèle de contraintes + recherche ».

Cette thèse explore des modèles d’exécution au sein desquels le contrôle et la recherche peuvent être remontés selon le contexte dans la logique ou dans le modèle de contraintes, tout en préservant la sémantique. Les trois parties de cette thèse correspondent aux trois équivalences sémantiques démontrées : la première entre deux langages logiques en chaînage avant avec choix commis, la seconde entre programmes logiques avec contraintes et modèles de contraintes, la troisière entre les sémantiques des gardes dans un cadre angélique. Chacune de ces équivalences est constructive au sens qu’il existe un codage permettant la compilation depuis l’un des paradigmes dans l’autre.

Premièrement, nous montrons que des transformations simples de programmes existent dans les deux sens entre les langages Constraint Handling Rules (CHR) et Linear Logic Concurrent Constraint (LLCC), les rendant sémantiquement équivalents bien que syntaxiquement différents, ce qui ferme la question de l'implémentation d'une sémantique de choix commis pour LLCC, en utilisant CHR comme langage noyau.

Deuxièmement, nous montrons qu'une large variété de procédures de recherche peut être internalisée dans le modèle de contraintes avec une stratégie d'énumération fixe. La transformation de procédures de recherche en problèmes de satisfaction de contraintes présente plusieurs avantages : (1) cela rend les stratégies de recherche déclaratives et modélisables au même titre que les problèmes de satisfaction de contraintes ; (2) cela rend possible l'expression de stratégies de recherche dans les langages de modélisation existants, sans recourir à des extensions ; (3) cela ouvre la voie à des algorithmes de propagation de contraintes pour les contraintes de recherche et à l'implémentation de nouvelles procédures de recherche basées sur la propagation de contraintes. Ceci est illustré par la conception du langage de modélisation ClpZinc, avec une interprétation angélique des clauses de Horn qui permet la compilation vers un noyau de contraintes basé sur la réification.

Pour finir, en programmation concurrente avec contraintes, la sémantique par choix commis crée une hiérarchie de sémantiques non équivalentes axée sur la puissance d'expression des mécanismes de synchronisation. Nous montrons que la hiérarchie des gardes s'effondre avec la sémantique angélique, permettant au plus primitif des mécanismes de synchronisation de coder tous les autres. La principale conséquence de cet effondrement est l'identification d'un langage noyau, avec un mécanisme de synchronisation primitif et un système de contraintes élémentaires qui sont suffisants pour reconstruire les autres formes de synchronisation et les autres systèmes de contraintes comme modules, au sens de l'ingénierie logicielle.