6. Programmer en Prolog

6. Programmer en Prolog

6.1 Faits, règles, programme et traduction directe

Prolog tire son nom de programmation logique. Le programme décrit les connaissances. La console contient le but. Dans le fragment du cours, un fait est une clause positive unitaire et une règle a une seule tête positive.

% Faits
p(a).
p(a,b).

% Règles
p(a,b) :- q(a,b).
p(X,Y) :- q(X,Y), r(X,Y).

La seconde règle se lit : p(X,Y) est vrai si q(X,Y) et r(X,Y) sont prouvés. La correspondance est :

(q(X,Y) ∧ r(X,Y)) → p(X,Y)
≡ ¬q(X,Y) ∨ ¬r(X,Y) ∨ p(X,Y)
↔ écriture Prolog : p(X,Y) :- q(X,Y), r(X,Y).

La dernière flèche indique une traduction de notation. La conclusion est à gauche, les conditions à droite de :-. On retire les négations des conditions lors de cette traduction; leur rôle logique est porté par la structure de la règle.

La tête exprime une seule relation avec ses arguments. Les conditions peuvent être multiples. Une fois cette correspondance comprise, on peut traduire directement une phrase simple en Prolog : identifier la conclusion, puis ses conditions. L’enseignante rapproche cette démarche des règles de jeu et de leurs préconditions, sans imposer neuf transformations écrites pour chaque règle élémentaire.

L’exemple de §5.3 devient :

pere(charles,marie).
parent(claude,julie).
parent(X,Y) :- pere(X,Y).

parent(charles,marie). réussit; parent(X,marie). donne X=charles. L’extraction des variables est assurée par le moteur. La programmation logique peut constituer une composante d’un logiciel, sans nécessiter que tout le logiciel utilise ce paradigme.

6.2 Syntaxe et identité des termes

Un atome y minuscule n’est pas une variable Y. Deux occurrences de la même variable dans une clause doivent recevoir des termes compatibles. Deux symboles de même nom mais d’arités différentes, comme p/2 et p/3, sont distincts.

Les variables des exemples n’ont pas de déclaration de type statique. Cela ne signifie pas que tout s’unifie : les constantes, les symboles, les arités et les structures imposent des contraintes. Une variable peut conserver une autre variable libre à l’intérieur d’un terme composé.

Le langage fournit des prédicats prédéfinis pour des opérateurs, notamment arithmétiques, des entrées/sorties, des opérations sur ensembles et d’autres services. Le matériel annonce leur approfondissement; cette semaine expose surtout les faits, règles, requêtes et substitutions.

Les noms composés du corrigé généalogique sont normalisés ici avec des underscores : soeur_frere, tante_oncle, petit_enfant, cousin_cousine. Un trait d’union non cité est un opérateur Prolog, pas simplement un caractère dans un nom de prédicat. Utiliser les mêmes noms normalisés dans le programme et les requêtes.

6.3 Buts fermés, variables et conjonctions

Une requête est saisie sans la négation utilisée sur papier :

?- p(a).
?- p(X,Y).
?- p(a,b), q(a,b).
?- p(X,Y), q(X,Y), r(X,Y).

Le préfixe ?- représente la console; dans Swish, il est déjà indiqué à côté de la zone de saisie. Le but fermé demande un succès ou un échec. Avec des variables, le moteur affiche les substitutions trouvées.

La virgule entre sous-buts exprime ET. Toutes les conditions doivent réussir. Pour p(X,Y),q(X,Y), si la première donne X=a et Y=b, le sous-but suivant est q(a,b). Les liaisons se propagent aux obligations restantes; le deuxième but n’obtient pas des valeurs indépendantes pour les mêmes noms.

La mention « aucun lien » du diaporama pour des buts à constantes signifie qu’il n’y a pas de variable partagée à instancier, pas qu’un seul des buts suffirait. Dans la lecture clausale d’un but conjonctif p∧q, sa négation est ¬p∨¬q; les deux conditions positives devront être résolues pour fermer ce but.

Un succès ne garantit pas que toutes les solutions ont été affichées. Un échec d’une branche peut provoquer un retour arrière vers un autre choix. false après épuisement de la recherche signifie que le programme n’a pas établi le but; ce résultat est distinct d’une erreur d’exécution et d’une preuve classique de ¬B.

6.4 Moteur, sous-buts et retour arrière

Le moteur présenté cherche en profondeur d’abord. Il tente d’unifier le but avec un fait ou la tête d’une règle. Un fait résout le but; une règle le remplace par les conditions de son corps. Il poursuit ces conditions avant d’explorer d’autres choix. Les variables d’une règle sont locales à chaque utilisation.

Avec les faits parentaux du cours, parent(nathalie,W) essaie d’abord parent(julie,anne), qui échoue sur les constantes Julie/Nathalie. parent(nathalie,anne) réussit et donne W=anne. Pour une autre réponse, la recherche poursuit ses choix jusqu’à parent(nathalie,jimmy), qui donne W=jimmy. Le premier fait incompatible n’arrête donc pas toute la requête.

Pour la règle :

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

la requête soeur_frere(nathalie,W) donne les étapes suivantes :

1. Unifier la tête : X ↦ nathalie, Z ↦ W.
2. Nouveaux sous-buts : parent(nathalie,Y), parent(W,Y).
3. Premier choix : parent(nathalie,anne), donc Y ↦ anne.
4. Sous-but restant : parent(W,anne).
5. Rechercher les valeurs de W parmi les faits à parent anne.
6. Au retour arrière, poursuivre ces choix, puis essayer Y = jimmy.

Y sert de variable intermédiaire reliant les deux sous-buts; la requête initiale demande W. La substitution de tête agit sur le corps, puis chaque nouvelle substitution agit sur les sous-buts restants.

L’unification n’est pas une affectation impérative qui modifie arbitrairement une valeur. Elle rend des termes compatibles sur la branche courante. Le retour arrière rouvre les choix et défait les liaisons de la branche abandonnée. Une branche qui ne termine pas peut empêcher d’atteindre d’autres solutions : la recherche de « toutes les solutions » n’est pas une garantie inconditionnelle.

6.5 Les deux orientations de parent/2

Le matériel emploie deux conventions. Elles doivent être lues séparément :

Le nom parent ne suffit pas à déterminer le sens. Ne pas fusionner les faits des deux bases comme s’ils décrivaient une relation orientée de la même manière.

Voici le programme du diaporama et de la démonstration, avec l’orientation enfant → parent :

parent(jean,sylvain).
parent(jean,julie).
parent(julie,anne).
parent(nathalie,anne).
parent(luc,anne).
parent(julie,jimmy).
parent(nathalie,jimmy).
parent(luc,jimmy).
parent(sylvie,luc).
parent(sylvie,rachel).

soeur_frere(X,Z) :- parent(X,Y), parent(Z,Y).
grandparent(X,Z) :- parent(X,Y), parent(Y,Z).

Dans la dernière règle, Z est grand-parent de X. grandparent(jean,X) trouve Anne et Jimmy en passant par Julie. La branche passant par Sylvain ne fournit pas de grand-parent dans la base donnée.

La formule de parent commun peut être écrite avec une portée explicite :

∀x∀z ((∃y (parent(x,y) ∧ parent(z,y))) → soeur_frere(x,z))

Elle conduit à la règle universelle puis à ¬parent(x,y)∨¬parent(z,y)∨soeur_frere(x,z). Y est le même parent dans les deux relations; des parents choisis indépendamment ne définiraient pas la fratrie.

La règle initiale n’exclut pas X=Z et ne déduplique pas les preuves. C’est précisément le problème traité par la démonstration suivante.