Prolog, Programmation logique

Inhoudsopgave

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 Jon Postel est une personne.
Nous nous posons la question suivante : Est-ce que Jon Postel 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(jon_postel)
? mortel(jon_postel) ?

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

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

Inhoudsopgave 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. % Jon Postel est une personne
  6. personne(jon_postel).

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

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

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

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

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

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

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

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

Nederlandse vertaling

U hebt gevraagd om deze site in het Nederlands te bezoeken. Voor nu wordt alleen de interface vertaald, maar nog niet alle inhoud.

Als je me wilt helpen met vertalingen, is je bijdrage welkom. Het enige dat u hoeft te doen, is u op de site registreren en mij een bericht sturen waarin u wordt gevraagd om u toe te voegen aan de groep vertalers, zodat u de gewenste pagina's kunt vertalen. Een link onderaan elke vertaalde pagina geeft aan dat u de vertaler bent en heeft een link naar uw profiel.

Bij voorbaat dank.

Document heeft de 11/04/2010 gemaakt, de laatste keer de 28/10/2018 gewijzigd
Bron van het afgedrukte document:https://www.gaudry.be/nl/programmation-logique.html

De infobrol is een persoonlijke site waarvan de inhoud uitsluitend mijn verantwoordelijkheid is. De tekst is beschikbaar onder CreativeCommons-licentie (BY-NC-SA). Meer info op de gebruiksvoorwaarden en de auteur.

Notes
  1. ↑a,b,c,d,e,f… 3 meer 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 : komt overeen met « 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 : komt overeen met « couper » en français

Inhoudsopgave Haut

Referenties

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

Deze verwijzingen en links verwijzen naar documenten die geraadpleegd zijn tijdens het schrijven van deze pagina, of die aanvullende informatie kunnen geven, maar de auteurs van deze bronnen kunnen niet verantwoordelijk worden gehouden voor de inhoud van deze pagina.
De auteur Deze site is als enige verantwoordelijk voor de manier waarop de verschillende concepten, en de vrijheden die met de referentiewerken worden genomen, hier worden gepresenteerd. Vergeet niet dat u meerdere broninformatie moet doorgeven om het risico op fouten te verkleinen.

Inhoudsopgave Haut