Cours Prolog

5/11/2018 Cours Prolog - slidepdf.com

http://slidepdf.com/reader/full/cours-prolog 1/34

C.U. SOUK AHRAS 3eme Année LMD Informatiqu

MOKDAD AROUS Cours Programmation Logiqu

Chapitre 01 : Introduction

1. Préambules

1.1. Système expert

Les experts d'un domaine ont pour caractéristiques :

• d'être rares, donc peu disponibles.

• d'être compétents (si possible les meilleurs).

• d'être souvent incapables d'expliquer leur démarche.

• d'être mortels. Les objectifs des systèmes experts :

• rendre une expertise accessible à tous.

• approcher au mieux la perfection.

• décortiquer le raisonnement expert pour expliquer.

• rendre une connaissance experte insensible au temps.

En un mot, simuler le comportement d'un expert humain sans avoir les petits (et grands) défauts de lanature humaine.

D'une manière générale, un système expert (SE) est un outil capable de reproduire les mécanismescognitifs d'un expert, dans un domaine particulier, il s'agit de l'une des voies tentant d'aboutir àl'intelligence artificielle. Plus précisément, un système expert est un logiciel capable de répondre à desquestions, en effectuant un raisonnement à partir de faits et de règles connus. Il peut servir notammentcomme outil d'aide à la décision.

a) Structure générale d'un SE

Lors de la conception d’un système expert, on sépare explicitement les connaissances spécifiques dudomaine et les mécanismes d’interprétation. Pour simplifier, on peut structurer un système expert de la

manière suivante : La base de faits: contient les informations concernant le problème particulier à résoudre. Cette

base fournit les conditions initiales de résolution, à partir desquelles des connaissances pourront êtreutilisées.

La base de règles: rassemble l’ensemble des connaissances du domaine, exprimées sous une formparticulière.

http://fr.wikipedia.org/wiki/Intelligence_artificielle



http://fr.wikipedia.org/wiki/Logiciel



http://fr.wikipedia.org/w/index.php?title=Aide_%C3%A0_la_d%C3%A9cision&action=edit&redlink=1









MOKDAD AROUS Cours Programmation Logiqu2

Le moteur d’inférence: simule le raisonnement de l’expert en enchaînant les connaissances suivan

une certaine logique. Il est en principe indépendant de la base et il est capable d’effectuer desrapprochements entre les connaissances et le problème à résoudre.

Quand on lance le système expert, le moteur d’inférence exploite à la fois les faits et les connaissances et

en tire de nouvelles informations grâce au moteur d’inférence. Les faits de départ, puis ceux résultant des

déductions produites par l’action du moteur d’inférence sur la base de connaissances, viennents’accumuler dans la base de faits.

Cette structure en trois parties est le principal avantage des systèmes experts sur les programmesclassiques. En effet, la base de connaissances peut être développée, modifiée, agrandie sans qu’il ne soit

nécessaire de modifier le moteur d’inférence.

Les faits: Toute description d'une situation implique des entités liés par des relations.

Exemple:

La relation est-un :est-un ( PHILOSOPHE, HOMME)

La relation nationalité :nationalité ( J.P.SARTRE, FRANCAIS )

La relation mortel? :

est-un ( x, HOMME) mortel? ( x, oui )

Base de ConnaissanceBase de

FaitsBase deRègles

Expert

Utilisateur

Moteurd'inférenc

Acquisition du

savoir

Interface utilisateur





Les règles de production: Une règle de production est composée

• d'une partie prémisse (SI):

= condition logique que doivent vérifier des faits.

• d'une partie condition (ALORS):

= actions à opérer sur la base de faits.Les actions usuelles: ajouter, modifier, effacer des faits.

Exemple :

SI le site de la culture est le sang

ET l'identité de l'organisme n'est pas connu avec certitude

ET la coloration de l'organisme est GRAM négatif

ET la morphologie de l'organisme est bâtonnet

ET le patient a été sérieusement brûlé

ALORS l'identité de l'organisme est Pseudomas (0.4)

b) Stratégies de raisonnement:

Le moteur d'inférences est un mécanisme qui permet d'inférer des connaissances nouvelles à partir de labase de connaissances du système.

On distingue essentiellement trois modes principaux de fonctionnement des moteurs d'inférences: lechaînage avant le chaînage arrière et le chaînage mixte.

La marche avant

Principe (démarche déductive): Le mécanisme du chaînage avant est très simple: pour déduire un faitparticulier, on déclenche les règles dont les prémisses sont connues jusqu'à ce que le fait à déduire soitégalement connu ou qu'aucune règle ne soit plus déclenchable.

Entrée : une base de faits F, une base de règles R

Sortie : la base de faits F transformée

Algorithme :

répéter

S = ensemble des règles applicables de R

si S ≠ Ø alorsa = choix d'une règle de S

application de la règle choisie a

marquer la règle a

finsi

jusqu'à S = Ø

(Une règle applicable est une règle : non marquée et dont la prémisse est satisfaite)





La marche arrière

Principe (démarche hypothético-déductive): Le mécanisme de chaînage arrière consiste à partir du faitque l'on souhaite établir, à rechercher toutes les règles qui concluent sur ce fait, à établir la liste des faitsqu'il suffit de prouver pour qu'elles puissent se déclencher puis à appliquer récursivement le mêmemécanisme aux faits contenus dans ces listes.

Entrée : une base de faits F, une base de règles R, un ensemble P de faits à prouver

Sortie : la base de faits transformée F

Algorithme :

tantque P ≠ Ø

extraire (en l'effaçant) de P un fait f

si le fait f est absent de F alors

S = ensemble des règles concluant sur f

si S ≠ Ø alors

a = choix d'une règle de S

prouver tous les faits en prémisse de a

si a est applicable alors

appliquer la règle a

finsi

finsi

finsi

Fin du tant que (attention au problème du bouclage, donc de nonterminaison)

La marche mixte

L'algorithme de chaînage mixte combine, comme son nom l'indique, les algorithmes de chaînage avant etde chaînage arrière. Son principe est le suivant:

Entrée: P (à déduire)

Algorithme du chaînage mixte

Tant que P n'est pas déduit mais peut encore l'être faire

Saturer la base de faits par chaînage avant (c'est-à-dire, déduir

tout ce qui peut être déduit)Chercher quels sont les faits encore éventuellement déductibles

Déterminer une question pertinente a poser à l'utilisateur etajouter sa réponse à la base de faits

Fin du tant que





c) Types de moteurs d'inférence

Moteur d'inférences d'ordre 0

Le fonctionnement du moteur d'inférences peut s'expliquer à l'aide de la logique des propositions seule.

- aucune notion de variable n'est autorisée,

- les seules actions autorisées sont l'ajout et l'effacement de faits,

- toute règle appliquée est éliminée.

exemple

si l'animal est un mammifère

et l'animal possède un pelage rayé de noir et de blanc

alors l'animal est un zèbre.

Moteur d'inférences d'ordre 0+

Moteur d'ordre 0 autorisé à modifier des faits (par exemple un compteur que l'on incrémente), et une règlappliquée n'est pas nécessairement effacée.

Exemple

si la température est < 30°C

et la consigne est ≤ 50

alors ajouter 2 à la consigne.

Moteur d'inférences d'ordre 1

Le fonctionnement du moteur s'explique avec la logique des prédicats :

- notion de variable et d'appariement (unification),- une règle appliquée reste toujours possiblement applicable.

Exemple

si X est un homme alors X est mortel.

d) Conception des SE aujourd'hui

Conception de A à Z (programmation du moteur, etc…) : de plus en plus rare…

Utilisation de générateurs de SE (moteurs d'inférences nus) : M1, OPS5, MP-LRO

Usage de langages de programmation pour l'IA

- Langages fonctionnels : LISP, ML, CAML

- Langages logiques : PROLOG





e) Le langage PROLOG

Un langage idéal pour construire rapidement des prototypes de SE.

PROLOG en un exemple:

Ecrire des faits:

père(pierre, michel) .

père(michel, paul) .

Poser des questions (réduire des buts):

?- père(X, Y).

X = pierre Y = michel

X = michel Y = paul

?- père(michel, X).

X = paul

Ecrire des règles:

grand-père(X, Z) :- père(X, Y), père(Y, Z) .

?- grand-père(X, paul).

X = pierre

1.2. Paradigmes de programmation

La très grande majorité des langages de programmation qui sont utilisés de nos jours se répartissent selon3 types de programmations :

a) Programmation Impérative (Actionnelle): les opérations sont écrites en termes de séquencesd'instruction. Le programme se déroule en écrasant les valeurs d'une zone mémoire par une nouvellevaleur. L'action de base dans la programmation impérative est l'affectation, c'est-à-dire la modification dela valeur associée à une variable du programme. L'affectation va être soit séquencée, soit choisie, soititérée selon les compositions définies par les algorithmes. Ce type de programmation est le plus pratiqué;c'est le plus proche du fonctionnement de la machine d'exécution, où une mémoire change d'état. Les

langages de programmation basés sur ce principe sont les plus nombreux, et vont, historiquement, del'assembleur à Fortran, Algol, Pascal, C , Ada, etc.

b) Programmation Fonctionnelle (Applicative): le calcul est considéré en tant qu'évaluation defonctions mathématiques.

Dans la programmation applicative, l'action de base est le calcul d'une expression ou, plus précisément, lecalcul du résultat d'une fonction pour des valeurs de ses arguments (on applique la fonction). Le grandancêtre de cette classe de langage est Lisp dont sont issues de nombreuses variantes.





Ces langages sont le plus souvent interprétés, et ils sont utilisés de manière interactive, alors que leslangages du type précédent sont le plus souvent compilés. Ils ont été très utilisés en intelligenceartificielle, mais on leur préfère maintenant la programmation logique ou la programmation par objets.

Le langage fonctionnel le plus connu est ML dont il existe un standard SML. Ces langages sont peu utilispour le génie logiciel, sans doute parce qu'ils ne sont pas très efficaces et qu'ils n'offrent pas de véritable

modularité. Ils sont surtout utilisés en milieu universitaire, à des fins d'enseignement et de recherche, maiil y a des cas d'utilisation en milieu industriel à des fins de prototypage.

c) Programmation Déclarative (relationnelle): consiste à créer des applications sur la base decomposants logiciels indépendants du contexte et ne comportant aucun état interne.

La programmation déclarative est ainsi nommée car elle consiste à énoncer les propriété d'un système derésolution -programme- (à les déclarer) plutôt qu'à décrire les opération à effectuer comme dans le cas dela programmation impérative. Elle permet de séparer clairement les trois parties d'un logiciel:

Les connaissances sur le domaine d'application

La formulation du problème à résoudre

Le mécanisme de résolution du problème, général et indépendant des deux autres parties bienqu'opérant sur elles.

Ce que l'on ne peut faire aussi nettement dans les autres modes de programmation. La programmationdéclarative repose sur la logique.

La programmation logique est basée sur un principe très différent des autres approches. Le but d'unprogramme logique est de permettre la résolution d'une expression logique ou d'une conjonction de tellesexpressions. Par résolution, on entend la recherche des valeurs des variables qui rendent l'expression vrai(les solutions). Il n'y a pas d'affectation. Des mécanismes d'unification sont mis en oeuvre.

Le langage de programmation logique le plus connu est Prolog. Prolog est une forme de programmationdéclarative. Son originalité est d'offrir un cadre homogène pour la description des connaissances ainsi que

pour celle du problème à résoudre. Prolog inclus un moteur d'inférence d'ordre 1 permettant la résolutiondu problème.

Paradigme Le programme est: L'exécution consiste à: Style: Langages

Impératif (Actionnel)

Un ensemble d'actionsséquentielles

Déclancher les actions etmodifier l'état devariables

"fais ça" Pascal, C, ADFortran, …

Fonctionnel

(Applicatif)

Une fonction

(composition)

Evaluation de la fonction

avec des paramètreseffectifs

"Evalue ça" LISP, ML, Cam

…

Déclaratif (relationnel)

Un ensemble de règles etde faits

Lancer une résolution entenant compte des règleset de l'état de la base defaits

"Que pense-tude ça?"

Prolog, SQL,..





2. La programmation logique

La programmation logique est une forme de programmation qui définit les applications à l'aide d'unensemble de faits élémentaires les concernant et de règles de logique leur associant des conséquences pluou moins directes. Ces faits et ces règles sont exploités par un démonstrateur de théorème ou moteurd'inférence, en réaction à une question ou requête.

Cette approche se révèle beaucoup plus souple que la définition d'une succession d'instructions quel'ordinateur exécuterait. La programmation logique est considérée comme une programmation déclarative plutôt qu’impérative, car elle s'attache davantage au quoi qu'au comment, et elle est particulièrement adaptée aux besoins de l’intelligence artificielle, dont elle est un des principaux outils.

La programmation logique est le fruit des recherches menées par R. Kowalski et A. Colmerauer sur usous ensemble de la logique des prédicats du premier ordre à savoir les clauses de Horn.

La programmation logique constitue un paradigme de programmation simple et déclaratif. Ce paradigmreflète une méthodologie de programmation parfaite, le fait qu'il distingue entre l'aspect logique et l'aspecontrôle des programmes. Cette distinction n'est pas appliquée dans les autres styles de programmation.

La principale différence entre les langages de programmation logique, tel que "Prolog", et les langag

'classiques', tel que "Pascal" est que : ces derniers sont de nature impérative : c-à-d il faut décrire problème à résoudre selon un algorithme, alors que les langages logiques, sont de nature déclarative, ceveut dire qu'il suffit d'indiquer au système les données du problème à traiter. Le moteur d'inférence qpermet de mettre en relation ces données, rend alors toutes les solutions. Ainsi avec cette nouvelle visioon peut résoudre des problèmes complexes sans recourir à des techniques algorithmiques.

La programmation logique touche aujourd'hui des champs d'application très variés tels que :

1 1- La conception de systèmes experts dans le but de simuler l'expertise humaine.

2 2- La conception des SGBDR.

3 3- Le traitement du langage naturel.

4 4- L'enseignement assisté par ordinateur

5 5- L'automatisme.

6 6- La législation.

La souplesse de la programmation logique est assurée grâce aux concepts logiques qui utilisent unmanière de spécification des informations décrivant le problème à résoudre en se basant sur la logique dpremier ordre.

3. Principales caractéristiques de la Programmation Logique

La programmation logique se base sur la syntaxe de logique de 1er ordre.

Elle est considérée comme une programmation déclarative plutôt qu'impérative.

Elle s'attache d'avantage au "quoi" qu'au "Comment".

Elle révèle beaucoup plus soupe que la définition d'une succession d'instructions que l'ordinateurexécuterait.

La programmation interactive est une caractéristique importante de la programmation logique:l'utilisateur peut écrire un seul programme et peut l'interagir par moyen de requêtes pour lesquelledes réponses sont produites.





Elle est particulièrement adaptée aux besoins de l'intelligence artificielle, dont elle est un desprincipaux outils.

4. Avantages et inconvénient de la Programmation Logique

Nous présentons dans ces qui suit les principaux avantages de la programmation logique :

1 1- Simplicité : L'aspect déclaratif de la programmation logique offre une manière très simple pour résolution des problèmes. La tâche du programmeur est réduite à la description des connaissances du problème à résoudre.

2 2- Puissance : La puissance de la programmation logique réside dans le fait d'utiliser le concepd'unification et de la résolution pour inférer la solution du problème, à partir des descriptions.

3 3- Procédures non directionnelles : Les procédures utilisées dans la programmation logique sodifférentes de celles utilisées dans les langages conventionnels au sens où une procédure peut êtutilisée pour résoudre différentes types de problèmes et cela selon l'instanciation de ses arguments.

Cependant la programmation logique connaît quelques inconvénients :

1 1- Lenteur : La lenteur de la programmation logique est due essentiellement à l'inadaptation du stylogique vis à vis du modèle de Von-Neumann. Cela répercute irrémédiablement sur le temd'exécution des programmes logiques.

2 2- Pauvreté en représentation des données : La programmation logique n'est pas adaptée à la définitiode nouveaux types de structures de données. Les structures existantes sont parfois inefficaces ecomparaison avec des structures plus spécialisées telle que les vecteurs par exempl





Chapitre 02 : Le Langage Prolog

Afin de voir l'application pratique des notions vues jusqu'à maintenant, nous allons présenter le langagProlog, qui est le plus représentant des langages de programmation logique.

1. Prolog

Le nom Prolog est un acronyme de PROgrammation LOGique. Il a été créé par Alain Colmerauer Philippe Roussel vers 1972. Le but était de faire un langage de programmation qui permettait d'utilisl'expressivité de la logique au lieu de définir pas à pas la succession d'instructions que doit exécuter uordinateur.

Prolog est utilisé dans de nombreuses applications d’intelligence artificielle, comme les systèmes expertl'analyse syntaxique du langage naturel, … . Ses syntaxe et sémantique sont considérées comme tr

simples et claires (le but original était de procurer un outil pour les linguistes ignorant l’informatique). Prolog est basé sur le calcul des prédicats du premier ordre. Cependant, il est restreint dans sa versioinitiale à n’accepter que les clauses de Horn (les versions modernes de Prolog acceptent des prédicats plucomplexes). L’exécution d’un programme Prolog est effectivement une application du théorème prouvapar résolution du premier ordre.

Prolog est un langage de programmation logique basé sur deux grands mécanismes: l'unification et chaînage arrière.

L'unification est le fait d'essayer de rendre deux assertions identiques (un fait et une têtede règle en général) en donnant des valeurs aux variables qu'elles contiennent.

Le chaînage arrière est le fait de partir du but recherché, de rechercher les règles dont lebut est la conclusion, puis, en prenant les conditions de ces règles comme nouveaux sous buts,recommencer la recherche récursivement. Ensuite, il ne reste plus qu'à unifier les faits trouvésavec le but recherché.

L'unification est une opération de base dans un programme logique. Pour pouvoir appliquer la règle drésolution à deux clauses, il est nécessaire de savoir si deux ou plusieurs formules atomiques peuvent êtunifiées, i.e. s'il existe une substitution des variables de ces formules par des termes du langage qpermettent de les rendre égales.

L'unification représente le processus par lequel tout langage logique met en correspondance un atome aveun fait, où la tête d'une règle pour vérifier le but proposé. L'algorithme utilisé pour appliquer ce processus'appelle algorithme d'unification.

Exemple :

1 i) f(X1, X1) et f(a,b) ne sont pas unifiables.

2 ii) f(X1, X2) et f(a,X3) sont unifiable avec l'unificateur σ = {X1/a, X2/X3}.

http://fr.wikipedia.org/wiki/Acronyme


http://fr.wikipedia.org/wiki/Alain_Colmerauer


http://fr.wikipedia.org/wiki/Philippe_Roussel


http://fr.wikipedia.org/wiki/1972


http://fr.wikipedia.org/wiki/Langage_de_programmation


http://fr.wikipedia.org/wiki/Logique



http://fr.wikipedia.org/wiki/Ordinateur





http://fr.wikipedia.org/wiki/Calcul_des_pr%C3%83%C2%A9dicats_du_premier_ordre



http://fr.wikipedia.org/wiki/Clause_de_Horn
















MOKDAD AROUS Cours Programmation Logiqu

Prolog repose sur l'utilisation de la logique du premier ordre dans la résolution des problèmes. Uprogramme Prolog comporte une base de faits et un ensemble de règles.

La logique du premier ordreUn prédicat est une propriété ou une relation.

Un argument (de prédicat) est objet sur lequel porte un prédicat.

Exemple :

heureux (walid).Aime (walid, lalogique).

Une clause est une phrase de système exprimant que des conditions entraînant des conclusions.

Exemple : « si Ali aime la logique, alors il est heureux ou fatigué »

Une clause de Horn est une clause constituée d’une conclusion, ce sont les clauses manipulées par Prolog

Exemple :« si Ali aime la logique, alors il est heureux»heureux(ali) :- aime (ali, lalogique).

« si Ali aime la logique, alors il est fatigué »fatigue (ali) :- aime (ali, lalogique).

Ce qui intéresse un programmeur, est de résoudre le problème posé d'une manière efficace. Dans ce styde programmation, la résolution est une méthode de démonstration automatique qui utilise un système ddéduction pour les formules du premier ordre qui sont sous forme de clauses. L'application de cet

méthode nécessite préalablement, soit d'exprimer le problème directement sous forme de clauses, soit dtransformer un ensemble de formules de premier ordre en un ensemble de clauses. L'algorithmd'unification permet ensuite d'appliquer la règle de résolution à cet ensemble de clauses.

Base de faits :

Les faits sont des clauses, qui expriment des connaissances qui sont inconditionnellement vraies.

Exemple : les clauses suivantes constituent une base de faits exprimant des connaissances aériennes entrvilles :

liaison (alger, oran).

liaison (oran, ghardaya).

liaison (ghardaya, tamanraset).

Base de Règles:

Les règles permettant de définir, sous forme de clauses complètes, de nouveaux concepts à partir de faiou de concepts préexistants. L'emploi des règles est particulièrement économique en place mémoire.

Exemple :

lien(Ville_depart, Ville_arrivé) :-





liaison(Ville_depart, Ville_inter), liaison(Ville_inter, Ville_arrivé).

Questions :

La base des faits et l'ensemble des règles constituent un programme dont on peut demander l'exécution eposant des questions.

Exemple : La question :?- liaison (alger, oran).

est une question, qui aura la réponse "Vrai".

La réponse à la question

?- liaison (oran, X).

consiste à trouver la valeur de X, qui rend le fait liaison(oran, X) vrai. L'inconnue X, sera li(ou instanciée) à une constante (ghardaya).

La résolution en Prolog, revient à explorer la base de faits afin de répondre à la question posée.

2. Syntaxe et terminologie Prolog

Un programme Prolog est constitué d'un ensemble de clauses, une clause est une affirmation portant sudes atomes logiques, un atome logique exprime une relation entre des termes, les termes sont les objets dl'univers. Dans cette section, on va successivement définir ce qu'est un terme, un atome logiquune clause et un programme Prolog.

2.1. Les termes

Les objets manipulés par un programme Prolog (les "données" du programme) sont appelés des termeOn distingue trois sortes de termes:

Les variables: représentent des objets inconnus de l'univers. Syntaxiquement, une variable estune chaîne alpha-numérique commençant par une majuscule (par exemple: Var, X,Var_longue_2) ou par un sous-ligné (par exemple: _objet, _21). La variable anonyme estnotée "_'' et représente un objet dont on ne souhaite pas connaître la valeur.

Attention: Une variable Prolog s'apparente plus à une variable mathématique qu'à une variableinformatique. Elle représente toujours le même objet (inconnu) tout au long de sa durée de vie et nepeut pas changer de valeur.

Les termes élémentaires (ou termes atomiques): représentent les objets simples connus del'univers. On distingue trois sortes de termes élémentaires:

o Les nombres: peuvent êtres des entiers (34, -45, +12) ou des réels (-34.14, 0.987

-0.4e+2).

o Les identificateurs (parfois appelés atomes): un identificateur est une chaîne alpha-numérique commençant par une minuscule (par exemple: toto, aX12, jean_Paul_2),

o Les chaînes de caractères entre guillemets (par exemple: "Toto est \#\{@", "123").

Les termes composés: représentent les objets composés (structurés) de l'univers. Syntaxiquemenun terme composé est de la forme:





foncteur(t1 , ... , tn)

où foncteur est une chaîne alpha-numérique commençant par une minuscule, et t1, ..., tn sont destermes (variables, termes élémentaires ou termes composés). Le nombre d'arguments n est appelé ari

du terme.

Par exemple adresse(18,"rue des lilas",Ville) est un terme composé de foncteur adresse et d'arité 3, dont les deux premiers arguments sont les termes élémentaires 18 et "ruedes lilas" et le troisième argument est la variable Ville.

De même, cons(a,cons(X,nil)) est un terme composé de foncteur cons et d'arité 2, dont premier argument est le terme élémentaire a et le deuxième argument le terme composé cons(X,nil).

2.2. Les relations (atomes logiques)

Un atome logique exprime une relation entre des termes, cette relation peut être vraie ou fausse.Syntaxiquement, un atome logique est de la forme:

symbole-de-prédicat(t1, ... , tn )où symbole-de-prédicat est une chaîne alpha-numérique commençant par une minuscule, et t

..., tn sont des termes. Le nombre d'arguments n est appelé arité de l'atome logique.

Exemple:

pere(toto,paul)

est une relation d'arité 2 entre les termes élémentaires toto et paul pouvant être interprétée par"toto est le père de paul''.

De même,

habite(X,adresse(12,"rue r",nice))

est une relation d'arité 2 entre la variable X et le terme composé adresse(12,"rue

r",nice) pouvant être interprétée par "une personne inconnue X habite à l'adresse (12,"rue

r",nice)''.

2.3. Les clauses

Une clause est une affirmation inconditionnelle (un fait) ou conditionnelle (une règle). Un programmeProlog comporte des faits et des règles.

Un fait est de la forme:

A.

où A est un atome logique, et signifie que la relation définie par A est vraie (sans condition). Parexemple, le fait

pere(toto,paul).

indique que la relation "toto est le père de paul" est vraie.

Une variable dans un fait est quantifiée universellement. Par exemple, le fait

egal(X,X).





indique que la relation "X est égal à X '' est vraie pour toute valeur (tout terme) que X peut prendre

Les règles expriment des relations conditionnelles entre les objets (clauses de Horn).Une règle est de la forme:

A0 :- A1 , ... , An.

où A0, A1 , ... , An sont des atomes logiques. Une telle règle signifie que la relation A0 est vraie siles atomes logiques A1, A2 ... et An sont vraies. A0 est appelé tête de clause et A1, ... , An estappelé corps (ou aussi Queue) de clause.

La tête de la règle exprime la conséquence, la queue exprime une conjonction de condition(ET implicite). Autrement dit une règle : Tête :- Queue. peut se lire : "Pour que Tête soitvérifiée il faut que les différentes conditions de Queue soient vérifiées".

Une variable apparaissant dans la tête d'une règle (et éventuellement dans son corps) estquantifiée universellement. Une variable apparaissant dans le corps d'une clause mais pas dans stête est quantifiée existentiellement. Par exemple, la clause

meme_pere(X,Y) :- pere(P,X), pere(P,Y).

se lit: "pour tout X et pour tout Y, meme_pere(X,Y) est vrai s'il existe P tel que pere(P,X) epere(P,Y) soient vrais''.

Dans le corps d'une règle, la virgule "," est le symbole représentant un "ET" logique : la conjonctionde buts. Le symbole ";" représente le "OU" logique: le disjonction de buts. Par exemple :

A :- B ; C .

Est équivalente à :

A :-B.A :-C.

2.4. Les programmes Prolog

Un programme Prolog est constitué d'une suite de clauses regroupées en paquets. Chaque paquet définitun prédicat et est constitué d'un ensemble de clauses dont l'atome de tête a le même symbole de prédicat la même arité. Intuitivement, deux clauses d'un même paquet sont liées par un ou logique. Par exemple, lprédicat personne défini par les deux clauses:

personne(X) :- homme(X). personne(X) :- femme(X).

se lit "pour tout X, personne(X) est vrai si homme(X) est vrai ou femme(X) est vrai''.

Beaucoup de Prolog demandent que toutes les règles et tous les faits d'un même prédicat soient contigus egroupés ensemble dans le fichier du programme. On note un prédicat par son nom et son arité, par

exemple: homme/1, femme/1, personne/1, pere/2.

2.5. Exécution de programmes Prolog

"Exécuter" un programme Prolog consiste à poser une question à l'interprète Prolog. Une question (but ouactivant) est une suite d'atomes logiques séparés par des virgules (entrée après l’invite ?- ). La réponsede Prolog est "Yes'' si la question est une conséquence logique du programme, ou "No'' si la question n'epas une conséquence logique du programme.

?- pere(toto,paul).





Yes

?- pere(toto,sara).

No

Une question peut comporter des variables quantifiées existentiellement. La réponse de Prolog est alorsl'ensemble des valeurs des variables pour lesquelles la question est une conséquence logique du

programme. Par exemple, la question:?- pere(toto,X).

se lit "est-ce qu'il existe un X tels que pere(toto,X) soit vrais''. La réponse de Prolog estl'ensemble des valeurs de X qui vérifient cette relation (l'ensemble des enfants de toto, si toto eseffectivement un père), s'il n'existe pas aucune réponse Prolog affiche "No". Sinon, après chaque réponsel'utilisateur appuie sur ";" pour que l'interpréteur affiche la réponse suivante, ou sur "entrée" pour quel'interpréteur termine l'exécution.

Les questions peuvent être elles-mêmes des conjonctions :

?- pere(toto,X), pere(X,Y).

se lit "est-ce qu'il existe X et Y tels que pere(toto,X) et pere(X,Y) soient vrais''. Autrementdit, la réponse de Prolog à cette question devrait être l'ensemble des enfants et petits-enfants de toto. stoto est effectivement grand-père.

La variable "_" est appelée la variable anonyme, elle indique à Prolog que l'on ne s'intéresse pas à lavaleur de cette variable, par exemple la requête

?- homme(_).Demande juste s'il existe un homme, peut importe son nom.

2.6. Mécanisme utilisé pour répondre à une question (approche informelle)

Prolog tente de faire correspondre la question avec les faits disponibles. Si un fait s'accorde avec laquestion alors les variables de la question prennent les valeurs nécessaires. On dit que l'on unifie laquestion avec le fait et que les variables sont instanciées. Cette instanciation se fait par construction d'unsubstitution qui est un ensemble des couples (variable, valeur), généralement représenté sous la forme{Var1 = Val1, ..., Varn = Valn}.

Définition : Une Substitution est une liste de couples (v,t) tels que le premier élément est une variable ele second un terme Prolog contenant éventuellement des variables.

Définition : Instancier un prédicat P avec une substitution σ (on note Pσ ), c'est remplacer dans P toutesles occurrences d'une variables de σ par son expression associée dans σ.

Définition : Deux prédicat P et Q sont unifiables si on peut trouver une substitution σ telle que: Pσ = Qσ

Exemple:Question Q: pere(toto,X)

Fait F: pere(toto,paul)

Q et F sont unifiables par la substitution σ={X=paul}. en instanciant Q par σ, c'est-à-dire en remplaçandans Q les variables par leurs valeurs dans la substitution σ, on obtient:

Qσ = pere(toto,X){X = paul} = pere(toto,paul) = F

Exemple : Soit P1 = aime(jean, A) et P2 = aime(B, laLogique).





La substitution σ = {A = laLogique, B = jean} permet d'unifier P1 et P2.





3. Les Opérateurs en Prolog

Le langage Prolog considère les opérateurs comme des foncteurs et transforme les expressions en termespar exemple: 2*3+4*2 est un terme identique à: +(*(2,3),*(4,2))).

3.1. Règles de précédence et d'associativité

Les opérateurs sont définis par leurs priorités et leurs associativités. L'associativité détermine leparenthésage d'une expression: A op B op C :

Si elle est à gauche, on a : (A op B) op C

Si elle est à droite, on a : A op (B op C)

Sinon elle est non associative, les parenthèses sont obligatoires, et la syntaxe A op B op C estinterdite.

En tout cas, l’emploi de parenthèses permet de préciser l’ordre de l’évaluation. Mais, en l’absence decelles-ci, une expression comme « 4 + 5 * 5 » possède deux évaluations possibles. Il faut donc préciser :

- la préséance des opérateurs ;- l’associativité.

La préséance se définit habituellement par un ordre de priorité. Habituellement, les opérateurs binaires « » et « / » ont une priorité plus forte que « + » et « - » (mais attention l’opérateur unitaire « + » et « -

» aura une plus forte priorité que « * » et « / »).

L’associativité permet de dire si l’expression « 16/4/2 » doit être évaluée comme « (16/4)/2 » (associatif

gauche) ou comme « 16/(4/2) » (associatif à droite).

3.2. Opérateurs logiques d'unification

Le symbole « = » en Prolog signifie l'unification et pas l'affectation, le symbole = dans "X=Y" signifie

"X s'unifie avec Y ". Exemple :

?- a(b,X,c)=a(b,Y,c).X = Y

L'opérateur: \= dans " x\=Y" signifie " X ne s'unifie pas avec Y "

Exemple :

?- a(b,X,c)\= a(b,Y,c).No

3.3. Opérateurs arithmétiquesUne expression arithmétique est un terme fait de nombre et de foncteurs ou opérationsreprésentant des fonctions arithmétiques. Les principaux opérateurs sont: +, - , * , / (division réelle), // (division entière) et mod (modulo: reste de la division).

Evaluer un terme représentant une expression arithmétique revient à appliquer les opérateurs, ceci se faitpar le prédicat prédéfini is /2. Pour affecter une valeur numérique à une variable, en évaluantmathématiquement le résultat, il faut utiliser « is ».





Exemples :

?- M=1+1, N is 1+1.M = 1+1N = 2 ;No

?- N is 1+1, M is N+3, P = N+M.N = 2M = 5P = 2+5 ;No

?- X is 1+1+a. % erreur car a n'est pas un nombre

?- X is 1+1+Z. % erreur car Z n'est pas instanciée

?- 5 is (3*7+1)//4.

YesLes opérateurs suivants permettent de manipuler les expression arithmétiques :

1. Expr1 =:= Expr2 réussit si les valeurs des deux expressions sont égales.

Par exemple 2*3=:=1+5 réussit mais: 2*3=:=5 échoue.

Il ne faut pas confondre ce prédicat avec le prédicat d’unification . Par exemple 2*3=6 échoue parceque les deux termes ne sont pas unifiables. Le terme 2*3 est un terme composé (en fait il correspond auterme *(2,3)) alors que 6 est un entier.

2. Exprl =\= Expr2 réussit si les valeurs des deux expressions sont différentes.

3. Exprl < Expr2 réussit si la valeur de Exprl est strictement inférieure à celle de Expr2.4. Exprl =< Expr2 réussit si la valeur de Exprl est inférieure ou égale à celle de Expr2.

5. Exprl > Expr2 réussit si la valeur de Exprl est strictement supérieure à celle de Expr2.

6. Exprl >= Expr2 réussit si la valeur de Exprl est supérieure ou égale à celle de Expr2.

Pour chacun de ces prédicats, si une des deux expressions n’est pas éva luable parce quelle contient desvariables non instanciées, Prolog retourne un message d'erreur. La requête X=:=3 produit un messaged’erreur, alors que la requête X=3 , X=:=1+2 réussit.

Dans l’expression :

?- 1 + 2 < 3 + 4.Il y a évaluation des 2 additions (celle de gauche puis celle de droite) avant d’évaluer la comparaison.

Il est important de distinguer les opérateurs numériques des opérateurs littéraux, ainsi que d’unification.

Exemples?- 1 + 2 =:= 2 + 1.Yes





?- 1 + 2 = 2 + 1.No

?- 1 + 2 = 1 + 2.Yes

?- 1 + X = 1 + 2.X=2.

?- 1 + X =:= 1 + 2. % X n’est pas instanciée

Exemple : Comment exprimer qu'on veut calculer la somme de deux nombres ?

somme(X,Y,S) :- S is X+Y.

Exemple : Soient 2 entiers positifs X et Y, leur plus grand diviseur commun D, peut être calculéen considérant 3 cas :

1. Si X et Y sont égaux alors D est égal à X2. Si X < Y alors D est égal au plus grand diviseur commun de X et de la différence X - Y

3. Si Y < X alors faire la même chose que dans le cas 2 avec X et Y interchangés

gcd(X,Y,D) est défini par le programme prolog suivant:

gcd(X,X,X).gcd(X,Y,D) :− X < Y, Y1 i s Y − X, gcd(X,Y1,D) . gcd(X,Y,D) :− Y < X, X1 i s X − Y, gcd(X1,Y,D) .

3.4. Opérateurs littérales

1. T1 == T2 réussit si T1 est identique à T2 (terme à terme)

2. T1 \== T2 réussit si T1 n’est pas identique à T2





L'opérateur == permet une comparaison littérale (terme à terme), mais cette dernière n’est pas restreint

aux constantes. Ainsi, dans le cas d’une comparaison entre variables, la syntaxe de ces dernières constitul’élément de comparaison (et non plus la valeur comme dans le cas d’une constante). Ainsi, cette fonction

prend comme valeur Yes si les deux termes sont identiques, No dans le cas contraire.

Exemples:

?- "1 + 2" == "1 + 2".Yes

?- 1 + 2 == 2 + 1.No

?- 1 + a == 1 + a.Yes

?- 1 + a \== a + 1.Yes

?- a(b,X,c) == a(b,Y,c).No

?- a(b,X,c) == a(b,X,c).Yes

? - A \== "hello". % « A n’est pas déjà instanciée»Yes

?- a(b,X,c) \== a(b,Y,c).Yes

3.5. Entrées / SortiesIl existe quelques actions prédéfinies comme: write() qui est applicable à une constante, unevariable ou une chaîne de caractères entre guillemets simples, read() qui permet la lecture à partir declavier, et nl pour passage à la ligne. Par exemple :

?- write('bonjour'),nl,write('toi').bonjourtoiYes





?- X is 2, write(X).2X = 2 ;No

?- write('Donner la valeur de N'), nl, write('N='), read(N).Donner la valeur de NN=20.

N = 20

yes

En Prolog, on ne définit pas de fonction ou de procédures mais des prédicats (à valeur dans {0,1}),éventuellement avec 0 argument. Donc :

Pour faire l'équivalent d'une procédure, on dit qu'un certain prédicat est vrai à condition qu'un certainnombre d'actions soient faites, par exemple :

affiche :- write('bonjour').

Pour définir une fonction f(X1,...,Xn)=Y, on définit un prédicat P(X1,X2,...,Xn,Y) quest vrai si f(X1,...,Xn)=Y, par exemple :

a_pour_successeur(X,Y) :- Y is X+1.

4. Sémantique des programmes Prolog

4.1. Définitions préliminaires :

o Substitution

Une substitution (notée σ) est une fonction de l'ensemble des variables dans l'ensemble des termes. Parexemple : σ={X=Y,Z=f(a,Y)} est la substitution qui "remplace'' X par Y, Z par f(a,Y), et laisseinchangée toute autre variable que X et Z.

Par extension, une substitution peut être appliquée à un atome logique. Par exemple :

σ(p(X,f(Y,Z))) = p(σ(X),f(σ(Y), σ(Z))) = p(Y,f(Y,f(a,Y)))

o Instance :

Une instance d'un atome logique A est le résultat σ(A) de l'application d'une substitution σ sur A.

Par exemple : pere(toto,paul) est une instance de pere(toto,X).

o Unificateur :

Un unificateur de deux atomes logiques A1 et A2 est une substitution σ telle que σ(A1)=σ(A2).

Par exemple : soit A1=p(X,f(X,Y)), et soit A2=p(a,Z),

σ = { X = a, Z = f(a,Y) }

est un unificateur de A1 et A2 car σ(A1)=σ(A2)=p(a,f(a,Y)).





o Unificateur plus général :

Un unificateur σ de deux atomes logiques A1 et A2 est le plus général (upg) si pour tout autreunificateur σ' de A1 et A2, il existe une autre substitution σ'' telle que σ'=σ''(σ).

Par exemple :

σ={X=Y} est un upg de p(X,b) et p(Y,b), tandis que:

σ'={X=a,Y=a}

n'est pas un upg de p(X,b) et p(Y,b).

4.2. Dénotation d'un programme Prolog

La dénotation d'un programme Prolog P est l'ensemble des atomes logiques qui sont des conséquenceslogiques de P. Ainsi, la réponse de Prolog à une question est l'ensemble des instances de cette question qu

font partie de la dénotation. Cet ensemble peut être "calculé" par une approche ascendante, dite en"chaînage avant" : on part des faits, et on applique itérativement toutes les règles conditionnelles pourdéduire de nouvelles relations ..., jusqu'à ce qu'on ait tout déduit.

Exemple: Considérons le programme Prolog P suivant:

parent(paul,jean). parent(jean,anne). parent(anne,marie).

homme(paul).

homme(jean).pere(X,Y) :- parent(X,Y), homme(X).

grand_pere(X,Y) :- pere(X,Z), parent(Z,Y).

L'ensemble des relations vraies sans condition dans P est E_0 :

E_0 = { parent(paul,jean), parent(jean,anne), parent(anne,marie),homme(paul), homme(jean) }

à partir de E_0 et P, on déduit l'ensemble des nouvelles relations vraies E_1:

E_1 = { pere(paul,jean), pere(jean,anne) }

à partir de E_0, E_1 et P, on déduit l'ensemble des nouvelles relations vraies E_2:

E_2 = { grand_pere(paul,anne), grand_pere(jean,marie) }

à partir de E_0, E_1, E_2 et P , on ne peut plus rien déduire de nouveau.





L'union de E_0 , E_1 et E_2 constitue la dénotation de P.

Malheureusement, la dénotation d'un programme est souvent un ensemble infini et n'est donc pascalculable de façon finie.

Exemple: Considérons le programme Prolog P suivant:

plus(0,X,X). plus(succ(X),Y,succ(Z)) :- plus(X,Y,Z).

L'ensemble des atomes logiques vrais sans condition dans P est :

E_0 = { plus(0,X,X) }

à partir de E_0 et P, on déduit

E_1 = { plus(succ(0),X,succ(X)) }

à partir de E_0, E_1 et P, on déduit

E_2 = { plus(succ(succ(0)),X,succ(succ(X))) }

à partir de E_0, E_1, E_2 et P , on déduit

E_3 = { plus(succ(succ(succ(0))),X,succ(succ(succ(X)))) }

etc ..., dans cet exemple la dénotation du programme est un ensemble infini.

4.3. Signification opérationnelle

D'une façon générale, on ne peut pas calculer l'ensemble des conséquences logiques d'un programme parl'approche ascendante: ce calcul serait trop coûteux, voire infini. En revanche, on peut démontrer qu'unbut (composé d'une suite d'atomes logiques) est une conséquence logique du programme, en utilisant uneapproche descendante, dite en chaînage arrière. La sémantique de Prolog est donc basée sur une approchedescendante de calcul : le chaînage arrière (backward chaining).

Pour prouver un but composé d'une suite d'atomes logiques (But = [A_1, A_2, ..., A_n]),l'interprète Prolog commence par prouver le premier de ces atomes logiques (A_1). Pour cela, il chercheune clause dans le programme dont l'atome de tête s'unifie avec le premier atome logique à prouver (parexemple, la clause : A'_0 :- A'_1, A'_2, ..,A'_r. telle que upg(A_1,A'_0)=σ).

Puis l'interprète Prolog remplace le premier atome logique à prouver (A_1) dans le but par les atomeslogiques du corps de la clause, en leur a ppliquant la substitution (σ). Le nouveau but à prouver devient :

But = [σ(A'_1), σ(A'_2), ..., σ(A'_r), σ(A_2), .., σ(A_n)]

L'interprète Prolog recommence alors ce processus, jusqu'à ce que le but à prouver soit vide, c'est à dire jusqu'à ce qu'il n'y ait plus rien à prouver. A ce moment, l'interprète Prolog a prouvé le but initial ; si le b





initial comportait des variables, il affiche la valeur de ces variables obtenue en leur appliquant lessubstitutions successivement utilisées pour la preuve.

Il existe généralement plusieurs clauses dans le programme Prolog dont l'atome de tête s'unifie avecl'atome logique à prouver. Ainsi, l'interprète Prolog va successivement répéter ce processus de preuvepour chacune des clauses candidates. Par conséquent, l'interprète Prolog peut trouver plusieurs réponses à

un but.

Ce processus de preuve en chaînage arrière est résumé par la fonction prouver(But) suivante. Cettefonction affiche l'ensemble des instances de But qui font partie de la dénotation du programme:

fonction prouver(But: liste d'atomes logiques )

si But = [] alors

le but initial est prouvé

afficher les valeurs des variables du but initial

sinon soit But = [A_1, A_2, .., A_n]

pour toute clause (A'_0 :- A'_1, A'_2, ..,A'_r) du programme:

(où les variables ont été renommées)

σ <- upg(A_1 ,A'_0)

si σ ≠ echec alors

prouver([σ(A'_1), σ(A'_2),.. σ(A'_r), σ(A_2),.. σ(A_n)])

finsi

finpour

finsi

fin prouver

Quand on pose une question à l'interprète Prolog, celui-ci exécute dynamiquement l'algorithme précédentL'arbre constitué de l'ensemble des appels récursifs à la procédure prouver(But) est appelé Arbre deRecherche.

Prolog va chercher à effacer tous les termes du but (résolvant), il essaie par dérivation successivesd'obtenir une résolvante vide, s'il y arrive alors il y a succès et la substitution obtenue donne les conditionde la succès. S'il n' y parvient pas il y a alors échec.

Remarques

la stratégie de recherche n'est pas complète, dans la mesure où l'on peut avoir une suite infinied'appels récursifs,

la stratégie de recherche dépend d'une part de l'ordre de définition des clauses dans un paquet (siplusieurs clauses peuvent être utilisées pour prouver un atome logique, on considère les clauses





selon leur ordre d'apparition dans le paquet), et d'autre part de l'ordre des atomes logiques dans lecorps d'une clause (on prouve les atomes logiques selon leur ordre d'apparition dans la clause).

Exemple 01:

Prenons l’exemple du calcul de la multiplication d’un entier naturel X par un entier Y par additionssuccessives (Multiplication Egyptienne).

mlt(X,Y,R):-Y<0 , Y1 is -Y, mlt(X,Y1,R1),R is –R1. /* r1 *

mlt(_,0,0). /* r2: 0 est élément absorbant de la multiplication*

mlt(X,1,X). /* r3: 1 est élément neutre de la multiplication*

mlt(X,Y,R):- Y1 is Y-1, Y1>0, mlt(X,Y1,R1), R is R1+X. /* r4 *

Puisque la fonction prouver(But) est récursif, la même règle peut être utilisée plusieurs fois dans larésolution. Afin d’éviter toute confusion sur les variables telles que X, Y et R qui pourraient êtreapparaître plusieurs fois, nous effectueront des renommage du type _iX, _iY et _iR. Ce renommageest effectué en interne par le moteur de résolution de Prolog.

Soit la requête suivante:

?- mlt(10, — 2,A).

Le but à prouver: But=[mlt(10, — 2,A)]

tentative d’unification avec r1 réussie avec: σ1 = { _1X=10, _1Y= — 2, _1R=A }, on obtient:

But =[-2<0, _1Y1 is --2, mlt(10,_1Y1,_1R1), A is -_1R1]

— 2<0 et _1Y1 is --2 s’éliminent (prouvés avec succès), et produisent: σ2 = {_1Y1=2}.

But =[mlt(10,2,_1R1), A is — _1R1]

tentative d’unification avec r1 réussie avec: σ3 = {_2X = 10, _2Y = 2, _2R = _ 1R1}

But =[2<0, _2Y1 is -2, mlt(10,_2Y1, _2R1), _1R1 is - _2R1, A is — _1R1]

backtrack (retour arrière) car 2<0 est faux.

But =[mlt(10, 2, _R1), A is —

_1R1]

tentative d’unification avec r2 échoue : 2 n’est pas nul

tentative d’unification avec r3 échoue : 2 n’est pas égal à 1

tentative d’unification avec r4 réussie avec : σ3 = {_3X=10, _3Y=2, _3R= _1R1 }

But =[_3Y1 is 2-1,_3Y1>0, mlt(10,_3Y1,_3R1),_1R1 is _3R1+10, A is -1R1





élimination des deux premières clauses avec la substitution: σ4 = {_3Y1 = 1}, donc:

But =[mlt(10,1,_3R1), _1R1 is _3R1+10, A is -_1R1]

tentative d'unification avec r1 réussie avec: σ5 = {_4X=10, _4Y=1, _4R=_3R1},

But =[ 1<0, _4Y1 is -1, mlt(10,_4Y1,_4R1), _4R1 is -_3R1, _1R1 is _3R1+10, A is -_1R1]

backtrack car 1<0 est faux.

But =[mlt(10,1,2_3R1),_1R1 is _3R1+10,A is -1R1]

tentative d'unification avec r2 échoue : 2 n'est pas nul

tentative d’unification avec r3 réussie avec: σ6 = {_3R1 = 10}

But =[ _1R1 is 1O+10, A is — _1R1]

élimination des deux derniers termes avec: σ7 = {_1R1 = 20, A = — 20}. On obtientfinalement un but vide But =[]. Le but initiale donc réussite, et la réponse de l'interprète Prolog à cettquestion est donc Yes avec l'affichage de valeur de la variable A = -20.

Exemple 02:

Prenons le programme Prolog suivant :

s(a). p(X,Y) :- q(X),r(X,Y).s(b). q(X) :- t(X).r(a,b). q(X) :- s(X).r(b,c).r(c,b).

Soit la question suivante:

?- p(A,B).

L’arbre de résolution de ce but: p(A,B) est le suivant :









5. Les Listes

La liste est un terme composé particulier de symbole de fonction " . " et d'arité 2: le premier argumentest l'élément de tête de la liste, et le deuxième argument est la queue de la liste. La liste vide est notée: [

Notations:

Le foncteur « . » est le foncteur de liste : .(a,.(b,[])) est équivalent à: [a,b] .

la liste: .(X,L) est également notée: [X|L],

la liste: .(X1,.(X2, L)) est également notée: [X1, X2|L],

la liste: .(X1,.(X2, ...,.(Xn,L)... )) est également notée: [X1,X2,...,Xn|L],

La liste vide est: [].

Par exemple, la liste: [a,b,c] correspond à la liste: .(a,.(b,.(c,[]))) et contient les 3

éléments: a , b et c. La liste: [a,b|L] correspond à la liste .(a,.(b,L)) et contient les 2éléments: a et b, suivis de la liste (inconnue): L.

L'opérateur « | » est un constructeur de liste et peut servir pour extraire la tête de la liste.

Exemples

?- L = .(a,.(b,.(c,[]))).L = [a, b, c] ;No

?- [a|[b,c]] = L.L = [a, b, c] ;No

?- [a,b|[c]]=[a,b,c|[]].Yes

?- [a,b|X]=[a,b,c|[]].X = [c] ;No

?-[a,b]=[X|Y].X = aY = [b];No

?-[a]=[X|Y].X = aY = [];No





?-[a,[b]]=[X|Y].X = aY = [[b]];No

?-[a,b,c,d]=[X,Y|Z].X = aY = bZ = [c, d];No

?-[[a,b,c],d,e]=[X|Y].X = [a, b, c]Y = [d, e];No

Une liste est une structure récursive: la liste liste=[X|L] est composée d'un élément de tête X etd'une queue de liste L qui est elle-même une liste. Par conséquent, les relations Prolog qui "manipulentles listes seront généralement définies par:

une ou plusieurs clauses récursives, définissant la relation sur la liste [X|L] en fonction de larelation sur la queue de liste L,

une ou plusieurs clauses non récursives assurant la terminaison de la manipulation, et définissant relation pour une liste particulière (par exemple, la liste vide, ou la liste dont l'élément de têtevérifie une certaine condition... etc.).

Dans la suit de cette section, nous prenons quelques exemples de prédicats de manipulation de listes (cesprédicats sont prédéfinis dans Prolog et on peut les utiliser directement).

5.1. Prédicat member/2

Ce prédicat permet d'examiner l'appartenance d'un élément à une liste. Première façon d'écrire ce prédica

member(X,[Tete|Queue]) :- X = Tete.member(X,[Tete|Queue]) :- X \= Tete, member(X,Queue).

Mais puisque les règles dans Prolog sont exécutées dans l'ordre qu'elles sont écrites, on peut simplifier ladéfinition du prédicat comme suit :

member(X,[X|_]).member(X,[_|Queue]) :- member(X,Queue).

Exemples

?- member(a,[b,c,a]).Yes

?- member(a,[c,d]).No





?- member(X,[a,b,c]).X = a;X = b;X = C;No

5.2. Prédicat append/3

Le prédicat append/3 permet de concaténer deux listes (ou de vérifier qu'une liste est la concaténatiode deux premières).

append([],L,L).append([x|XS],YS,[x|Liste]):- append(XS,YS,Liste).

Exemples

?- append([a,b,c],[d,e,f],[a,b,c,d,e,f]).

Yes

?- append([a,b],[c,d],[e,f]).No

?- append([a,b],[c,d],L).L = [a,b,c,d];No

?- append(L,[c,d],[a,b,c,d]).L = [a,b];No

?- append(L1,L2,[a,b,c]).L1 = [] ,L2 =[a,b,c];L1 = [a],L2 =[b,c];

… etc., avec toutes les combinaisons.

5.3. Prédicat length/2

Ce prédicat permet de détermine la longueur d’une liste:

length([] ,O).length([Tete | Queue] ,N) :- length(Queue,N1), N is N1 + 1.

Exemples?- length([a,b,c] ,3).Yes

?- length([a,[a,b],c], N).N= 3;No





6. Opérateur de Coupure

Par défaut Prolog tente de prouver la requête de toutes les façons possibles (suivant le programme) jusqu’à ce qu’une preuve soit trouvée, Si une preuve échoue, Prolog fait un retour-arrière pour tenter une autre ligne de preuve.

Dans certains cas ce retour-arrière peut être nuisible:

1. si le retour-arrière va répéter une solution.

2. si le retour-arrière n’a aucune chance de trouver une solution.

Exemple:

Soit la fonction "membre" qui vérifie qu’un élément est bien dans une liste.

Première solution :membre1(X,[Y|L]) :- X = Y.

membre1(X,[Y|L]) :- X \= Y, membre1(X,L).

Deuxième solution :

membre2(X,[X|_]).membre2(X,[_|L]) :- membre2(X,L).

L’idée ici, c’est que le cas d’égalité a été traité avec la première règle et que l’on n’a pas à en ten

compte lors de l’écriture de la deuxième règle.

Évaluation du travail effectué

Évaluation avec le prédicat membre1. Évaluation avec le prédicat membre2.

Conclusions





— L’écriture du programme a de grosses conséquences sur son exécution.

— Seule la première occurrence de X dans L nous intéressait ici. Nous aurions aimé pouvoirspécifier que le programme devait s’arrêter dès la première occurrence trouvée.

5.1. Signification opérationnelle de la coupure

La coupure, aussi appelée "cut", est notée " ! ".

La coupure est un prédicat sans signification logique (la coupure n'est ni vraie ni fausse), utilisée pour"couper" des branches de l'arbre de recherche.

La coupure est toujours "prouvée" avec succès . La "preuve" de la coupure a pour effet de modifier l'arbrede recherche: elle coupe l'ensemble des branches en attente créées depuis l'appel de la clause qui aintroduit la coupure. l'opérateur de la coupure sert donc à restreindre l’arbre de recherche en empêchant ldéveloppement de branches qui conduisent à des échecs ou à des solutions que l’on n’a pas besoin de

connaître

Principe :

tete(...) :- pr1(...), pr2(...), !, pr3(...), pr4(...).

Si pr1 ne réussit pas, on peut tenter de démontrer tete avec une autre clause

Si pr2 ne réussit pas, on peut annuler l'unification de pr1 et tenter de démontrerpr1 ou tete avec d'autres clauses

Si pr1 et pr2 réussissent, on franchit la coupure (qui réussit toujours) et les

unifications de pr1 et pr2 ne peuvent être modifiées (par contre si pr4 ne réussit pas, onpeut revenir sur pr3).

Exemple : Considérons l'exemple suivant qui concerne ma constitution du plat principale d'un repas,nous avons les clauses liées aux plats et celles liées aux viandes et aux poisons :

poisson(truite).

poisson(daurade).

viande(steak).

viande(escalope).

plat(P) :- poisson(P).

plat(V) :- viande(V).

Dessinons l’arbre de résolution de la question plat (P) , viande (P). qui fournit en réponse tons les plats qsont de la viande.





Dessinons l'arbre de résolution de la question plat(P), viande(P), ! . qui fournit en réponse le premier platqui est de la viande.

Dessinons l'arbre de résolution de la question plat (P), ! ,viande(P). qui ne fournit aucune réponse.

Comme nous l'avons vu ci-dessus, le cut permet donc d'affiner une question.

Exemple :

?- repas(E,P,D) ,poisson(P). /* quels sont les repas comprenant dupoisson? */





?- poisson(P) ,repas(E,P,D). /* idem */

?- repas (E, P , D), ! , poisson(P). /* le premier repas de la basecomprend-il du poisson? */

?- poisson(P), ,repas(E,P,D) . /* construire un repas avec le premier

poisson de la base */

?- repas(E,P,D) ,poisson(P), ! . /* quel est le premier repas contenandu poisson? /

?- poisson(P) ,repas(E,P,D), ! . /* idem $/

?- ! ,repas(E,P,D) ,poisson(P). /* idem sans cut */

Exemple : Dans la recherche d’appartenance d’un élément à une liste, la coupure permet d’arrêter leprogramme lors de la découverte de la première solution possible.

membre(X,[X|_]) :- !.membre(X,[_|L]) :- membre(X,L).

5.2. Les applications de la coupure

Recherche de la première solution Exprimer le déterminisme La négation Le "si-alors-sinon"

si-alors-sinon(C, P, Q) :- C, !, P.

si-alors-sinon(C, P, Q) :- Q.

Documents

Cours Prolog