Le titre de ce mémoire, 
Prolog de A à Z, ne fait pas référence
à son contenu.
En effet,
il n'est pas exhaustif,
et donne une plus large part aux travaux de son auteur qu'il ne conviendrait à
un ouvrage exhaustif -- il ne faut pas confondre le A et le Z,
et l'Alpha et l'Omega.
Le titre fait référence à l'organisation du mémoire,
qui pour une grande part prend la forme d'un lexique.
Cette organisation a trois origines :
d'abord,
les travaux présentés ici ont été conduits à plusieurs
niveaux d'abstraction qui entretiennent des relations de dépendance mutuelle,
ensuite,
nous avons voulu fournir des éclaircissements sur des concepts et des noms
qui sont utilisés parfois rituellement et sans conscience de leur signification,
alors qu'ils sont importants pour le domaine étudié,
et enfin,
le langage de programmation titre,
Prolog,
est lui même conçu à la croisée de plusieurs théories.
L'organisation en lexique permet de rendre également visibles toutes ces
dimensions.
Les travaux présentés dans ce mémoire ont été conduits à plusieurs
niveaux d'abstraction qui interagissent.
Cela est conscient et délibéré car pour nous
il n'était pas question d'étudier l'implémentation d'une famille de langages de
programmation sans connaître leur utilisation.
Et inversement,
même si l'utilisateur ordinaire n'a pas à connaître l'implémentation,
les experts qui la connaissent peuvent
promouvoir telle ou telle pratique de programmation.
Chaque langage de programmation propose
des techniques de programmation particulières
dont on veut parfois développer l'usage.
Il faut pour cela que l'implémentation ne cause pas de mauvaise surprise à
l'utilisateur.
Celui-ci aura en retour de nouvelles exigences,
qui doivent à leur tour être implémentées, etc.
Cette démarche a guidé nos travaux sur Prolog.
Ils ont bien sûr été présentés et publiés les uns après les autres,
mais selon une séquence un peu arbitraire.
Ils ont aussi fait l'objet de synthèses partielles,
mais il nous a semblé que ce mémoire
était le bon endroit pour tenter une présentation moins
hiérarchique.
Le vocabulaire de la programmation logique utilise rituellement des
expressions comme
«clause de Horn» ou «base de Herbrand».
Qui sont Horn et Herbrand ?
Quel est le rapport entre Jacques Herbrand mort en 1931 et la programmation
logique née vers 1970 ?
Chacun sait ce que sont les dénotations de «clause de Horn» et
«base de Herbrand»,
mais la signification de ces expressions est beaucoup moins connue.
En d'autres termes,
si la définition des clauses de Horn est largement connue,
le pourquoi de cette référence à Alfred Horn l'est beaucoup moins.
La théorie de Prolog apporte son lot d'expressions rituelles
avec les «formules de Harrop»
et les «-termes simplement typés».
Qui est Harrop ?
Pourquoi «simplement typés» ?
L'usage rituel d'une expression dont on oublie la motivation
n'est pas une habitude spécifique à la programmation logique :
le vocabulaire de l'interprétation abstraite utilise l'expression
«connexion de Galois»,
celui de la programmation utilise «méthode de Horner».
Nous avons voulu répondre à ces questions et à d'autres comme
«Comment marche l'unification des
-termes ?»,
et d'abord «Qu'est-ce qu'un
-terme ?».
L'objectif est de fournir des réponses là où la littérature
n'en donne presque pas hormis les écrits originaux
(cas de Horn et,
dans une moindre mesure,
de Herbrand),
ou d'éviter au lecteur un détour là où la littérature
abonde mais la question est si centrale à notre sujet que l'accès
à une réponse rapide est nécessaire
(cas des -termes).
L'ouvrage «Logique, réduction, résolution»
(René Lalement, Masson, 1990)
comble ce genre de manque pour le
domaine qu'il couvre :
les théories des programmations fonctionnelles et logiques,
de la calculabilité et de la complexité.
Il ne couvre pas Prolog,
mais la plupart des théories qui en sont à l'amont,
et il les traite en plus grand détail que nous le faisons dans ce mémoire.
Nous y renvoyons donc le lecteur pour toute question qui n'est pas directement
liée à Prolog.
Le langage Prolog est fondé sur les mêmes théories
que la programmation logique et la programmation fonctionnelle,
calcul des prédicats et -calcul,
mais il en fait un usage différent qui permet justement la rencontre
des deux théories dans un même langage de programmation.
Par exemple,
la théorie de la programmation logique exploite beaucoup le point de
vue des modèles du calcul des prédicats,
alors que la théorie de Prolog exploite plutôt le point de vue des preuves.
De la même manière,
la théorie de Prolog est en partie fondée sur le -calcul,
mais n'en fait pas le même emploi que la programmation fonctionnelle.
Donc,
ce n'est pas seulement l'«autre» composante qui est nouvelle pour
un programmeur logique ou fonctionnel ;
la composante qu'il croit connaître est aussi traitée en de nouveaux termes.
Présenter Prolog exige donc de répondre à de nombreuses questions,
y compris de la part d'un auditoire qui est théoriquement proche.
Répondre à ces questions dans des incises ou dans des notes a plusieurs inconvénients. D'abord cela n'offre pas une bonne visibilité aux réponses car elles ne sont accessibles que séquentiellement, au fil du texte. C'est ainsi que les notes d'un ouvrage peuvent être rééditées isolément pour leur donner la visibilité qui leur manquait : par exemple «Éléments d'Histoire des Mathématiques, Nicolas Bourbaki, Hermann» est un recueil des notes historiques de «Éléments de Mathématique, ibid.». De plus, cela abuse des ressources typographiques. En effet, de la taille même des caractères employés dans les notes en bas de page on peut inférer qu'elles sont prévues pour un usage marginal. Y mettre ce qu'il est essentiel de connaître pour comprendre le texte principal constitue donc un abus.
L'organisation en lexique est classiquement utilisée pour
présenter des domaines multidimentionnels lorsque l'auteur ne souhaite
pas privilégier une dimension
(«Shakespeare de A à Z, Michel Grivelet, Aubier, 1988»,
«Le dictionnaire Khazar, Milorad Pavic, Belfond»,
«Le dictionnaire encyclopédique du génie logiciel, Henri Habrias, Masson, 1997», etc.).
Elle a trouvé ces dernières années un prolongement informatique
dans la notion d'hypertexte.
Ce document
est donc la version hypertextuelle d'un
mémoire d'Habilitation à diriger des recherches
qui lui est de composition traditionnelle [].
On trouvera dans une première partie de ce mémoire des essais sur
quelques aspects de Prolog,
de son implémentation et de ses applications.
Cette partie ne contient pas de définitions formelles ni de théorèmes,
et les formules qu'elle contient sont d'abord des illustrations.
Une deuxième partie est un lexique qui contient les définitions des concepts
utilisés en Prolog,
le rappel de théorèmes utiles,
et la description succincte des travaux qui ont conduit à utiliser
quasi rituellement le nom de leurs auteurs.
Les deux parties contiennent des liens vers des sections de la première
d'entre elles et vers des articles de la seconde
(par exemple Prolog*).