L’intelligence artificielle avec la PROgrammation LOGique (a.k.a PROLOG)

A ceux qui souhaitent découvrir un autre pan du domaine de l’intelligence artificielle, Prolog est fait pour vous.

Introduit en 1972 par les français Alain Colmerauer et Philippe Roussel, le langage Prolog est le fruit d’une idée toute simple, à savoir dialoguer en français avec son ordinateur. Ainsi, au départ il n’était nullement question d’en faire un langage de programmation.

Étant donné la complexité du projet, ce dernier a donné le jour de fil en aiguille à un langage à part entière. Qui plus est un langage qui se veut clair et lisible afin de répondre à l’objectif de départ, à savoir dialoguer dans un langage nature avec sa machine.

(Ressource disponible à cette adresse pour en savoir davantage sur la naissance du projet).

Ce qui a fortiori permet à tout le monde d’écrire un programme avec celui-ci. C’est ce point qui s’avère être intéressant parce que cela permet à des personnes non initiées à l’informatique -des mathématiciens notamment- de profiter de l’outil informatique afin de résoudre des problèmes logiques. Un ordinateur n’est jamais qu’une machine capable d’effectuer des calculs plus vite qu’un humain.

Ce langage passerelle entre le langage naturel et la machine se compose de trois éléments :

  • de faits
  • de règles
  • de questions

Ainsi, le langage répond à une question considérant les règles et faits établies au préalable.

Sans entrer tout de suite dans le vif du sujet, voici un bref exemple de déclaration de faits ainsi que d’une règle :

food(burger).                        
food(sandwich).
food(pizza).
lunch(sandwich).
dinner(pizza).
meal(X) :- food(X).

De même, voici un exemple d’une question posée par un humain à la machine et de la réponse :

?- meal(X), lunch(X).
X = sandwich.

Basé sur le calcul de prédicats de premier ordre

Les mathématiciens étant une cible important de ce langage, il est basé sur la logique des prédicats pour faciliter sa prise en main. Cependant, ce n’est en aucun cas un prérequis.

On parle de prédicat (et non de fonction comme dans d’autres langages informatiques). Un prédicat est en général un fait, soit une information connue par le programme.

Une petite difficulté réside dans le fait de correctement interpréter le prédicat. Par exemple dans l’exemple qui suit, rien ne stipule l’ordre de lecture des arguments :

Qui est le chef de qui ? A vous de conventionner votre programme en choisissant le bon mot.

chief(shirley, audrey).

Un prédicat se constitue de clauses, soit un fait ou une règle en fonction de la nature de la clause. Par exemple, pour exprimer en fonction de condition on utilise une règle.

Elles sont définies dans une notation différente de la logique de premier ordre. En effet, des majuscules sont utilisées pour les variable et des minuscules pour les constantes, le contraire en logique.

En logique :

A ^B => C

En Prolog :

C : -A,B.

Remarque : La virgule sépare les clauses en Prolog.

Fait important, une clause ne retourne pas de valeur : soit elle s’exécute, soit elle échoue. De ce fait, on dit qu’une clause est composée d’un ou plusieurs but(s).

Pour résumer, nous avons des prédicats qui peuvent être des faits ou des règles. Et, les questions permettent de venir interroger cette base de connaissances.

La nature du langage

animal(dog).animal(cat).girl(audrey).girl(shirley).mother(audrey, shirley).

Voici les faits décris par le programme dans cet exemple :

  • cat et dog sont des animaux
  • shirley et audrey sont des filles
  • audrey est la mère de shirley

C’est pourquoi on parle d’un langage déclaratif.

Comme dit précédemment, si alain prend une majuscule, comme suit Alain, alors il ne s’agira plus d’une constante mais d’une variable.

Exemple de question avec des constantes :

:- mother(audrey, tiana).

Naturellement la réponse du programme à cette question (compte tenu de la base de faits déclarées ci-desssus) est :

false.

Un autre exemple de question avec une variable cette fois :

:- mother(audrey, Tiana).

La réponse du programme :

Tiana = shirley.

A présent, posons à Prolog des questions pour lesquelles l’interpréteur consultera les faits et les règles inscrits dans le programme.

Première question : shirley est-elle une fille ?

?-girl(shirley).

L’interpréteur nous répond true : shirley est bien une fille dans la base des faits.

Autre question : qui sont tous les animaux ?

?-animal(Animal).

La variable X va prendre pour valeur chaque nom d’animal (le point virgule permet de passer à la valeur suivante). Une fois que la liste est terminée, Prolog termine par un point. En l’occurrence, le résultat est :

Animal = dog;
Animal = cat.

C’est pourquoi on parle également d’un langage indéterministe. Il permet le traitement de problèmes comportant plusieurs solutions.

En outre, la notion de variable anonyme permet de ne pas accorder d’importance au contenu de la variable.

Par exemple : existe-t-il des animaux ?

?- animal(_).

Ici l’expression animal(_) sera vraie chaque fois que Prolog rencontre un animal (peut importe lequel) dans la base des faits du programme.

A la recherche de l’efficacité

Le langage est basé sur le chaînage arrière (depth-first).

C’est-à-dire que le programme extrait de la question posée par l’utilisateur un but, puis il commence par rechercher les règles dont le but est la conclusion. Chaque conditions qu’il traverse devient alors un but et itère ce processus récursivement.

Les clauses sont testées dans l’ordre du programme.

Si la conception d’un programme Prolog est dite déclarative, la phase d’interprétation est quelque peu procédurale. En effet, il existe un ordre dans les instructions à exécuter puisqu’il traite les lignes une à une de la première à la dernière.

L’avantage étant qu’il est possible “d’optimiser” un programme via l’ordre des clauses en concevant un programme de manière procédurale.

Par ailleurs

  • En prolog, il n’y a pas d’autres moyens de faire des boucles que d’utiliser la récursivité.
  • Les tableaux n’existent pas, les listes permettent de combler ce besoin. L’utilisation de crochet permet de lister des éléments :
[element1, element2]

L’opérateur « |» permet de jouer avec les listes en y ajoutant des élements par exemple :

[element0|[element1, element2]] = [element0, element1, element2]

element0 est le 1er élément de la liste qui se trouve à droite de l’opérateur « |».

Ou afficher la liste via la récursivité donc :

display([E|L]) :- write(E), display(L).
  • D’autres opérateurs :

== pour tester l’égalité

Le symbole « = » en Prolog signifie l’unification et pas l’affectation. Pour affecter une valeur numérique à une variable il faut utiliser « is ».

Exemple pour effectuer la somme de deux nombres :

somme(X,Y,S) :- S is X+Y.

\= pour tester l’inégalité

Les opérateurs classiques X<Y, X>Y, X=<Y, X>=Y, X+Y, X-Y, X/Y, X*Y

La division entière X//Y

Crédit image