Prolog

Un article de Wikipédia, l'encyclopédie libre.

Vous avez de nouveaux messages (diff^?).

Cet article fait partie de la série
Langages de programmation

Langages à objets

C++ - C#
Delphi - Eiffel - Java
Groovy - Python - Ruby
Simula - Smalltalk
Visual Basic - WinDev

Langages impératifs

APL - ASP - Assembleur
BASIC - C - Cobol
Forth - Fortran - Logo
Pascal - Limbo - Perl - PHP

Langages fonctionnels

Haskell - ML/OCaml
Lisp/Common Lisp
Scheme
XSLT

Langages déclaratifs

Clips - Prolog

Langages concurrents

Ada 95 - Erlang

Langage de balisage

HTML - SGML - XML
S-expressions

Voir aussi

Conception - Codage
Tests - Optimisations

Prolog est l’un des principaux langages de programmation logique. Le nom Prolog est un acronyme de PROgrammation LOGique. Il a été créé par Alain Colmerauer et Philippe Roussel vers 1972. Le but était de faire un langage de programmation qui permettait 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). Ses syntaxe et 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 à n’accepter que les clauses de Horn. 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.

Une des particularités de prolog est que l'on peut construire une base de connaissance dans un ordre indéterminé. Prolog résoudra ensuite des séries de problèmes logiques.

[modifier] Types de données

Prolog n’emploie pas des types de données dans la manière habituelle des langages de programmation. Nous devons parler à ce propos des éléments lexicaux.

[modifier] 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).

[modifier] Nombres

La plupart des implémentations Prolog ne font pas de différence entre des nombres entiers et réels.

[modifier] Variables

Les variables sont indiquées en utilisant un ensemble de lettres, nombres et caractères soulignés 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 auxquel 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.

La variable anonyme est écrite avec un tiret bas (_).

[modifier] Termes

Les termes sont les seules façons dont Prolog peut représenter des données complexes. Un terme 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 est identifié par sa tête et son arité, habituellement écrit comme foncteur/arité.

Exemples de termes

aime(romeo,juliette)
f(g(X),h(Y))

[modifier] Listes

Une liste n’est pas un type de données isolé, car elle est définie par une construction récursive (utilisant le terme '.') :

l'atome [] est une liste vide
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)]
Décomposer en un seul élément: [abc | L1]
Décomposer en des éléments multiples: [abc, 1, f(x) | L2]
Expansion du terme: '.'(abc, '.'(1, '.'(f(x), '.'(Y, '.'(g(A, rst), [])))))

[modifier] 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 code ASCII.

[modifier] Faits

La programmation en Prolog est très différente de la programmation dans un langage impératif. En Prolog, vous alimentez une base de connaissances de faits et de règles ; vous pouvez alors faire des demandes à 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;
     non.

Dans ce second exemple, à la question 'chat(X)' l'interpréteur propose la réponse 'X = tom' unifiant la variable 'X' à l'atome 'tom'. L'utilisateur demande une autre réponse par ";", l'interpréteur répond qu'il n'en trouve pas.

Les prédicats sont en général définis pour exprimer quelque fait que le programme connaît à propos du monde. Dans la plupart des cas, l’usage de prédicats requiert une certaine convention. Donc, quelle version des deux prédicats ci-dessous voudrait signifier que Pat est le père de Sally ?

père(sally, pat).
père(pat, sally).

Dans les deux cas, 'père' est la tête tandis que 'sally' et 'pat' sont les arguments. Cependant, dans le premier cas, Sally vient en premier dans la liste des arguments, et dans le second c’est Pat (l’ordre dans la liste des arguments importe). Le premier cas est un exemple d’une définition dans l’ordre verbe-sujet-objet, et le second de verbe-objet-sujet. Comme Prolog ne comprend pas le langage naturel, les deux versions sont correctes en ce qui le concerne ; cependant c’est un bon style de programmation que d'adopter des conventions cohérentes dans un programme.

Quelques prédicats sont bâtis dans le langage et permettent à un programme Prolog de faire des activités de routine (comme les entrée/sortie, utiliser 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.

[modifier] 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.

Ce qui n’est pas autorisé, ce sont des règles comme:

a;b :- c.

qui est « si c alors a ou b ». C’est à cause de la restriction pour les clauses de Horn.

[modifier] Évaluation

Quand l’interpréteur reçoit une demande il essaye de trouver des faits qui correspondent à la question. Si aucun fait simple n'est disponible, il essaye de satisfaire toutes les règles qui ont le fait comme conclusion. Par exemple ayant ce code Prolog

frère_ou_sœur(X,Y) :- parent(Z,X), parent(Z,Y).
père(X,Y) :- parent(X,Y), mâle(X).
mère(X,Y) :- parent(X,Y), femelle(X).
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).
mâle(tom).
femelle(trude).
mâle(mike).

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 assemblant (substituant) sally à X et erica à Y. 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.

Le code

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

peut sembler suspect. Après tout chaque parent n’est pas un père. Mais il est vrai que chaque père est un parent. D’un autre côté, quelqu’un n’est la mère de l’un que si elle est à la fois son parent et femelle.

Pour indiquer que tous les pères sont mâle vous avez besoin du code

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

ce qui simplement est indifférent à qui est l’enfant (le soustiret est une variable anonyme).

[modifier] Négation

Typiquement, une demande est considérée comme fausse si on ne trouve pas de règles ou de faits qui montrent qu'elle est vraie. Cela est appelé la prémisse du monde fermé ; on considère que tout ce qui doit être connu est inclus dans la base de données, alors il n’y a pas de monde extérieur qui pourrait contenir les preuves inconnues. En d'autres termes, si un fait n’est pas connu comme étant vrai (ou faux), il est considéré comme faux (ou vrai).

Une règle comme celle-ci :

mangeable(X) :- not indigeste(X).
(not est en miniscule et pas en Majuscule, sinon l'interpreteur la prendra pour une variable !)

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 échec.

[modifier] Exécution

Prolog est un langage logique, aussi en théorie vous ne devriez pas vous préoccuper de comment 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.

[modifier] 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