Prolog: Programming in logic.
Prolog est un des langages de programmation les plus répandus parmi les chercheurs en intelligence artificielle. S’opposant aux langages dits impératifs — comme C ou Java , il se distingue en ce qu’il est un langage déclaratif. Cela signifie que pour résoudre un problème en Prolog, au lieu de définir comment, par quels moyens on va atteindre un objectif fixé, on décrit plutôt ce qu’est la situation: les faits et les règles (rules and facts) qui découlent de celle-ci. C’est de ces données que l’interpréteur Prolog déduit la solution du problème.
Par exemple, si on devait comparer des animaux X et Y par leur taille, et trouver lequel est le plus grand, alors plusgrand(X,Y) serait un fait. Cependant, on aurait beau dire que plusgrand(girafe,lion) et plusgrand(lion, chien), on ne pourrait pas conclure que plusgrand(girafe, chien) est vrai: on n’aurait pas suffisamment de faits, la description de la situation serait imprécise. C’est alors qu’on peut appeler la définition suivante:
est_plusgrand(X,Y) :- plusgrand(X,Y)
est_plusgrand(X,Y) :- plusgrand(X,Z), est_plusgrand(Z,Y)
cette règle fait appel à la transitivité de ‘plusgrand’ . Pour répondre à la requête (query) suivante: ?- est_plusgrand(girafe, chien) , Prolog va essayer de satisfaire la première définition de la règle est_plusgrand, mais faillir à trouver un fait validant la requête. Il va ensuite utiliser la seconde, ou un mélange des deux, évaluer toutes les combinaisons de règles et de faits pour répondre.
C’est ainsi que sur un échantillon bien plus large d’animaux, Prolog pourra répondre de la façon suivante à des requêtes telles que celle-ci:
?- is_plusgrand(X , ane) .
X = cheval ;
X = girafe ;
X = elephant ;
No
Le ‘No’ signifiant qu’il n’y a plus de solutions, que Prolog a épuisé toutes les combinaisons de faits et de règles. La façon dont Prolog évalue ces combinaisons — le plus rapidement possible, est appelée le backtracking.
Pour l’illustrer, traitons le Syllogisme célèbre:
All men are mortal.
Socrates is a man.
Hence, Socrates is mortal.
Ce que l’on traduit par un fait, et une règle:
mortal(X) :- man(X)
man(socrates).
Enfin, on peut reproduire le syllogisme en une unique requête:
?- mortal(socrates).
Yes
Pour répondre, Prolog a procédé par ordre: en partant de l’objectif demandé, il a parcouru — après avoir échoué à trouver le fait correspondant, toutes les règles disponibles, en l’occurrence ‘mortal(X)’, avec X=socrates. Prolog déduit que les X qui sont solution doivent vérifier le fait man(X), il cherche à vérifier man(socrates), parcours tous les faits pour trouver celui qui correspond, et réussit.
Les limites de la logique, les paralogismes ou sophismes sont elles aussi les limites de Prolog ? Pour le savoir, étudions un des paralogismes les plus connus:
Plus il y a de fromage, plus il y a de trous ;
(or) plus il y a de trous, moins il y a de fromage ;
(donc) plus il y a de fromage, moins il y a de fromage.
Où est donc la faille de ce faux syllogisme ? Prolog peut-il la déduire en l’état ? Voyons, définissions la situation avec deux règles et un fait:
plus_fromage.
plus_trous :- plus_fromage.
moins_fromage :- plus_trous.
Irrémédiablement, Prolog est piégé par le même biais que nous, humains: demandons lui si, avec les deux règles fixées d’après l’énoncé, et en partant du fait qu’on a ‘plus_fromage’, on a ‘moins_fromage’…
?- moins_fromage.
Yes
La raison pour laquelle Prolog reproduit notre erreur, c’est parce qu’elle est inhérente à notre description de la situation: le choix du modèle (donc des faits et règles), l’ambiguïté du langage — le français, pas le Prolog, sont les sources de notre erreur ! Ici on confond dans ‘plus_fromage’ deux situations distinctes: celle ou on fait varier la densité à volume constant, et celle ou on fait varier le volume à densité constante. Soit on prend un fromage plus gros avec la même proportion de trous, soit on prend un fromage aussi gros avec moins de trous, ce n’est pas la même chose.
Et pour Prolog ? En prenant en compte nos deux situations possibles pour ‘plus_fromage’, et en adaptant nos règles:
vol_const__densite_variable.
vol_variable__densite_const.
plus_fromage(vol_variable__densite_const).
plus_fromage(vol_const__densite_variable).
plus_trous(X) :- plus_fromage(X) , not( vol_variable__densite_const ).
moins_fromage(X) :- plus_trous(X) , not( vol_const__densite_variable ).
En effet, ‘plus_trous’ implique ‘moins_fromage’ seulement si la densité varie à volume constant, et vice-versa… alors?
?- moins_fromage(X).
No
Il n’existe pas de X tel qu’on ait à la fois ‘plus_fromage(X)’ et ‘moins_fromage(X)’, CQFD.
La force de Prolog, c’est aussi sa proximité avec la logique telle qu’elle s’est développée pendant plus de deux millénaires. Notre maîtrise de celle-ci, de ses formalismes, avec ses limites et ses paradoxes, est un très bon point de départ pour un langage qui trouvera certainement son utilité pratique dans le futur.
Lien utilisé pour tester les différents exemples, SWI-Prolog.
