A la découverte de Prolog

En septembre 2020, nous avons accueilli dans nos locaux un meetup Software Crafters. Le thème de la soirée était « À la découverte de Prolog ». Dans ce billet, je vous propose de vous résumer ce que nous y avons découvert.

C’est quoi Prolog ?

Prolog est un langage différent de ce qu’on peut connaître. Il ne s’agit pas à proprement parler d’écrire des algorithmes, mais plus de décrire des problèmes.

On déclare des « règles », on énonce des « faits » et on demande à Prolog si ce qu’on vient d’écrire est juste.

Comment ça s’écrit du Prolog ?

Pour suivre les exemples, vous pouvez installer SWI-Prolog et lancer la commande suivante.

swipl

Commençons par quelques faits simples.

Tout d’abord deux listes identiques sont égales.

?- [1, 2, 3] = [1, 2, 3]. true.

Ici, nous constatons une étrangeté de Prolog, le résultat de la fonction est contenu dans le dernier argument. La fonction, elle, retourne « true ».

?- append([1], [2], [1, 2]).
true.

Ca sert à rien alors ?

Maintenant que nous avons quelques notions de syntaxe, nous pouvons nous essayer à interroger le langage. Pour cela, il nous suffit d’intégrer une inconnue dans nos précédentes instructions.

?- [1, 2, 3] = [1, 2, A].
A = 3.

?- append([1], L2, [1, 2]).
L2 = [2].

?- append(L1, L2, [1, 2]).
L1 = [],
L2 = [1, 2] ;
L1 = [1],
L2 = [2] ;
L1 = [1, 2],
L2 = [] ;
false.

Pour cette dernière interrogation, Prolog va vous proposer une première solution, en appuyant sur ‘;’ il vous proposera la suivante.

Cela est répétable, jusqu’à ce qu’il indique ne plus avoir de solutions en retournant false.

Définir des relations

En Prolog, il est possible de définir des relations. Par exemple, dans un fichier « parents.pl », nous écrirons :

parent(robert, robin).
parent(roberta, robin).
parent(robert, rosalie).
parent(roberta, rosalie).
parent(robert, roger).
parent(geraldine, roger).

Vous remarquerez que nous n’avons pas déclaré ce que voulait dire « parent » ou la signification de tous ces prénoms. C’est inutile, le langage comprend qu’il s’agit de « vérités ».

Dans notre REPL, on chargera le fichier via la commande

?- ["parents"].

Nous pouvons contrôler que nos nouveaux faits sont bien présents.

?- parent(robert, robin).
true.

?- parent(patricia, robin).
false.

Pouvons-nous interroger cette fonction « parent », comme nous l’avons fait avant avec « append » ?

?- parent(robert, A).
A=robin;
A=rosalie;
A=roger;
false.

Pour corser un peu la chose, nous pouvons vérifier deux faits en même temps.

?- parent(robert, A), parent(geraldine, A).
A=robin;
A=rosalie;
false.

Quand est-ce qu’on code ?

Jusqu’à présent, nous n’avons pas vraiment eu besoin de coder. Dans certains cas, il est nécessaire de définir des relations de manière « programmatique ».

Par exemple, imaginons que nous voulions créer la notion « ancestor ». « ancestor(A, B) » est vrai, s’il existe une chaine de parents entre A et B.

Dans notre fichier « parents.pl », on pourra ajouter le code suivant. Nous commençons par ajouter quelques ancêtres aux enfants de Robert.

parent(robert_father, robert).
parent(robert_father_father, robert_father).

Il faut ensuite définir une règle en s’appuyant sur « parent ». Comme vous pouvez le voir, c’est un algorithme récursif :

• Définition de la condition d’arrêt.
• La règle s’appelle elle-même.

ancestor(X, Y)
    :-  parent(X, Z), parent(Z, Y).
ancestor(X, Y)
    :-  parent(X, Z), ancestor(Z, Y).

Après avoir rechargé notre fichier, il est possible de tester notre règle.

?- ancestor(robert_father, robin).
true.

?- ancestor(robert_father_father, A).
A = robert ;
A = robin ;
A = rosalie ;
A = roger ;
false.

?- ancestor(A, robin).
A = robert_father ;
A = robert_father_father ;
false.

Et on code quoi maintenant ?

Maintenant que nous avons vu les concepts et saisi un peu la syntaxe, il serait intéressant de se lancer dans un exercice de code. Initialement, j’avais pensé faire des Katas classique, mais je n’en ai pas trouvé qui soit un bon cas pour Prolog. L’idée m’est venue d’utiliser le jeu Logik Ville. Pour ceux qui ne connaitrait pas, un rapide résumé du jeu : vous disposez de X Maisons et de X Personnages, une carte vous décrit les règles de placement (Jaune et Rouge sont voisins, Vert habite dans la 3ème maison, …). Il présente un certain nombre d’avantages pour l’exercice :

• C’est un jeu à contrainte. On peut espérer « coder » la carte et que Prolog nous donne la solution.
• Les maisons sont posées côte à côte. La structure de données est évidente, c’est une liste de taille fixe.
• Les cartes sont de difficulté croissante. On peut donc procéder par itérations, en ajoutant les règles plus complexes en allant.

Je me suis mis derrière le clavier et c’est dans une forme de Mob Programming que nous avons attaqué l’implémentation.

Pour être honnête, dans les premières minutes, nous avons eu un petit moment de flottement.

Comment définit-on l’ensemble des couleurs ? Comment spécifie-t-on que chaque couleur est représentée une et une seule fois ? …

La solution nous ai venu de Bruce Tate et de son livre 7 languages in 7 weeks, dans le chapitre Prolog, il résoud un problème de coloration de carte. Nous lui avons emprunté quelques lignes et l’implémentation a pu réellement démarré.

Vous trouverez le code pour les 9 premières cartes dans le repository Github dédié à la soirée. Note : Nous avons passé la 6 qui ne présentait pas de nouveauté.

Conclusion

Le bilan de cette expérience de découverte en groupe a ét très positif. Tout le monde veut avancer sur le problème, résoudre une carte de plus, … Le côté ludique du sujet a bien aidé sur ce point.

Je ne suis pas sûr que tous les langages se prêtent à ce type d’exercice. Voici (selon moi) les caractéristiques de Prolog qui ont facilité la tâche.

• Le Shell/REPL permet une interactivité dans l’enchainement implémentation-exécution.
• Pas de cérémonie. En Prolog, pas de « static void main … », on écrit directement du code utile.
• Une syntaxe très stricte. Le langage est tellement différent que l’on est plongé directement dedans, pas moyen de bricoler en se rapprochant de la façon d’écrire de notre langage préféré.