ASP est un langage de programmation un peu particulier, à ne pas confondre avec l'Astronomical Society of the Pacific, le groupe de métal, ou l'ASP.NET. C'est ce genre de langage qui en bave des ronds de chapeaux pour additionner les éléments d'une liste, mais qui n'a besoin que de 6 lignes de code pour résoudre un sudoku.

Ceci est un tuto pour apprendre à le lire, l'écrire, et l'utiliser pour diverses tâches.

Au programme : faire le placement de table pour votre mariage, monter votre PC, résoudre des énigmes, des donjons de Zelda et des sudokus.

Après ce tuto, ASP vous resservira souvent, par exemple pour trouver les solutions des énigmes de votre tonton rigolo, choisir le meilleur hôtel, faire un GPS pour votre robot aspirateur, ou gagner du temps quand vous développez et avez besoin des résultats d'un algo complexe.

Introduction

Cet article est un tuto, qui se veut accessible, sur Answer Set Programming, un langage de programmation déclaratif implémentant la Programmation Par Contrainte, ou PPC (comme java implémente la POO et haskell la PF).

Pour ceux qui connaissent, il fera certainement penser à Prolog, puisque ces deux langages reposent sur les même concepts, bien qu'ils ne l'implémentent pas de la même manière.

L'objectif n'est pas seulement d'apprendre les bases en faisant joujou, mais de développer des programmes qui résolvent des problèmes de la vie réelle, éventuellement avec quelques lignes en plus pour pouvoir être réellement utilisés dans la vie de tous les jours.

Dans une certaine mesure, ce tuto s'adresse aussi à ceux qui n'ont jamais codé ; après tout, les langages logiques sont les meilleurs pour commencer :) (je fais un effort de simplification durant tout le tuto, justement pour permettre à des personnes n'ayant jamais codé de s'y intéresser)

Aussi, une grosse partie du tuto est théorique. Ce n'est peut-être pas très équilibré, surtout au début. Si ça ne vous motive pas, installez directement, et commencez à jouer avec l'introduction du langage.

Quêtes annexes

D'autres articles de ce blog à propos d'ASP s'intègrent dans ce tuto. Il s'agit, par référence aux jeux vidéos, de quêtes annexes optionnelles et indépendantes du reste. Une compréhension de base du langage est parfois nécessaire, donc n'allez sur les quêtes annexes qu'après avoir avancé un peu sur la quête principale (le présent tuto, donc).

• Jeux de logique, résolution d'énigmes logiques diverses, incluant l'énigme d'Einstein
• Encodings, où l'on parle d'espace de recherche et des coûts induits par certains encodings
• Logique temporelle, où l'on parle de représentation du temps et de la résolution de problèmes qui en utilise la notion
• Propagateurs, un moyen pour suivre, gérer et étendre le solving

Si vous voulez un aperçu de ce qui arrive, regardez les sources de cette page web ;)

Quelques liens préliminaires

Où l'on se demande pourquoi faire un tuto si c'est pour envoyer tout le monde voir ailleurs

Je conseille volontier la lecture parallèle d'un tuto existant ; ça aide toujours d'avoir plusieurs sources pour comprendre un concept.

Voici quelques liens :

• un dépôts de codes et d'exemple
• un tuto applicatif avec toute une démarche de construction d'un projet (PDF)
• un tuto qui passe très vite sur les bases (en anglais) (LIEN MORT: je cherche le contenu)

Les scripts utilisés ici sont disponibles sur le dépôt learning-ASP. Vous pouvez les télécharger, et même participer à leur développement si besoin.

Notez aussi que clingo, le groundeur/solveur que nous allons utiliser, est accompagné d'un manuel bien fournis, d'un nombre impressionnant d'exemples de tous types dans ses sources (j'insiste ; faites y un tour, il y a un exemple pour presque toute les fonctionalités du solveur), et d'une mailing list active où beaucoup de questions intéressantes sont posées. (il y a une autre mailing list pour les annonces des développeurs, typiquement les nouvelles versions du solveur)

Notez également que ce blog a déjà parlé d'ASP :

• Deponia et ASP : résoudre un puzzle avec ASP
• se-lang : définir des systèmes astrophysiques avec ASP

Prérequis

Un peu de logique. Booléenne, c'est encore mieux. Non, sérieusement, on va parler de programmation logique ; savoir ce qu'on appelle la logique booléenne et ses principaux opérateurs est un plus. Néanmoins, pas besoin d'une grosse connaissance : juste savoir ce que veulent dire «et» et «ou» en logique. En clair, avoir lu les exemples introductifs de la page wikipédia, ou ceux-là qui sont franchement pas mal mais un poil bourrin, ou ce cours qui attaque beaucoup de choses très utiles (quantificateurs, notamment, qu'on utilisera bientôt).

Concepts généraux

Où l'on découvre à quelle sauce nous allons être mangés

Principes de Programmation Déclarative

Comment collecter tous les entiers positifs inférieurs à 100 et multiples de 3 ? En python, une manière de faire est la suivante (à droite, après le #, il s'agit de commentaires qui ne sont pas interprétés par la machine, qui sont là juste pour l'humain) :

for nb in range(1, 100):  # pour chacun des nombres de 1 à 100
    if nb % 3 == 0:       # si le nombre est un multiple de 3
        print(nb)         # afficher le nombre à l'écran

Ce qu'il y a à voir ici, c'est que l'on explique au programme exécutant le code (ici, l'interpréteur python) comment arriver à la solution qui nous intéresse. Ce paradigme, dit impératif, consiste à expliquer comment calculer la solution.

C'est une approche qui est en fait assez peu naturelle, et ça se voit quand on commence la programmation. C'est effectivement assez consternant de devoir s'expliquer auprès d'un ordinateur qui semble avoir les capacités de compréhension d'un enfant de 5 ans (et c'est encore pire avec les langage de bas-niveau), et c'est un gros problème dans l'enseignement en informatique.

La programmation déclarative aborde le problème d'un angle différent : l'humain ne doit plus expliquer comment atteindre la solution, mais plutôt la décrire, c'est-à-dire répondre au quoi, ce qui est beaucoup plus naturel pour un humain. Le paradigme déclaratif consiste en l'explication du quoi.

HTML est un bon exemple de langage déclaratif: on décrit bien la solution (la structure finale de la page web). Le HTML n'est pas un langage impératif ; d'ailleurs, si la page finale dépend de paramètres extérieurs (compte utilisateur par exemple, pour afficher l'avatar en haut à droite de la page), vous ne pouvez plus compter uniquement sur le HTML. C'est généralement là qu'interviennent des langages impératifs (Javascript, PHP, Python, Java,…) qui permettent de générer du HTML à partir de templates et des paramètres extérieurs.

Sans ces languages, il faudrait avoir en mémoire toutes les pages web possibles, ce qui n'est pas possible pour une grande partie des sites web, et difficilement maintenable.

Principes de Programmation Logique

Le paradigme logique est un sous-ensemble du paradigme déclaratif. Autrement dit, un langage logique est un langage déclaratif. À l'inverse, un langage déclaratif n'est pas nécessairement logique (le HTML, par exemple, n'est pas logique).

Le paradigme logique repose sur les méthodes formelles issues des maths et de la théorie de la logique. C'est avec ces outils que la description de la solution (le quoi) est donnée à l'ordinateur.

C'est précisément à cette catégorie de langage qu'ASP appartient.

Pour présenter un peu le concept de la programmation logique, imaginons un langage qui nous permettrais d'expliquer ce qu'est la solution au programme python vu précédemment (calculer les nombres entre 1 et 100 qui sont multiples de 3) :

euh… ben, tout les nombres qui sont multiple de 3, tu vois, mais
entre 1 et 100. Et puis, «nombre» oui, mais pas ceux à virgule, hein.
Ouais, décimaux, c'est ça.

Ce langage, le français, possède deux propriétés attractives : la majorité des francophones le comprendrais, ET ils seraient capable de le réutiliser pour exprimer le même problème, ou une variation (les multiples de 4, ou les nombres de 1 à 200,… Essayez chez vous, vous verrez, c'est facile).

Le problème, c'est qu'aujourd'hui en informatique, créer un programme qui comprendrais ce language relève encore de la science-fiction. Hors, et c'est bien là l'objet de ce tuto, on veut utiliser notre ordinateur perso, pas un super calculateur et l'équipe de chercheur en langage naturel qui va avec.

Donc, essayons maintenant de faire un language que nos petits ordinateurs puisse comprendre :

afficher x tel que : x est un entier, 1 < x < 100, x est un multiple de 3.

C'est compréhensible, simple et efficace ; c'est de la programmation logique ! Ce langage précis n'est pas implémenté, certes (et ASP est un peu moins haut niveau (i.e. proche du langage naturel) que cela), mais il s'agit d'un exemple d'approche d'un langage expressif. On remarque bien ici qu'il ne s'agit finalement que de décrire la solution.

Autre remarque : on pourrait complètement inverser les conditions. Écrire x est un multiple de 3 avant x est un entier ne change rien au résultat. Nous verrons bientôt qu'en ASP, cette propriété va encore plus loin : vous pourrez mélanger autant que vous voudrez les lignes de votre programme, ça ne changera rien à la solution.

La page wikipédia française sur la programmation déclarative est courte, mais suffisante pour notre étude.

Principes de Programmation Par Contrainte

Nous pouvons définir une contrainte comme une restriction sur les solutions. En d'autres termes, la programmation par contrainte consiste à ajouter des expressions qui écartent des solutions, qui sinon seraient autorisées.

C'est un moyen efficace de s'assurer qu'une propriété est respectée dans toutes les solutions.

À propos de notre exemple sur les nombres de 1 à 100 divisibles par trois, nous pouvons trouver quelques contraintes : «seulement des nombres entiers», ou encore «doit être divisible par trois», ou bien «doit être inférieur à 100».

En vérité, les contraintes sont très naturelles dans nos langages naturels.

«Deux joueurs ne peuvent commencer à une distance de moins de 5 mètres» pourrait dire un designer de jeu.

«Un taxon ne peut appartenir à deux branches» dira le phylogénéticien.

«Je ne peux pas mettre plus de deux packs de lait sur le support arrière du caddie» dis-je pendant mes courses.

Bref, il est souvent plus simple d'exprimer une contrainte plutôt qu'inclure cette restriction dans la génération de la réponse elle-même (bon, je vais faire les courses en ne mettant pas deux packs de lait à l'arrière du caddie).

Aussi, la contrainte est parfois moins coûteuse. Par exemple, si je cherche mon caddie dans le magasin, je compare ceux que je vois avec les souvenirs que j'en ai : euh, celui-là a un pack de lait à l'arrière, c'est peut-être le miens. Mais plus rarement, je m'amuse à inventorier ces points commun : ya bien une conserve de ravioli, un pack de brosse à dent,… À la place, je fonctionne plutôt avec des contraintes : non, c'est pas celui-ci, il n'a pas de chocolat à l'avant.

En bref, lorsqu'on cherche quelque chose, écarter les mauvaises possibilités en trouvant une seule différence est souvent plus rapide que d'énumérer les points communs.

En général, un langage autorisant la programmation par contrainte pourra être divisé en deux parties :

1. définir les possibles solutions (la modélisation de l'espace de recherche)
2. interdire les résultats qui ne nous intéressent pas (les contraintes)

La première partie, c'est la génération, où l'on génère les candidats pour la solution. Comme en général ces candidats ne sont pas tous bons, on besoin de les filtrer, d'où la seconde étape, l'application de contraintes, qui permet de définir quels candidats seront écartés. (digression-culture: ce n'est pas le seul usage des contraintes, mais on verra ça bien après)

Answer Set Programming est un langage logique où les contraintes font partie du langage autant que le reste des déclarations. Néanmoins, la dichotomie entre génération et contraintes se voit dans beaucoup de codes ASP, car les développeurs ont intuitivement ce découpage dans leur réflexions.

Exemple de code ASP

Reprenons notre problème initial : afficher à l'écran tous les multiples positifs de 3 inférieurs à 100. En ASP, nous pourrions résoudre ce problème ainsi :

#show solution(X): X=1..100, X\3=0.

On retrouve la même structure que tout à l'heure : afficher solution(X) pour X entre 1 et 100 (génération de l'espace de recherche), et X\3=0 qui est la vérification que X est bien multiple de 3 (contrainte). C'est finalement assez proche que la proposition précédente.

À la fin de ce tuto, vous serez capable de comprendre parfaitement ce code, et d'imaginer d'autres manières de le résoudre.

Outillage

Où l'on va enfin faire quelque chose ; mais pas du code

Il existe de nombreuses implémentations d'ASP, chacunes avec des approches uniques et intéressantes pour résoudre des problèmes plus ou moins spécifiques.

Pour ce tuto, nous allons utiliser la suite Potassco, un ensemble de logiciels qui gravitent autour d'une idée : implémenter et utiliser ASP. Plus particulièrement, nous allons utiliser clingo.

(si ça vous motive et que vous êtes à l'aise, prenez une autre implémentation ; en général les différences conceptuelles du langage ne seront pas monstrueuses, mais certaines implémentations fonctionneront différemment.

Cela étant dit, suivre un tuto avec les bons outils, c'est pas plus mal. Bref, faites comme vous voulez, mais dans le doute, utilisez clingo et explorez les autres après si l'envie vous en prend)

Clingo, en deux (cents) mots et deux parties

Si vous ne comprenez rien au charabia de cette section, pas d'inquiétude : c'est juste pour fixer les idées des informaticiens. Lisez tout de même, je met quelques simplifications au milieu.

Clingo est à ASP ce que CPython est à Python: une usine à gaz (un gros programme bien compliqué) qui comprend et applique les effets de bord du langage.

Clingo est en fait constitué de deux composantes: gringo et clasp (que l'on peut récupérer et utiliser à part).

Gringo est à ASP ce que le compilateur de CPython est à Python, ou ce que gcc est à C: une grammaire et un ensemble de routines qui compilent vers un langage simplifié à l'extrême. (dans le cas d'ASP, c'est du smodels, pour Python c'est du bytecode, et pour C c'est de l'assembleur)

Clasp est à ASP ce que l'interpréteur de CPython est à Python : un ensembles de routines qui pigent le langage simplifié calculé par l'outils précédent (gringo/compilateur) et en appliquent les effets de bord (mémoire et calculs).

Pour être plus précis à propos de gringo et clasp, le premier compile un programme qui suit la grammaire d'Answer Set Programming (et un peu plus, nous verrons cela), et le second est une routine qui, à l'aide d'une heuristique très personnalisable, va chercher les solutions acceptables (ou modèles stables) dans le programme compilé.

En ASP, on parle de grounding pour la partie assurée par gringo, et de solving pour la partie assurée par clasp. Clingo est donc un programme qui se charge du grounding et du solving d'un seul coups.

De notre point de vue, c'est ça en moins à gérer, mais c'est important de s'en rendre compte, car dans pas mal de cas il peut être intéressant de manipuler les deux indépendemment. Mais ce sera l'objet d'un autre tuto.

Installation

il est possible de faire tourner clingo dans un navigateur. C'est très pratique : il n'y a rien à installer, ça marche tout seul, pas besoin de se prendre la tête.

Si vous voulez savoir comment ce bijoux technologique est possible, allez voir l'issue à propos, et mon exemple fonctionnel.

Si toutefois vous préférez utiliser votre environnement de dev favori, et que vous vous sentez de faire deux clics gauche et un clic droit, Clingo est disponible sur le dépôt github. Le site de référence étant le site de Potassco lui-même.

À l'écriture de ce tuto, la version de clingo la plus récente est la 5.2.2.

Installation manuelle

A moins que vous ne soyez concerné par l'un des quelques OS qui ont un packaging, le plus simple est probablement de

1. Télécharger ou compiler le binaire clingo
2. Le mettre dans le PATH (/usr/bin pour les bourrins, ~/.local/bin/ pour les moins bourrins)

Qu'est-ce que le PATH ? Pour les windowsiens, pour les unxiens.

Personnellement, j'ai un répertoire ~/bin/ vers lequel mon PATH pointe. C'est ici que j'y ai mis mes binaires clingo:

❯ ls -lA ~/bin | cut -c 50- | grep clingo
clingo522
clingo454
clingo -> clingo522

(clingo est un lien symbolique vers l'une des versions installée… généralement la plus récente)

Compilation

Pour les plus à l'aise, la compilation de clingo depuis les sources est aussi possible, et nécessaire si vous voulez une version particulière avec le support de python ou de lua avec une version particulière (je pense à python 3, notamment)

Voici le makefile que j'utilise sous fedora pour l'update, la compilation et l'installation :

all: update_repo compile install

install:
    cp clingo/bin/clingo ~/bin/clingo_compiled_from_repo

compile:
    cd clingo && cmake . -DPYTHON_LIBRARY:FILEPATH=/usr/lib64/libpython3.5m.so -DPYTHON_INCLUDE_DIR:PATH=/usr/include/python3.5m -DPYTHON_EXECUTABLE:FILEPATH=/usr/bin/python3.5m
    cd clingo && make
    cd clingo && cmake --target test . -DPYTHON_LIBRARY:FILEPATH=/usr/lib64/libpython3.5m.so -DPYTHON_INCLUDE_DIR:PATH=/usr/include/python3.5m -DPYTHON_EXECUTABLE:FILEPATH=/usr/bin/python3.5m
    cd clingo/app/clingo/tests && python3.5m run.py --clingo ../../../bin/clingo run

update_repo:
    cd clingo && git pull
    cd clingo && git submodule update --init --recursive

Quelques tests préliminaires

Où l'on commence à jouer, avec une retenue typique d'une centrale hydroélectrique

Maintenant que vous avez clingo qui fonctionne, effectuons quelques tests préliminaires pour étudier un peu l'environnement.

Version

Pour avoir la versions de clingo, il suffit de demander: clingo --version. Vous verrez quelque chose du style:

clingo version 5.2.2
Address model: 64-bit

libgringo version 5.2.2
Configuration: with Python 3.6.2, with Lua 5.3.4

libclasp version 3.3.2 (libpotassco version 1.0.0)
Configuration: WITH_THREADS=1
Copyright (C) Benjamin Kaufmann

License: The MIT License <https://opensource.org/licenses/MIT>

On peut, notamment, voir les versions de gringo et clasp utilisées, ainsi que les supports de langages de scripts (ici python et lua sont supportés tous les deux, ce ne sera peut-être pas votre cas, selon la manière dont vous l'avez installé/compilé/récupéré).

Le «bytecode» d'ASP

Il est possible de voir la sortie de gringo avec l'option --text. Avec ce flag, clasp ne sera pas appelé et ne sera retourné que le code simplifié issu du grounding. (pour ceux qui passe par le navigateur : il ne semble pas y avoir d'options pour le voir, mais il existe, soyez en sûr)

Lorsque l'on utilise ASP pour un problème combinatoire, il arrive souvent que l'on s'intéresse au grounding du programme. C'est en effet en étudiant ce code intermédiaire qu'il sera possible de déterminer quelles règles en ASP génèrent beaucoup de données, et donc quelles règles sont impliquées dans un temps de solving long.

Lancez la machine !

Lancez clingo sur les fichiers contenant les programmes de ce tuto, ou lancez le sans fichier en argument, et tapez directement le programme, puis contrôle-D (fin de fichier). Clingo vous répondra en fonction.

Prenez vraiment l'habitude de lancer les programmes, et de les trifouiller. C'est comme ça qu'on apprend ! (pour ceux qui sont dans leur navigateur : copiez-collez les programmes dans la zone de texte, modifiez-les à l'envie, et appuyez sur run)

Pour bien montrer comment clingo s'utilise, voici une session complète où j'écris un programme ASP dans l'entrée standard de clingo (j'aurais aussi pu l'écrire directement dans l'entrée standard clingo) :

❯ echo "a. b." > program.lp
❯ clingo -n 0 program.lp
clingo version 5.2.1
Reading from program.lp
Solving...
Answer: 1
a b
SATISFIABLE

Models       : 1
Calls        : 1
Time         : 0.000s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.000s

(pour ceux qui sont dans l'interface web, écrivez juste a. b. dans le champs de texte, et appuyez sur run)

Du point de vue de clingo, que se passe-t-il ici ?

• d'abord, clingo parse les arguments de la ligne de commande (ici -n 0 et program.lp)
• il apprend que je veux tous les modèles, toutes les réponses possibles (-n 0)
• il apprend également qu'il doit considérer le programme dans le fichier program.lp
• il lance gringo sur le programme, et obtient le code compilé (smodels).
• il lance clasp sur le code compilé, et m'affiche le résultat.
• j'apprend que mon programme n'a qu'une seule et unique solution (Answer: 1), où les atomes a et b sont vrais.
• j'apprend que le problème est satisfiable (évidemment, il y a eu une solution)
• clingo me donne quelques infos statistiques sur l'opération (notamment à propos du temps écoulé)

Notez que la ligne Reading from program.lp correspond au grounding, et la suivante, Solving..., correspond au solving.

Si clingo semble ne rien faire après avoir écrit la première, c'est que le grounding est long (et le pc ne fait pas rien ; vous avez probablement un CPU qui tourne à 100% pendant toute la durée du grounding). Dans l'autre cas, c'est le solveur qui pédale dans la semoule : votre problème est très long à traiter.

help et options diverses

Vous pouvez avoir l'aide de clingo avec l'option --help (ou --help=3 pour l'aide complète ; encore une fois, ceux qui sont sur le navigateur ne peuvent pas lancer ces commandes,… désolé). Quelques options intéressantes dont je ne parlerais pas ou peu :

• --text: pour avoir le code groundé (le solveur, clasp, n'est pas appelé). Cf --mode.
• --stats: pour avoir plus d'info sur le déroulement du solving lorsque celui-ci est terminé (il y a une checkbox sur l'interface web)
• --time-limit: permet de donner un temps maximum de grounding/solving
• --parallel-mode: utiliser le multithreading : utiliser plusieurs cœurs en même temps pour le solving
• --enum-mode: choix de l'énumération des modèles : tous les modèles, ou tous les meilleurs modèles par exemple
• --outf: choix du format de sortie (l'un des plus intéressant est probablement JSON, si vous voulez récupérer le résultat sans faire de parsing manuel)

Principes d'Answer Set Programming

Où l'on va (enfin !) faire quelque chose de significatif dans ce monde où seule l'action prime

Maintenant que l'on a plein de théorie dans la tête et clingo sur le pc, attaquons le vif du sujet: parler ASP !

Commentaires

Les commentaires sont des parties du texte que clingo ne va pas considérer. Pour le dire autrement, vous pouvez mettre les pires cochonneries dans des commentaires, clingo ne se formalisera pas. En général, c'est très utilisé par les humains pour expliquer à quoi sert le code qui est à côté. Utiliser les commentaires aide à comprendre ce que fait un code ; il est donc conseillé d'utiliser les commentaires pour s'aider soi-même.

Les commentaires commencent par un %:

% Je suis un commentaire
Je ne suis pas un commentaire  % ni de l'ASP valide d'ailleurs

Ici, clingo plante sur Je ne suis pas un commentaire, car il ne s'agit pas d'ASP valide. Comme indiqué dans le commentaire à droite.

Les commentaires multilignes commencent avec %* et terminent avec *%. Notez que clingo n'est pas capable de gérer la présence d'un %* dans un commentaire multiligne, ni ne considère ce qu'il y a après un %, empêchant d'utiliser le snippet % *% comme le //*/ en C.

Les atomes

Un atome est un fait, une relation qui est considérée vraie. Par défaut, tout atome est considéré faux, jusqu'à ce qu'il soit explicitement statué comme vrai.

Un programme ASP repose sur ce principe, si bien que la solution à un problème est en fait décrite par les atomes vérifiés.

Tout le jeu d'un programme ASP est de définir quels atomes doivent être vrais, sous quelles conditions (c'est la modélisation du problème), et quelles combinaisons d'atomes rendent une réponse caduque (c'est le job des contraintes).

Considérons le programme suivant:

a.

Ici, on indique que le fait a est vrai. À l'inverse, tout autre fait est faux, et si on lance clingo sur ce programme, nous ne trouverons qu'un seul et unique modèle (ou (ensemble-)réponse) : celui où a est vrai.

Le point . est un peu comme le point-virgule en C, ou le saut de ligne en Python : il termine chaque règle et atome du programme. Si vous oubliez un point, vous aurez droit à une erreur de type unexpected machin-bidule bla bla bla ASP pas content.

a(4).

Cette déclaration est un peu plus complexe, mais revient au même : le prédicat a d'arité 1 (c'est-à-dire avec 1 argument) avec comme premier (et unique) argument 4, est vrai.

De la même manière, il est possible de déclarer b, b(42), mais aussi a(b), a(a,b,c,3), a(b(1)), ou encore a(a(b(b(9)))). Le nombre d'argument potentiel est virtuellement illimité, et un atome peut être argument d'un autre.

L'usage typique des arguments, c'est de donner des valeurs à un concept, par exemple:

papa(jacques_dutronc,thomas_dutronc).  % J. Dutronc est le papa de T. Dutronc
papa(dark_vador,luke).  % Pareil pour dark vador et luke
papa(chronos,zeus).  % idem
papa(zurg,buzz).  % bref, vous avez compris
maman(metis,athena).  % pareil, mais pour les mamans
papa(zeus,athena).
papa(la_force,dark_vador).  % c'est ça ou les midichloriens :D
maman(shmi,dark_vador).
maman(padme,luke).
maman(jobal,padme).  % la famille Naberrie
papa(ruwee,padme).
maman(jobal,sola).  % Sola est la sœur de Padmé
papa(ruwee,sola).

Voilà, toutes ces données sont considérées vraies par clingo (et en plus sont vraies dans réalité véritable, que demander de plus ?). Bien sûr, on ne va pas s'amuser à les mettre dans tous les programmes qu'on utilise : ça a beau être vrai, ce n'est pas toujours pertinent.

Notez aussi que l'ordre dans lequel les atomes apparaissent dans le code n'a pas d'influence sur le résultat. Nous verrons ça plus loin, mais vous découvrirez bientôt que la notion même d'ordre en ASP est… globalement absente.

Notation

a/1 est l'ensemble des atomes de prédicat a avec un seul argument. Par exemple a(1) ou a(a(a(staying,alive))). De la même manière, ha(do,pi) et ha(do,ken) appartiennent tout deux à l'ensemble des atomes décrits par ha/2.

Questions (sans piège) : comment décrire l'atome k(2,"mille",v(2)) ? coucou ? Et symballium(v,o,l,u,m,e," ",i,v,"<3") ?

(si vous n'êtes pas sûr de vos réponses, allez voir la fin de page)

Retour sur les atomes

Ci-après, un autre programme qui génère des atomes (donc, des faits, des éléments considérés vrais pendant le solving).

% Les atomes nb(X) sont vrais pour tout X entier de -23 à 42
nb(-23..42).
% Les atomes nb_ex(X) sont vrais pour tout X ∈ [1;4]
nb_ex(1;2;3;4).
% On peut aussi combiner les deux écritures :
nb_cb(1;2;3..10).
% Et on peut rajouter encore des nb/1 :
nb(51..138).
% Ou encore nous répéter
%  (ASP s'en fiche, quelque chose de deux fois vrai est toujours vrai) :
nb(51..53).

Donnez ce programme directement à manger à clingo ! Vous comprendrez vite comment ça fonctionne.

Et, histoire de radoter un peu : l'ordre des lignes ne change rien au résultat, et il n'y a qu'une seule solution, celle contenant tous les atomes vrais.

Règles

Maintenant que l'on peut déclarer des faits, nous pouvons commencer à déclarer des règles de causalité. En d'autres termes, il est possible de définir qu'un atome est vrai sous certaines conditions.

En ASP, cela se fait avec l'opérateur :-, une espèce de si :

% l'atome ok est vrai SI l'atome a est vrai
ok :- a.
% l'atome ok est vrai SI les atomes b ET c sont vrais
ok :- b ; c.  % notez que le ET est symbolisé par le point-virgule

On appelle la partie avant le :- la tête (head), et la partie à droite le corps (body). La tête est vraie si et uniquement si le corps est vrai.

Les règles sont les premiers éléments utiles dans un programme ASP. Ce sont ces règles qui vont permettre d'exprimer des implications, et donc de réellement commencer à travailler sur les atomes existants.

Donc, dans un programme ASP, vous avez des atomes considérés vrais (souvent, ce sont des données du problème), et des ensembles de règles qui vont permettrent d'inférer la véracité d'autres atomes.

Variables

Les variables permettent d'écrire des règles plus généralistes. Tout mot commencant par une majuscule est une variable.

Par exemple:

% l'atome ok(X) est vrai si l'atome a(X) est vrai
ok(X) :- a(X).

Avec ce programme, si a(2) est vrai, alors ok(2) le sera également. Même chose pour n'importe quelle valeur de X, de 1 à a en passant par -42000, "i have υτφ-8 characters" ou b(c(d,d(3),e(f,g(a(b,8)),0)),k20,flip,flop(py(disk),"hello, world!")).

Exemples de règles avec des variables :

% L'atome nb_3(X) est vrai pour tout X positif inférieur à 100 et multiple de 3.
nb_3(X) :- 0<X ; X<100 ; X\3=0.  % le '\' c'est pour le modulo, ou "division entière"
% l'atome entoure(X-1,X,X+1) est vrai si l'atome a(X) est vrai
entoure(X-1,X,X+1):- a(X).  % par exemple, avec a(2), ça donne entoure(1,2,3)

(à propos de modulo/division entière)

Variable muette

La variable muette, c'est une manière de dire explicitement : cette valeur ne m'intéresse pas. Par exemple, si je voulais avoir un atome d'arité 1 qui me donne les papas, indépendemment de leurs enfants, je pourrais faire ainsi :

papa(P):- papa(P,E).

Sauf que le E qui sert à rien là, c'est pas très joli. Du coups, on peut le remplacer par une variable muette :

papa(P):- papa(P,_).  % une variable muette commence par un _ ('underscore')

Et voilà ! Il est bien clair pour tout le monde que le second argument ici ne nous intéresse pas. Il faut qu'il existe, évidemment, mais la valeur exacte n'est pas pertinente dans le contexte.

Notez qu'on pourrait tout à fait se passer des variables muettes. Elles sont tout à fait optionnelle. C'est ce qu'on appelle du sucre syntaxique : un truc sympa qui ne fait que simplifier la vie du programmeur.

Exeeeeerciiiiiiice ! Tel père, tel fils

Petit exercice à faire chez vous, c'est obligatoire, sinon, lorsque vous commencerez à lire la partie suivante, ce site s'autodétruira (offre soumise à condition).

Je vous propose simplement de reprendre la base de donnée des filiations présentée plus haut (avec papa(jacques_dutronc,thomas_dutronc) et les autres), et de faire un programme qui, connaissant ces liens de parenté, va définir qui est l'enfant de qui.

En clair, si j'ai papa(monpapa,moi). ou maman(mamaman,moi)., je veux obtenir enfant(moi,monparent)..

Pour réussir ce petit tour, il faut utiliser les deux concepts vus précédemments : les règles et les variables.

(NB: pour simplifier la sortie de votre programme en affichant uniquement les atomes enfant/2, utilisez l'expression #show enfant/2.. Nous verrons plus tard le fonctionnement exact de ce genre d'expression)

Aide

Si au bout de 20 minutes vous :

• n'avez rien essayé : bah quoi ? Allez-y ! Tapez des trucs ! Si ya bien un domaine où il faut se tromper pour y arriver, c'est l'informatique ! Et l'ordi il est là pour ça vous savez ; et il aura oublié aussi tôt que vous aurez essayé autre chose. À moins que vous ne soyez détenu par un psychopathe qui vous observe et vous oblige à faire ce tuto ? Et qu'à la moindre erreur, il vous fait boire une soupe d'avocat ? Si c'est le cas, je suis désolé que ça tombe sur mon tuto, mais cela étant dit, je suis assez content d'avoir vu juste. Envoyez moi un mail quand vous serez sortit de là, hein ? Ça me rassurera. Et puis, dans votre malchance, vous avez de la chance : ya vraiment rien de compliqué. Nouveau, oui, mais il faut savoir sortir de sa zone de confort. Par contre, j'avoue, la soupe d'avocat c'est un peu sévère. Bref. Concentrez-vous, vous allez y arriver, faites-vous confiance (par contre, dépêchez-vous, la soupe d'avocat froide, c'est encore pire ! … désolé).
• n'avez rien essayé, malgré le fait qu'aucun psychopathe ne vous menace avec une soupe d'avocat : là, il va falloir se lancer, hein (et revenez ensuite, hein ?).
• toujours pas trouvé, malgré bien des tentatives : en bas de page, ya les solutions.

Bonus

Considérons qu'un atome moi/1 indique qui je suis. En utilisant toujours les même données, faites en sorte que si mon père est Dark Vador ou l'infâme Zurg, alors l'atome nooooooooooon doit être vrai.

Notez que pour résoudre ceci, il faut un «ou» : «si mon père est Dark Vador ou l'infâme Zurg». Pour émuler ceci, il y a plusieurs solutions :

• on peut écrire plusieurs fois les règles, avec à chaque fois une valeur attendue différente.
• on peut définir Dark Vador et Zurg comme appartenant à un groupe, puis mettre comme condition à l'atome nooooooooooon que le père y appartienne.

Négation

Notez qu'il est possible d'utiliser la négation:

% l'atome ko(X) est vrai pour tout X de nb_ex(X) qui n'est pas ok(X)
ko(X):- nb_ex(X) ; not ok(X).

Notez que le point-virgule est utilisé comme opérateur et, l'équivalent de and en Python ou && en C.

Une autre manière de voir cette règle, plus verbeuse mais plus puissante, est la suivante: Pour tout X tel que nb_ex(X) est vrai et ok(X) est faux, on a ko(X).

Cette formulation nous permettra de mieux comprendre une prochaine construction du langage.

Il n'existe pas réellement de ou en ASP ; il faut alors créer 2 règles, chacune implémentant un cas :

% l'atome ok(X) est vrai si nb_ex(X) ou si nb_in(X)
ok(X):- nb_ex(X).
ok(X):- nb_in(X).

Exeeeeerciiiiiiice ! Tel non-père, non-tel fils

Toujours avec la base de donnée des filiations présentée plus haut (avec papa(jacques_dutronc,thomas_dutronc) et les autres), l'objectif est de déterminer les atomes papapa/1, indiquant quels enfants ne sont pas papa.

Par exemple, dans les résultats attendus, on s'attends à trouver papapa(athena). et papapa(luke).

Il va falloir utiliser la négation, sans oublier que si vous vous contentez de dire ce que ça n'est pas, ASP ne peut pas deviner ce que ça est : il faut donc indiquer qui sont les enfants.

(NB: pour simplifier la sortie de votre programme en affichant uniquement les atomes enfant/2, utilisez l'expression #show enfant/2.. Nous verrons plus tard le fonctionnement exact de ce genre d'expression)

Aide

Si au bout de 20 minutes vous :

• n'avez rien essayé : essayez un truc. N'importe quoi. Genre papapa X papa :- choux-rouge enfant X,_, qui n'a pas beaucoup de sens mais c'est déjà un début. Ensuite, comme on sent bien que choux-rouge n'a rien à faire ici, on l'enlève. Ensuite, c'est un peu mélangé entre papa et enfant : relisez bien les parties juste précédentes, réorganisez bien. Pensez à lancer régulièrement clingo sur votre code, et si il fait une erreur, dites vous «pfff, il faut vraiment que je lui explique tout !»
• n'avez rien essayé, mais c'est parce que vous lisez ce tuto en diagonale avant de savoir «si je vais vraiment le faire» : chaque exercice est un petit bonbon mental : ne refusez pas une telle confiserie à votre cerveau, il aime ça !
• vous avez beaucoup cherché, mais votre seule trouvaille est une idole en or massif appartenant à un peuple péruvien oublié : se pourrait-il qu'ASP ait été inventé pendant une danse du Soleil par un cosmologiste incas ? Ou alors peut-être cherchez vous au mauvais endroit ? Vite, allons voir les solutions pour le découvrir !

Disjonction (choix)

Une construction très importante en ASP est le choix. Le choix consiste en un… choix. C'est dur à expliquer autrement.

Voici un exemple simple, avec le résultat donné par clingo, qui consiste en un choix de exactement 1 parmis 3 atomes :

1 { a;b;c } 1.

Notez qu'il s'agit d'une règle sans corps, donc avec uniquement une tête. Le résultat donné par clingo est le suivant :

clingo version 5.2.2
Reading from stdin
Solving...
Answer: 1
b
Answer: 2
c
Answer: 3
a
SATISFIABLE

Models       : 3
Calls        : 1
Time         : 0.000s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.000s

La sortie de clingo est toujours très semblable à celle-ci. Les données importantes sont les différentes réponses possibles (et leur nombre).

(notez que sans l'option -n 0, seul un modèle aurait été montré. le n est en fait la version courte de nombre de modèle à afficher, ou 0 pour tous les afficher. Notez que, si des modèles n'ont pas été affichés à cause de cette option, clingo le fera savoir en affichant un + à côté du nombre total de modèles calculés)

La première réponse (ou modèle, ou answer set, ou ensemble réponse), contient uniquement l'atome b. La seconde contient uniquement l'atome c. Enfin, la dernière réponse contient uniquement l'atome a.

Pourquoi pas deux en même temps ?

C'est vrai ça ! Pourquoi on pourrait pas avoir a et b en même temps par exemple ?

Résonnons par l'absurde : si on a a et b en même temps, cela veut dire que a et b sont vrais dans le même modèle.

Or, dans le programme, il est dit 1 { a;b;c } 1., c'est-à-dire qu'au moins une et qu'au plus un des trois atomes entre accolades est vrai. Si a et b sont vrais, alors il y a deux valeurs vraies parmis les valeurs entre accolades, ce qui n'est pas possible, puisqu'il doit n'y en avoir qu'une !

En suivant la même logique, on devine qu'il ne peut pas non plus y avoir a, b et c en même temps, ni aucun des trois.

Le fait qu'il n'y ait qu'un seul des trois de vrai pour un modèle donné agit comme une contrainte.

Pourquoi cet ordre ?

C'est vrai ça ? Pourquoi le modèle 1 contient b, le 2 contient c et le dernier contient a ? Pourtant, l'ordre alphabétique, c'est fantastique !

Parce qu'en ASP, on travaille sur des set (answer set programming). Les set, ou ensemble en français, sont au sens mathématique du terme, des ensembles non ordonnés d'éléments uniques.

Les conséquences de ces propriétés sont les suivantes :

• les réponses ne sont pas ordonnées (nous verrons que… mais c'est pour plus tard)
• un atome ne peut pas être choisi deux fois : soit il est vrai, soit il ne l'est pas. Il ne peut être vrai deux fois (car cela reviendrait à avoir deux fois le même élément dans un set)
• l'ordre des règles en ASP n'a pas d'importance (contrairement à Prolog, vous pouvez donc mélanger les lignes de votre programme sans que cela n'ait d'effet : allez-y, testez, c'est rigolo ! (nan, en vrai, c'est chiant comme une course d'escargot en ralentit pendant la nuit : il se passe rien))

Gardez cela à l'esprit, car ces propriétés sont fondamentales dans la construction mathématique derrière ASP, et donc dans les notions que l'on va voir après.

Retour à nos moutons

Le programme traité par clingo est le choix suivant : 1 { a;b;c } 1, qui se traduit un élément parmis a, b ou c. Le 1 à gauche est la borne minimale, par défaut égale à zéro. Le 1 à droite est la borne maximale, par défaut l'infini.

Si le programme avait été 2 { a;b;c } 2, j'aurais également eu trois modèles/réponses, mais leur contenu exact aurait changé: a b, b c et a c sont les trois ensembles possibles de deux éléments parmis a, b et c.

De la même manière, si le programme était { a;b;c }, j'aurais eu 8 modèles. Et si il était { a;b;c } 2, j'aurais eu 7 modèles. Pourquoi 8 et 7 ? Je vous laisse tester vous-même, vous comprendrez tout de suite.

(remarquez que tout cela n'est que pure combinatoire)

Aller, un dernier exemple pour la route, qui montre comment avoir un seul nb(X) vrai pour chaque answer set:

% On choisis un nombre entre 1 et 100.
1 { nb(1..100) } 1.

Vous pouvez (devriez) vérifier : nous obtenons bien 100 answer sets, chacun avec sa propre valeur de nb(X).

«Je veux celui-là !» : choisir parmis un ensemble

Tel que je vous l'ai décrit, le choix ne peux se réaliser que sur un ensemble décidé à l'avance. Mais mettons que je veuille choisir une maman parmis toutes les mamans de la base de connaissance. Comment faire ?

Une première façon, à la fois très rébarbative et risquée, serait de recopier les noms des candidates :

1 { meilleure_maman(metis) ; meilleure_maman(shmi) ;
    meilleure_maman(padme) ; meilleure_maman(jobal) } 1.
% Ou, c'est équivalent :
1 { meilleure_maman(metis;shmi;padme;jobal) } 1.

Mais, heureusement, il existe un moyen simple pour s'assurer de choisir dans un ensemble donné :

1 { meilleure_maman(M): maman(M,_) } 1.

Ici, on dit «choisir exactement un M sachant que M doit apparaître comme premier argument d'un atome maman/2». Notons qu'il est possible de donner plusieurs conditions, séparées par des virgules (car le point-virgule sépare les choix), comme par exemple :

1 { meilleure_maman(M): maman(M,_), est_candidate(M) } 1.

Exeeeeerciiiiiiice ! Mon papa c'est le meilleur

Un petit exercice tout simple : toujours avec la base de donnée des filiations, choisir le Papa de l'Année, titre honorifique qui sera officiellement décerné lors d'une grande fête intergalactique.

Votre tâche, si vous l'acceptez (et vous êtes obligés, sinon la fête est annulée et tout le monde va vous en vouloir, surtout l'infâme Zurg, et il est vachement rancunier alors je serais vous je ferais vachement gaffe), est de choisir le Papa de l'Année.

Bon, avec un grand pouvoir vient de grandes désillusion : les grandes fêtes intergalactique, je vous le cache pas, c'est surtout une occasion de revoir la famille lointaine et d'essayer ce nouvel alcool fort de tonton Gaston. Du coups, quelque soit le papa que vous choisissez, il y aura des bastons et des gens qui hurlent.

Donc, comme on aime bien investir, nous, les illuminatis-de-l'espace-qu-on-contrôle-toute-la-galaxie-tavu, nous sommes dit que ce serais pas mal d'avoir un programme qui choisi pour tout le monde. Pas de jaloux, c'est le hasard.

Du coups, allez-y : faites un programme ASP qui choisi un papa. Et nous, les illuminatis-de-l'espace-qu-on-contrôle-toute-la-galaxie-tavu, on prendra le premier modèle (ou le second. Ou le dernier. Bref, celui qui nous arrange, mais chut c'est tip-top-secret !).

Aide

Si au bout de 20 minutes, vous:

• n'avez rien essayé : j'en déduit que la soupe d'avocat est bonne. Perso, la seule fois où on en a fait, j'étais tout petit, y avait mon papa et ma maman qui avaient fait la soupe. Ben personne n'en a mangé. C'était. Vraiment. Pas. Bon. En vrai, rien qu'à l'odeur, on a tous fait des têtes bizarres. Et ensuite ma maman elle a goûté, et ensuite elle nous a défendu d'en prendre. Plus tard, dans ma fratrie, la légende racontait (racontait, hein, parce que bon, maintenant on a grandit, on sait tous que je l'avais inventée juste pour faire mon intéressant, alors qu'en vrai c'était juste l'hiver) que, après que les parents l'ai jetée dans le compost, les plantes ont arrêtée de pousser pendant plusieurs mois.
• n'avez rien essayé, mais êtes bien conscient qu'il faut se lancer, mais au font avez trop peur qu'en appuyant sur la mauvaise touche, je sorte de l'écran, bouillant de rage, en hurlant des insanités et en maudissant votre famille sur 29.3 générations : un indice : il suffit de choisir un papa parmis tous ceux qui sont papa de quelqu'un.
• avez tout essayé, y compris de faire une méta-méta-heuristique qui contrôlait un algo génétique multi-objectif qui testait des combinaisons au hasard de lettre pendant plus de 25 ans sur un supercalculateur : il y a les solutions en bas de page, mais en vrai, c'est d'un séminaire sur le lâché prise dont vous avez besoin.

Le comptage comme une condition

Nous avons vu que le choix/la disjonction s'effectue en utilisant la notation avec les accolades dans la tête d'une règle. Que se passe-t-il si on met ça dans le corps ? Eh bien, ça devient une condition :

{a;b;c}.  % choix d'un sous-ensemble
ok(N):- 2{a;b;c}3.  % ok si 2 ou 3 éléments dans le sous-ensemble

L'atome ok sera vrai si 2 ou 3 atomes parmis a, b et c sont vrais.

Le comptage comme une donnée

Un autre usage de cette syntaxe est celui-ci :

{a;b;c}.
nb(N):- N={a;b;c}.  % compte le nombre d'éléments

Le comptage comme un calcul

Il existe une troisième manière d'utiliser un comptage : pour compter des valeurs, éventuellement avec des poids différents pour chaque atome. Pour cela, on utilise la directive de métaprogrammation #count, qui n'est pas vue dans ce tuto.

Disjonction simple

L'écriture de la disjonction avec les accolades est une généralisation d'une écriture plus simple, qui exprime le choix d'exactement un des opérandes.

a;b;c.

Lorsque vous lancez clingo là-dessus, vous trouverez trois modèles, un pour chacun de ces trois atomes. Il est également possible de mettre cette construction dans le head d'une règle :

b;c:-a.

Ici, b OU c sera vrai si a est vrai.

Notez bien que {a;b;c} n'est pas égal à a;b;c ! Comme expliqué précédemment, les bornes minimales et maximales par défault dans l'écriture avec accolades sont respectivement zéro et l'infini. Autrement dit, a;b;c est équivalent à 1{a;b;c}1.

Respect du choix

Quels sont les modèles issus de ce programme ?

1{a;b;c}1.
a;b;c.

Et de celui-là ?

1{a;b;c}1.
2{a;b;c}2.

et de celui-ci ?

1{a;b;c}1.
a :- b;c.

Et de celui-lô ?

a;b;c.
a;b;c.

Ces exemples montrent que les choix agissent comme des contraintes : on dit qu'ils ne sont pas génératifs. Autrement dit, a;b. ne signifie pas que cette règle ajoute a ou b au modèle, mais bien que un modèle contient a ou b.

Contraintes

Les contraintes ! On en a souvent parlé, et certainement brûlez-vous d'impatience à l'idée de les utiliser !

Reprenons un de nos derniers exemples, en ajoutant une contrainte qui écarte tous les modèles avec une valeur qui n'est pas multiple de 3 :

% On choisis un nombre entre 1 et 100.
1 { nb(1..100) } 1.

% On écarte tout modèle dont le nombre choisis n'est pas multiple de 3.
:- nb(N) ; (N\3) != 0.

Premier constat, l'écriture d'une contrainte ressemble à celle d'une règle, à l'exception de la tête, qui est vide. C'est exactement la description d'une contrainte dans la grammaire d'ASP: une règle sans tête.

Cela, logiquement, à un sens : la contrainte est une règle. Hors, dans une règle, rappelez-vous : lorsque le corps est vrai, la tête est vraie.

Sauf que, dans le cas de la contrainte, la tête est vide : cela veux dire que si le corps est vrai… rien ne peut être vrai !

C'est l'exact sens de la contrainte : si son corps est vrai, alors rien n'est vrai. Il s'agit d'une contradiction fondamentale entre le fait que rien n'est vrai, et que le corps (et probablement d'autres atomes du programme) est vrai. Par conséquent, le modèle est faux, et ne sera pas considéré par le solveur.

Ici (N\3) != 0 n'est vrai que si N n'est pas un multiple de 3 (N modulo 3, écrit N\3 en ASP, renvois le reste de la division entière, c'est-à-dire zéro quand le nombre divisé est multiple du quotient, ici 3). Par conséquent, le corps de la contrainte est vrai lorsque nb(X) est vrai avec X un multiple de trois. Le modèle est donc invalidé dans ce cas. À l'inverse, lorsque X n'est pas un multiple de trois, le corps de la contrainte est faux, donc ladite contrainte n'invalide pas le modèle.

Ainsi, sur les 100 modèles précédemment générés, il n'en reste plus que 33: les nombres entre 1 et 100 qui sont multiples de 3.

Un peu de gymnastique intellectuelle est nécessaire quand vous manipulez les contraintes : elles expriment ce qui doit être faux, pas ce qui doit être vrai.

Négation dichotomique

Il s'agit d'une forme de négation explicite sur un atome, qui ressemblent, dans leurs effets, à des contraintes.

D'abord, considérons le programme suivant :

{b;a}.

Il génère quatre ensembles-réponse : l'ensemble vide, a, b et ab. Si nous ajoutons la règle suivante :

a :- b.

Alors il n'y a plus que trois modèles : le modèle contenant uniquement b n'est pas possible, car a est une conséquence de b. Jusqu'ici, rien de nouveau sous le soleil.

Maintenant, considérons ce programme :

{b;a}.
-a :- b.

La seule différence vient de l'atome a, préfixé d'un - dans la seconde règle. Ce trait d'union est la marque explicite de la négation dichotomique.

Les answer-sets de ce modèle sont l'ensemble vide, a et b. Il n'y a pas a et b en même temps.

Pourquoi ? Parce que -a signifie exactement que l'atome a est faux. Or, lorsque l'on choisi à la fois a et b dans la première ligne, a et b sont vrais. Mais cela entre en conflit avec la seconde règle, qui stipule que si b est vrai, alors a doit être faux.

Une autre manière de l'écrire serais la suivante, indiquant que a et b ne peuvent être vrais en même temps :

{b;a}.
:- b ; a.

Bien qu'elles aient ici un effet identique, il existe entre ces deux écritures une différence logique. Gardez-la donc en tête : parfois la négation dichotomique est plus simple ou lisible qu'une contrainte.

Insatisfiabilité

s'il n'y a pas de solution à un problème, c'est qu'il n'y a pas de problème

Avec cette histoire de contraintes qui empêchent certains modèles d'exister, on est en droit de se poser une question… Et si un problème n'est pas satisfiable, c'est-à-dire qu'il n'existe pas de réponse ? Que se passe-t-il ?

Et bien, accrochez vous à vos ceinture, c'est tout à fait possible:

a.  % a est vrai
-a.  % a est faux (ici équivalent à `:- a.`)

Ceci est la contradiction la plus simple imaginable. C'est la quintessence même du ridicule, on en viendrait à rire, autant que si les poules avaient des dents, en plus de leur bec !

De son côté, clingo réagit exactement comme il faut:

clingo version 5.2.1
Reading from program.lp
Solving...
UNSATISFIABLE

Models       : 0
Calls        : 1
Time         : 5.189s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.000s

Le problème est bien insatisfiable, autrement dit, il n'a aucun answer set, aucun modèle, aucun ensemble-réponse possible.

Un petit mot en passant : si vous avez un jour un problème, que vous arrivez à le modéliser en ASP, et que vous obtenez une insatisfiabilité, c'est une preuve que votre problème n'est pas soluble (dans ce cas, est-ce encore un problème ?).

Ou alors que vous avez mal encodé votre problème :)

Tokens

Petite partie théorique avant d'attaquer un nouveau morceau conceptuel.

Les tokens sont les morceaux de texte, les unités minimales qui peuvent être utilisées pour écrire. C'est un concept théorique assez important, car il peut aider à comprendre mieux le langage dans son ensemble.

En ASP, il existe cinq types de tokens:

• les identifiants: par exemple a, hello_world ou a_3_on_y_va, mais pas A, _, Arachide ou _case (l'expression régulière est donc [a-z][a-z0-9A-Z_]*).
• les variables: un identifiant qui commence par une majuscule ou un underscore (exp. reg: [A-Z_][a-z0-9A-Z_]*).
• les nombres: seuls les nombres entiers sont gérés (expreg: -?[0-9]+).
• les textes/string: encadrés par des double-guillemets ", ils peuvent contenir n'importe quoi, sauf des double guillemets non précédés d'un antislash (sinon, ça termine le texte).
• les opérateurs: mathématiques (+ - / * / \ ^ ..) ou logiques (; , :- : { })

Tout le langage ASP repose sur ces tokens. Nous verrons qu'il existe un sur-ensemble du langage plus ou moins spécifique à clingo, qui rentre dans la catégorie de la méta-programmation, mais c'est hors contexte pour le moment.

(C'est la méta-programmation qui nous permettra de tuner la recherche de la solution, par exemple en définissant quels atomes doivent être affichés dans les résultats, ou définir les valeurs de constantes)

∃ vs ∀

Vous connaissez certainement les deux opérateurs mathématiques suivant : - ∃: il existe, c'est-à-dire il y en a au moins un - ∀: pour tout, c'est-à-dire tous les éléments considérés

Par exemple ∃ jour de la semaine, je fais la grasse matinée est vrai : pour moi c'est le dimanche. Mais je connais des lève-tôt qui se lèvent tôt tous les jours. Pour eux, il faudrait plutôt dire ∀ jour de la semaine, ils ne font pas la grasse matinée.

En ASP, ces signes cabalistiques n'apparaissent pas explicitement, mais leur sémantique apparaît visiblement. Le premier, il existe, nous l'avons déjà utilisé : il est implicite dans les corps des règles.

Ainsi, dans a(X):- p(X), il est dit que a(X) est vrai si il existe un p(X). C'est particulièrement visible avec la règle a:- p(X). Ici, il suffit qu'un p(X) soit vrai, quelque soit la valeur de X, pour que a soit vrai.

D'ailleurs, on pourrait écrire la même règle avec une variable muette pour que ce soit encore plus clair : a:- p(_)..

Maintenant que l'on comprend bien que le il existe est partout par défaut, attaquons le pour tout avec un exemple complet :

% J'ai 3 copains dans ma classe
copain(1..3).
% Parfois certains ne viennent pas à la récré
{ en_recre(1..3) }.
% On joue au tarot quand on est tous les quatre
on_joue_au_tarot:- en_recre(C): copain(C).

Cet exemple génère 8 answer sets, dont un seul contient on_joue_au_tarot.

Ici, le corps de la dernière règle implémente la condition en_recre(C) doit être vrai pour tout les copains C. Autrement dit, si il existe un copain C tel que en_recre(C) est faux, alors la condition est brisée, et le corps de la règle est faux, et par conséquent, on ne joue pas au tarot.

Il est possible d'avoir plusieurs conditions à droite du :, et elles doivent être séparées par une virgule , (et non un point-virgule).

Ce second opérateur mathématique est très important. C'est lui qui nous permettra d'encoder des relations telles que la clef ne doit pas avoir été utilisée, ou le mot n'a été trouvé par personne.

Exeeeeerciiiiiiice ! Garde contre et roi de trèfle

Ajouter au programme précédent la ou les règles nécessaires pour que l'atome on_joue_au_ballon soit vrai lorsque l'on ne joue pas au tarot (donc, lorsque qu'un copain n'est pas là pour la récré).

Aide

Si au bout de 10 minutes, vous:

• n'avez rien essayé : faites une pause plutôt qu'attendre que ça se passe : chantez les plus grands tubes de la compagnie créole, ça détends.
• n'avez rien essayé, mais ya des nouvelles couleurs dans les couleurs de l'arc-en-ciel : GG. Un indice : dichotomie. Ou négation. Ou choix. Ou les deux ?
• avez trouvé comment faire, mais seulement dans le vide et avec des copains sphériques : je suis content de voir que mon tuto est utile aux physiciens ! La solution est en fin de tuto.

Erreurs et warnings

Une partie que je vois rarement dans les tutos pour un language, c'est celle dédiée aux erreurs. L'intérêt, c'est de pousser les gens à ne pas paniquer en voyant un message d'erreur qui sort de leur code, et d'apprendre à comprendre la méthodologie pour y répondre.

En vrai, la méthodologie elle est assez universelle : il faut lire, comprendre, réfléchir, corriger, réessayer.

Unsafeness

En codant, il vous arrivera régulièrement de voir clingo lever une erreur du type :

test.lp:19:1-24: error: unsafe variables in:
  hadoken(Y):-[#inc_base];saiyan(X).
test.lp:19:9-10: note: 'Y' is unsafe

En clair, dans le fichier test.lp, ligne 19, de la colonne 1 à 24, clingo n'arrive pas à décider de la valeur de la variable Y, utilisée dans le fichier test.lp, ligne 19, de la colonne 9 à 10. C'est la notion même d'unsafe : une variable dont la valeur peut virtuellement être n'importe quoi.

Hors, vous vous en souvenez, on est sensé durant l'étape de grounding avoir la génération des atomes avec toutes les valeurs possibles. Vous vous doutez que si le nombre de valeur possible sur un atome est infini, on a un problème.

Eh bien, c'est plus ou moins ce que détecte ici clingo : on ne sait pas quoi mettre en valeur de Y.

Dans ce cas précis, il s'agit juste d'une erreur de nom de variable :

hadoken(Y):- saiyan(X).  % effectivement, on se demande bien ce que peut être Y…

Il faut juste corriger pour que toute variable utilisée dans la tête soit définie dans le corps de la règle.

Unsafeness, deuxième tournée

Retrouvons l'erreur, légèrement changée :

test.lp:19:1-36: error: unsafe variables in:
  hadoken(Y):-[#inc_base];saiyan(X,Y):gandalf(X).
test.lp:19:9-10: note: 'Y' is unsafe

Dans ce cas précis, on avait le code suivant :

hadoken(Y):- saiyan(X,Y): gandalf(X).

Autrement dit: on a hadoken Y s'il existe un saiyan X Y pour tout gandalf X. Ne cherchez pas la logique dans la sémantique, mais plutôt dans le lexique. On définit bien X: il s'agit d'une valeur donnée par l'atome gandalf. Mais Y ? Eh bien, imaginons que saiyan(X,Y) soit définit tel que X est une valeur donnée par gandalf/1, et Y une valeur donnée par dumbledore/1. Dans ce cas, il nous suffit de rajouter une définition pour Y:

hadoken(Y):- saiyan(X,Y): gandalf(X) ; dumbledore(Y).

Et voilà, l'erreur a disparue. Maintenant, le sens pourrait être différent: on pourrait vouloir hadoken Y s'il existe un saiyan X Y pour tout gandalf X et pour tout dumbledore de Y. Dans ce cas, on utilise la virgule pour include dumbledore dans la condition pour tout :

hadoken(Y):- saiyan(X,Y): gandalf(X), dumbledore(Y).

L'unsafeness arrive également quand dans une condition pour tout des variables à gauche du : ne sont pas définies, à droite du : (premier cas) ou dans le contexte de la règle (second cas).

Syntax error

Celle-là sont en général assez simple à résoudre : il s'agit d'une mésutilisation de la grammaire du langage.

Souvent, lorsque vous avez une telle erreur, c'est que vous avez oublié un point, une parenthèse,…

Comme clingo vous donne l'endroit où est arrivé un token inattendu (comme un identifiant à la place d'un point par exemple), il est assez simple de voir d'où viens l'erreur. Petit détail : clingo vous donne la localisation du token inattendu : cela veut dire que si l'erreur est levée à cause d'un point qui manque, c'est le token suivant qui sera ciblé.

Donc le code suivant lève bien une erreur :

atome(avec,arguments,mais,sans,point)
autre_atome(normal,celui,la).

Mais clingo vous dira que l'erreur provient de la seconde ligne. C'est normal : de son point de vue, c'est autre_atome qui est en faute, puisqu'il s'agit d'un identifiant qui se trouve près un atome complet, ce qui n'est pas attendu d'après la grammaire du langage ASP.

Ce détail est très important, et quand on débute en informatique, on a tendance à regarder uniquement la ligne d'où vient l'erreur.

Exeeeeerciiiiiiice ! Yodel et papier crépon

Je ne vous le cacherais pas : cet exercice est un poil plus complexe que les précédents, mais ne vous en faites pas, vous y arriverez tout pareil.

Voici l'énoncé : on cherche des ensembles de personnes partageant les même goûts, sachant que l'on sait qui aime quoi via les atomes aime/2, tel que aime("Gérard","Joueur du Grenier") signifie que Gérard aime l'émission du Joueur du Grenier.

Assez simplement, deux personnes partagent les même goûts si elles aiment une chose en commun. Il existe au moins deux manières de faire ; voici donc quelques phrases qui pourraient vous aider à trouver les différentes manières d'attaquer le problème.

• Il y a au moins deux personnes, au moins un sujet, et tous les atomes aime/2 nécessaires sont vrais
• Il y a au moins deux personnes, au moins un sujet, et il n'existe pas de paire personne-sujet tel que aime/2 n'existe pas
• Les personnes choisies aiment les sujets choisis, et les sujets choisis sont aimés par les personnes choisies.

Les données

aime("Gérard",("Joueur du Grenier";"Les pois cassés")).
aime("Julie",("Les pois cassés";"Star Wars 9: les siths fantôme contre-retournent l'espoir")).
aime("Marlène",("Les chansons des années 20";"Symballium volume 4";"les roses vertes")).
aime("Michel",("La grande musique (dans le sens de la longueur)";"Star Wars 9: les siths fantôme contre-retournent l'espoir")).
aime("Dominique",("La grande musique (dans le sens de la longueur)";"les roses vertes";"Les poids cassés";"Symballium volume 4")).

Avec ces données, vous devriez obtenir 6 modèles. Si vous en obtenez plus, il est possible que certains des modèles soient des sous-ensembles d'autres modèles. C'est l'effet de bord d'une des deux solutions.

Aide

Si au bout de 30 minutes, vous:

• n'avez rien essayé : bon, au risque de paraître un tantinet habité d'une quelconque passion à propos d'une soupe où nagerait des atomes d'avocats (au sens philosophique, pas physique), j'aimerais vous raconter une petite anecdote, que je connais d'expérience, et qui est assez représentative de l'expérience générale des enseignants dans mon domaine. Il se trouve que, lorsqu'on enseigne, on s'aperçoit assez vite que pas mal d'étudiants (et il se trouve qu'il s'agit majoritairement de filles, moins souvent des gars ; rapport à l'éducation ?) essayent à peine, ou lorsqu'ils essayent, c'est avec un mélange de timidité et de stress ; si bien que, au bout de longues minutes à s'imaginer être incompétents, ils finissent par appeler l'enseignant pour de l'aide. Enseignant qui ne voit qu'un écran blanc, et n'a comme unique information j'y arrive pas. Difficile de faire quoique ce soit dans ce contexte, et même impossible si yavais soupe d'avocat à la cantine. Le truc, c'est que ces étudiants ne se lancent pas, craignent l'idée de ne pas réussir du premier coups (comme si c'était possible, ou même souhaitable). Je sais que c'est un problème très commun en info (ça doit arriver ailleurs, certainement), mais je n'ai aucune espèce de piste pour résoudre le problème, à part travailler, en amont, au niveau de l'éducation elle-même. La conséquence de ça, je pense, c'est que ces étudiants ne collectent aucune expérience qui sera plus tard nécessaire à faire un boulot en info (ou un boulot tout courts). Certains arrivent au bout de plusieurs années d'études, et sont toujours incapable de lire ou écrire un quelconque morceau de code. Je n'ose imaginer ce que ça donne après dans un contexte professionnel. Bref, évitez la soupe à l'avocat.
• n'avez rien essayé, mais c'est parce que votre poisson rouge est mort, votre grand-mère s'est remise à l'haltérophilie, votre ordinateur fait des mises à jour, et il est déjà 24h64 à hawaï : je comprend, ça doit être dur. Un indice : l'ASP c'est tellement haut niveau, il suffit souvent de traduire les phrases pour avoir un résultat.
• avez trouvé 18 manières différentes de résoudre le problème, mais toutes nécessitent un microscope électronique à balayage et à pile, ou une fusée voyageant à au moins 0.6c : vous avez peut-être mal compris l'énoncé. Les solutions sont toujours en bas de page, et vous noterez qu'elles ne nécessitent aucun appareillage sophistiqué.

En pratique !

Où l'on s'attaque à une première volée de problèmes qu'ASP résouds sans soucis

Maintenant que l'on a les bases, nous allons (enfin !) pouvoir attaquer de vrais problèmes.

Je suis certain que depuis le temps, vous vous êtes demandés si tout ceci n'était pas une vaste conspiration pour vous faire perdre votre temps. Mais ne vous inquiétez pas : il n'y a nul conspiration.

Ici, il ne s'agit pas d'exercice à proprement parler, dans le sens où le but est de lire et comprendre un code existant. Néanmoins, la définition du problème sera donnée en amont, et par conséquent, vous permet d'essayer de votre côté avant de regarder le code tout fait.

Je vous conseille évidemment de faire les choses ainsi.

Notez également qu'une directive de méta-programmation sera utilisée pour éviter de polluer trop la sortie des solutions : #show. Ne vous inquiétez pas trop à ce propos, il s'agit juste de choisir quels atomes sont affichés en sortie. Il n'a pas d'effet sur le programme, donc ignorez-le ou triturez-le un peu pour comprendre après (le second exemple s'y prête bien), et éventuellement allez lire la partie qui y est consacrée.

Résoudre une énigme du livre jaune des devinettes

Le livre jaune des devinettes est un texte qui se trouve dans le jeu Skyrim, dans lequel on trouve quelques énigmes écrites. L'une d'entre elle nous intéresse tout particulièrement, car elle tombe pile dans le cadre de la logique. En voici l'énoncé :

Un Bosmer a été tué. L'Altomer affirme que le Dummer est coupable. Le Dummer accuse le Khajiit. L'Orque jure qu'il n'a pas tué le Bosmer. Le Khajiit dit que le Dummer ment. Si un seul de ces messieurs dit la vérité, qui a tué le Bosmer ?

Les noms sont propres à l'univers du jeu The Elder Scrolls, et n'a aucun impact sur la résolution. Si cela vous gêne, remplacez Bosmer, Altomer, Dummer, Orque et Khajiit par Gérard, Gontran, Michel, Eugène et Siméon.

Réponse

Le code ASP est étonnement proche de l'énoncé. Notez que les deux premières expressions sont données implicitement dans le problème. Notre ordinateur n'étant pas une intelligence forte, nous devons même si cela tombe sous le sens lui donner explicitement l'informations qu'il y a un coupable, et qu'il s'agit de l'un des quatre suspect.

% Un des quatre suspect est coupable.
ppl(altomer;dummer;khajiit;orque).
1{guilty(X): ppl(X)}1.

% L'Altomer affirme que le Dummer est coupable.
right(altomer):- guilty(dummer).
% Le Dummer accuse le Khajiit.
right(dummer):- guilty(khajiit).
% L'Orque jure qu'il n'a pas tué le Bosmer.
right(orque):- not guilty(orque).
% Le Khajiit dit que le Dummer ment.
right(khajiit):- not guilty(khajiit).
% Un seul de ces messieurs dit la vérité.
1{right(X): ppl(X)}1.

L'unique answer set reçu est ppl(altomer) ppl(dummer) ppl(khajiit) ppl(orque) guilty(orque) right(khajiit), qui contient notamment guilty(orque). C'est bien, d'après le livre jaune des devinettes, la réponse attendue !

Grâce à ce code ASP, on peut jouer au détective : que se passe-t-il si 1 ou 2 personnes disent la vérité ? Et si une complicité entre deux suspects est possible ? Dans ces cas là, notez la place particulière de l'Orque.

Du bruit dans la cuisine

Un petit exercice qui me vaudra des lettres de menace de la part de mes amis acousticiens.

En considérant une maison, composée de diverses pièces (genre, la cuisine, le salon, le placard à balai,…), dont l'une est la source d'un bruit d'un certain niveau (d'une certaine force, dirons nous, afin d'agacer les physiciens).

Question : quelle est le niveau sonore enregistré dans les autres pièces ?

Approximation : disons qu'un niveau sonore est une valeur qui va de 1 à 10, pour 1 étant à peine audible et 10 étant j'ai mal aux tympans, et que le niveau baisse de 1 pour chaque pièce traversée. (pour le dire autrement : pas d'échelle logarithmique, pas de calculs pour les phénomènes de réverbérations/amortissement, que sais-je encore)

Intuitivement, le son ne se propage d'une salle à une autre que si elles sont connectées, et le niveau sonore enregistré (ce qui nous intéresse) est égal au niveau maximal dans la salle.

mézon

Voici une manière d'encoder le plan de la maison :

% connected rooms
next_room(0,9). % la salle 0 est à côté de la salle 9
next_room(4,(3;5)).  % la salle 4, à côté des salles 3 et 5
next_room(6,(3;13;5)).  % et caetera
next_room(7,(0;1;2;3;8;12;13)).
next_room(8,(9;11)).
next_room(10,(9;11)).
next_room(11,(10;12)).

Et maintenant, on dit qu'il y a un son de niveau 10 dans la salle 4:

sound(4,10).

Logiquement, puisque le niveau sonore ne peut que baisser, la salle 4 possède déjà son niveau sonore enregistré : 10. On notera que, par définition, une salle accessible depuis la 4 aura un niveau sonore de 9.

Vous avez largement ce qu'il faut pour décider de votre approche !

Calcul de solutions

Voici une solution possible

% le lien est commutatif : si A est à côté de B, alors B est à côté de A.
next_room(X,Y):- next_room(Y,X).

% Transmission du niveau sonore, avec un offset de -1.
sound(X,Level-1):- sound(Y,Level) ; next_room(X,Y) ; Level >= 0.

% On ne considère que le niveau sonore maximal.
max_sound(X,L):- sound(X,L) ; not sound(X,L2): L2 > L, sound(X,L2).

% N'afficher que les niveaux sonores enregistrés.
#show.
#show max_sound/2.

Discussion

En fait, cet exemple, c'est essentiellement du jeu d'exploration de graphe pas hyper malin. L'intérêt, c'est surtout d'introduire un cas simple qui sera la base de cas plus complexes qui viendrons plus tard.

Résoudre (ou générer) des sudoku (même les plus durs)

Ça, c'est l'application typique utilisée pour ASP : c'est simple, et c'est impressionnant. Le sudoku est un jeu de logique avec des règles simples.

Autant vous dire que le dieu de la logique et des langages ésotériques est déjà tout excité à l'idée qu'on s'y intéresse.

Implémentation des règles

Considérons les atomes s/3 comme ceux encodant une grille, tel que : l'atome s(X,Y,V) est équivalent à «la case en ligne X et en colonne Y porte la valeur V».

Par exemple, un sudoku avec juste un 4 dans la case en haut à gauche serait encodé avec un seul atome : s(1,1,4).

Maintenant, notre objectif, c'est de faire en sorte qu'ASP génère tous les s/3 restants, en respectant les règles du sudoku.

% Valeurs autorisées
val(1..9).
% Les bordures des 9 sous-grilles
border(1;4;7).

% On ne prend qu'une seule valeur par carré
%  (ça paraît évident pour nous, mais l'ordinateur ne peut pas le deviner)
1 {s(R,C,V): val(V) } 1:- val(R) ; val(C).

% Une valeur ne peut pas apparaître plusieurs fois dans la même colonne
1 {s(R,C,V): val(R) } 1:- val(C) ; val(V).

% Ni dans la même ligne.
1 {s(R,C,V): val(C) } 1:- val(R) ; val(V).

% Et là, la partie velue : une valeur ne peut pas apparaître plusieurs fois
%  dans une sous-grille.
1 { s(R,C,V):
   val(R), val(C),  % R et C sont des lignes/colonnes
   R1<=R, R<=(R1+2),  % la ligne est contenue entre les limites de la bordure
   C1<=C, C<=(C1+2)   % pareil pour la colonne
} 1 :- val(V) ; border(R1) ; border(C1).

Ce code peut sembler un tantinet complexe, mais il faut bien comprendre ce que font chacune des expression de choix.

Lorsque j'écris un truc du style 1{ … }1, cette ligne agit à la fois comme un choix d'atomes à générer (le solver va chercher des combinaisons d'atomes en fonction des choix qui lui sont donnés), ainsi que comme une contrainte : il ne peut y avoir qu'un seul parmis ce qui est donné.

D'ailleurs, sur le dépôt, vous pouvez trouver une implémentation alternative qui utilise des contraintes à la place de certaines règles de génération, mais pas toutes. Pourquoi ? Parce que s'il n'y a que des contraintes, vous ne générez plus rien. Donc ASP va juste dire : «ben ya rien à chercher, donc pas de nouveaux atomes. Bonne journée !»

Bon, maintenant, si vous lancez ce programme directement, ASP va vous générer… tout les sudokus valides. Il y en a 6 670 903 752 021 072 936 960, donc vous allez attendre longtemps.

Données et résultats

Un détail rigolo dans le sudoku, c'est que ce que l'on donne au joueur est une partie de la solution : les cases déjà remplies. En ASP, cela se traduit par une dualité données/solution : les cases déjà connues (les données) sont les même atomes que ceux trouvés par le solveur.

Bien, maintenant, trouvons un sudoku vachement dur, tel que celui-ci, encodons-le en ASP sous la forme d'atomes s/3 :

s(1,4,2).
s(1,8,6).
s(1,9,3).

s(2,1,3).
s(2,6,5).
s(2,7,4).
s(2,9,1).

s(3,3,1).
s(3,6,3).
s(3,7,9).
s(3,8,8).

s(4,8,9).

s(5,4,5).
s(5,5,3).
s(5,6,8).

s(6,2,3).

s(7,2,2).
s(7,3,6).
s(7,4,3).
s(7,7,5).

s(8,1,5).
s(8,3,3).
s(8,4,7).
s(8,9,8).

s(9,1,4).
s(9,2,7).
s(9,6,1).

Et lancons-le avec clingo et l'encoding du problème, pour obtenir une seule et unique solution :

clingo version 5.2.2
Reading from solve-sudoku.lp ...
Solving...
Answer: 1
s(1,4,2) s(1,8,6) s(1,9,3) s(2,1,3) s(2,6,5) s(2,7,4) s(2,9,1) s(3,3,1) s(3,6,3) s(3,7,9) s(3,8,8) s(4,8,9) s(5,4,5) s(5,5,3) s(5,6,8) s(6,2,3) s(7,2,2) s(7,3,6) s(7,4,3) s(7,7,5) s(8,1,5) s(8,3,3) s(8,4,7) s(8,9,8) s(9,1,4) s(9,2,7) s(9,6,1) s(1,1,8) s(3,1,2) s(4,1,7) s(5,1,6) s(6,1,1) s(7,1,9) s(1,2,5) s(2,2,9) s(3,2,6) s(4,2,8) s(5,2,4) s(8,2,1) s(1,3,4) s(2,3,7) s(4,3,5) s(5,3,9) s(6,3,2) s(9,3,8) s(2,4,8) s(3,4,4) s(4,4,1) s(6,4,9) s(9,4,6) s(1,5,1) s(2,5,6) s(3,5,7) s(4,5,2) s(6,5,4) s(7,5,8) s(8,5,9) s(9,5,5) s(1,6,9) s(4,6,6) s(6,6,7) s(7,6,4) s(8,6,2) s(1,7,7) s(4,7,3) s(5,7,1) s(6,7,8) s(8,7,6) s(9,7,2) s(2,8,2) s(5,8,7) s(6,8,5) s(7,8,1) s(8,8,4) s(9,8,3) s(3,9,5) s(4,9,4) s(5,9,2) s(6,9,6) s(7,9,7) s(9,9,9)
SATISFIABLE

Models       : 1
Calls        : 1
Time         : 0.028s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.028s

Voilà, on a résolu un sudoku difficile en trois centièmes de seconde !

Certes, le résultat est pas hyper lisible. Avec ce programme python, il est possible de représenter cet answer set et en faire quelque chose de lisible :

|8|5|4|  |2|1|9|  |7|6|3|
|3|9|7|  |8|6|5|  |4|2|1|
|2|6|1|  |4|7|3|  |9|8|5|

|7|8|5|  |1|2|6|  |3|9|4|
|6|4|9|  |5|3|8|  |1|7|2|
|1|3|2|  |9|4|7|  |8|5|6|

|9|2|6|  |3|8|4|  |5|1|7|
|5|1|3|  |7|9|2|  |6|4|8|
|4|7|8|  |6|5|1|  |2|3|9|

Bon, ben voilà. On a bien travaillé.

Benchmark

En utilisant l'option --time-limit de clingo, j'ai pu comparer les deux implémentations : celle sans contraintes génère 299857 modèles en 30 secondes. L'autre, avec des contraintes, en trouve 315212, soit 5% de plus. Elle semble donc un poil meilleure.

Ce speed-up est dû au fait que, dans le cas avec contraintes, le solveur doit travailler avec moins de règles pour généner un answer set. Il les génère donc plus rapidement. De plus, les contraintes sont peu coûteuses, donc s'applique assez vite. D'où un speed-up général.

Merci les contraintes !

Placement de table, première approche

Lors d'une fête de famille, ils y a deux problèmes majeurs :

• qui finit les frites ?
• qui s'assoie où à table ?

C'est bien entendu le second qui nous intéresse ici.

Spécification du problème

L'idée est la suivante : nous avons un ensemble de places numérotées, et des relations entre elles. Par exemple : la place 2 est à côté des places 1 et 3, et en face de la place 9.

Nous avons également des personnes, qui doivent toutes être placée sur une place exactement.

Maintenant, il y a des contraintes. Par exemple :

• Christine et Dominique ont des places atitrées.
• Marise et Cunégonde ne veulent pas être près de la cuisine pour éviter d'avoir à y aller.
• Christine ne supporte pas Yolande et Michel.
• Mettre Gérard à côté de Michel et Richard est en revanche conseillé : ensembles ils font rire leurs voisins avec leurs histoires de championnat de scuba-curling.
• Si Christine peut voir Dominique, elle lui fera des remarques bruyantes et désagréables sur sa frange mauve : donc non.
• Yolande ne veux pas être à côté de Richard car il écarte beaucoup les bras en mangeant.
• Marise veut être à côté de l'un des membres de sa fratrie (Cunégonde et Roger).

Bref, le joyeux bordel typique du placement de table d'une réunion de famille. Eh bien, rassurez-vous : ce calvaire est fini, vous pouvez annoncer à votre famille que désormais c'est vous qui vous en occupez ! Et ça ne vous prendra pas bien longtemps pour tout encoder parfaitement, et placer les étiquettes indiquant les positionnement des gens. Il ne restera donc plus qu'à vous faire mousser pour ce placement de table par-fait !

Objectifs

Avoir pour chaque personne une place qui lui convienne.

Avoir plusieurs modèles/ensembles réponse, chacun décrivant un positionnement possible.

Pourquoi une première approche

Il est sous-entendu qu'une seconde approche se fera, plus tard. Effectivement, cette première approche est naïve : elle considère qu'il existe une solution qui satisfasse toutes les contraintes. Si vous avez une famille avec beaucoup de contraintes, il est possible que le problème soit insatisfiable, et par conséquent, certaines contraintes doivent être retirées.

Il existe une solution élégante à ce problème, grâce aux directives de méta-programmation, et plus précisément les optimisations, que nous verrons plus tard.

C'est donc dans la deuxième volée d'applications que nous verrons une approche plus maligne qui nous permettra de gérer les familles trop compliquées. Cela dit, même si votre famille est compliquée, il est possible qu'une solution existe : alors essayez avec la pelle avant d'amener le bulldozer, vous pourriez être surpris.

Les humains

Ça, c'est facile : c'est l'ensemble des humains que l'on veut placer.

human(roger;cunegonde;marise;michel;yolande;dominique;gerard;richard;christine).

La table

Décrivons la table, ou plus exactement les places disponibles :

% Il y a neuf places.
place(1..9).
% Deux places sont à côté si consécutives.
next(X,X+1):- place(X) ; place(X+1).
next(1,9).  % la table est circulaire.
% Les places qui sont en face.
face(2,9;3,8;4,7;5,6).
% Les places qui sont proches.
proche(X,Y):- next(X,Y).
proche(X,Y):- face(X,Y).
% Les places alignées.
rangee(2,3;3,4;4,5).
rangee(6,7;7,8;8,9).
% Réversibilités.
next(X,Y):- next(Y,X).
face(X,Y):- face(Y,X).
rangee(Y,X):- rangee(X,Y).
rangee(X,Y):- rangee(X,Z) ; rangee(Z,Y).
% places situées à des endroits particuliers.
cheminee(5;6).
cuisine(1;10).

Génération de placements

Maintenant, décrivons un placement de table : on associe une place à chaque personne, et une personne maximum à chaque place (on autorise une place vide, si il y a plus de places que de personnes).

0 { place(N,H): human(H) } 1 :- place(N).
1 { place(N,H): place(N) } 1 :- human(H).
#show place/2.

Maintenant, si on lance le programme, on obtient TOUS les placements possibles. Hors, et c'est bien ce qui pose problème, on ne veux que ceux qui respectent les contraintes vues plus haut.

C'est parti !

Encoding des contraintes

C'est pratique : un placement de table est équivalent à un modèle. Cela veux dire que notre objectif maintenant, c'est d'écrire des contraintes pour écarter les modèles qui ne nous intéressent pas… C'est parti !

D'abord, rendons-nous service et définissons des contraintes sur pas_copain/2 et copain/2, qui nous permettrons de générer automatiquement les contraintes pour les cas simples (machin veut (pas) être à côté de bidule) :

% Quand deux personnes sont pas copains, il faut éviter qu'elles soient à côté.
:- pas_copain(H1,H2) ; place(X,H1) ; place(Y,H2) ; cote(X,Y).

% Quand deux personnes sont copains, il faut les placer à côté.
:- copain(H1,H2) ; place(X,H1) ; place(Y,H2) ; not cote(X,Y).

Maintenant, on peut traduire les contraintes vues plus haut :

% Christine et Dominique ont des places atitrées.
1{place((6;9;2;5),christine)}1.
1{place((6;9;2;5),dominique)}1.

% Gérard doit être placé à côté de Michel et Richard.
copain(gerard,(richard;michel)).

% Mais Dominique ne doit pas être à côté de Christine.
pas_copain(dominique,christine).
% Pire : ces humains ne doivent même être sur la même rangée, pour être sûr qu'ils ne se voient pas !
:- place(X,dominique) ; place(Y,christine) ; not rangee(X,Y).

% Christine ne supporte pas Yolande et Michel.
pas_copain(christine,(yolande;michel)).

% Marise, Cunégonde et Roger sont frères et sœurs.
soeur(marise;cunegonde;roger).
% Marise veut être à côté de l'un des membres de sa fratrie.
:- place(X,marise) ; place(Y,FS):soeur(FS) ; next(X,Y).

% Yolande ne veux pas être à côté de Richard car il travaille dans l'aviation.
:- place(X,yolande) ; place(Y,richard) ; not next(X,Y).

% Marise et Cunégonde ne veulent pas être près de la cuisine.
:- place(X,marise) ; not cuisine(X).
:- place(X,cunegonde) ; not cuisine(X).

Résultats

Et voici les 8 modèles (trouvés en deux centièmes de seconde) :

clingo version 5.2.2
Reading from table.lp
Solving...
Answer: 1
place(2,dominique) place(5,christine) place(3,yolande) place(8,michel) place(4,richard) place(7,gerard) place(9,cunegonde) place(1,marise) place(6,roger)
Answer: 2
place(2,dominique) place(5,christine) place(8,yolande) place(3,michel) place(7,richard) place(4,gerard) place(9,cunegonde) place(1,marise) place(6,roger)
Answer: 3
place(2,christine) place(5,dominique) place(7,yolande) place(4,michel) place(8,richard) place(3,gerard) place(9,cunegonde) place(1,marise) place(6,roger)
Answer: 4
place(2,christine) place(5,dominique) place(4,yolande) place(7,michel) place(3,richard) place(8,gerard) place(9,cunegonde) place(1,marise) place(6,roger)
Answer: 5
place(2,christine) place(5,dominique) place(7,yolande) place(4,michel) place(8,richard) place(3,gerard) place(9,marise) place(6,roger) place(1,cunegonde)
Answer: 6
place(2,dominique) place(5,christine) place(8,yolande) place(3,michel) place(7,richard) place(4,gerard) place(9,marise) place(6,roger) place(1,cunegonde)
Answer: 7
place(2,christine) place(5,dominique) place(4,yolande) place(7,michel) place(3,richard) place(8,gerard) place(9,marise) place(6,roger) place(1,cunegonde)
Answer: 8
place(2,dominique) place(5,christine) place(3,yolande) place(8,michel) place(4,richard) place(7,gerard) place(9,marise) place(6,roger) place(1,cunegonde)
SATISFIABLE

Models       : 8
Calls        : 1
Time         : 0.019s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.019s

Approche iterative

La recherche des contraintes (ce moment où vous vous interrogez sur qui ne doit pas être à côté de qui) n'est pas nécessairement un travail à faire avant leur encoding. Personnellement, lorsque j'utilise ce genre de programme, je le fait avec d'autres personnes, et les contraintes viennent en discutant. On ajoute une contrainte, puis on regarde une solution. C'est là que machin dit : «nan, mais il est nul ton programme, je suis à côté de bidule mais j'ai pas envie». Donc j'ajoute la ligne pas_copain(machin,bidule), je redonne une nouvelle solution. Et le manège recommence, jusqu'à ce que, au choix :

• machin n'arrive plus à trouver de contraintes pour mettre en défaut le programme (parce que machin ne croit pas une seule seconde qu'un ordinateur soit capable de résoudre un problème de logique mieux qu'un humain, ça heurte son égo)
• machin comprenne l'intérêt du programme, et dise «et si on ajoute une contraite qui…» plutôt que «il est nul ton programme»

Bref, aux humains près, ce genre de recherche est souvent itérative : on regarde une solution, on dit pourquoi on l'aime pas, on le formalise, et on relance. Et quand il n'y a plus de solutions possible, c'est le moment où il faut relaxer des contraintes.

Dans le turfu

Cette application d'ASP est simple et directe ; d'autant plus que normalement, la famille ne change pas trop entre deux repas, et comme on ne change généralement pas de table si souvent non plus… Le programme est réutilisable !

Et pas que avec les repas de famille : il marche également avec les places au cinéma, les soirées entre amis, les réunions de confrères de secte, les barbecues entre collègues, les fêtes des voisins, le pot de la chorale… C'est fou l'informatique.

On peut facilement imaginer la suite de cette application : faire une interface pour pouvoir définir les places, les contraintes, et voir les solutions. Faites ça sur mobile, et voilà, vous avez une application portable de placement de table complète que vous pouvez vendre. N'oubliez pas de faire une distribution pour ordinateur normaux, histoire de pouvoir travailler sérieusement sur les placement de table importants, comme les mariages, où on atteint vite la centaine de personnes (je vous ai déjà dit que j'aimais pas les ordiphones ?).

Dans la même veine, vous pouvez vous intéresser au placement des gens dans votre lieu de travail, en prenant en compte les préférences de chacun en matière de cohabitation professionnelle. C'est un travail que j'ai attaqué avec le projet Cathplace, qui propose notamment une interface graphique pour visualiser les résultats.

Métaprogrammation

Où l'on apprend que bien des choses sont possibles avec juste un petit zest de méta(l)

Métaprogrammation est un mot qui peut faire peur, un peu comme nombre complexe en maths, ou staphilococus en cours de phylogénie. Mais en vrai, ça va.

Clingo (gringo) est capable de comprendre un sur-ensemble de l'ASP qui relève de la méta programmation. Autrement dit, il existe des expressions valides qui ne sont pas de l'ASP, mais qui permettent de manipuler le grounding ou le solving du programme (c'est donc méta).

Ces expressions ce nomment directives de métaprogrammation, et commencent systématiquement par un # (elles sont donc faciles à reconnaître).

Nous allons ici voir les plus utiles. Pour plus d'exhaustivité, je vous renvoie au manuel de clingo.

#show

Il s'agit probablement de la directive la plus utilisée : il s'agit de déterminer quels atomes seront affichés dans la sortie de clingo.

En effet, pour chaque answer set, clingo donne la liste complète des atomes vrais. Dans certains cas, notamment quand vous avez beaucoup de données et d'atomes intermédiaires, seuls quelques uns vous intéressent.

Par exemple, si vous codez un programme de placement de table, les données (les humains qui sont copains, les noms des humains,…) ne changent pas, sont constantes d'un answer set à l'autre : vous ne voulez pas les afficher.

C'est là que #show intervient.

a(1;2;3).
b(X):- a(X).
#show b/1.

En runnant ce programme, avec ou sans la dernière ligne, vous allez avoir exactement 1 modèle/answer set, contenant 3 ou 6 atomes selon les cas.

Pour être plus rigoureux, dans les deux cas les atomes vérifiés dans le modèle sont strictement identiques, c'est juste qu'avec la dernière ligne, seuls 3 sont affichés (ceux ayant b comme prédicat). #show change les atomes affichés, pas les answer sets.

Notez la manière dont on renseigne l'ensemble des atomes de prédicat b: en utilisant une notation très courante dans le monde de la programmation logique: <prédicat>/<arité>. Si vous remplacez le 1 par un 2, clingo n'affichera rien : il va en effet afficher uniquement les atomes de prédicat b avec deux arguments, c'est-à-dire, dans ce cas précis, aucun.

Un truc rigolo

Regardez, ce programme fait bugger clingo ! Il lui fait afficher 3 fois la même réponse ! Alors que normalement c'est pas possible, on l'a vu dans une section précédente !

1{a(1..3)}1.
#show.
#show b.

Bon, vu que vous avez lu le paragraphe sur #show, vous ne vous êtes pas fait avoir : ce n'est pas trois answer set équivalents, mais 3 différents qui sont affichés pareil.

Bon, pour le moment, les deux dernières lignes semblent assez inexplicables, alors allons explorer les subtilités de cette directive.

Le côté obscur de #show

Le programme suivant affiche 4 atomes, et aucun d'entre eux ne fait réellement partis du modèle trouvé par le solveur.

b(1).
#show b.
#show 23.
#show p(X): b(X).

Nous voyons ici trois usages différents de show. Le premier et le second sont des moyens d'afficher des données, y comprit des nombres.

Le troisième montre qu'il est possible de faire quelques opérations logiques sur les règles à montrer. Cela peut servir pour filtrer précisément les atomes à afficher, ou pour renommer les atomes (ici, on renomme b/1 en p/1).

Notez bien que ces usages de show sont génératifs : ils ajoutent des atomes dans la réponse, sans les ajouter dans le solving lui-même (essayez en ajoutant c(X):- p(X)., vous verrez que c/1 n'appartient pas à l'answer set, car aucun p/1 ne s'y trouve).

Notez également que, contrairement à l'usage précédent, le show ici n'a pas empêché les autres atomes du programme d'être affichés, car b(1) est bien affiché par clingo. C'est parce que tous les shows du programmes sont génératifs. Rajoutez en un seul qui ne le soit pas, et vous perdez b(1).

Le #show impératif

Il existe une dernière forme pour cette directive : #show.. Elle se traduit par n'affique strictement que ce qui est demandé.

Par exemple, si tous les shows de mon programme sont génératifs (cf section précédente), comment faire pour n'afficher que ceux-là, et pas le reste du programme ?

a.
#show 23.

Ce programme va afficher dans l'unique modèle les atomes a et 23. Maintenant, si j'ajoute #show. quelque part…

a.
#show.  % par exemple, ici
#show 23.

Paf ! Seul 23 est affiché. Pourquoi ? Parce que a n'a pas été explicitement rattaché à un show, et n'est donc pas affichable.

En général, les directives #show se trouvent en fin de fichier (du point de vue de l'humain, c'est la dernière chose qui est faite), et le premier show est généralement #show.. C'est une habitude qu'on retrouve dans beaucoup de codes ASP.

Cependant, ils se retrouvent parfois au tout début, pour que le lecteur sache tout de suite quelles sont les outputs. Malin !

#const

Comme C utilise #define et const, clingo utilise un mélange des deux : #const. Là s'arrête le parallèle, et commence un exemple :

#const ma_constante_avec_un_nom_a_rallonge = 42.
#const m_constnte_sns_l_lettre_ = "a".

a(m_constnte_sns_l_lettre_).
a(ma_constante_sans_la_lettre_b).
p(X):- X=ma_constante_avec_un_nom_a_rallonge.
#show ma_constante_avec_un_nom_a_rallonge.

Nous avons ici deux constantes, nommées ma_constante_avec_un_nom_a_rallonge et m_constnte_sns_l_lettre_, associées aux valeurs 42 et "a", respectivement.

Le #const se comporte comme le #define du C: lors du grounding, toute occurence du nom de la constante sera remplacée par sa valeur.

Et tout comme le #define en C, il peut être réécrit lors de l'appel au compilateur. Dans notre cas, lors de l'appel à clingo.

Ainsi, si vous voulez définir la valeur d'une constante lors du lancement du programme, il suffit d'utiliser l'option -c : clingo -c ma_constante_avec_un_nom_a_rallonge=23. Il s'agit donc d'un excellent moyen de proposer une personalisation d'un programme sans avoir à tripoter le code.

Enfin, notez que tout comme le préprocesseur du C, clingo est malin :

#const cst = b.
cst(cst).

Ce code génère un answer set d'un atome qui est… cst(b), car #const agit sur les valeurs, pas les prédicats.

pause détente

Quel est le style de musique préféré des programmeurs lisp ?

Le heavy-méta.

#minimize et #maximize

Le nerf de la guerre dans bien des problèmes dits d'optimisation.

Les answer sets trouvés par le solveur ne sont pas toujours égaux : souvent, l'objectif est de maximiser ou minimizer un score, et cela permet de trier les bonnes et les mauvaises solutions.

Par exemple, si vous créez un solveur de puzzle, vous allez vouloir préférer les solutions qui utilisent le moins de ressources (nombre de coups, nombre de pièces, nombre de je-sais-pas-quoi-que-le-puzzle-utilise-et-qu'on-veut-utiliser-le-moins-ou-le-plus-possible,…).

Dans un autre registre, c'est ce qui nous permettra, dans les prochains exemples, de trouver le meilleur PC selon des contraintes diverses.

En général, à partir du moment où vous cherchez le plus bidule ou le moins machin, vous avez besoin d'une minimisation ou maximisation. (parfois ce ne sera pas nécessaire, mais gardez l'idée à l'esprit)

Considérations techniques

En soit, ça ne change pas grand chose sur le solving, puisqu'en théorie, il suffit de générer toutes les réponses, puis les trier selon leur score.

L'inconvénient, c'est qu'il faut (1) énumérer tous les réponses, ce qui n'est pas forcément pratique (essayez donc de générer et sauvegarder l'ensemble des grilles de sudoku pour voir), et (2), trouver le maximum là-dedans a posteriori, c'est-à-dire sans que l'heuristique du solveur n'ait joué de rôle.

Hors, et c'est bien là tout l'intérêt d'une heuristique faite par des experts : si on donnait la mesure du score à l'heuristique, elle ne se contenterait pas d'énumérer les réponses possibles et de les triers par score : elle s'abstiendrait de générer celles qui sont moins bonnes que celles déjà générées (on parle d'élaguage de l'espace de recherche).

En d'autre terme, donner à l'heuristique nos préférences en matière de modèle lui permet d'élaguer l'espace de recherche pour aller plus vite, et se diriger petit à petit vers l'une des meilleure réponse, le modèle optimal.

Syntaxe

La syntaxe est un poil bizarre au début, mais on s'y fait bien.

1 { nb(1..100) } 1.  % un modèle == un entier
#maximize{N:nb(N)}.  % maximiser l'entier choisi

Ici, c'est la deuxième ligne qui fait le travail d'optimisation : on dit à clingo de maximiser N, pour N le nombre choisi en ligne 1.

Il y a beaucoup de subtilités avec cette syntaxe, essayez par exemple de changer la borne supérieure de la disjonction par un 2, ou par rien.

Notez aussi que, pour minimiser, il suffit de remplacer maximize par minimize.

Priorité

Parfois, il y a plusieurs paramètres à minimiser/maximiser.

1 { nb(1..100) } 1.  % un modèle == un entier
#minimize{N@2:nb(N)}.  % minimiser l'entier choisi (priorité 2)
#maximize{N@1:nb(N)}.  % maximiser l'entier choisi (priorité 1)

Considérations générales

Les optimisations, qu'elles soient de maximisation ou minimisation, sont des composantes importantes de l'heuristique : non seulement elles permettent d'élaguer l'espace de recherche, mais elles permettent de réellement encoder certains problèmes sans avoir à modéliser les relations entre modèles.

Imaginez devoir générer le meilleur remplissage de sac-à-dos sans optimisation : même avec un petit sac, il existe une très grande quantité de manière de ranger des objets dans un sac, et surtout, beaucoup sont équivalentes. Sans optimisations, vous allez vous retrouver avec (1) un très grand nombre de modèles qui (2) sont inintéressants pour 99% d'entre eux.

Avec une optimisation, vous n'avez qu'à compter la place restante dans le sac, et minimiser ce nombre : le solver s'occupe seul de ne pas polluer la sortie : le dernier modèle trouvé par le solveur est à tout instant le meilleur qu'il ait trouvé. Cela veux même dire que vous pouvez l'arrêter en cours de route, lorsque les modèles qu'il propose sont suffisamment bons.

Dernier mot pour cette section : il existe bien d'autres directives de métaprogrammation.

#sum

Dans la série des directives utiles, #sum a une place de choix : elle permet d'additionner. Pourquoi aurait-on besoin d'une telle directive alors qu'on a déjà l'opérateur + ? Cas typique : vous voulez ajouter les valeurs contenues dans le premier argument des atomes val/1. Comment vous faites avec un + ? Ben, vous faites pas. ou alors, de manière très compliquée:

% les valeurs à additionner
val(1;3;18;23;42;67;72).

% On prend le plus petit d'abord.
first(X):- val(X) ; not val(Y): val(Y), Y<X.
% On détermine le suivant, celui qui est juste supérieur.
next(X,Y):- val(X) ; val(Y) ; X<Y ; not val(Z): val(Z), X<Z, Z<Y.
% Maintenant, on parcours la liste, et on additionne au fur et à mesure.
sum(1,F,F):- first(F).  % à l'étape 1, la valeur est celle du premier
sum(N+1,W,T+W):- sum(N,V,T) ; next(V,W).  % à l'étape n, la valeur est celle de l'étape n-1 plus la valeur de l'étape n
step(S):- sum(S,_,_).
% Et la somme, c'est la dernière somme réalisée.
sum(S):- sum(N,_,S) ; not sum(M,_,_): step(M), N<M.
#show sum/1.  % on est fier de notre résultat !

C'est un poil complexe, et surtout ça pollue pas mal le code avec des noms d'atomes généraux. Pas super, donc.

C'est là où #sum entre en jeu ! Voyez plutôt :

% les même données initiales
val(1;3;18;23;42;67;72).

% On additionne !
sum(S):- S=#sum{V: val(V)}.
#show sum/1.  % on est fier de notre résultat !

Et évidemment, ça vient avec la flexibilité d'ASP :

% les données, cette fois-ci réparties en deux groupes
val(a,1;b,3;a,18;b,23;a,42;b,67;a,72).

% récupération des groupes
group(G):- val(G,_).

% On additionne pour chaque groupe, indépendamment.
sum(G,S):- S=#sum{V: val(G,V)} ; group(G).
#show sum/2.  % on est fier de nos résultats !

La syntaxe réelle de #sum

En fait, la syntaxe de #sum est un poil plus générale. Regardons un exemple avec le sum étalé sur plusieurs lignes :

#show N:N=#sum{
    10: a;  % si a est vrai, ajouter 10
    20: b;  % si b est vrai, ajouter 20
    30;     % sans condition, ajouter 30
    40: not a  % si a est faux, ajouter 40
}

La logique est assez simple : #sum va ajouter des choses en fonction des conditions qui lui sont données. Ainsi, si vous lancez ce code tout seul, vous obtiendrez 70 (30 + 40). Si vous ajoutez l'atome a, vous aurez 42, ou 62 si b est vrai aussi. Ou encore 50 si seul b est vrai.

Variables

Maintenant, quand j'écris par exemple :

valeurs(1,10;2,20).
total(S):- S=#sum{N: valeurs(U,N)}.

Le grounder va faire son job, i.e. étendre la somme pour toutes les valeurs de variables possibles :

total(S):- S=#sum{
    10: valeurs(1,10);
    20: valeurs(2,20)
}.

On obtient bien un total de 30. Super. Maintenant, changeons légèrement les données :

valeurs(1,10;2,10).
total(S):- S=#sum{N: valeurs(U,N)}.

Et là, on lance et on obtient un total de… 10 ?! WTF ?!

Gérer les valeurs égales

Il y a un point noir dans l'exemple précédent. Regardons comment le grounder va étendre l'expression :

total(S):- S=#sum{
    10: valeurs(1,10);
    10: valeurs(2,10)
}.

A priori, rien de fou : on a des valeurs (ici, deux fois 10), et on cherche à les ajouter pour avoir la valeur totale. Sauf que, quand je lance clingo dessus, j'obtiens :

Solving...
Answer: 1
contrainte(1,10) contrainte(2,10) score(10)
SATISFIABLE

Quoi ?! Un total de 10 ? Ça n'a aucun sens ! Eh bien, en fait, c'est dû au fonctionnement interne d'ASP. Vous vous souvenez ? ASP ne sait pas ce qu'est une liste. Il ne travaille que sur des ensembles.

il va donc ignorer l'un des deux 10, même s'il n'ont pas la même condition, si bien que pour lui l'expression du sum devient #sum{10: valeurs(1,10)}, et donc atteint un total de 10.

C'est un peu nul, hein ?

Et bien voici une solution :

total(S):- S=#sum{N,U: valeurs(U,N)}.

Notez ici l'importance du N,U:. Maintenant, le grounder arrive à cette expression :

total(S):- S=#sum{
    10,1: valeurs(1,10);
    10,2: valeurs(2,10)
}.

Ça change tout : les valeurs sont désormais différentes. On a donc bien deux valeurs à ajouter : 10,1 et 10,2. Ici, #sum se fiche du second argument pour additionner : il se contente de considérer le premier nombre. On atteint donc 10 + 10 = 20. C'est bien la solution !

L'exemple complet

Voici un exemple simple qui montre les différences de deux approches :

objet(a,1).
objet(b,1).
objet(c,1).
objet(d,2).

total(naif,   T) :- T=#sum{V: objet(_,V)}.
total(correct,T) :- T=#sum{V,O: objet(O,V)}.

#show total/2.

Interface avec Python

Où l'on apprend que l'on peut interfacer un langage puissant avec un langage puissant pour faire des trucs vachement puissants

Vous avez déjà étendu Python avec du C pour gagner un peu en performances ? Eh bien, de la même manière, on peut mettre du Python (ou du Lua) dans ASP pour profiter, pendant le solving même, de la puissance d'un langage impératif.

ASP s'interface nativement avec Python et Lua. Je n'en traiterais pas beaucoup ici, mais plutôt dans des quêtes annexes qui apparaîtrons petit à petit.

Pour ces annexes, je considère python comme un langage acquis. Il me faudrait 5000 lignes supplémentaires pour expliquer les concepts que j'utilise ici, et du coups ce tuto deviendrait un énième tuto pour python. Si c'est juste les concepts de POO qui vous manquent, allez voir sametmax. Si vous connaissez déjà python et que vous voulez progresser, allez voir sametmax.

Le reste de cette section est là pour donner une vue générale de ce qu'il est possible de faire avec python ou lua.

Extending d'ASP

La première manière de coupler les langages, c'est de mettre du python/lua dans ASP.

Cela nécessite d'avoir compilé clingo avec les bonnes librairies (avec clingo --version vous pouvez voir si votre clingo supporte l'un ou l'autre des langages), et permet de faire plein de choses rigolotes qui seront présentées dans des annexes.

Pour donner juste une intuition de l'usage, voilà un code où l'on donne un identifiant unique à des atomes :

% Données en entrée
atom(a;b;c;d;e).

% Le script python, qui va définir la fonction gen_id
#script(python)
import itertools
gen = itertools.count(1)

def gen_id():
    "retourne un nouvel identifiant"
    return next(gen)
#end.

% On donne à chaque atome son identifiant, en utilisant la fonction gen_id.
uid(V,@gen_id()):- atom(V).  % le préfix @ permet d'indiquer qu'il s'agit d'une fonction python
#show uid/2.

On utilisera python pour se simplifier la vie sur une application dans une prochaine section.

Embedding dans Python

L'autre manière pour coupler les deux langages, c'est de faire l'inverse : mettre ASP dans Python.

Par exemple, plutôt qu'appeler clingo pour tous nos cas de tests, et vérifier à la main si ils fonctionnent correctement, on peut faire un programme python qui va faire ça tout seul. Aussi, si on a besoin d'appeler clingo plusieurs fois avec des traitements des résultats, il est possible de le faire depuis Python.

API officielle

Il existe un module officiel, qui est dans les sources du logiciel et que vous pouvez installer avec un python setup.py install standard après compilation de clingo.

La doc est ici, et permet de faire tout ce que vous voulez : propagateurs, manipulation du grounding/solving, programmes,…

Je n'utilise pas cette API en règle générale, puisqu'il faut que le client compile clingo avec le support python, ça demande parfois du boulot. C'est pourquoi il existe d'autres moyens.

Autres API

Je vous recommande pour démarrer clyngor. C'est un module python on ne peut plus standard, disponible sur pypi, et qui ne nécessite qu'une chose: que le binaire clingo soit dans votre PATH.

Et normalement, c'est déjà fait si vous l'avez installé proprement :)

(Il y aura probablement une quête annexe sur clyngor, parce qu'il offre bien plus que juste une récupération des solutions)

Une alternative est pyasp. Néanmoins, ce package ne supporte pas clingo seul, mais plutôt gringo et clasp comme deux binaires séparés appelés séquentiellement. Hors, dans les nouvelles versions du solveur, seul clingo est distribué. Pyasp n'est donc (pour le moment) pas une alternative viable pour utiliser les versions les plus récentes.

Conseils de style

Où l'on s'imagine tel Gotlib mesurer au pouce cette pomme qu'il ne dessina jamais, mais en fait, non, ça n'a que peu à voir

Cette partie est légère et calme : il s'agit de donner quelques conseils pour écrire de beaux codes. Bien sûr, la beauté est subjective, et peut-être ces conseils seront-ils à jeter à la poubelle d'après une autre personne.

Ceci est vrai pour tous les langages en informatique : le style est quelque chose de subjectif. Plus encore, c'est quelque chose qui dépend d'avec qui vous travaillez, et aussi du genre de code qui est écrit.

Certains languages ont la chance d'avoir un guide officiel, comme la PEP8 en python, d'autres non. Certains languages ont une très forte culture de liberté de style, comme perl, d'autres non.

Bref, c'est au cas par cas. Mais en général, les conseils suivants s'appliquent :

• avoir un style consistant dans une base de code
• privilégier la lecture à l'écriture

Le premier est simple : il faut conserver la même manière d'écrire les choses (et de les nommer ; ça fait aussi partie du style). Le second est plus compliqué, mais se retranscrit assez simplement : le nom de variable i est nul. Le nom index est mieux. Sauf quand ça rend le code illisible. Mais là encore c'est subjectif.

Suivent donc quelques conseils de style pour les codes ASP.

Premières lignes

Une volée de commentaires au début du code, expliquant le pourquoi du code, les entrées, les sorties, le comportement attendu,… Ça semble évident, mais souvent «on oublie», parce que c'est chiant.

Pourtant, je ne saurais trop vous conseiller de prendre l'habitude d'écrire ça en premier. Savoir exactement ce que l'on a et ce que l'on veut, c'est 50% du travail de modélisation. Ça fixe les idées et aide à réfléchir.

Commentaire d'accompagnement

Avant chaque règle (ou choix, ou contrainte), expliquer en commentaire ce qu'elle fait, à haut-niveau. Pas la peine de répéter le contenu de la règle, mais expliquer ce qu'elle fait en gros permet d'avoir sans réfléchir le sens derrière une ligne de code.

% Les oiseaux volent.
fly(X):- bird(X).

Aération

Laisser une ligne entre chaque règle (avec le commentaire qui l'accompagne), et laisser deux lignes pour marquer une grosse séparation, typiquement entre deux parties qui n'ont rien à voir.

% Les oiseaux volent.
fly(X):- bird(X).

% Le feu ne mouille pas.
not wet(X):- on_fire(X).


% Je m'appelle Jean-Christophe.
name(me,"Jean-Christophe").

Ordre logique

Souvent, les programmes sont divisés en plusieurs sous-parties logique, comme par exemple données, expansion, modélisation, contraintes et affichages.

A moins qu'elle ne soit placées dans un fichier dédié (ce qui est généralement préférable), les données doivent être bien séparées du reste. C'est la partie mouvante du programme, dans le sens où il ne s'agit que d'une instance d'un problème général que le programme tente de résoudre. Indiquer en commentaire le sens de ces données est également une bonne idée.

L'expension est un ensemble de règles qui permettent d'obtenir des données des informations qui seront nécessaires pour la modélisation. C'est une étape souvent inutile, car les données sont généralement bien faites de base. Mais dans certains cas (que nous rencontrerons après), il peut être intéressant de permettre des écritures simplifiées dans les données, qui seront expansées après.

La modélisation est, comme vous vous en doutez, l'ensemble de règles et choix qui implémentent la solution au problème et génèrent les solutions candidates. Parfois, les contraintes font parties intégrantes de la modélisation, et ne devraient donc pas en être dissociées. En effet, si l'ordre dans lequel les règles sont écrites ne compte pas pour le résultat, il vaut mieux qu'elle soient correctement ordonnée pour le lecteur humain. Ainsi, si une contrainte fonctionne de concert avec une règle, il est souvent plus clair de ne pas les séparer.

Les affichages (#show) viennent souvent en dernier, car cela est assez logique, mais notez que ce n'est peut-être pas la meilleure solution. Une bonne autre position pour les affichages serait… tout au début ! À côté des commentaires en premières lignes, qui indiquent les entrées du programme. Avec les #show marqués explicitement, la documentation est réellement exhaustive, et ne fait pas doublon avec le code ! Merci ASP : c'est génial de pouvoir placer les lignes où l'on veut !

Des longueurs dans le texte

Évitez les lignes trop longues : elles sont illisibles, sont cassées par les éditeurs, ou nécessitent de scroller vers la droite : c'est pas un bon deal. À la place, cassez vos règles, et usez des sauts de lignes pour étaler vos règles trop longues à la vertical, pas à l'horizontal.

je_suis_content :- passe_moi(le_beurre) ; passe_moi(le_sel) ; passe_moi(le_poivre) ; passe_moi(le_pain) ; passe_moi(le_couteau(beurre)) ; passe_moi(le_saussisson) ; passe_moi(le_couteau(saussisson)) ; passe_moi(les_cornichons) ; passe_moi(la_fourchette(cornichons)).

Est plus lisible lorsqu'écrit ainsi :

je_suis_content :-
    passe_moi(le_sel) ; passe_moi(le_poivre) ; passe_moi(le_pain) ;
    passe_moi(le_beurre) ; passe_moi(le_couteau(beurre)) ;
    passe_moi(le_saussisson) ; passe_moi(le_couteau(saussisson)) ;
    passe_moi(les_cornichons) ; passe_moi(la_fourchette(cornichons)).

C'est d'autant plus pratique que l'on peut maintenant commenter chacun des groupes de passe_moi/1, plutôt que tout commenter d'un coups avant ou après.

Point-virgule et virgule

Ces deux caractères indiquent la même chose : le et logique. Cependant, ils n'ont pas la même priorité.

a:- b, c. et a:- b ; c. sont strictement équivalents. Mais, préférez le ; pour une raison simple :

a(X):- val(X) ; b(X): c(X), d(X). n'a pas du tout le même sens que a(X):- val(X) ; b(X): c(X) ; d(X). !

Essayez avec les données val(1..9).b(1;2).c(1;2).d(1)..

Dans le premier cas, d(X) appartient à l'expression b(X): c(X), d(X), qui est toujours vraie (b(X) est vrai lorsqu'on a c(X) et d(X)). Dans le second, il n'y appartient pas, et est donc une condition supplémentaire, qui n'est vraie que pour d(1).

Donc, mon conseil : utilisez toujours le point-virgule, sauf lorsque vous devez utiliser une virgule. Ça vous évitera d'avoir à retaper toutes vos virgules si l'un des terme d'une condition devient une expression pour tout (∀), et en plus, ça permet une cohérence générale, qui souvenez-vous est l'une des deux règles fondamentales du style.

Real-world application

Où, enfdeux, on touche du doigt l'intérêt d'être entré dans le monde merveilleux de l'ASP

Une nouvelles volées d'applications, prenant parti de nos dernières découvertes sur la métaprogrammation et l'embedding de Python.

Placement de table, seconde approche

Après la première approche vient… la seconde approche !

Nous avons vu le placement bourrin de table, où l'objectif était de satisfaire toutes les contraintes. Ça marche le plus souvent, mais si votre famille est trop compliquée, ça marche plus : le problème est juste insatisfiable, il n'y a aucun moyen d'atteindre un placement idéal.

Maintenant, plutôt que des contraintes, nous pourrions modéliser un score à maximiser.

Intuitivement, ce n'est pas tant qu'il faille que Tata Christelle et Tonton Robert soient à côté : c'est juste mieux. De fait, une telle combinaison augmenterais le score. À l'inverse, mettre Gérard le Normand et Michel le Breton l'un en face de l'autre, c'est lourd, mais c'est pas non plus une catastophe, donc on diminue le score.

L'intérêt est double : on va pouvoir hierarchiser les contraintes (toutes n'ont pas la même importance ; et à la limite les plus importantes peuvent rester des contraintes), et on va pouvoir gérer des familles très compliquées, tellement compliquées que toutes les contraintes ne sont pas satisfiable simultanément.

Contraintes avec score

En soit, il n'y a pas grands changements : plutôt que faire des contraintes simples comme celle-ci :

:- pas_copain(H1,H2) ; place(X,H1) ; place(Y,H2) ; proche(X,Y).

On va définir des poids :

contrainte(1,-10):- pas_copain(H1,H2) ; place(X,H1) ; place(Y,H2) ; proche(X,Y).

Indiquant que la contrainte 1 à un poids de -10 (donc si elle est vrai, elle retire 10 points au score).

Unicité des contraintes

Cette solution n'est pas parfaite : si j'indique deux fois pas_copain/2 dans mon code, je ne vais avoir qu'une fois contrainte(1,10). Ça, c'est un effet direct du fait qu'ASP manipule des ensembles : un atome ne peux pas être vrai deux fois.

Donc, la solution est la suivante :

% J'utilise toujours pas_copain/2 comme avant.
pas_copain(dominique,christine).

% Sauf que maintenant, je l'étends avec un troisième argument, un identifiant unique :
pas_copain(@gen_id(),X,Y):- pas_copain(X,Y).

% Et le numéro de la contrainte utilise l'identifiant unique pour la contrainte:
contrainte(Uid,-10):- pas_copain(Uid,H1,H2) ; place(X,H1) ; place(Y,H2) ; proche(X,Y).

Notez que l'on utilise la fonction gen_id vue dans la partie sur l'extending d'ASP, mais que ce n'est pas obligé : on pourrait donner les identifiants à la main ; c'est juste plus simple ainsi.

Maintenant que tous nos pas_copain/2 sont convertis en contraintes uniques de poids -10, il nous reste deux choses à faire :

• remplacer toutes les contraintes par des modifications du score (et pas seulement pas_copain/2)
• calculer le score, et le maximiser.

Les autres contraintes

% J'utilise toujours copain/2 comme avant.
copain(gerard,(richard;michel)).

% Sauf que maintenant, je l'étends avec un troisième argument, un identifiant unique :
copain(@gen_id(),X,Y):- copain(X,Y).

% Et le numéro de la contrainte utilise l'identifiant unique pour la contrainte:
contrainte(Uid,10):- copain(H1,H2) ; place(X,H1) ; place(Y,H2) ; not proche(X,Y).

Toutes les contraintes peuvent être converties ainsi. Par exemple, la contrainte sur Dominique et Christine :

% Mais Dominique ne doit pas être à côté de Christine.
pas_copain(dominique,christine).
% Pire : ces humains doivent même être sur la même rangée, pour être sûr qu'ils ne se voient pas !
contrainte(@gen_id(),-40):- place(X,dominique) ; place(Y,christine) ; not rangee(X,Y).

Voyez, les poids sont modifiables selon vos préférences : ici il est vraiment important que Christine et Dominique ne doivent pas se voir. Donc on met un poids de -50.

On peut continuer ainsi sur l'ensemble des contraintes, chacune avec des poids en fonction de l'importance de la chose. On peut ainsi déclarer des «primes» en fonction de certains critère : si je suis à côté de Christine, vu que je l'aime bien : paf, bonus ! (l'idée, c'est que ces bonus soient petits, juste histoire de départager deux solutions équivalentes ; l'autre solution plus propre serait d'avoir un second score à maximiser, mais de priorité moindre)

Calcul du score

On sait que toutes nos contraintes sont de la forme contrainte(UID,POIDS), avec l'UID un nombre unique qui sert juste à permettre d'avoir plusieurs fois une valeur de contrainte, par exemple le -10 si Dominique et Christine sont à côté, et celui de -10 si Michel et Christine sont à côté.

Le POIDS quant à lui est la valeur à sommer, et pour cela, si vous vous souvenez bien, on a vu la directive de méta-programmation #sum :

score(S):- S=#sum{N,U: contrainte(U,N)}.

Notez ici l'importance du N,U, nécessaire si certaines contraintes ont le même poids (toujours le même problème des doublons en ASP).

Maintenant, nous pouvons tout simplement indiquer à clingo qu'il faut maximiser le score :

#maximize{S:score(S)}.

Clingo va donc chercher le modèle qui a le plus grand score. Ce sera le dernier modèle qu'il affichera. Et ce modèle sera le meilleur placement de table possible, selon nos contraintes et leurs poids.

Dans le turfu et plus loin encore

Avec cette méthodologie, il est possible de gérer des groupes de personnes impossibles à placer correctement, ce que ne gérait point la première implémentation avec juste des contraintes.

Maintenant, vous pouvez gérer n'importe quel groupe, et avoir un système de contrainte avec des poids assignés par les gens.

Eh oui : quid d'une appli qui permet à chacun des membres de votre famille de donner ses contraintes, éventuellement sous une forme «humaine» (je suis en discussion avec bidule, je veux bien aider à la cuisine,…), qui les rassemblent toutes, lance le calcul et indique à chacun où il doit se mettre ?

Future is coming !

Choisir l'itinéraire d'un réveil coureur

Un réveil coureur, c'est un réveil qui se met à courir partout lorsqu'il se met à sonner. Intérêt principal : vous devez l'attraper avant de pouvoir l'éteindre. Autant vous dire que c'est efficace pour vous empêcher de vous recoucher, surtout après un coups de tête dans le lavabo et un doigt de pied dans la porte.

Sauf que, aujourd'hui, les réveils coureurs ne sont pas très intelligents : ils courent au hasard, et les développeurs espèrent juste qu'ils s'écrasera pas contre un mur.

Pour cet exemple, nous allons imaginer avoir un robot capable de se représenter dans l'espace en 2 dimensions (c'est déjà de la science-fiction à ce niveau, mais passons). Notre objectif : faire le code qui permettra au robot de savoir où aller, sachant qu'il doit aller réveiller tout le monde dans la maison, et ne s'arrêter qu'au fond du frigo, en étant passé par la cave avant.

Bref, il s'agit d'un parcours de graphe d'un point de départ au point d'arrivée, avec des jalons sur lesquels le chemin doit passer. Notez que le contexte de l'exercice est assez ridicule, mais en vrai, parcourir l'espace et passer par des endroits particulier, c'est une tâche assez standard en IA, très utile pour les jeux vidéos par exemple, ou encore la robotique (robot nettoyeur, drone,…).

Les données

position(1,1).                position(3,1). position(4,1). position(5,1).
position(1,2). position(2,2). position(3,2). position(4,2).
position(1,3). position(2,3).                position(4,3). position(5,3).
position(1,4). position(2,4). position(3,4).                position(5,4).
position(1,5). position(2,5). position(3,5). position(4,5). position(5,5).

Tout simplement, on indique les positions possibles. On en déduira les passages praticables.

milestone(1,5).  % coin en bas à gauche
milestone(5,1).  % coin en haut à droite

Là, les deux endroits par lesquels il faut passer.

start(1,1).
goals((1,1);(5,5)).  % on s'arrête sur l'un des deux

Et maintenant, là où on commence, et là où on doit s'arrêter (notez le choix possible entre deux cibles).

blocked((1,4),(1,5)).  % pas possible de sauter de 1,4 à 1,5

blocked/2 nous permet d'indiquer les chemins bloqués, c'est-à-dire où le réveil coureur ne peux pas passer, même si les positions sont juste à côté.

Avec ces données, on s'attend à avoir la réponse suivante : 11 -> 12 -> 13 -> 24 -> 15 -> 25 -> 34 -> 43 -> 42 -> 51 -> 41 -> 31 -> 22 -> 11.

Solution

#const path_maxlen=100.

% Il y a un arc entre deux position si elles existe et que le passage n'est pas bloqué.
edge((X,Y),(I,J)):- position(X,Y) ; position(I,J) ; |X-I|=0..1 ; |Y-J|=0..1 ; |X-I|+|Y-J|=1..2 ; not blocked((X,Y),(I,J)).
% NB: ça autorise les mouvements en diagonale. Pour les interdire, il faut que |X+Y-I-J| soit égal à 1 strictement

% On créé une position virtuelle, qui sera la cible. Toutes les cibles possibles sont liées à cette position.
%  (ça permet de gérer simplement le fait qu'il y ait plusieurs fins possibles)
edge(G,endgoal):- goals(G).

% Définition du choix d'un chemin du début à la fin.
path(1,(X,Y)):- start(X,Y).
0{path(N+1,E): path(N,S), edge(S,E), S!=endgoal}1:- path(N,_) ; N<path_maxlen.

% Taille du chemin.
pathlen(N):- path(N,_) ; not path(N+1,_).

% Écarter tous les chemin qui ne finisse pas sur le nœud final.
:- path(N,E) ; pathlen(N) ; not E=endgoal.
% Ainsi que ceux qui ne passent pas par un des milestones.
:- not path(_,(X,Y)) ; milestone(X,Y).


% Et maintenant, on minimise la taille du chemin.
#minimize{N: pathlen(N)}.


% Outputs.
#show.
#show path/2.
#show milestone(N,(X,Y)): milestone(X,Y), path(N,(X,Y)), path(M,_), not path(M,(X,Y)), M<N.

Lien vers la solution complète.

Golfing

Le golfing, en informatique, est un jeu qui consiste à réaliser une tâche avec le moins de commande possibles. Par exemple, le vim golfing consiste à changer un texte donné en un autre texte cible (donné également) en utilisant le moins de commande possibles au sein de l'éditeur vim. Il existe aussi le code golf, qui consiste à faire un programme le plus court possible. C'est ça qui nous intéresse ici.

Si vous ne connaissez pas codegolf.stackexchange, il s'agit d'une des instances de stackexchange (la plus connue d'entre elles étant probablement stackoverflow), où les questions sont des challenges de code golf, où des centaines de programmeurs s'amusent à imaginer les programmes les plus courts possible, dans une multitude de langages différents (parfois créés uniquement pour le code golf). Le score correspond au nombre de caractères dans le code ; le but étant de faire le programme le plus court possible, il faut donc minimiser ce score.

Nous allons nous intéresser au calcul de score du boggle, car il est simple et nécessite un peu de python. C'est bon pour l'entraînement.

Nous allons voir qu'il est possible d'atteindre un score certes moins bon que python seul, mais meilleur que les langages les plus verbeux comme java.

Principes

Chaque joueur possède un ensemble de mot uniques d'au moins 3 caractères. Le score d'un joueur est la somme des valeurs de ses mots. Un mot trouvé par un autre joueur vaux zéro. Un mot de 3 ou 4 lettres vaux 1 point. 5 lettres, 2 points, 6 lettres, 3 points, 7 lettres, 5 points, 8 lettres ou plus, 11 points.

Données

Les données seront encodées avec un prédicat qui associe un numéro de joueur et les mots qu'il a trouvé. Les contraintes sur les mots nous servent bien : un mot ne peut pas apparaître plus d'une fois pour un joueur.

Suit le premier exemple donné dans la question :

player(1,("cat";"dog";"bird";"elephant")).  % score: 12
player(2,("bird";"dog";"coyote")).  % score: 3
player(3,("dog";"mouse")).  % score: 2

Calculons ensembles le score du joueur 1: cat donne 1 point, dog et bird ont été trouvés par d'autres joueurs et donnent donc 0 point, et elephant donne 11, soit un total de 12 points pour le premier joueur. De notre point de vue, cela veux dire que nous devons rendre vrai l'atome score(1,12).

Méthodologie

Déjà, nous avons besoin de déterminer quels sont les mots qui compterons pour le score. Une première solution est de dire que 1 et 1 seul joueur à trouvé le mot. L'autre solution est que, sachant un joueur l'ayant trouvé, tous les autres ne l'on pas trouvé.

unique(P,W):- 1 { player(_,W) } 1 ; player(P,W).  % 1 seul joueur l'a trouvé
% ou, c'est équivalent :
unique(P,W):- player(P,W) ; not player(P2,W): player(P2,_), P2!=P.  % aucun autre joueur ne l'a trouvé

Maintenant que l'on sait quels mots doivent être comptés dans le score pour chaque joueur, il est temps de se poser la question du score lui-même :

score(P,S):- S = #sum{L: unique(P,W), value(W,L)} ; player(P,_).

L'atome score(P,S) associe un joueur et son score final, obtenu en faisant la somme des valeurs L des mots W qui sont uniques et associés au joueur.

Le problème de cette approche, c'est la génération automatique de value(W,L). En effet, en ASP, il n'est pas possible d'obtenir la longeur d'une chaîne. Par conséquent, nous allons faire un peut de magie avec python:

#script (python)
def value(word):
    return len(word.string)
#end.

Notons que la valeur est facilement calculable en python, en utilisant le snippet utilisé ici:

#script (python)
def value(word):
    return [1,1,2,3,5,11][min(len(word.string),8)-3]#end.#show s/2.
#end.

Et voilà, nous pouvons accéder à la valeur d'un mot W avec @value(W). Que c'est magnifique ! Il serait possible d'encoder le mapping de la taille et de la valeur en ASP ainsi:

value(3,1).
value(4,1).
value(5,2).
value(6,3).
value(7,5).
n(8..99).
value(X,5):- n(X).

Mais l'inconvénient est triple : c'est long, il y a une génération de nombreux atomes inutiles, et ça oblige à donner une limite supérieure à la taille des mots.

Donc, on garde la fonction python qui fait la totalité du mapping mot vers score, ce qui nous permet de l'appeler dans la somme, et on obtient le code total suivant :

unique(P,W):- 1 { player(_,W) } 1 ; player(P,W).
score(P,S):- S = #sum{@value(W): unique(P,W)} ; player(P,_).
#script (python)
def value(word):
    return [1,1,2,3,5,11][min(len(word.string),8)-3]
#end.

Wow ! On obtient bien les bons scores pour chaque joueurs : score(1,12), score(2,3) et score(3,2).

Maintenant que le programme fonctionne, il ne reste plus qu'à le golfer, et à compter les caractères. Voici donc notre script final, atteignant un score de 137 caractères, ce qui le place avant-avant dernier (devant PHP et Java) au moment où j'ai écrit ce programme :

u(P,W):-1{p(_,W)}1;p(P,W).s(P,S):-S=#sum{@v(W):u(P,W)};p(P,_).#script(python)
def v(w):return[1,1,2,3,5,11][min(len(w.string),8)-3]#end.

Notez que les données d'entrées doivent être encodées avec le prédicat p à place de player. Aussi, la directive de script ignore le reste de sa ligne, par conséquent, faire un one liner parfait est impossible ici.

Golf du Mexique

Évidemment, cet exemple n'est pas là pour servir directement, à moins que vous ne jouiez vous-même au boggle.

L'intérêt est qu'il montre que bien des jeux, même ceux avec des règles complexes, peuvent être encodés en ASP pour être résolus ou étudiés.

Et aussi, ça montre que parfois, ASP donne de bonne solutions pour le code golf (et des fois, non).

Amis golfeurs, je vous salut !

Construire un PC

Ici, on va s'intéresser à un jeu de lego : construire une machine.

Cela pourrait vous servir un jour, et sinon, c'est en fait une tâche assez standard en informatique, nommé le problème du sac-à-dos. Ça a des applications partout, de la gestion des ressources à l'optimisation sur un cluster de calcul partagé.

Cependant, nul besoin de vous y connaître en montage de PC, les explications viennent avec (ce tuto est inter-disciplinaire :p).

Ce genre de programme s'organise autour de trois principaux sous-programmes :

• celui qui récupère les données, c'est-à-dire les pièces de pc disponibles, comme par exemple les cartes graphiques, les processeurs, les boîtiers,…
• celui qui construit le pc à partir des pièces récupérées, c'est-à-dire qui choisi quelles pièces utiliser,
• et celui qui affiche le résultat à l'utilisateur et lui permet de relancer la machine avec d'autres paramètres.

Le mot-clef, vous l'aurez compris, c'est choisir, et il se trouve dans la seconde étape. L'interface avec un distributeur de matériel informatique n'est pas le sujet de ce tuto, donc on s'arrangera avec quelques données faites à la main.

Mais si un jour quelqu'un veux s'amuser, la première étape est tout à fait automatisable, par exemple en tapant dans l'API d'un distributeur qui en propose une.

Spécifications

Une machine est un ensemble de plusieurs pièces : CPU, GPU, RAM, carte mère, refroidissement, disque dur, SSD, boite, périphérique. Chacune de ces catégories doit se voir assigner une (et une seule) pièce, ou éventuellement zéro si la catégorie est optionnelle (par exemple, je peux vouloir un SSD si possible ; c'est donc optionnel)

Chaque pièce appartient donc à une catégorie, et possède un prix, des dépendances et des incompatibilités. Aussi, elles auront chacune une note de préférence : je pourrais ainsi dire je préfère la GPU 1080 à la 1070 en mettant une plus grande préférence sur la première.

Enfin, et c'est là tout le sel : on ne veux pas dépasser un prix maximum.

En clair

On veut un programme ASP qui, en considérant les pièces disponibles, nos préférences personnelles, les interdépendances entre les pièces, et un prix maximum, soit capable de nous donner une bonne solution, voir la meilleure.

Là où ASP est génial, c'est qu'il n'y a pas besoin de connaître grand chose en heuristique pour résoudre ce genre de problème.

Le code le plus récent est disponible sur le dépôt. Nous allons ici l'aborder point par point.

Commentaires

Nous allons étudier le programme, découpé en 5 parties. Les premières parties sont de la pure description, nous allons donc nous contenter de décrire des faits, comme par exemple cette GPU est trop cool, ou ce composant est incompatible avec celui-là.

Les dernières parties vont implémenter le moteur réel, la partie du programme qui va utiliser les faits pour en déduire une configuration valide d'ordinateur. C'est ici que nous trouverons les contraintes et les directives de maximisation.

Données

Tout d'abord, nous déclarons les données que nous allons utiliser, c'est-à-dire les pièces disponibles, pour chaque catégories, avec leur nom et leur score (qui représente à quel point la pièce nous intéresse).

component(gpu,"A",330,10).

Ici, le composant de catégorie GPU, sobrement nommé A, coûte 330€ et est noté 10/10, autrement dit, cette GPU, c'est notre préférée.

Les deux autres GPU accessibles sont données avec les trois lignes suivantes.

component(gpu,"B",200,7).
component(gpu,"embedded graphic chipset",0,4).
embeds(gpu,"embedded graphic chipset",cpu,"C").

Les deux autres GPU étant moins bonnes, leurs prix et notes sont moins hauts (voir nuls pour la C, mais il s'agit d'une puce graphique intel, ce n'est donc qu'une solution par défaut).

Dépendances

Notez l'atome embeds/4 qui nous permet de définir que la puce intégrée nécessite le CPU C, et par conséquent (la règle qui s'en assure sera vue plus tard, elle appartient à la modélisation) que le choix de cette GPU oblige à utiliser le processeur qui l'embarque (c'est assez logique, finalement).

Néanmoins, si on choisi le cpu C, nous ne sommes pas obligés de choisir la puce intégrée, laissant le champs libre pour une autre carte graphique plus puissante. (la logique étant que la puce intégrée ne prend pas l'emplacement de la carte graphique, c'est juste un module du processeur ; personnellement mon processeur possède une puce intégrée, mais je ne l'ai jamais utilisée, j'ai une vraie carte graphique à côté que j'utilise à la place)

Les autres composants

CPU, RAM, SSD, HDD,… Tous vont passer dans la grande moulinette de l'ASP, avec toujours les même informations : un type, un nom, une note, et parfois un require/4. Je vous invite à regarder le code pour avoir une idée de toutes les pièces qui seront utilisées dans cet exemple.

Préférences

Les choix concernant le build : pièces optionelles, importances relatives,…

% J'ai pas besoin d'un SSD, c'est juste une bonne upgrade si possible.
optional(ssd).

% Set importances of various components (default is 5).
% Je peux préférer maximiser certains composants
set_importance(gpu,10).  % je suis un gamer
set_importance(motherboard,3).  % une motherboard pas cher, ça reste une motherboard
set_importance(ssd,4).  % le ssd j'ai pas besoin qu'il soit d'une qualité/taille folle

Connaissances du domaine

Pas très utilisé pour le moment, mais donne un exemple simple de ce qui pourrait y être placé.

% Le CPU et la carte mère doivent avoir le même bridge, sinon l'ordi il marchera pas.
incompatible(cpu,CPU,motherboard,MB):-
    component(cpu,CPU) ; component(motherboard,MB) ;
    bridge(cpu,CPU,CPU_Bridge) ; bridge(motherboard,MB,MB_Bridge) ;
    MB_Bridge != CPU_Bridge.

Expansion des données

C'est à ce moment qu'on transforme les raccourcis pour l'utilisateur en atomes qui seront utilisés par le modèle. Bref, on fait le pont entre l'interface haut niveau et les atomes pour la couche d'en dessous.

Sans ça, l'utilisateur serait obligé d'écrire tout lui-même, donc ça complexifierait l'étape de description des données.

% Extraction des données des composants.
component(O,Name):- component(O,Name,_,_).
price(O,Name,P):- component(O,Name,P,_).
rate(O,Name,R):- component(O,Name,_,R).

% Quantité minimales de composants à acheter.
% Par défaut, un composant est nécessaire.
minimal_quantity(O,1):- component(O) ; not optional(O).
minimal_quantity(O,0):- component(O) ; optional(O).

% Importances des composants.
% Par défaut, tous les composants sont équivalents en importance.
importance(O,5):- component(O) ; not set_importance(O,_).
importance(O,I):- component(O) ; set_importance(O,I).

% Si on a marqué qu'un composant en contient un autre (embedding),
% alors c'est équivalent à dire que l'un requiert l'autre et inversement.
require(C1,N1,C2,N2):- embeds(C1,N1,C2,N2).
require(C2,N2,C1,N1):- embeds(C1,N1,C2,N2).

Modèle

C'est ici que le principal se passe : en s'appuyant sur les préférences et autres informations, on va pouvoir définir ce que l'on attend d'ASP.

component(O):- component(O,_).  % juste un raccourcis

% On choisi un de chaque composant.
Q { use(O,X): component(O,X) } 1 :- component(O) ; minimal_quantity(O,Q).

% Si un composant choisi à des requirements, on doit les avoir choisi aussi.
use(O2,N2):- use(O1,N1) ; require(O1,N1,O2,N2).
1 { use(O2,X): require_one(O1,N1,O2,X) } 1:- use(O1,N1) ; require_one(O1,N1,O2,_).

% On écarte tout modèle qui présente des incompatibilités.
:- incompatible(O1,N1,O2,N2) ; use(O1,N1) ; use(O2,N2).

% Calcul du coût total, et du score total.
total_cost(T):- T=#sum{C,O: use(O,I), price(O,I,C)}.
total_rate(T):- T=#sum{R*I,O: use(O,C), rate(O,C,R), importance(O,I)}.
total_size(T):- T={use(_,_)}.

% On écarte tout modèle où le score est supérieur au max autorisé.
:- total_cost(T) ; T>max_cost.

% On maximise le score.
#maximize{S:total_rate(S)}.


% On affiche ce qui intéresse l'utilisateur : les composants à prendre, et les scores.
#show.
#show use/2.
#show total_cost/1.
#show total_rate/1.
#show total_size/1.

Aller plus loin

Réflexion de fond d'informaticien

Vous noterez que nous avons définis des couches successives d'abstractions : par exemple, nous utilisons require/4 au lieu d'écrire une contrainte, laissant une règle dans l'expansion des données s'occuper de créer la contrainte associée.

Ce principe rapellera à certains les Domain Specific Languages (DSL), des languages utilisés dans un projet pour décrire un modèle de donnée. Ces DSL ont beaucoup d'applications, et vous voyez que dans une certaine mesure, ASP permet d'en créer. Ici, nous avons créé un DSL pour décrire les pièces d'ordinateur et leurs relations.

Là où c'est plus fort, c'est que vous pouvez aller plus loin : permettre à l'utilisateur de décrire les tâches qu'il veut faire avec son PC (les logiciels qu'il utilise, notamment, comme les jeux ou la bureautique qu'il veut faire tourner), et en déduire plus de contraintes sur le PC final : pas la peine d'avoir plus de 2GB de RAM si l'utilisateur final veut juste lire ses mails ou se connecter aux réseaux sociaux, et à l'inverse, une puissance minimale de GPU peut être nécessaire pour certains jeux.

Vous pouvez facilement imaginer ASP comme un générateur de DSL : c'est ce que je fait avec Biseau et se-lang, et c'est ce qu'on a fait aussi pour le placement de table avec les atomes copains/2 et pas_copains/2.

Attrapez les toutes

Une première étape pour l'utilisation du programme dans la vie de tous les jours, c'est effectivement de récupérer les données, i.e. les pièces disponibles et leurs relations.

Évidemment, récupérer TOUTES les pièces possibles est un peu long, alors avoir des informations en amont, notamment les prix minimaux et maximaux (globaux, et par catégorie) permet déjà d'élaguer. En général, toute limitation est bonne à prendre : taille de la RAM, du stockage, nombre de cœurs…

Tout cela est facile à intégrer dans le programme ASP : il ne s'agit que de rajouter des pièces, des préférences, voir des contraintes.

Une solution pourrait être de parser ou chopper l'API d'un site de vente de matériel, par exemple LDLC ou partpicker (ya un module python non-officiel qui pourrait aider ;).

Cet hypothétique programme consiste simplement en l'extraction d'info de ces sites, et l'écriture de règles ASP à mettre dans les données. Pas une tâche monstrueuse, donc.

Dans le ¬Sephiroth

Une fois que les deux premières parties sont mises en place et travaillent ensembles, vient l'étape de distribution de votre projet révolutionnaire : d'autres personnes pourraient en bénéficier.

Une manière de faire, c'est une interface web, où les utilisateurs peuvent checker les pièces disponibles qui les intéressent, éventuellement faire un peu d'apprentissage pour proposer des pièces intéressantes (si 80% des utilisateurs qui prennent 8Go de RAM choissisent aussi une 1080, alors automatiquement proposer une 1080 à tout utilisateur qui prend 8Go de RAM).

La deuxième étape, c'est de constituer la base de donnée et de préférence de l'utilisateur en fonction des composants qu'il a choisi et des indications qu'il a donnée.

Enfin, il faut faire tourner le solveur (dans le navigateur du client grâce à du webassembly parce que nous vivons déjà dans le futur), et de sortir les meilleurs build au client.

Et paf, vous vous faites connaître, r/buildapc devient votre source d'utilisateur principale, et vous devenez riche grâce à un système comme coinhive, qui bien sûr, dans le futur, est bien plus mature, éthique, démocratisé, et contrôlable par l'utilisateur final.

PC construit, nuit de folie

Cet exemple ne sera pas utile tel quel à tout le monde, mais vous comprenez bien que vous pouvez l'adapter un peu pour, par exemple, choisir le meilleur portable disponible en fonction des fonctionnalités qu'on vous vend, faire les sandwichs pour la randonnée de demain en fonction de ce qu'il y a dans le frigo, ou plus généralement de décider comment faire quelque chose en fonction des limites.

J'ajouterais aussi que mettre à plat ce genre de chose aide beaucoup à faire un choix rationnel. Et en plus, le solver vous donne la meilleure solution juste en connaissant vos goûts !

Magique ? Non, informatique !

Résoudre un donjon de The Legend of Zelda

Contexte

Dans sa franchement intéressante série Boss Keys, Mark Brown, un designer professionnel du milieu du jeu vidéo, cherche, épisode par épisode, à comprendre la structure interne et les logiques qui sous-tendent les donjons des jeux de la licence The Legend of Zelda.

Si vous aimez cette série de jeu, ou le game design en général, je ne peut que trop vous conseiller Boss Keys, et plus généralement son excellente chaîne, Game Makers Toolkit.

Lorsqu'on regarde Boss Keys, au fur et à mesure des épisodes on s'aperçoit que Mark Brown imagine, formalise et améliore, vidéo après vidéo, un langage qui lui permet de définir formellement les donjons des jeux. Dans les derniers épisodes, le langage devient vraiment complet et descriptif.

Sans surprise, le langage est un graphe, qui donne des informations précises sur la répartition dans l'espace et le temps des objets et mécanismes qui constituent les donjons, et permet à Mark Brown de délimiter la solution du donjon, c'est-à-dire la succession d'actions à opérer qui permettent, à la fin, d'ouvrir la porte du boss avec la clef dédiée (d'où le nom de la série, boss keys).

Notre boulot

En lisant les lignes précédentes, une idée vous est venue : si nous avons accès à une représentation formelle des donjons du jeu, et que nous pouvons formellement décrire les actions et les buts, alors il serait possible d'écrire un programme qui, comprenant le langage de description de Mark Brown, serait capable de décider d'une solution au donjon.

Bien sûr, vous vous doutez que si j'en parle ici, c'est parce que nous allons nous y intéresser avec ASP.

Voici une image piquée à la vidéo The Legend of Zelda: A Link Between Worlds' dungeon design | Boss Keys :

On voit bien le départ, la fin (boss, en bas), et les différentes étapes qui mène à la résolution du donjon. On comprend bien ici qu'une solution au donjon est un parcours de ce graphe qui part du départ et arrive au boss en ne passant par les obstacles que lorsque la clef ou l'outils associé est possédé.

Modélisation

Petit rappel sur le langage développé par Mark Brown, i.e. la représentation en graphes des donjons :

• les nœuds sont des salles, ou zones du donjon portant un objet d'intérêt.
• deux nœuds sont reliés si il existe un passage entre les deux.
• un objet d'intérêt est soit un obstacle, soit un objet à ramasser.
• un obstacle ne peut être contourné/annulé que par un objet.
• un objet à ramasser est sois un outils, soit une clef.
• une clef est à usage unique, mais ouvre n'importe quel obstacle qui attend une clef.
• un outil est soit la clef du boss, qui permet d'ouvrir la porte du boss, soit un objet de l'univers du jeu (grapping, arc, bottes,…).

Donc, en clair : il faut ramasser une clef pour pouvoir annuler un obstacle qui nécessite une clef (une porte verrouillée, donc), ou dans le cas des autres obstacles l'objet associé à l'obstacle (pour annuler un obstacle de type arc, il faut que l'objet arc ait été ramassé auparavant).

Notez que le graphe n'est pas forcément orienté. Néanmoins, on peut imaginer l'intérêt de l'orientation : des passages ne pouvant être pratiqués que dans un seul sens par le personnage (porte de sortie, toboggan,…).

Notez également que le langage est en fait un poil plus complexe, car il a une composante graphique importante (le placement des nœuds dépends de l'ordre dans lequel les objets/obstacles doivent être traités). Nous allons néanmoins ignorer cela, car l'information de l'ordre est redondante, et n'est là que pour faciliter la lecture pour les humains qui regardent la vidéo/l'image.

Le code

D'abord, la définition du donjon :

% Les portes fermées à clef.
keydoor(g;b).
% Une porte nécessite l'arc pour passer.
objdoor(f,arc).
% Ce sont des nœuds du donjon aussi.
node(D):- keydoor(D).
% On trouve une clef dans les nœud c et e.
haskey(c;e).
% l'arc est en d.
hasobj(d,arc).
% Et on commence à l'étape 1 sur le nœud s.
is(1,s,start).

% Liens entre les nœuds
link(s,(b;c;d)).
link(b,(e;f)).
link(f,g;g,boss).
link(X,Y):- link(Y,X).  % on peut aller dans les deux sens.

target(boss).  % c'est là qu'on veut aller

Et ensuite, vient la modélisation qui permet d'obtenir ce que l'on veut :

% Les nœuds à coté des nœuds ouverts sont atteignables à la prochaine étape.
accessible(E+1,Node):- link(Location,Node) ; is(E,Location,_).

% On garde en mémoire les nœuds déjà visité à l'étape E.
visited(E+1,Node):- is(F,Node,_) ; is(E,_,_) ; F<E.

% On remarque les nœuds «vide», qui n'ont ni objet ni clef ni porte fermée.
node(N):- link(N,_).
node(N):- link(_,N).
emptynode(N):- node(N) ; not haskey(N) ; not hasobj(N,_) ; not keydoor(N) ; not objdoor(N,_) ; not target(N).

% accessible/3: ce qu'on peut faire pour tout nœud à portée.

% Si contient une clef.
accessible(E,ClosedNode,found(key)) :- accessible(E,ClosedNode) ; haskey(ClosedNode) ; not visited(E,ClosedNode).
% Ou un objet.
accessible(E,ClosedNode,found(Obj)):- accessible(E,ClosedNode) ; hasobj(ClosedNode,Obj) ; not visited(E,ClosedNode).
% Ou si c'est juste un nœud avec rien.
accessible(E,T,reached) :- accessible(E,T) ; target(T).
accessible(E,N,empty) :- accessible(E,N) ; emptynode(N).

% Ou si on est déjà passé par là.
accessible(E,OpenNode,empty):- accessible(E,OpenNode) ; visited(E,OpenNode).

% Ou si est fermée à clef, mais qu'on en possède une non utilisée.
accessible(E,ClosedNode,openwith(KeyNode)):-
    accessible(E,ClosedNode) ; keydoor(ClosedNode) ;
    % On a une clef :
    is(_,KeyNode,found(key)) ;
    % Non utilisée :
    not is(F,_,openwith(KeyNode)): is(F,_,_), F<E ;
    % On a pas déjà ouvert la porte :
    not accessible(E,ClosedNode,empty).

% Ou si est fermée et associée à un objet, et qu'on le possède.
accessible(E,ClosedNode,openwith(Obj)):-
    accessible(E,ClosedNode) ; objdoor(ClosedNode,Obj) ;
    % On a l'objet :
    is(_,ObjNode,found(Obj)) ;
    % On a pas déjà ouvert la porte :
    not accessible(E,ClosedNode,empty).


% On choisi à chaque étape l'un des endroit accessible.
#const max_etape=20.  % le nombre maximal d'étape autorisé.
0{ is(E+1,O,A): accessible(E+1,O,A) }1:- is(E,N,_) ; E<max_etape ; not target(N).

% On veut arriver à la fin.
:- not is(_,T,_): target(T).

% On compte le nombre de mouvements.
nb_move(N):- N={is(_,_,_)}.
% On le minimise :
#minimise{N:nb_move(N)}.


% On montre les atomes is/3, qui montrent la solution.
#show is/3.

Réponse obtenue :

clingo version 5.2.2
Reading from l.lp
Solving...
Answer: 1
is(1,s,start) is(2,c,found(key)) is(3,s,empty) is(4,d,found(arc)) is(5,s,empty) is(6,b,openwith(c)) is(7,e,found(key)) is(8,b,empty) is(9,f,openwith(arc)) is(11,boss,reached) is(10,g,openwith(e))
Optimization: 11
OPTIMUM FOUND

Models       : 1
  Optimum    : yes
Optimization : 11
Calls        : 1
Time         : 0.073s (Solving: 0.04s 1st Model: 0.03s Unsat: 0.01s)
CPU Time     : 0.072s

En réalité, il existe beaucoup plus de solutions, mais comme on a demandé une optimisation, ASP ne montre que celles qui sont meilleures que celles qu'il a affichées avant. Dans notre cas, comme le problème est trivial, ASP trouve très rapidement la meilleure solution, l'affiche à l'écran, puis termine d'explorer l'espace de recherche sans en trouver de meilleure.

Notez bien la logique de cette solution : on ouvre la porte b avec la clef trouvée en c, puis la porte f avec l'arc, et ensuite la porte g avec la clef trouvée en e. Tout ça en 10 étapes pour arriver jusqu'au boss.

C'est globalement la même technique que j'avais utilisée pour résoudre un puzzle du jeu Deponia.

Généralisation

Évidemment, le donjon de zelda, ce n'est qu'un prétexte pour attaquer le principe de planification d'une tâche, qui ici n'est pas du tout réalisé de manière optimale. Déjà, l'étape suivante, ce serait de passer ça en résolution incrémentale.

Enfin, notez que ce genre de tâche est très standard. Dans la langue de Batman, on parle de planning. C'est un sujet de recherche où il y a beaucoup de choses à faire, surtout en ASP.

Conclusion sur le solveur de donjons

C'est un exemple assez complet (choix, récursivité, optimisation, logique, et même constantes !), qui montre que même avec un encoding un peu bourrin ASP peut gérer franchement efficacement des problèmes un peu compliqué.

Parmis les trucs à faire : réutiliser les dessins de Mark Brown pour encoder les véritables donjons (notamment le donjon de l'eau, avec tous ses états et modifications qui font de ce donjon un gros casse-tête). Ça nécessitera d'encoder les liens entre nœud de manière à prendre en compte des paramètres qui changent en fonction de leviers. Rien de complexe en soit, mais le programme va encore grandir d'une quinzaine de lignes.

TCC: The Conclusive Conclusion

Où l'on apprend que tout ceci n'était que le début, car en réalité, l'informatique est bien plus qu'un langage qui fait des trucs rigolos

Exeeeeerciiiiiiice ! Fil rouge en trois actes

Vous souvenez-vous de l'introduction ? On parlait du code ASP qui génèrais les multiples positifs de 3 inférieurs à 100, et du fait qu'il vous serait possible d'imaginer d'autres solutions que celle proposée. Maintenant semble être un bon moment pour y réfléchir.

Trouvez 3 autres manière d'encoder le problème, en utilisant des expressions différentes du langage : les contraintes, les choix, les négations dichotomiques,…

solutions

Liens

Autres applications

• ASP for FCA un ensemble de programmes qui utilisent ASP pour exprimer des concepts (pun intended) de l'Analyse de Concepts Formels.
• une page très complète avec beaucoup d'exemples et de programmes avec explications.
• Au sein du projet pygarden, solasp est un code ASP qui permet d'optimiser le placement de plantes dans le jardin sachant leurs préférences de voisinage.
• pytest-asptest : un plugin pytest pour faire des tests unitaires sur des codes ASP.
• clyngor : un package pour appeler et gérer clingo depuis python.
• le jeu Warzone 2100 utilise ASP pour la génération de cartes.
• l'atterisseur Philae utilisait la programmation par contrainte pour organiser le lancement des appareils de mesure en fonction de l'énergie restante, de la position de Rosetta,…
• Angry-HEX, une intelligence artificielle pour le jeu Angry Birds, est implémentée en ASP.

And now, for something totally different

• Tuto/howto pour utiliser clingo en javascript, côté client.
• N'hésitez pas à poser des questions sur ASP sur stack-overflow.
• la page potassco/teaching regorge de liens.
• une erreur ? une idée ? une question ? Ça se passe sur le dépôt du blog.
• If you want to help for the english version, it's here.

Solutions aux exercices

Où l'on constate qu'effectivement, les exos étaient pas compliqués, mais que la soupe à l'avocat, elle, était horrible

Notation

k/3, coucou/0 et symballium/10.

Tel père, tel fils

Énoncé

enfant(Enfant,Papa):- papa(Papa,Enfant).
enfant(Enfant,Maman):- maman(Maman,Enfant).

Pour le bonus, une première solution «naïve» :

nooooooooooon:- moi(E) ; papa(dark_vador,E).
nooooooooooon:- moi(E) ; papa(zurg,E).

Et voilà une seconde solution, plus robuste :

mechant(dark_vador;zurg).
nooooooooooon:- moi(E) ; papa(P,E) ; mechant(P).

Tel non-père, non-tel fils

Énoncé

papapa(Lui):- papa(_,Lui) ; not papa(Lui,_).
pamaman(Elle):- maman(_,Elle) ; not maman(Elle,_).

En revanche, aucune trace de cosmologiste incas :/

Une famille en answer-set

Énoncé

Mon papa c'est le meilleur

Énoncé

papa(P):- papa(P,_).
1 { meilleur_papa(P): papa(P) } 1.  % ou papa(P,_), mais sans la règle précédente ça revient au même

Garde contre et roi de trèfle

Énoncé Les deux règles suivantes sont équivalentes dans ce contexte :

on_joue_au_ballon:- -on_joue_au_tarot.
% équivalente à :
on_joue_au_ballon:- copain(C) ; not en_recre(C).

Yodel et papier crépon

Énoncé Une première solution, qui génère aussi les sous-ensembles de solutions :

2 {peoples(X): aime(X,_) }.
2 {subject(Y): aime(_,Y) }.
:- not aime(X,Y) ; peoples(X) ; subject(Y).

Pour éviter les sous-ensembles, une solution est d'obliger un sujet aimé de toutes les personnes d'être membre de la solution :

subject(Y):- aime(X,Y): peoples(X) ; aime(_,Y).

Vous remarquez que le code ressemble alors à la seconde solution, qui est en fait beaucoup plus simple :

peoples(X):- aime(X,_) ; aime(X,Y): subject(Y).
subject(Y):- aime(_,Y) ; aime(X,Y): peoples(X).
:- 2>{peoples(_)}.  % au moins deux personnes
:- 1>{subject(_)}.  % au moins 1 sujet

Fil rouge en trois actes

Énoncé Une première solution, qui génère un answer set pour chaque solution :

candidats(1..100).  % les valeurs candidates
solution(X): candidats(X), X\3=0.  % un candidat est solution s'il est divisible par 3.
#show solution/1.  % affiche la solution

Une seconde, qui utilise la négation dichotomique :

1{candidat(1..100)}1.  % choisi un candidat
-candidat(X):- candidat(X) ; X\3>0.

Une troisième, avec un choix explicite et une contrainte :

1{candidat(1..100)}1.  % choisi un candidat
:- candidat(X) ; X\3!=0.

Et enfin, l'encoding bonus : ASP doit maximiser un score qui dépends du sous-ensemble de candidat choisi :

% On prend un sous-ensemble des 100 valeurs.
{solution(1..100)}.

% Le score est la somme des valeurs des solutions.
%  Une solution divisible par 3 compte pour 1
%  Une solution qui n'est pas multiple de 3 compte pour -1
score(N):- N=#sum{1,X: solution(X), X\3=0 ; -1,X: solution(X), X\3>0}.

% On veut le modèle avec le plus grand score.
#maximize{N@1: score(N)}.

Cette dernière solution, avec le multithreading et un bon processeur, met plus de 1 minute à être résolue.