Prolog, Programmation logique

Sommaire du document

Prolog [PROgrammation LOGique] est un langage de programmation logique céé par Alain Colmerauer et Philippe Roussel en France (Marseille) vers 1972. Il est utilisé dans les techniques d'intelligence artificielle, et dans le traitement de la linguistique.

Prolog nous permet de décrire un problème et son environnement (son domaine), et nous pouvons décrire ce que nous connaissons du domaine dans n'importe quel ordre.
Lorsque nous soumettons le problème, Prolog va tenter de le résoudre pour nous, sans nous embarrasser de la manière de le résoudre.

Exemple de programmation logique

Nous disposons des informations suivantes : toute personne est mortelle, et von Braun Wernher est une personne.
Nous nous posons la question suivante : Est-ce que von Braun Wernher est mortel(le) ?

Nous pouvons traduire ce problème logique en logique de premier ordre, ce qui nous donne :

Enfin, voici la traduction de la logique de premier ordre vers Prolog :

Syntaxe Prolog

Nous verrons plus en détails la syntaxe du langage Prolog, mais nous pouvons déjà voir un petit bout de code pour les plus pressés.

/*
Exemple de code Prolog
*/
mortel(X) :-  personne(X).
% von Braun Wernher est une personne
personne(von_braun_wernher).

Nous pouvons à présent poser nos questions comme ceci :

steph@astate:∼$ ?- mortel(von_braun_wernher)

Nous pouvons constater que les commentaires sur plusieurs lignes sont encadrés par /* et */, alors que les commentaires sur une seule ligne débutent par %.

Requêtes Prolog

Le but de notre programme est de nous donner la solution à une question, sous la forme d'une affirmation booléenne, et ces questions sont des requêtes en Prolog. Une requête débute par les signes ?- suivis par l'expression prédicative.

Si notre requête comporte des variables, Prolog devra procéder à une série de substitutions.

Clauses de Horn

Une clause de Horn est une clause qui contient au maximum un atome non nié.

Les clauses de Horn sont extrêmement utiles en programmation logique, et Prolog utilise les clauses de Horn étendues au calcul des prédicats.

Prolog comme une horloge abstraite

Alain Colmerauer a utilisé le terme « horloge abstraite » pour décrire l'exécution des réductions qu'utilise Prolog. Ce terme lui a été notamment suggéré par l'analogie entre son schéma et une horloge^[2].

L'horloge abstraite comporte une boîte d'unification, une boîte d'échec et terminaison, et le point d'entrée en haut (le balancier de notre horloge abstraite).

Structure de données de l'horloge abstraite

Dans l'exemple d'implémentation didactique suivant, nous utiliserons des tableaux et quelques variables pour mémoriser les données de fonctionnement de l'horloge abstraite Prolog. Cet exemple, s'il n'est pas le plus performant, est toutefois une implémentation fonctionnelle qui permet de comprendre comment fonctionne Prolog. Voici une idée de quelques variables utilisées :

• booléen echec initialisé à false qui nous indique si nous avons réussi ou pas notre dernière unification
• nombre entier i qui est le niveau d'inférence. C'est l'indice de la règle d'inférence que nous sommes occupés à traiter
• tableau R, de longueur rmax, qui contient les règles d'inférence
  R_[i] permet de mémoriser pour tout point de choix (c'est à dire pour tout niveau d'inférence) la dernière règle utilisée
• tableau Σ, le tableau des substitutions. Ce tableau mémorise tous les mgu produits progressivement, ce qui nous permet de produire à la fin une substitution calculée.
  Σ_[i] mémorise les mgu produits jusqu'au niveau d'inférence i, ce qui nous permet de revenir sur certains points de choix par la suite.
• G, qui mémorise les buts (requêtes à satisfaire).
  G_[i] mémorise le but qu'il reste à satisfaire au niveau d'inférence i

Fonctionnement de l'horloge abstraite

Voyons à présent le principe sommaire du corps de l'horloge abstraite (la boîte d'unification, et la boîte d'échec et terminaison).
Le principe est de pouvoir déterminer à chaque moment si nous sommes face à un échec, ou si nous avons atteint le but vide pour le niveau d'inférence considéré. Nous pouvons entrer dans un cas ou l'autre, mais pas dans les deux en même temps.

• Soient
  • G_[i = A₁,..., A_m
  • H ← B₁,..., B_n) = (i + 1)^ème copie de la règle G_[i]
    à chaque incrémentation les variables sont copiées et renommées.
  
  
  • Si H s'unifie avec A₁ alors
    soit σ mgu de H et de A₁
    Σ[i + 1] := (Σ[i])σ
    G[i + 1] := (B₁,..., B_n, A₂,..., A_m)σ
  • sinon echec est vrai
• Si la requête à satisfaire est vide ou si echec est faux. Nous ne pouvons avoir les deux cas en même temps :
  • Soit la requête à satisfaire est vide (nous sommes dans le cas d'une terminaison), imprimer Σ[i] restreint aux variables de G[0]
    • Si l'utilisateur introduit ; alors simulation d'un échec pour lancer la recherche d'une autre solution.
    • Sinon le traitement par l'horloge abstraite est terminé et retourne un succès.
  • Soit nous sommes en présence d'un échec d'unification, nous devons reprendre le traitement depuis l'inférence précédente (pour autant que i soit supérieur à 0, sinon échec définitif).

Cut

Parfois, nous souhaitons ne plus remettre en question certaines requètes, et le “cut”^[5] nous permet ce genre d'opération par l'élaguage d'une partie de notre arbre et/ou de recherche.

Le “cut” en Prolog est un atome spécial représenté par le point d'exclamation. Dans une conjonction d'atomes, nous placerons le “cut” après la virgule qui suit l'atome que nous souhaitons élaguer; comme le “cut” est lui-même un atome, nous ajoutons aussi une virgule entre le “cut” et le premier atome qui suit.
Comme le “cut” est un atome, il sera évalué, mais sa résolution réussit toujours directement (car il est plus un atome de gestion flux de traitement qu'un atome de définition du domaine).

Une fois que nous avons passé le “cut”, les alternatives que nous n'avons pas encore exploré ne sont plus accessibles.

Nous pouvons combiner le “cut” et “fail” pour court-circuiter une conclusion. Comme son nom l'indique, “fail” fera échouer directement la requête sans passer aux suivantes. Cela revient à dire « Inutile d'essayer d'autres alternatives ».

Nous pouvons aussi utiliser uniquement le “cut” pour dire « Si vous êtes arrivés ici, vous avez trouvé la solution unique au problème ».

Négation

Le “not” en Prolog est un prédicat qui permet d'inverser le résultat après la résolution de son argument.

not(X) peut se décomposer en :

1. Résoudre X
2. Inverser le résultat (si succès, rapporter échec; si échec, rapporter succès avec la substitution vide).

Attention que l'emploi du not sur des variables non instanciées retourne succès, car ça revient à exécuter un not(fail). Nous pouvons alors tester préalablement si la variable est instanciée par un ground(X).

Notes

1. ↑^{a,b,c,d,e,f,g,h,i} Prolog : PROgrammation LOGique
   
   
2. ↑ Horloge abstraite : Tout comme pour les arbres abstraits en informatique, l'horloge abstraite de Colmerauer est représentée à l'envers, le balancier en haut.
   
   
3. ↑^a,b,c most general unifier : correspond à « unificateur le plus général” en français
   
   
4. ↑^a,b,c mgu : “most general unifier” (en français, « unificateur le plus général »)
   
   
5. ↑ cut : correspond à « couper” en français
   
   

Références

1. IHDCB337 - Technique d'intelligence artificielle : JM Jacquet, Programmation déclarative (2009)
2. IHDCB337 - Technique d'intelligence artificielle : H Toussaint, Tp (2009)
3. Prolog : P. Trau, IPST-ULP (version 28/03/10)
4. Prolog : Wikipedia (version 28/03/10)

Ces références et liens indiquent des documents consultés lors de la rédaction de cette page, ou qui peuvent apporter un complément d'information, mais les auteurs de ces sources ne peuvent être tenus responsables du contenu de cette page.
L'auteur de ce site est seul responsable de la manière dont sont présentés ici les différents concepts, et des libertés qui sont prises avec les ouvrages de référence. N'oubliez pas que vous devez croiser les informations de sources multiples afin de diminuer les risques d'erreurs.

Structure du document