Prolog, Programmation logique

Inhaltsverzeichnis

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 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 :

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

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

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

Inhaltsverzeichnis 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. % von Braun Wernher est une personne
  6. 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 %.

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

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

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

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

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

Deutsche Übersetzung

Sie haben gebeten, diese Seite auf Deutsch zu besuchen. Momentan ist nur die Oberfläche übersetzt, aber noch nicht der gesamte Inhalt.

Wenn Sie mir bei Übersetzungen helfen wollen, ist Ihr Beitrag willkommen. Alles, was Sie tun müssen, ist, sich auf der Website zu registrieren und mir eine Nachricht zu schicken, in der Sie gebeten werden, Sie der Gruppe der Übersetzer hinzuzufügen, die Ihnen die Möglichkeit gibt, die gewünschten Seiten zu übersetzen. Ein Link am Ende jeder übersetzten Seite zeigt an, dass Sie der Übersetzer sind und einen Link zu Ihrem Profil haben.

Vielen Dank im Voraus.

Dokument erstellt 11/04/2010, zuletzt geändert 28/10/2018
Quelle des gedruckten Dokuments:https://www.gaudry.be/de/programmation-logique.html

Die Infobro ist eine persönliche Seite, deren Inhalt in meiner alleinigen Verantwortung liegt. Der Text ist unter der CreativeCommons-Lizenz (BY-NC-SA) verfügbar. Weitere Informationen auf die Nutzungsbedingungen und dem Autor.

Aufzeichnungen
  1. ↑a,b,c,d,e,f… 3 weitere 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 : entspricht « 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 : entspricht « couper » en français

Inhaltsverzeichnis Haut

Referenzen

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

Diese Verweise und Links verweisen auf Dokumente, die während des Schreibens dieser Seite konsultiert wurden, oder die zusätzliche Informationen liefern können, aber die Autoren dieser Quellen können nicht für den Inhalt dieser Seite verantwortlich gemacht werden.
Der Autor Diese Website ist allein dafür verantwortlich, wie die verschiedenen Konzepte und Freiheiten, die mit den Nachschlagewerken gemacht werden, hier dargestellt werden. Denken Sie daran, dass Sie mehrere Quellinformationen austauschen müssen, um das Risiko von Fehlern zu reduzieren.

Inhaltsverzeichnis Haut