Dis ProLog, qui es-tu ?
La programmation logique est un moyen d’écrire des programmes informatiques en utilisant des langages basés sur la logique formelle, soient des langages basés sur des interrogations écrites en français.
Prolog comme exemple
Dans les années 70, Alain Colmerauer et Philippe Roussel développent le langage Prolog. Alors que la plupart des langages que nous connaissons sont itératifs (C, java etc..), ProLog est un langage dit déclaratif. Un langage déclaratif est le fait de se demander « que faire » plutôt que « comment faire ». C’est un langage, non pas composé de lignes d’instructions, mais d’un ensemble de règles définissant les relations entre les objets. ProLog (contraction de Programmation Logique) a eu de grandes influences sur le traitement de la langue et sur l’avancement des intelligences artificielles.
Dis Prolog, qu’est-ce qu’un langage déclaratif ?
Voici un exemple comparant une méthode itérative et une méthode déclarative :
Nous nous mettons dans la situation suivante : Vous rentrez du travail, passez devant une boulangerie et vous voulez acheter du pain et un croissant.
La façon itérative :
- Entrer dans la boulangerie
- Faire la queue
- Demander une baguette et un croissant
- Oui, pas trop cuite s’il vous plait
- Payer
- Prendre ses produits et partir
La façon déclarative :
-Je voudrais une baguette pas trop cuite et un croissant s’il vous plait.
Grossièrement, à la place de donner les instructions étape par étape (la façon itérative), en déclaratif il suffit de dire ce que l’on veut au programme qui va se débrouiller pour nous sortir une solution.
Construction de ProLog :
ProLog ne fonctionne qu’avec peu de types d’information, les objets ou terms. Il existe donc les constantes (chaines de caractères ou nombres), les variables, et les termes complexes (fonctions).
Prolog est composé de plusieurs fonctionnalités :
- L’unification
L’unification de deux termes revient à les rendre identiques en remplaçant des variables. On peut voir ça comme la résolution d’une équation.
L’unification associer les termes identiques, la variable X avec toutes les variables ou termes identiques. Une variable peut être unifiée avec une constante, si x= « voiture », elle va être unifiée avec la constante « voiture ». De même avec les fonctions, func(x) va alors être unifiée avec func(voiture).
Un exemple pour mieux comprendre :
Cette clause exprime la phrase « Léa habite à Paris ».
On exécute :
et le programme nous renvoie
Ainsi Paris et Ville ont été unifiés.
- Le backtracking
Le backtracking est le fait de retourner à un objectif précédent, et d’essayer de le re-satisfaire différemment.
Un exemple :
- Début à la root, les choix sont A et B, le programme choisi A
- Choix entre C et D, le programme choisi C
- C est la mauvaise réponse, retour à A
- À A, C a déjà été essayé et c’est faux, il essaye D
- D est faux, retour à A
- Toutes les solutions de A ont été essayées, retour à Root
- À Root, A a déjà été essayé, essai de B
- Choix entre E et F, choix de E
- C’est la bonne réponse.
-La récursivité
Le fait, pour un programme, de s’appeler soi-même jusqu’à vérifier une condition.
Pas de fonction en ProLog ?
Vous n’avez encore pas entendu parlé de fonctions en ProLog, et c’est normal, puisqu’on ne parle pas de « fonctions, mais de « prédicats ».
Un prédicat est organisé de plusieurs « clauses », elles-mêmes composées de buts.
Une clause ne renvoie pas de valeur, elle utilise l’unification des variables passées en paramètres. Le fonctionnement d’une clause est assez simple, soit les buts sont atteints et une valeur est « retournée » grâce à l’unification, soit un des buts n’est pas réussi et la clause échoue.
Nous n’avons pas encore évoqué les coupe-choix, le symbole de non-unification et l’instruction d’échec de clause.
Le coupe-choix « ! », est très utilisé en ProLog, il permet de signifier au programme que l’on ne s’intéresse pas aux points de choix en attente. C’est à dire que les autres solutions possibles ne seront pas examinées. Il est très utile lorsqu’une solution est suffisante, par exemple si l’on cherche une valeur dans une liste, on peut s’arrêter dès la première occurrence trouvée.
Exemple :
Soit un prédicat Afficher ([X|Y]), qui affiche le premier élément x d’une liste avant de s’appeler récursivement en passant le reste de la liste, Y en paramètre. Et on veut que ça s’arrête lorsque l’on atteint la liste vide.
On écrit alors :
afficher([]):-!. % s’arrête si on a la liste vide
afficher([X|Y]):-writeln(X),afficher(Y). % appel récursif si la liste est non vide
Et le résultat affiché sera alors :
?- afficher([a,b,c,d]).
a
b
c
d
true.
Cependant il est délicat de l’utiliser, car il peut perdre des solutions.
Le symbole de non-unification « _ » est utilisé lorsque dans une clause il n’est pas nécessaire de faire référence à un paramètre. C’est en effet utile puisque ça évite d’introduire des paramètres non-utilisés, pouvant être sources d’erreurs.
L’instruction de l’échec de clause « fail », signale l’échec de la clause courante et permet donc au programme de faire du backtracking en recherchant le dernier point de choix. Cette instruction peut, et est souvent associée au coupe-choix pour exprimer une exception dans un programme.
Prolog induit une programmation simple et claire à l’exécution rapide, c’est un langage avec une grande expressivité, qui peut s’intégrer facilement à un programme écrit dans un autre langage. Un langage à la syntaxe bien différente du C et du Java, mais plus simple car moins de mots réservés, ProLog est beaucoup utilisé pour les Intelligences Artificielles, c’est donc un langage d’avenir.
Et maintenant ?
Maintenant que vous en savez plus sur ProLog, si vous voulez en apprendre plus et vous exercer, voici un site proposant plusieurs problèmes (corrigés) à différents niveaux : https://sites.google.com/site/prologsite/prolog-problems
Sources :
http://www.info.univ-angers.fr/pub/stephan/MASTER2PRO/PROGRAMMATION_LOGIQUE/M2_Prog_Log.pdf
https://perso.liris.cnrs.fr/nathalie.guin/Prolog/Cours/Cours2-Prolog1.pdf
https://fr.wikipedia.org/wiki/Programmation_logique
https://medium.com/moral-robots/prolog-programming-in-logic-1ab391762831
https://matvidal.files.wordpress.com/2016/02/prologcours1.pdf
