La programmation par contraintes a été motivée à l'origine par des problèmes concrets difficiles avec une forte composante combinatoire. Historiquement, elle hérite de plusieurs domaines, en particulier de l'intelligence artificielle et de la recherche opérationnelle. Son objectif est de permettre une modélisation plus facile des problèmes en utilisant un langage proche de l'utilisateur et en séparant clairement les phases de spécification et de réalisation. L'idée est de réduire l'effort de programmation et de laisser l'ordinateur envisager tous les cas induits par la modélisation pour ne retenir que ceux qui conviennent, c'est-à-dire qui satisfont aux contraintes spécifiées.
La programmation par contraintes n'a pu se développer qu'à partir du moment où les problèmes pouvaient être traités dans un temps raisonnable, ce qui est du en grande partie à la puissance des machines actuelles. A partir de là, de nombreux domaines d'application se sont intéressés à la notion de contraintes et notamment le domaine des interfaces graphiques interactives.
La deuxième section de ce chapitre présente quelques définitions sur les contraintes. La troisième section montre quels sont les avantages de la programmation par contraintes et présente quelques uns de ses domaines d'application. La quatrième section détaille un domaine particulier qui est celui des interfaces graphiques interactives.
[Table des matières]
2.1 Contrainte
Une contrainte exprime une relation qui porte sur une ou plusieurs variables. Par exemple, dire que la T.V.A. d'un article est égale au prix hors taxe multiplié par 20,6% est une contrainte. Spécifier que deux objets ont la même couleur est également une contrainte.
Résoudre ou satisfaire une contrainte consiste à trouver, pour chaque variable, une affectation de valeur qui satisfait la condition définie par celle-ci. Normalement une contrainte doit rester maintenue tant qu'elle est active, même si l'une ou l'autre des variables qui la compose est modifiée.
[Table des matières]
2.2 Système de contraintes
Un système de contraintes consiste en un ensemble de variables et en un ensemble de contraintes qui limite les combinaisons de valeurs pour ces variables. Plus formellement, il est défini par un triplé {V, D, C} où :
foralli in [1, n], Di est le domaine des valeurs possibles pour la variable Vi,
Une solution pour un tel système est une instanciation des variables de V qui satisfait toutes les contraintes de C.
[Table des matières]
2.3 Représentation graphique
Un système de contraintes est communément représenté par un graphe non orienté. Le graphe de la Fig 1 correspond au système {C1:C=A+B, C2:E=C+D et C3:F=B}. Les cercles représentent les variables et les carrés noirs les contraintes. Les arêtes symbolisent les liens variables-contraintes c'est-à dire, l'appartenance d'une variable à une contrainte. Un tel graphe est appelé graphe de contraintes du système.
Fig 1. Graphe de contraintes
[Table des matières]
2.4 Satisfaction de contraintes ou maintien de solution
Etant donné un système de contraintes, nous pouvons identifier deux problèmes de résolution différents : la satisfaction de contraintes et le maintien de solution .
Dans un problème de satisfaction de contraintes, l'objectif est d'assurer la cohérence d'un système de contraintes. La résolution d'un tel problème consiste à trouver une ou toutes les combinaisons de valeurs des variables qui permettent de satisfaire l'ensemble des contraintes.
Dans un problème de maintien de solution, l'objectif est de rétablir la cohérence d'un système de contraintes à partir d'une solution courante et d'une perturbation de cette solution. Cette perturbation peut être provoquée soit par la modification de la valeur d'une variable, soit par l'ajout ou le retrait d'une contrainte.
Cette classification correspond à celle que l'on trouve dans certains articles sous le nom de refinement model ou perturbation model , .
[Table des matières]
3.1 Caractéristiques
La programmation par contraintes repose sur une approche déclarative des problèmes plutôt que sur une approche impérative. L'utilisateur décrit le résultat à obtenir sans préciser la façon de l'obtenir.
L'utilisation de contraintes offre plusieurs avantages notamment celui de fournir un moyen intuitif pour décrire des relations entre des objets, comme par exemple spécifier "A avant B" pour exprimer qu'une tâche A précède une autre tâche B. Elle permet également de simplifier la phase de programmation. En effet, dans une approche impérative, le programmeur doit à la fois spécifier les relations mises en jeu et écrire le code nécessaire à leur maintien durant la phase d'exécution. Dans une approche basée sur les contraintes, le programmeur doit seulement exprimer les relations entre les objets, sans tenir compte de la manière dont elles seront maintenues à l'exécution. Cette responsabilité incombe à un programme spécifique, le résolveur de contraintes qui assure automatiquement le maintien de l'ensemble des contraintes spécifiées (Fig 2 ). Cela décharge le programmeur d'une tâche parfois fastidieuse et très souvent source d'erreurs. De plus cela permet d'avoir des programmes plus compacts et plus faciles à maintenir.
Fig 2. Structure d'un programme à base de contraintes
La programmation par contraintes présente néanmoins certains inconvénients . D'abord, l'évaluation du temps d'exécution d'un programme peut être dépendante du problème et il n'est pas possible d'énoncer des règles claires concernant les performances temporelles, ce qui s'accommode mal avec les exigences de certains projets. De plus, un problème induit par la programmation par contraintes réside dans le fait que le niveau requis pour programmer efficacement une application à base de contraintes est supérieur à celui exigé pour une qualité comparable en programmation "traditionnelle".
[Table des matières]
3.2 Applications
La programmation par contraintes est d'ores et déjà utilisée par de nombreux types d'applications industrielles et professionnelles parmi lesquelles nous pouvons citer :
Il est également un type d'applications privilégié pour l'utilisation des contraintes qui est celui des interfaces graphiques interactives.
Dans les interfaces graphiques interactives, il est naturel de parler d'objets et d'utiliser des relations de positionnement entre eux (au-dessus-de, aligné-avec, etc.). Cette approche peut être spécifiée comme un système de contraintes où les objets représentent les variables et les relations entre objets les contraintes du système. La résolution d'un tel système détermine alors la position des objets dans l'image affichée.
Les contraintes exprimées dans ces interfaces se divisent en deux catégories principales :
[Table des matières]
4.1 Besoins spécifiques
Dans la pratique, une interface graphique interactive exige plus que la seule détermination de coordonnées d'objets et d'autres besoins spécifiques sont à prendre en compte. Parmi ceux-ci nous pouvons citer :
Une qualité première de toute interface interactive réside dans sa capacité à répondre rapidement aux actions des utilisateurs. Une lenteur excessive les amènera à répéter inutilement leurs commandes ou à se détourner d'une application jugée inefficace. Le système de contraintes doit donc travailler en temps réel ce qui fait de l'efficacité du résolveur utilisé un facteur déterminant.
Une notion importante des interfaces interactives est la notion de retour d'informations. Il est important que toute action de l'utilisateur conduise à une réponse de la part du système et que la même action conduise toujours à la même réponse. Lorsque le système est confronté à une impossibilité ou une erreur, la réponse doit être suffisamment explicite. Dans certains cas, il est même préférable de donner une solution la "moins fausse" possible plutôt que de n'en donner aucune. Le même problème existe lorsque le système trouve un grand nombre de solutions, voir une infinité. La réponse ne peut consister en l'énumération de chacune et il est demandé au système d'en choisir une.
Une bonne interface ne surprend pas les utilisateurs par des réponses inattendues. Il est important que les réponses proposées soient intuitives et déforment le moins possible la solution courante pour éviter de dérouter les utilisateurs. Ce problème est d'autant plus sensible en présence de solutions multiples où le système doit choisir une "bonne solution". Un principe souvent retenu est celui du moindre étonnement (least astonishment) où la bonne solution est celle qui minimise le déplacement des objets.
[Table des matières]
4.2 Solutions
Les besoins des interfaces graphiques interactives en matière de résolution de contraintes se situent clairement dans un problème de maintien de solution. En effet, elles doivent être capables de fournir une solution à un système de contraintes en réaction à une perturbation de ce système, cette perturbation pouvant être provoquée soit par la création ou la suppression d'objets et de contraintes, soit par la modification du placement des objets. De plus, la réponse obtenue doit être la plus rapide possible, ce qui influe sur les techniques utilisées, et doit modifier le moins possible la solution courante.
Les travaux concernant les contraintes dans ces interfaces ont été à l'origine du développement de nouvelles techniques de résolution et de nouveaux types de résolveurs, qui feront l'objet du chapitre suivant. Dans le suite de ce chapitre, nous allons présenter quelques exemples d'applications graphiques à base de contraintes.
[Table des matières]
4.3 Exemples d'applications graphiques à base de contraintes
Historiquement, de nombreux travaux sur les interfaces graphiques interactives ont utilisé des contraintes, mais ces travaux sont encore du domaine de la recherche et aucune application commerciale n'intègre encore complètement la technique de programmation par contraintes. Dans la suite de cette section, nous allons exposer quelques interfaces graphiques expérimentales à base de contraintes.
SketchPad, développé par Ivan Sutherland dans le cadre de sa thèse au M.I.T. en 1963 est le pionnier de l'utilisation des contraintes. Il est destiné à la conception interactive de figures géométriques complexes. L'utilisateur dispose d'un ensemble d'objets graphiques de base (des points, des lignes ou des cercles) et d'un certain nombre de contraintes prédéfinies pouvant être appliquées sur ces objets. On peut ainsi forcer une ligne à être verticale, rendre deux lignes parallèles ou d'égale valeur ou bien contraindre un point à figurer sur une ligne donnée. Pour obtenir un hexagone régulier par exemple, l'utilisateur dessine un polygone quelconque à six côtés puis contraint les sommets à rester sur un cercle et à être à égale distance. Tout dessin peut ensuite être utilisé comme objet primitif en le transformant en macro.
La méthode de résolution utilisée par SketchPad est basée sur une technique de propagation locale par degré de liberté (section 0.0). Celle-ci s'effectue sur le graphe de contraintes orienté qui a été préalablement trié pour déterminer l'ordre d'évaluation des variables. Cette méthode de résolution possède deux inconvénients majeurs. D'abord, l'ensemble des variables est réévalué lors de chaque édition du dessin. Ensuite, lorsque la structure du dessin est modifiée par l'ajout ou la suppression d'un objet élémentaire, il est nécessaire de reconsidérer toutes les contraintes du graphe pour déterminer le nouvel ordre d'évaluation.
De nombreux travaux sur les contraintes dans les interfaces graphiques se sont inspirés de SketchPad dont les idées, très en avance sur leur temps ne sont pas encore obsolètes plus de trente ans après.
ThingLab II est un système de programmation interactif orienté objets à base de contraintes écrit en Smalltalk 80 . Comme son nom le suggère, ThingLab II est le descendant de ThingLab , mais son objectif est différent. Le système ThingLab développait et appliquait des techniques de programmation par contraintes dans le cadre de simulations physiques interactives comme par exemple pour les circuits électriques ou les liens mécaniques. Le système ThingLab II s'intéresse plus particulièrement à l'application de ces techniques pour la construction d'interfaces utilisateurs. Pour cela, il offre de bonnes performances, un mécanisme d'encapsulation et une séparation claire entre les contraintes et les parties impératives de Smalltalk 80.
Dans la plupart des interfaces graphiques interactives, les contraintes évoluent graduellement et fréquemment. ThingLab II exploite cette particularité en utilisant un résolveur de contraintes de nature incrémentale qui ne réévalue que les variables nécessaires, c'est-à-dire qu'il ne prend en compte que les contraintes qui ont été modifiées à la suite d'une interaction de l'utilisateur. Cet algorithme, appelé DeltaBlue (section 0) fut l'un des premiers à utiliser une technique de propagation locale par valeurs (section 0.0) et a été à l'origine de nombreuses recherches depuis sa diffusion.
Garnet a été développé à l'université de Carneggie-Mellon sous la direction de Brad Myers . C'est un environnement de développement d'interfaces utilisateur basé sur les contraintes. Il est divisé en en deux parties principales : la boîte à outils et les outils. La boîte à outils est composée d'un système d'objets (KR), d'un système de contraintes et d'un système graphique (Opal). Dans la partie outils sont réunis un générateur d'interfaces (Lapidary), un système de création de boîtes de dialogue et un tableur (C32).
Dans Garnet, les objets sont composés d'un ensemble de slots non typés. Garnet étant écrit en Lisp, un slot peut être n'importe quel objet Lisp (variables, champs, etc.). Un slot contient une valeur et peut posséder une expression associée, ou formule, qui calcule la valeur du slot en fonction de la valeur d'autres slots. Lorsque la valeur d'un slot est modifiée, alors un résolveur maintien les formules concernées en évaluant le code contenu dans ces dernières.
Les objets sont construits à partir d'autres objets selon le modèle de prototypes. La Fig 3 montre la définition de trois rectangles avec des formules associées pour certains de leurs slots. Les formules référencent la valeur d'autres slots par la fonction gv (get value). Dans l'objet rect-proto, la valeur du slot :right est calculée à partir de la valeur des slots :left et :width du même objet. Dans l'objet rect2, la valeur du slot :left est égale à la valeur du slot :left de l'objet référencé par le slot :main (l'objet rect1 dans notre exemple). Dans ce cas, la formule contraint l'objet rect2 à être aligné à gauche avec l'objet rect1. Si le slot :left de l'objet rect1 est modifié, alors la formule associée au slot :left de l'objet rect2 est recalculée.
Fig 3. Objets et contraintes en Garnet
Puisque le système d'objets est basé sur un modèle de prototype, chaque objet peut être utilisé comme parent d'autres objets. Le système de contraintes est alors intégré avec le mécanisme d'héritage, autorisant les formules à être héritées de la même manière que la valeur des slots. Dans la Fig 3 , la formule associée avec le slot :right de l'objet rect-proto est définie une seule fois puis héritée par les autres objets. Les formules héritées référencent les slots internes à l'objet. Ainsi, la formule héritée par le slot :right de l'objet rect1 référence les slots :left et :width de l'objet rect1, pas ceux de l'objet rect-proto. Dans ce cas, la valeur du slot :width de l'objet rec-proto est également héritée par l'objet rect1.
Kaleidoscope est un langage intégrant la programmation classique impérative et la programmation déclarative basée sur les contraintes. Il a été développé en partant du constat que dans une interface graphique, certaines parties, comme la définition et le maintien automatique de relations sont plus facilement décrites en utilisant des contraintes alors que d'autres, comme le séquencement d'opérations le sont plus efficacement par des techniques de programmation impérative.
Considérons l'exemple de la Fig 4 où un dispositif graphique permet à un utilisateur de faire varier le niveau de mercure d'un thermomètre à l'aide de la souris. La Fig 5 présente deux fragments de pseudo-code pour gérer cette spécification. La partie de gauche utilise uniquement des instructions de programmation impérative et impose au programmeur de tester les changements d'états et le cas échéant de redessiner les rectangles. La partie de droite combine les instructions impératives et les contraintes. Les contraintes (1) à (6) sont constamment maintenues alors que la contrainte (7) ne doit être satisfaite que si la condition spécifiée est vraie. Les instructions impératives comme le TantQue sont utilisées pour contrôler l'exécution du programme, en particulier pour spécifier quand certaines contraintes doivent être maintenues.
Fig 4. Exemple de variation du niveau de mercure d'un thermomètre
Fig 5. Deux pseudo-code différents pour gérer la variation du mercure
Le système de contraintes utilisé dans Kaleidoscope est hérité de ThingLab II présenté plus haut. Pour la résolution des contraintes, il utilise également un résolveur de nature incrémentale basé sur la technique de propagation locale par valeurs. Ce résolveur, appelé SkyBlue (section 0) est plus récent et plus général que le résolveur DeltaBlue utilisé dans ThingLab II.
L'objectif du projet Wand développé par l'université de Saskatchewan est de fournir des outils pour la visualisation de l'exécution de logiciels et pour leur mise au point graphique , . L'application ICOLA (Incremental Constraint- based Object Layout Algorithm) représente la partie graphique du projet Wand. Elle permet de déterminer le placement d'objets graphiques dans une image sans qu'il soit nécessaire de préciser leurs positions absolues. Il suffit pour cela de déclarer ces objets et de définir des contraintes spécifiant leur positionnement relatif.
Définir une image dans ICOLA consiste à déclarer les objets de cette image et les contraintes de positionnement entre ces objets. Cette définition s'effectue par l'intermédiaire d'un langage spécifique appelé PDI (Picture Description for ICOLA). Pour déclarer un nouvel objet, il suffit de spécifier son nom et son type, choisi parmi un ensemble de types possibles : boîte, ellipse, point, ligne, triangle, arc, texte. Un exemple de déclaration est objet(nom_image, boîte). Chaque objet est alors représenté par son rectangle d'encombrement. Des fonctions permettent d'identifier les bords gauche, droit, haut et bas de ces rectangles. Par exemple, la fonction left(parent) désigne le bord gauche du rectangle associé à l'objet parent. Chaque image est associée à un objet spécial appelé racine. Tous les objets composant cette image sont automatiquement contenus dans celui-ci.
Les contraintes exprimées en PDI spécifient le positionnement relatif des objets à l'intérieur de l'image. Les principales contraintes sont : left_of, right_of, above, below, horizontal_distance, vertical_distance, aligned. La contrainte left_of [right(a), left(b)] spécifie qu'un objet a est à gauche d'un objet b, plus précisément que le bord droit de a est à gauche du bord gauche de b (Fig 6 ).
Fig 6. Exemple de contrainte dans ICOLA
PDI complète la définition d'une image en associant des attributs aux objets la composant. Certains de ces attributs comme color peuvent s'appliquer à n'importe quel objet, alors que d'autres comme font ne s'appliquent qu'à un type d'objet particulier, en l'occurrence les objets de type texte. L'objet racine possède un attribut particulier, default_distance qui spécifie la distance par défaut entre les objets.
A partir de la définition d'une image en PDI, les coordonnées absolues des objets sont déterminées pour générer l'image concrète et ce en respectant les contraintes spécifiées. Cette opération est effectuée par le résolveur de contraintes d'ICOLA. Celui-ci manipule un ensemble de variables et de contraintes. Les variables sont au nombre de quatre par objet et représentent la position de chacun des bords du rectangle associé par rapport à l'origine de l'objet racine. Les contraintes exprimées dans PDI sont traduites en formules linéaires. Ainsi la contrainte left_of [right(a), left(b)] s'exprime sous la forme aright + default_distance <= bleft. L'algorithme ICOLA est de nature incrémentale et utilise des techniques de résolution proches de celles employées par l'algorithme DeltaBlue. Sa particularité réside dans le traitement des systèmes sous-contraints, c'est-à-dire qui possèdent plusieurs solutions. Dans ce cas, ICOLA applique des heuristiques spécifiques afin de n'en produire qu'une seule.
Dans ce chapitre, nous avons présenté brièvement la programmation par contraintes, ses caractéristiques, ses avantages et quelques uns de ses domaines d'application. Nous avons insisté sur le domaine des interfaces graphiques interactives car certaines d'entre elles présentent une problématique relativement proche de la nôtre concernant le placement spatial des éléments dans Madeus.
Ces interfaces graphiques à base de contraintes reposent sur un problème de maintien de solution où le résolveur est chargé de trouver une nouvelle solution à un système de contraintes en réaction à une perturbation de ce système.
L'un des besoins principaux de ces interfaces réside dans leur rapidité à répondre à une action de l'utilisateur et donc dans les performances des techniques de résolution mises en oeuvre.
De nombreux travaux ont été menés pour améliorer les performances des résolveurs, lesquels représentent le point crucial de tout système de contraintes. Ces travaux ont abouti à la mise au point de nouvelles techniques de maintien de solution et notamment la technique par propagation locale utilisée dans les exemples présentés dans ce chapitre.
Le chapitre suivant propose une étude sur ces techniques et montre dans quelle mesure les résolveurs basés sur celles-ci peuvent être utilisés pour le problème du placement spatial dans Madeus.