# Prolog

Prolog est un langage 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 à Luminy, Marseille. Le but était de créer un langage de programmation où seraient définies les règles logiques attendues d'une solution et de laisser le compilateur la transformer en séquence d'instructions. L'un des gains attendus était une facilité accrue de maintenance des applications, l'ajout ou la suppression de règles au cours du temps n'obligeant pas à réexaminer toutes les autres.
Prolog est utilisé en intelligence artificielle et dans le traitement linguistique par ordinateur (principalement langues naturelles). Ses règles de syntaxe et sa sémantique sont simples et considérées comme claires (un des objectifs poursuivis était de procurer un outil aux linguistes ignorant l’informatique). Les premiers résultats obtenus avec Prolog suscitèrent quelque temps, dans les années 1980, des recherches sur une cinquième génération, matérielle et logicielle, d'ordinateurs (nommée Cinquième génération japonaise en raison de l'engagement important du MITI sur le projet). L'effort engagé fut important, les retombées plus modestes, Prolog restant un langage parmi d'autres dans la panoplie du programmeur.
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.
On peut construire en Prolog une base de connaissances dans un ordre indéterminé, puisque seules comptent les relations en présence et non leur séquence d'écriture. 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), problème similaire à la recherche d'une issue (ou plusieurs) dans un labyrinthe de contraintes établies.

## Types de termes

Prolog n’emploie pas de typage de données au sens habituel des langages de programmation. Il n'effectue en effet pas de distinction réelle entre les données du programme et le programme lui-même (principe de la programmation déclarative ainsi que de la programmation fonctionnelle). Ses éléments lexicaux, nommés termes, englobent les types suivants.

### Atomes

Les textes constants constituent des atomes. Un atome est ordinairement constitué d'une chaîne de lettres, nombres et traits bas (_), commençant par une lettre minuscule. Pour introduire un atome non alphanumérique, on l'entoure d'apostrophes : ainsi '+' est un atome, + un opérateur).

### Nombres

Les implémentations courantes de Prolog ne distinguent pas les nombres entiers des flottants.

### 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.
Ainsi, X3 comme Prix_Unitaire sont des noms de variables admissibles.
Prolog n'est pas un langage de programmation impératif ; une variable n’y est donc pas un contenant auquel on affecte une valeur, mais représente (comme en mathématiques dans X > 0) l'ensemble des valeurs admissibles pour elle dans le cadre des contraintes.
Le champ initialement indéfini de la variable se précise par l'unification autour des contraintes. Une fois la variable 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 dans le cadre de la poursuite de la recherche de valeurs admissibles (ou de nouvelles valeurs admissibles), dans le cadre d'une exploration exhaustive.
La variable anonyme est écrite avec un tiret bas (_). Toute variable dont le nom commence par un tiret bas est également une variable anonyme. C'est, comme le x ou le y de l'algèbre, une variable muette servant d'intermédiaire de calcul.

### Termes composés

Prolog ne peut représenter des données complexes que par termes composés. 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, nommé arité du terme, est en revanche significatif. Un terme composé est identifié par sa tête et son arité, et 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é, mais 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é) :
* 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é, comme en LISP.
Pour la commodité 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 :
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 :
Dans ce second exemple, à la question 'chat(X)' l'interpréteur propose la réponse 'X = tom' unifiant la variable 'X' à l'atome 'tom'. En 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-déterministe (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.
Dans ce dernier exemple, à la question 'chat(vim)' l'interpréteur répond qu'il ne peut pas prouver ce fait, en Prolog il s'agit d'un échec. En faisant l'hypothèse que tous les faits sont connus (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 :
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 avec l'auxiliaire 'ê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é.
On conviendra par exemple que
signifie que pierre et marie sont respectivement le père et la mère de 3 enfants : arthur, bruno et charlotte ; "famille" est alors un prédicat à 3 termes, le dernier étant une liste d'un nombre quelconque (éventuellement nul) d'enfants.

### Prédéfinis

Quelques prédicats sont bâtis dans le langage et permettent à un programme Prolog 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
affichera 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 bord.
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...)
N.B.- 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 :
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 :
pour signifier qu'un X est père d'un Y si X est parent de Y et X est mâle, où " , " indique une conjonction.
On pourrait avoir de même :
pour signifier qu'un X est parent d'un Y si X est père de Y ou X est mère de Y, où " ; " indique une alternative.
Un fait est un cas particulier de règle. En effet les deux lignes suivantes sont équivalentes :

## É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 :
Il en résulte que la demande suivante est évaluée comme vraie:
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 puisse satisfaire cela) n'est présent. Aussi à la place, tom est substituée 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(prédicat)). En négation par l'échec, la négation d'un prédicat est considérée comme vrai si l'évaluation du prédicat mène à l'échec (n'est pas vérifiable).
Dans Prolog, la négation par l'échec s'appuie sur l'hypothèse du monde clos : tout ce qui est vrai est connu ou démontrable à partir de ce qui est connu en un temps fini.
Voir l'exemple ci-dessous :

## Exécution

Prolog est un langage logique, aussi en théorie, on n'a pas à se préoccuper de la façon dont il s’exécute. Cependant il est parfois 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.
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, 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;
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 avoir écrit;
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 écrite 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:
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. Évaluer 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:
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. Si les règles sont mélangées, vous pouvez maintenant utiliser votre carte de crédit avant de dépenser votre argent disponible.
Vous écrirez donc plutôt :
qui se lit : pour miser X, ou j'ai cet argent d'emblée, ou sinon j'ai le crédit nécessaire.

## Réversibilité

En général, Prolog n'impose pas 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 a priori et sera défini en fonction des requêtes, et parfois des prédéfinis utilisés.
Ceci permet souvent la définition de prédicats réversibles : les requêtes fermées, fournissant des résultats à partir des données, pourront être inversées en requêtes ouvertes, cherchant les données menant à un résultat positif.
    age(capitaine, 45) est vrai ou faux ; age(capitaine, X) demande quel est l'âge X du capitaine, age(X, 45) demande quel X a 45 ans.
Cette possibilité est utilisée dans le générateur/accepteur ci-dessus.

### Exemples

Prenons des arbres binaires avec comme nœud f et comme feuille 0 ou 1.
L'utilisation standard de ce prédicat est du type :
Mais l'on peut aussi avoir :

## Particularités

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.

## Emplois
### Aspect bases de données

Dès le départ, Prolog s'est adressé au domaine des bases de données relationnelles, auquel il apporte une grande souplesse en matière de requêtes, dès lors qu'elles sont déductibles des faits : elles deviennent ainsi des bases de données déductives. Ainsi, une base de faits du style famille(Père, Mère, ListeDesEnfants) pourra, moyennant quelques règles, répondre à diverses questions de généalogie.
Au-delà, Prolog peut également proposer un système de requêtes commun à un ensemble de bases données interdépendantes ; en combinant les relations de base disponibles, on obtient les services d'une base virtuelle combinant ces bases, d'où un enrichissement considérable des requêtes possibles.

### Aspect linguistique

Des traitements linguistiques sont possibles en Prolog sur la base de grammaires formelles.
* un générateur engendrera des phrases conformes à une grammaire et un lexique donné, un accepteur vérifiera la conformité d'une phrase ;
* un analyseur ayant reconnu une phrase (ou un texte), construira un "arbre décoré" qui en sera l'abstraction ; par exemple, le groupe nominal le beau chat deviendra
       gn(le, beau, chat) ou mieux
       gn(art(le), adj(beau), nom(chat)), voire en fonction de l'objectif
       gn(art(le, def, masc, sing), adj(beau, masc, sing), nom(chat, masc, sing, animé)).
* au-delà, un traducteur supposera la transformation de l'arbre abstraction-de-l'entrée en arbre abstraction-de-la-sortie, qui pilotera le générateur du texte final.
un ACCEPTEUR / GENERATEUR
DIALOGUE :
un ANALYSEUR apparenté
DIALOGUE :
où les '???' dénotent les erreurs ou les limites du programme.
Les applications linguistiques de Prolog ont été simplifiées et amplifiées par l'emploi des DCG (Definite Clause Grammar (en)) (Pereira & Warren, 1980).
On peut de là utiliser Prolog en vue de la traduction automatique ou semi-automatique.
Plus fréquemment, un analyseur simple permettra l'emploi de requêtes pseudo-naturelles pour l'interrogation des bases de données relationnelles.

### Aspect combinatoire

Des applications Prolog a priori intéressantes pouvaient avoir des temps d'exécution excessifs du fait de la combinatoire sous-jacente. Prolog et la programmation logique ont donné naissance à un courant de programmation combinant la plupart des spécificités de Prolog et les apports de la Programmation par contraintes pour aboutir avec Prolog IV (1996) à la Programmation Logique sous Contraintes (PLC).Cette approche est très efficace dans les problèmes combinatoires, notamment en CAO, en recherche opérationnelle et dans les jeux.
En effet, on peut par exemple imposer que n variables partageant un domaine à n valeurs s'excluent mutuellement, ramenant le nombre de cas de n^n à n!. Par exemple, pour n=10, de 10 milliards à 3,6 millions.
En 1980, le projet japonais 5e génération (en) avait mis de grands espoirs dans la parallélisation de Prolog, qui se sont heurtés au fait que Prolog étant d'inspiration grammaticale, ses connecteurs logiques ne sont pas commutatifs. Cependant, l'exploitation des règles peut s'accommoder d'un mode pipe-line, interruptible si nécessaire. Soit la règle :
Dès que Prolog trouve un musicien, il peut vérifier s'il est grec, auquel cas il s'agit d'une première réponse. De ce fait, la vérification de la nationalité d'un musicien peut se faire pendant que se poursuit la recherche des autres musiciens connus du système. Ce procédé est d'autant plus efficace que la recherche commence par le prédicat le plus sélectif : c'est le cas si le système connait moins de musiciens que de Grecs.

### Aspect mathématique

Prolog permet le raisonnement par récurrence, et fournit ainsi la possibilité de vérifier des conjectures. Sa capacité à traiter des arbres pouvant représenter des formules permet de l'employer en calcul formel.

### Modules intelligents

Au-delà d'applications purement Prolog, la possibilité de combiner Prolog à des langages traditionnels a permis dès les années 85 de doter de nombreuses applications de modules intelligents tels que des modules experts. À performances comparables, ces modules augmentent ainsi souplesse et pertinence des applications.

## Évolutions

* Prolog travaille dans le cadre de la logique d'ordre 1 et la bonne fin des programmes Prolog est garantie dans un cadre de logique monotone, qui suppose qu'il n'y pas mise à jour de la base de connaissances durant un raisonnement. Cependant des résultats intermédiaires réutilisables peuvent être mémorisés à l'aide du prédicat assert, correspondant à une forme irréversible d'apprentissage, par exemple en mémoïsation.
    Au-delà, l'emploi de prédicats retract permet la modification de la base de connaissances, exigé par le traitement des systèmes dynamiques, comme par certains désapprentissages nécessaires, mais Prolog travaille alors en logique non monotone, en perdant la garantie de bonne fin.
    Ces questions ont amené une distinction entre faits statiques, inmodifiables, et faits dynamiques.
* Des extensions ont été proposées, notamment dans le Prolog ISO, pour favoriser la programmation sous contraintes, la réification permettant un accès limité à l'ordre 2.
* PROLOG est également le support d'extensions dans le domaine de la logique non classique, et en particulier de la logique modale, avec le langage MOLOG développé par l'équipe de Luis Fariñas Del Cerro à l'IRIT.

## Implémentations

* Amzi! Prolog, payant sauf version sans serveur ni redistribuables
* B-Prolog, payant sauf Academic licence
* Borland Turbo Prolog, implémentation pour MS-DOS commercialisée en 1987, reprise par la suite par une entreprise danoise sous le nom Visual Prolog
* Ciao Prolog, libre (GPL)
* GNU Prolog, développé par l'université Paris-1 Panthéon-Sorbonne, libre (GPL et LGPL)
* Rebol Prolog, implémentation en Rebol, à interpréter dans Rebol
* Scryer Prolog, implémentation en Rust, Gratuit.
* SICStus Prolog, développé par le Swedish Institute of 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
* Prolog II (1982) III & IV (1996), gratuits, PC et DOS ou Windows, les Prologs de Alain Colmerauer et son équipe de Marseille