Prolog

Pour les articles homonymes, voir Prolog (homonymie).

Prolog
Apparu en	1972
Auteur	Alain Colmerauer et Philippe Roussel
Paradigme	Programmation logique

Prolog est l’un des principaux langages de programmation logique. Le nom Prolog est un acronyme de PROgrammation en LOGique. Il a été créé par Alain Colmerauer et Philippe Roussel vers 1972. Le but était de créer un langage de programmation qui permettrait d'utiliser l'expressivité de la logique au lieu de définir pas à pas la succession d'instructions que doit exécuter un ordinateur.

Prolog est utilisé dans de nombreux programmes d’intelligence artificielle et dans le traitement de la linguistique par ordinateur (surtout ceux concernant les langages naturels). Sa syntaxe et sa sémantique sont considérées comme très simples et claires (le but original était de procurer un outil pour les linguistes ignorant l’informatique). Beaucoup de recherches menant à l’implémentation actuelle de Prolog vinrent des effets du projet pour les ordinateurs de la cinquième génération qui utilisaient comme base une variante.

Prolog est basé sur le calcul des prédicats du premier ordre ; cependant il est restreint dans sa version initiale à n’accepter que les clauses de Horn (les versions modernes de Prolog acceptent des prédicats plus complexes, notamment avec le traitement de la négation par l'échec). L’exécution d’un programme Prolog est effectivement une application du théorème prouvant par résolution du premier ordre. Les concepts fondamentaux sont l’unification, la récursivité et le retour sur trace. L'algorithme de résolution de Prolog est basé sur une extension de la SLD-résolution.

Une des particularités de Prolog est que l'on peut construire une base de connaissances dans un ordre indéterminé. Prolog peut ensuite résoudre des séries de problèmes logiques relatifs à une telle base de connaissances (notion base de données déductive).

Les différents types de termes

Prolog n’emploie pas des types de données selon la manière habituelle des langages de programmation. Ceci est principalement dû au fait qu'en Prolog, il n'y a pas de distinction réelle entre les données du programme et le programme lui-même (principe de la programmation déclarative). Nous devons parler à ce propos des éléments lexicaux, appelés termes, et qui englobent les types suivants.

Atomes

Les textes constants sont introduits sous forme d’atomes. Un atome est une séquence consistant en lettres, nombres et sous-tirets, qui commence par une lettre minuscule. Habituellement, si un atome non alphanumérique est nécessaire, il est entouré d'apostrophes (par exemple '+' est un atome, + est un opérateur).

Nombres

La plupart des implémentations Prolog ne font pas de différence entre des nombres entiers et à virgule flottante.

Variables

Les variables sont indiquées en utilisant un ensemble de lettres, nombres et caractères de soulignement et commençant avec une lettre majuscule.

Par exemple "X3" et "Prix_Unitaire" sont des noms de variables.

Dans l’environnement Prolog, à la différence des langages de programmation procéduraux, une variable n’est pas un contenant auquel on peut affecter une valeur. Son comportement est plus proche d’une forme, initialement indéfinie, que l'on précise de plus en plus par unification. Une fois que la variable est unifiée, sa valeur ne peut plus être modifiée au sein d'une même branche d'évaluation (le retour sur trace permet toutefois de revenir sur cette unification).

La variable anonyme est écrite avec un tiret bas (_). Toute variable dont le nom commence par un tiret bas est également une variable anonyme.

Termes composés

Les termes composés sont les seules façons dont Prolog peut représenter des données complexes. Un terme composé consiste en une tête, aussi appelée foncteur (qui doit être un atome), et des paramètres (sans restriction de type). Le nombre de paramètres, aussi appelé arité du terme, est significatif. Un terme composé est identifié par sa tête et son arité, il est habituellement écrit comme foncteur/arité.

Exemples de termes composés :

• aime(romeo,juliette)

Le foncteur est aime et l'arité 2, le terme composé s'écrit aime/2.

• f(g(X),h(Y))

Le foncteur est f et l'arité 2, le terme composé s'écrit f/2.

• initialisation

Le foncteur est initialisation et l'arité 0, le terme composé s'écrit initialisation/0. Un atome est donc un terme composé d'arité 0.

Listes

Une liste n’est pas un type de données isolé, car elle est définie par une construction récursive (utilisant le foncteur . d'arité 2, c'est donc au niveau de la représentation interne un terme composé) :

1. l'atome [] est une liste vide ;
2. si T est une liste et H est un élément, alors le terme '.'(H, T) est une liste.

Le premier élément, appelé la tête, est H, suivi par les contenus du reste de la liste, indiqué comme T ou queue. La liste [1, 2, 3] serait représentée en interne comme '.'(1, '.'(2, '.'(3, []))) Un raccourci de syntaxe est [H | T], lequel est surtout utilisé pour construire des règles. La totalité d’une liste peut être traitée en agissant sur le premier élément, et ensuite sur le reste de la liste, par récursivité.

Pour la facilité du programmeur, les listes peuvent être construites et déconstruites de diverses manières.

• Énumération d'éléments : [abc, 1, f(x), Y, g(A, rst)]
• Extraction de l'élément de tête : [abc | L1]
• Extraction de plusieurs éléments de tête : [abc, 1, f(x) | L2]
• Expansion du terme : '.'(abc, '.'(1, '.'(f(x), '.'(Y, '.'(g(A, rst), [])))))

Chaînes de caractères

Les chaînes de caractères sont en général écrites comme une séquence de caractères entourés par des apostrophes. Elles sont souvent représentées en interne par une liste de codes ASCII.

Prédicats

La programmation en Prolog est très différente de la programmation dans un langage impératif. En Prolog, on alimente une base de connaissances de faits et de règles ; il est alors possible de faire des requêtes à la base de connaissances. L’unité de base de Prolog est le prédicat, qui est défini comme étant vrai. Un prédicat consiste en une tête et un nombre d’arguments. Par exemple :

chat(tom).

Ici 'chat' est la tête, et 'tom' est l’argument. Voici quelques demandes simples que vous pouvez demander à un interpréteur Prolog basé sur ce fait :

?- chat(tom).
     oui.

?- chat(X).
     X = tom;
     fail.

Dans ce second exemple, à la question 'chat(X)' l'interpréteur propose la réponse 'X = tom' unifiant la variable 'X' à l'atome 'tom'. Dans la terminologie Prolog il s'agit d'un succès. Après cette première réponse, l'utilisateur peut demander s'il y a d'autres réponses en utilisant le ";" (symbole de la disjonction), ici l'interpréteur répond qu'il n'en trouve pas. Cette recherche d'autres solutions repose sur un modèle d'exécution non-deterministe (au sens du non-déterminisme des automates non-déterministes) avec retour sur les différents points de choix et exploration des alternatives non explorées.

?- chat(vim).
     fail.

Dans ce dernier exemple, à la question 'chat(vim)' l'interpréteur répond qu'il ne peut pas prouver ce fait, dans la terminologie Prolog il s'agit d'un échec. Dans une certaine mesure (par exemple en faisant l'hypothèse que tous les faits sont connus, i.e. hypothèse du monde clos), cela signifie que 'vim' n'est pas un chat.

Les prédicats sont en général définis pour exprimer les faits que le programme connaît à propos du monde. Dans la plupart des cas, l’usage de prédicats requiert une certaine convention. Par exemple, la sémantique des deux prédicats suivants n'est pas immédiate :

pere(marie, pierre).
pere(pierre, marie).

Dans les deux cas, 'père' est la tête tandis que 'marie' et 'pierre' sont les arguments. Cependant, dans le premier cas, Marie vient en premier dans la liste des arguments, et dans le second c’est Pierre (l’ordre dans la liste des arguments importe). Le premier cas est un exemple d’une définition dans l’ordre verbe-objet-sujet et pourrait se lire avec l'auxiliaire 'avoir' : Marie a pour père Pierre, et le second de verbe-sujet-objet et pourrait se lire ave l'auxiliarire 'être' : Pierre est le père de Marie. Comme Prolog ne comprend pas le langage naturel, les deux versions sont correctes en ce qui le concerne ; cependant il est important d'adopter des normes de programmation cohérentes pour un même programme. En général, c'est plutôt l'auxiliaire 'être' qui est utilisé.

Quelques prédicats sont bâtis dans le langage et permettent à un programme Prolog de faire des activités de routine (comme de l'évaluation numérique, les entrée/sortie, les fonctionnalités de l'interface graphique et généralement communiquer avec le système de l’ordinateur). Par exemple, le prédicat write peut être utilisé pour l’affichage à l’écran. Donc

write('Bonjour').

présentera le mot 'Bonjour' sur le moniteur. De tels prédicats ne relèvent pas à proprement parler de la programmation logique, leur fonctionnalité reposant exclusivement sur leurs effets de bords.

D'autres prédicats bâtis dans le langage sont de nature logique, et inclus dans des bibliothèques. Ils servent à simplifier le développement en encapsulant des traitements génériques, comme des algorithmes de traitement de listes par exemple.

D'autres prédicats, enfin, sont d'ordre supérieur et servent à contrôler l'exécution des interprètes Prolog (par exemple, ajout/retrait dynamique de règles et faits, abandon de points de choix, récolte des résultats d'une requête, ...)

Sans les prédicats prédéfinis, Prolog est parfois appelé Pure Prolog (selon le standard iso en anglais : definite Prolog).

Règles

Le second type d’instructions en Prolog est la règle. Un exemple de règle est :

lumière(on) :- interrupteur(on).

Le « :- » signifie « si »; cette règle indique lumière(on) est vraie si interrupteur(on) est vrai. Les règles peuvent aussi utiliser des variables comme :

père(X,Y) :- parent(X,Y), mâle(X).

Ce qui signifie « si quelqu’un est le parent de quelqu’un d'autre et que c'est un mâle, il en est donc le père ». L’antécédent et conséquent sont dans l’ordre inverse de ce que l’on trouve normalement en logique. Il est possible de placer des prédicats multiples et en conséquence, groupé avec une conjonction « et », par exemple :

a, b, c :- d.

qui est simplement l’équivalent de trois règles séparées, cependant les trois règles séparées ne sont pas l'équivalent de (a et b et c) si d, puisqu'il s'agit d'un « ou » inclusif :

a :- d.
b :- d.
c :- d.

Les règles de ce type ne sont par contre pas autorisées :

a;b :- c.

qui signifie « si c alors a ou b ». Ce n'est en effet pas une clause de Horn.

On notera qu'un fait est un cas particulier de règle. En effet les deux lignes suivantes sont équivalentes :

a.
a :- true.

Évaluation

Quand l’interpréteur reçoit une requête, il recherche les règles (faits inclus) dont la partie gauche peut être unifiée avec la requête, et effectue cette unification avec la première règle trouvée. Par exemple ayant ce code Prolog :

frère_ou_sœur(X,Y) :- parent(Z,X), parent(Z,Y), X \= Y.
parent(X,Y) :- père(X,Y).
parent(X,Y) :- mère(X,Y).
mère(trude, sally).
père(tom, sally).
père(tom, erica).
père(mike, tom).

Il en résulte que la demande suivante est évaluée comme vraie:

?- frère_ou_sœur(sally, erica).
     oui.

L’interpréteur arrive à ce résultat en faisant correspondre la règle frère_ou_sœur(X,Y) en unifiant X avec sally et Y avec erica. Cela signifie que la demande peut être étendue à parent(Z,sally), parent(Z,erica). Faire correspondre cette conjonction est obtenu en regardant tous les parents possibles de sally. Cependant, parent(trude,sally) ne mène pas à une solution viable, parce que si trude est substitué pour Z, parent(trude,erica) devra être vrai, et aucun fait tel (ou quelque règle qui peut satisfaire cela) n'est présent. Aussi à la place, tom est substitué pour Z, et erica et sally apparaissent être frère_ou_sœur néanmoins.

Négation par l'échec

La négation logique pure n'existe pas en Prolog, on se repose sur la négation par l'échec, qui se note différemment suivant les implémentations de Prolog (nous adopterons la notation par le mot-clé not). En négation par l'échec, un prédicat est considéré comme faux si, en un temps fini, on échoue à montrer qu'il est vrai (par l'algorithme de résolution de Prolog). Cela est appelé l'hypothèse du monde clos (opposé à l'hypothèse du monde ouvert) : on considère que tout ce qui doit être connu est inclus dans la base de données, il n’y a pas de monde extérieur qui pourrait contenir des éléments de preuve inconnus du programme. En d'autres termes, tant qu'un fait n’est pas connu comme étant vrai, il est considéré comme faux.

Une règle comme celle-ci :

mangeable(X) :- not indigeste(X).

peut seulement être évaluée en cherchant d'abord à montrer que 'indigeste(X)' est vrai. Si cette recherche échoue, alors "mangeable(X)" est vrai. C'est ce qu'on appelle la négation par l'échec.

Exécution

Prolog est un langage logique, aussi en théorie vous ne devriez pas vous préoccuper de la façon dont il s’exécute. Cependant il est quelquefois prudent de prendre en compte comment l’algorithme d’inférence agit, pour éviter qu’un programme Prolog ne dure trop longtemps.

Par exemple, nous pouvons écrire du code pour compter le nombre d’éléments d’une liste.

elems([],0).
elems([H|T], X) :- elems(T, Y), X is Y + 1.

Cela signifie simplement; si la liste est vide, le nombre d’éléments est zéro. Si une liste n’est pas vide, alors X est augmenté de un par rapport à Y, lequel est le nombre d’éléments dans le reste de la liste sans le premier élément.

Dans ce cas, il y a une distinction claire entre les cas dans l’antécédent dans les règles. Mais considérez le cas où vous avez besoin de décider si vous continuez à jouer dans un casino;

miser(X) :- avoirargent(X).
miser(X) :- avoircrédit(X), NOT avoirargent(X).

Si vous avez de l’argent, vous continuez à miser. Si vous avez tout perdu vous avez besoin d’emprunter, ou sinon... plus de pari. avoirargent(X) peut être une fonction très coûteuse, par exemple, si elle peut accéder à votre compte bancaire par l’internet. Mais c’est la même chose pour avoircrédit.

En théorie, les implémentations de Prolog peuvent évaluer ces règles dans n’importe quel ordre, aussi vous pourriez aussi bien avoir écrit;

miser(X) :- avoircrédit(X), NOT avoirargent(X).
miser(X) :- avoirargent(X).

Ce qui est bien, parce que les deux options s’excluent l’une l’autre. Cependant vérifier si vous pouvez obtenir un prêt n’est pas nécessaire si vous savez que vous avez de l’argent. Aussi en pratique, les implémentations de Prolog testeront d'abord la règle que vous avez écrit en premier. Vous pouvez utiliser l’opérateur cut pour dire à l’interpréteur de sauter la deuxième option si la première suffit. Par exemple:

miser(X) :- avoirargent(X), !.
miser(X) :- avoircrédit(X), NOT avoirargent(X).

Cela est appelé un opérateur d’arrêt vert. Le ! dit simplement à l’interpréteur de ne plus chercher d’alternative. Mais vous notez que si vous avez besoin d’argent il a besoin d’évaluer la seconde règle, et il le fera. Evaluer avoirargent dans la deuxième règle est plutôt inutile car vous savez que vous n’en avez pas, pour la bonne raison que, sinon, la seconde règle ne serait pas évaluée. Aussi vous pouvez changer le code en:

miser(X) :- avoirargent(X), !.
miser(X) :- avoircrédit(X).

Cela est appelé un opérateur d’arrêt rouge, parce qu’il est dangereux de faire cela. Vous êtes maintenant dépendant du placement correct de l’opérateur d’arrêt et l’ordre des règles pour déterminer leur sens logique. Les accidents de Couper-et-coller guettent dans les coins sombres. Si les règles sont mélangées, vous pouvez maintenant utiliser votre carte de crédit avant de dépenser votre argent disponible.

Grammaire générative

Lorsqu'on fait de la grammaire générative avec Prolog, le but est de ne pouvoir générer que des phrases grammaticalement correctes ; on peut aussi rajouter des foncteurs pour que Prolog nous donne des arbres représentant la structure des phrases.

EDITEUR : domains liste=string* predicates s(liste,liste) sn(liste,liste) sv(liste,liste) clauses /*grammaire*/ s(L0,L):-sn(L0,L1),sv(L1,L). /*lexique*/ sn([je|U],U). sv([mange|U],U). sv([viens|U],U). DIALOGUE : Goal:s([je,viens],[]) Yes Goal:s([je,mange],[]) Yes Goal:s([viens,mange],[]) No

EDITEUR : domains liste=string* expr= fs(string,string) predicates s(liste,liste,expr) sn(liste,liste,string) sv(liste,liste,string) clauses /*grammaire*/ s(L0,L,fs(A,B)):-sn(L0,L1,A),sv(L1,L,B). /*lexique*/ sn([je|U],U,je). sv([mange|U],U,mange). sv([viens|U],U,viens). DIALOGUE : Goal:s([je,viens],[],R) R=fs("je","viens") 1 Solution Goal:s([je,mange],[],R) R=fs("je","mange") 1 Solution Goal:s([viens,mange],[],R) No Solution

Réversibilité

Une particularité de Prolog est de ne pas donner de statut aux paramètres d'un prédicat, ce ne sont pas des paramètres 'donnés' ou 'résultats', ou même 'donnés/résultats', leur statut est indifférent et sera définis en fonction des requêtes utilisées.

Ceci permet, parfois, la définition de prédicats réversibles, c'est-à-dire dont les appels standards, permettant d'obtenir des résultats à partir de données, peuvent être inversés pour chercher les données initiales menant à certains résultats (alors ce qui est donné, ce sont les résultats, et ce qui est obtenu (les résultats) ce sont les données initiales recherchées).

Exemples

Symétrique d'un arbre binaire

Prenons des arbres binaires avec comme nœud f et comme feuille 0 ou 1.

 symetrique(0,0).
 symetrique(1,1).
 symetrique(f(A,B),f(Y,X)):-symetrique(A,X), symetrique(B,Y).

L'utilisation standard de ce prédicat est du type :

 ?- symetrique(f(f(0,1),1),R).
   R = f(1,f(1,0))

Mais l'on peut aussi avoir :

 ?- symetrique(A,f(f(0,1),1)).
   A = f(1,f(1,0))

Particularités de Prolog

Comme langage de programmation, Prolog se distingue par :

• le non-déterminisme, pour la résolution de problèmes ouverts : le 'ou' utilisé en Prolog est un vrai 'ou' logique qui permet l'exploration de l'ensemble des possibles.
• la réversibilité (cf. plus haut)
• la gestion des requêtes sous-contraintes/sur-contraintes : l'absence de statut pour les paramètres d'un prédicat (cf. réversibilité) et le modèle d'exécution employé permet, d'un côté, l'emploi de requêtes sous-contraintes exposant l'ensemble des possibles, et de l'autre côté, l'emploi de requêtes sur-contraintes permettant la vérification de propriétés particulières sur les solutions exhibées ou le filtrage de ces solutions.

Et après ?

Prolog et la programmation logique a donné naissance à un courant de programmation reprenant la plupart des spécificités de Prolog et les apports de la programmation par contrainte pour aboutir à la programmation logique par contrainte (PLC).

Autres pistes :

• vers les bases de données (?).
• avec du parallélisme (?).

Implémentations

• Amzi! Prolog, payant sauf version sans serveur ni redistribuables
• B-Prolog, payant sauf Academic licence
• Ciao Prolog, libre (GPL)
• GNU Prolog, développé par l'INRIA, libre (GPL)
• Open Prolog, libre (postcardware), pour Mac
• Prolog.NET, développé à l'Institut de Technologie de l'Oregon, libre, arrêté en 2006, pour .NET 2.0
• Qu-Prolog, un prolog multithread développé par l'Université du Queensland, libre, Unix et Linux seulement
• Quintus Prolog, développé par le Swedish Institute for Computer Science, multiplateforme, payant
• Rebol Prolog, implémentation en Rebol, à interpréter dans Rebol
• SICStus Prolog, développé par le Swedish Institute for Computer Science, payant
• Strawberry Prolog, version light gratuite
• SWI Prolog, développé par l'Université d'Amsterdam, libre (GPL)
• TuProlog, gratuit, deux versions, Java ou .NET
• Visual Prolog, Personal Edition gratuite
• http://xsb.sourceforge.net/ XSB, gratuit, basé sur InterProlog comme SWI et Yap
• YAP Prolog, développé par l'université de Porto, gratuit, multiplateforme, rapide
• Squeak Prolog Un Prolog intégré à Smalltalk dans l'environnement Squeak, issu du Prolog intégré à Smalltalk/V. Syntaxe non standard mais permet de mêler programmation objet impérative (Smalltalk) et logique (Prolog). Smalltalk peut poser des questions à Prolog et Prolog peut exécuter des ordres Smalltalk. Gratuit.
• Prolog II (1982) III & IV (1996), gratuits, PC et DOS ou Windows, les Prologs de Alain Colmerauer et son équipe de Marseille

Bibliographie

• Jean-Paul Delahaye, Cours de Prolog avec Turbo Prolog, Eyrolles, 1988 - id : 9782212081916.
• Jacky Legrand, Le langage Prolog - Exemples en Turbo Prolog, Technip, 1992 - (ISBN 2-7108-0627-4).
• Patrick Blackburn, Johan Bos, Kristina Streignitz, PROLOG tout de suite, College Publications, 7 août 2007.

Voir aussi

• Règle de résolution
• Warren's Abstract Machine

Liens externes

• (fr) Cours et Tutoriel Prolog

• (en) Learn Prolog Now!
• (fr) Page d'accueil d'Alain Colmerauer