Prolog, Programmation logique

Contents

Prolog 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 Moshe ben Nahman est une personne.
Nous nous posons la question suivante : Est-ce que Moshe ben Nahman est mortel(le) ?

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

∀X : mortel(X) ⇐ personne(X)
personne(moshe_ben_nahman)
? mortel(moshe_ben_nahman) ?

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

mortel(X) ← personne(X)
personne(moshe_ben_nahman)
?- mortel(moshe_ben_nahman)

Contents Haut

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.

  1. /*
  2. Exemple de code Prolog
  3. */
  4. mortel(X) :-  personne(X).
  5. % Moshe ben Nahman est une personne
  6. personne(moshe_ben_nahman).

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

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

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 %.

Contents Haut

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.

Contents Haut

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.

Contents Haut

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 horloge2.

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 = A1,..., Am
    • H ← B1,..., Bn) = (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 A1 alors
      soit σ mgu de H et de A1
      Σ[i + 1] := (Σ[i])σ
      G[i + 1] := (B1,..., Bn, A2,..., Am)σ
    • 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).

Contents Haut

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 ».

Contents Haut

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).

English translation

You have asked to visit this site in English. For now, only the interface is translated, but not all the content yet.

If you want to help me in translations, your contribution is welcome. All you need to do is register on the site, and send me a message asking me to add you to the group of translators, which will give you the opportunity to translate the pages you want. A link at the bottom of each translated page indicates that you are the translator, and has a link to your profile.

Thank you in advance.

Document created the 11/04/2010, last modified the 28/10/2018
Source of the printed document:https://www.gaudry.be/en/programmation-logique.html

The infobrol is a personal site whose content is my sole responsibility. The text is available under CreativeCommons license (BY-NC-SA). More info on the terms of use and the author.

Notes
  1. ↑a,b,c,d,e,f… 3 more links… 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 : corresponds to « 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 : corresponds to « couper » en français

Contents Haut

References

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

These references and links indicate documents consulted during the writing of this page, or which may provide additional information, but the authors of these sources can not be held responsible for the content of this page.
The author This site is solely responsible for the way in which the various concepts, and the freedoms that are taken with the reference works, are presented here. Remember that you must cross multiple source information to reduce the risk of errors.

Contents Haut