Mémoire de licence sur la programmation par contraintes

Aperçu

Étudiant de premier cycle en informatique, j'ai mené une recherche partie d'une question pratique : lorsqu'un simulateur accumule un grand nombre de conditions possibles, comment l'amener à cesser de réexaminer celles qui ne peuvent plus se produire ? J'ai conçu, implémenté et évalué pour HydLa une méthode qui s'appuie sur la direction dans laquelle une valeur évolue afin de retirer de la recherche les conditions devenues inutiles. Sur le modèle de référence, la durée totale de simulation est tombée à environ la moitié.

Ce travail est l'une des premières fondations de ma philosophie de design. La programmation par contraintes m'a appris que les résultats complexes n'ont pas toujours besoin d'être spécifiés directement : ils peuvent émerger d'un espace de règles, de priorités et de limites défini avec soin. Cette manière de penser soutient aujourd'hui ma façon de concevoir à partir de contraintes à l'ère de l'IA — concevoir les conditions à l'intérieur desquelles un système génératif est libre d'agir.

Résumé

HydLa est un langage de modélisation pour les systèmes hybrides : les systèmes où changement continu et événements discrets interagissent. Sa conception fondée sur les contraintes permet de décrire ces systèmes de façon concise et de les simuler avec une grande précision. En contrepartie, dans un grand modèle, le simulateur peut continuer à vérifier un très grand nombre de règles conditionnelles, alors même que certaines n'ont plus lieu d'être.

Cette recherche a proposé de réduire dynamiquement ces contraintes gardées. En reconnaissant un comportement monotone — une valeur qui continue d'évoluer dans un seul sens —, le simulateur peut établir que certaines gardes ne deviendront jamais vraies par la suite et cesser sans risque de les vérifier. L'approche s'est révélée particulièrement efficace sur un modèle comportant de nombreux objets gardés de la même manière, où le temps d'exécution mesuré est descendu à environ la moitié de l'original.

1. Introduction

Un système hybride associe un comportement continu à des événements discrets. Une balle qui rebondit en est un exemple simple : sa position et sa vitesse changent continûment tant qu'elle est en l'air, mais l'instant où elle touche une surface crée un événement discret qui change sa direction. Thermostats, véhicules et robots contiennent tous des versions plus lourdes de conséquences du même mélange.

HydLa permet de décrire ces systèmes par des contraintes mathématiques et logiques plutôt que d'écrire une unique séquence procédurale. Son simulateur, HyLaGI, effectue des calculs symboliques sans erreur d'arrondi et sait travailler avec des paramètres incertains. Cette expressivité crée toutefois un problème d'échelle : lorsqu'un modèle contient beaucoup de règles qui ne s'activent que sous certaines conditions, le simulateur doit sans cesse se demander si chacune de ces conditions pourrait être la prochaine à se réaliser.

2. Les contraintes gardées dans la simulation

Une contrainte gardée est une règle qui ne devient active que lorsque sa condition de garde est satisfaite. Dans le modèle de référence ci-dessus, chaque segment de la surface a sa propre règle : si la balle atteint la hauteur zéro alors que sa position horizontale se trouve dans ce segment, la règle du rebond s'applique. Découper la surface en davantage de morceaux donne donc au simulateur davantage de gardes à inspecter.

L'expérience a fait varier le nombre de segments de 10 à 200. Le simulateur d'origine ralentissait à peu près comme le carré de ce nombre. La portée dépasse l'exemple jouet : un modèle plus grand peut représenter de nombreux objets physiques, zones de contact ou événements possibles exactement sous cette forme gardée.

3. Localisation du goulet d'étranglement

Le profilage a montré que le ralentissement n'était pas réparti uniformément dans le simulateur. Avec 100 segments de surface, 96 % du temps d'exécution mesuré passait dans FindMinTime, l'opération qui recherche le prochain événement possible le plus proche. Elle réévaluait sans cesse les gardes de toutes les contraintes candidates.

Ce résultat a rendu la cible de l'optimisation précise : réduire le nombre de gardes que FindMinTime doit examiner, tout en préservant exactement le même comportement simulé.

4. Réduction des contraintes gardées

Imaginez une balle qui descend un escalier en rebondissant. Dès que la balle a dépassé une marche et continue d'avancer, cette marche ne peut plus l'affecter. Celui qui regarde le schéma écarte immédiatement les marches situées derrière la balle ; l'algorithme d'origine continuait de les vérifier une à une.

Le point difficile est de prouver qu'une garde écartée ne sera plus nécessaire par la suite. La retirer au seul motif qu'elle est fausse à présent pourrait produire silencieusement un résultat erroné si elle redevenait vraie. La proposition s'appuie donc sur la monotonie : peut-on garantir qu'une variable continuera de croître, ou continuera de décroître, sur un intervalle de temps ?

4.1 Approche de la monotonie uniforme

La première approche s'applique lorsqu'une variable évolue dans un seul sens pendant toute la simulation. Dans le modèle à surface découpée, la position horizontale de la balle croît toujours. Une fois un segment dépassé, la condition de ce segment ne peut plus jamais être satisfaite. Les techniques de vérification de modèles permettent d'établir cette propriété avant la simulation, si bien que les gardes devenues inutiles peuvent être retirées sans risque au fil de l'exécution.

4.2 Approche de la monotonie alternée

Beaucoup de systèmes réels n'évoluent pas indéfiniment dans un seul sens. Une variable peut croître, se retourner, puis décroître. L'article a donc esquissé une seconde approche : partir d'un sens supposé, surveiller cette hypothèse par des assertions, et reprendre la logique de réduction à partir du point où le sens change. Les gardes retirées pour un intervalle monotone sont rétablies au début du suivant.

5. Résultats expérimentaux

J'ai implémenté l'approche de la monotonie uniforme et l'ai évaluée sur le modèle à surface découpée. L'algorithme d'origine comme celui proposé mettaient toujours plus de temps à mesure que le nombre de segments augmentait, mais la version proposée effectuait systématiquement moins de travail. En comparant les courbes ajustées, le coefficient dominant est passé de 1,1463 à 0,6083 ; pour ce cas de référence, la durée totale de simulation a été à peu près divisée par deux.

Ce résultat n'affirme pas que tout modèle HydLa devient deux fois plus rapide. Il montre où la méthode aide : sur les modèles comportant beaucoup d'objets gardés et un sens de variation démontrable, où les gardes deviennent définitivement sans objet en cours d'exécution.

6. Conclusion et perspectives

La recherche a montré que la connaissance du modèle — et pas seulement un calcul de bas niveau plus rapide — peut rendre une simulation plus efficace. En se servant de la monotonie pour reconnaître quelles possibilités sont devenues impossibles, HyLaGI peut réduire son ensemble de contraintes actives sans changer le résultat.

L'expérience implémentée portait sur la monotonie uniforme. L'article a laissé deux directions pour la suite : évaluer la méthode par assertions dans le cas d'un comportement alterné, et utiliser d'autres invariants que la monotonie pour repérer d'autres contraintes que l'on peut retirer sans risque.