Intelligence Artificielle AI - Prolog : PROgrammation LOGique Bases de l’Intelligence Artificielle
Télécharger PDFIntroduction à la programmation logique avec Prolog
Historique et origines de Prolog
Prolog est un langage de programmation logique créé en 1972.
Alain Colmerauer, à l'Université Aix-Marseille, a développé le premier interpréteur de Prolog.
Robert A. Kowalski, à l'Université d'Édimbourg, a posé le cadre théorique et créé le premier compilateur.
En 1982, une nouvelle version de Prolog (Prolog II) a vu le jour, avec de nombreux interpréteurs utilisant différentes syntaxes.
En 1996, Prolog IV a été introduit, incluant SWI-Prolog, qui est utilisé dans ce cours pour sa syntaxe et ses conventions.
Différents modes de programmation
Il existe trois styles principaux de programmation : impératif, fonctionnel et déclaratif.
Les langages impératifs, comme C, ADA, Pascal ou Java, décrivent une suite d'actions pour transformer des données en résultats.
Les langages fonctionnels, comme Lisp, Scheme ou CAML, définissent les résultats comme des compositions de fonctions appliquées aux données.
Prolog, langage déclaratif, permet de décrire un problème (les objets, leurs propriétés et leurs relations) sans préciser comment le résoudre.
Il est souvent utilisé en intelligence artificielle pour sa capacité à modéliser des connaissances et des raisonnements.
Le langage Prolog
Prolog est un langage d'expression des connaissances basé sur la logique des prédicats du premier ordre.
Il implémente le principe de résolution, une méthode de démonstration en logique.
En Prolog, un programme est une collection de clauses exprimant des faits, des règles et des questions.
L'utilisateur définit une base de connaissances sans instructions, affectations ou boucles explicites.
L'interpréteur Prolog utilise cette base pour répondre à des questions ou résoudre des problèmes.
Éléments de base en Prolog
Prolog distingue les constantes et les variables.
Constantes
Les constantes incluent :
- Les nombres (ex. : 12, 3.5)
- Les atomes (chaînes de caractères commençant par une minuscule)
- Les chaînes de caractères entre guillemets (ex. : "texte")
- La liste vide :
[ ]
Variables
Les variables sont des chaînes de caractères commençant par une majuscule ou par un underscore (_).
La variable _ représente une variable indéterminée.
Trois types de connaissances : faits, règles et questions
Un programme Prolog est composé d'un ensemble de faits et de règles décrivant un problème.
Faits
Les faits sont des assertions simples de la forme P(...)., où P est un prédicat.
Par exemple :
pere(jean, paul).pere(albert, jean).
Ces assertions correspondent à des clauses de Horn réduites à un littéral positif.
Règles
Les règles sont des assertions de la forme P(...) :- Q1 (...), ..., Qn (...)., où P est la tête et Q1,...,Qn la queue.
En logique, cela correspond à Q1 ∧ ... ∧ Qn → P.
Un paquet de clauses est un ensemble de règles ayant le même littéral de tête.
Exemple de règles pour exprimer la relation grand-père :
papy(X,Y) :- pere(X,Z), pere(Z,Y).papy(X,Y) :- pere(X,Z), mere(Z,Y).
Questions
Les questions sont des clauses de Horn sans littéral positif, de la forme :- Q1 (...), ..., Qn (...)..
Exemple : :- pere(jean,X), mere(annie,X).
Exécuter un programme Prolog revient à résoudre un but, c'est-à-dire trouver toutes les valeurs des variables qui satisfont la question.
L'unification
L'unification est un processus permettant de rendre deux formules identiques en attribuant des valeurs aux variables.
Le résultat est appelé unificateur, par exemple {Jean/X, Paul/Y}.
L'unificateur le plus général est recherché, et il peut être unique ou multiple.
L'unification peut réussir ou échouer, comme dans le cas de P(X,X) et P(2,3), qui ne peuvent pas être unifiés.
Déclaratif vs Procédural
Prolog combine des aspects déclaratifs et procéduraux.
En mode déclaratif, une clause P :- Q, R. signifie que P est vrai si Q et R sont vrais. L'ordre des clauses n'a pas d'importance.
En mode procédural, pour résoudre P, on résout d'abord Q, puis R. L'interpréteur parcourt les clauses dans l'ordre.
Littéraux ordonnés et réfutation par résolution
Les littéraux en Prolog sont ordonnés : pour résoudre P :- Q1, Q2, ..., Qn., on résout Q1, puis Q2, etc.
La réfutation par résolution consiste à prouver qu'une question est fausse en montrant qu'elle conduit à une contradiction.
Exemple :
- Faits :
pere(charlie, david).,pere(henri, charlie). - Règle :
papy(X,Y) :- pere(X,Z), pere(Z,Y). - Question :
papy(X,Y). - Réponse :
X=henri, Y=david.
Programmation récursive
Un programme récursif en Prolog s'appelle lui-même pour résoudre un problème.
Exemple : calcul de la factorielle.
- Cas d'arrêt :
factorielle(1) = 1. - Appel récursif :
factorielle(n) = n * factorielle(n-1)sin≠1.
Pour écrire un programme récursif, il faut :
- Choisir le paramètre de récursion.
- Définir la relation entre le résultat de l'appel récursif et le résultat final.
- Définir le(s) cas d'arrêt.
Exemple de récursion : relation "mariés"
Voici un exemple de programme récursif définissant une relation symétrique "mariés" :
mariés(jean, sophie).mariés(philippe, stephanie).mariés(A, B) :- mariés(B, A).
Ce programme permet de vérifier toutes les paires de personnes mariées.
Influence de l'ordre des clauses
L'ordre des clauses en Prolog affecte le processus de résolution.
Exemple avec la relation "ancêtre" :
- Version 1 :
ancêtre(X, Z) :- parent(X,Z).puisancêtre(X, Z) :- parent(X,Y), ancêtre(Y,Z). - Version 2 :
ancêtre2(X, Z) :- parent(X,Y), ancêtre2(Y,Z).puisancêtre2(X, Z) :- parent(X,Z).
La version 2 peut causer des boucles infinies si l'ordre des clauses n'est pas correctement géré.
Exemple de version problématique : ancêtre3(X, Z) :- ancêtre3(X,Y), parent(Y,Z). puis ancêtre3(X, Z) :- parent(X,Z).
La version 4 corrige ce problème en inversant l'ordre des clauses : ancêtre4(X, Z) :- ancêtre4(X,Y), parent(Y,Z). puis ancêtre4(X, Z) :- parent(X,Z).
FAQ
Qu'est-ce qu'un prédicat en Prolog ?
Un prédicat est une assertion qui peut être vraie ou fausse. Il est composé d'un nom suivi d'une liste d'arguments. Par exemple, pere(X,Y) est un prédicat qui peut être vrai si X est le père de Y.
Comment éviter les boucles infinies en Prolog ?
Pour éviter les boucles infinies, il faut bien ordonner les clauses et définir des cas d'arrêt clairs. Par exemple, dans un programme récursif, la clause de base doit être vérifiée avant la récursion.
Quelle est la différence entre un fait et une règle en Prolog ?
Un fait est une assertion simple qui ne contient pas de conditions, comme pere(jean, paul).. Une règle est une assertion conditionnelle qui utilise des clauses de Horn, comme papy(X,Y) :- pere(X,Z), pere(Z,Y)..