Les logiques : notes en vrac

Dans ce document, je crois qu’il faut comprendre la différence entre fonction et relation, comme ceci : une relation, c’est ce qui n’apparaît (ou n’est censé apparaître, peut‑être) qu’au niveau le plus englobant d’un terme, tandis qu’une fonction peut apparaître dans les termes internes d’un terme.

Example : r(a, b) ou r(f(a), b) mais pas r(r(a, b)). Dans le second cas, la relation r apparaît dans un terme interne à un terme, faisant qu’elle ne devrait pas être qualifiée de relation. Je crois aussi qu’implicitement le terme le plus englobant ne peut pas être l’application d’une fonction, c’est à dire que f(a) ne serait pas conforme à cette distinction, tandis r(f(a)) y est conforme.

Après, doit‑on qualifier une constante de relation à posteriori après le constat qu’elle n’apparaît toujours que dans les termes les plus englobants, ou faut‑il poser à priori les constantes devant être utilisées comme relation et considérer comme non‑valides les cas contredisant ce status (de même pour les constantes désignant des fonctions, dans les termes internes), je ne sais pas …

Citation du précédent document :

Un ground term est un terme ne contenant pas de variables ; hors, un terme cyclique ne peut que contenir des variables ou au moins une. Ce n’est même pas que les termes cycliques peuvent aboutir à des inférences contradictoires pour la sémantique de Herbrand et du Prolog classique, c’est plus encore qu’ils n’y ont simplement pas de sens qui puisse y être validé.

Ça n’interdit pas de leur donner un sens (j’en dirai plus un peu plus tard), mais il est préférable de connaitre et comprendre la sémantique du Prolog de base, qui est la sémantique de Herbrand, avant d’en faire des généralisations ou des abstractions. Faire des démonstrations dans cette logique avec cette sémantique, ça permet d’avoir plus de confiance. Peut‑être même serait‑il possible de démontrer les propriétés d’une généralisation à partir de cette sémantique de base … ce serait l’idéal, mais j’ignore si c’est possible (ou pour le moment).

Toujours du même document :

C’est ce qui peut justifier la négation par l’échec en Prolog. Mais ça ramène encore le problème de la récursion infinie qui peut toujours se produire. La récursion ne se poursuit que temps qu’il n’y pas d’échec, mais tant qu’elle ne se termine pas, on ne peut pas dire que la règle s’est soldé par un succès. Mais même si la récursion ne se poursuit que temps qu’il n’y pas d’échec, elle peut être produite par un échec (je ne détail pas). Dans ces cas, ni la négation ni la confirmation ne peuvent être avancés.

J’exclus les possibles interprétations de certaines récursions infinies (interprétation d’après la cause de la récursion infinie), pour ne rien dire de trop aventureux (je le garde quand‑même pour moi).

Deux exemples d’interprétation de termes non correctes pour le Prolog classique, mais pouvant avoir un sens dans d’autres interprétations. Ces deux exemples ne concernent pas les termes récursifs, dont un exemple de contexte dans lequel ils pourraient avoir un sens, sera suggéré plus tard.

Un terme en Prolog classique, commence par une constante désignant soit une relation soit une fonction. La position de cette constante dans un terme, est seulement une convention. Contrairement à l’ordre des termes dans une conjonction, l’ordre des éléments dans un tuple, n’a pas d’importance, pourvu qu’il soit le même partout.

Ainsi, un terme tel que r(a, b) est correcte en Prolog classique, tandis que le terme (a, r, b) ne l’est pas (il ne passerait même pas les règles de la syntaxe), alors qu’il pourrait l’être, correcte, avec exactement la même sémantique, ce qui serait parfois plus lisible sans avoir besoin de définir r comme un opérateur. L’existence d’une traduction totale et sans ambiguïté entre les deux formes, peut faire office de preuve informelle de l’affirmation.

L’exemple précédent n’est qu’une question de convention, l’exemple qui suit, touche plus à ce qu’il est possible d’exprimer, il est plus sémantique.

Les relations et les fonctions sont désignées par des constantes. Les variables ne sont pas permises à cette place et la syntaxe du Prolog classique ne le permet d’ailleurs même pas.

Ainsi, un terme tel que r(a, b), comme plus haut, est correcte, tandis que le terme R(a, b) ne l’est pas (la majuscule fait que le nom R, est une variable). Il pourrait avoir comme sens d’être une requête pour connaître toutes les relations liant a et b, ce qui pourrait avoir une utilité. Peut‑être justement ce sens serait‑il restreint aux requêtes et non‑applicables aux règles ; ce serait à étudier. La même remarque peut s’appliquer aux fonctions.

Il a été défendu précédemment, que les types dépendants sont peu commodes, entre autres parce qu’ils posent trop de conditions de validité en même temps, qu’il serait préférable de séparer ces conditions en couches superposées, les couches du dessus se reposant sur des couches du dessous.

Un exemple de ce problème peut exceptionnellement même se poser avec les types simples. Les listes sont une structure commune, elle peuvent toujours être vides. Il peut arriver qu’un type ressemble à une liste mais ne puisse pas être vide sans perdre son sens. Définir un tel type ne pose pas de problème, mais parfois (pas toujours !), définir les opérations sur ce type peut aboutir à des complications ; comprendre que ça devient excessivement verbeux. Dans ces cas, il serait par exemple plus simple de rester au principe de la liste pouvant être vide et pour certaines formules en particulier, poser comme condition de validité que la liste ne doit pas être vide, plutôt qu’en faire une condition partout même dans les formules pour lesquelles ça n’a pas d’importance. Une question est : peut‑on temporairement oublier ce que signifie un certain type, peut‑on parfois temporairement faire abstraction d’une partie de ce qu’il est, au moins pour certaines opérations ? Ça dépend, mais il est certain (d’expérience) que parfois oui. Quand c’est le cas, poser le type, puis certaines opérations puis seulement ensuite vérifier des conditions de validité pour poser d’autres opérations, est sûrement plus simple. Sans système formelle permettant de vérifier les conditions de validité, on le fait généralement avec des branches aboutissant à des exceptions, mais sans certitude que les erreurs ne produiront jamais.

Cette question des couche superposées ramène à la question de pouvoir d’abord écrire des formules bien formées, avant de s’assurer de leur validité. C’est un exemple de cas où une généralisation du principe de l’unification et des règles à la Prolog, pourrait avoir une utilité, incluant possiblement les termes cycliques. L’interprétation ne serait plus logique mais assez comme syntaxique (pas exactement, comme distingué après), une question de forme des expressions. En marge, ce n’est pas parce que l’interprétation ne serait plus logique que le problème de la cohérence ne se poserait plus, il faudrait toujours s’assurer que quand une règle dit qu’une expression est bien formée, aucune règle ne le dément, quoique ça pourrait être trivialement le cas, en ne posant que des termes positifs (c’est à dire qu’on ne pose jamais la négation d’une règle dans aucune règle, même pas indirectement). Mais attention à une limite : si à une forme on veut associer un sens, on revient dans le domaine de la sémantique et de la logique, même si c’est d’une manière minimaliste, et là, il faut s’assurer qu’à une forme ne peut être associé qu’un sens, ce qui ne se résous plus en simplement se limitant à des terms positifs.

Je crois qu’une convention commode, est de poser un ensemble des constantes se distinguant comme les constantes des relations et implicitement, toutes les constantes ne figurant pas dans cet ensemble, sont des fonctions. Au moment d’ajouter une règle, il est vérifié que les foncteurs des termes les plus englobants appartiennent à cet ensemble des relations et que ceux des termes les plus internes, n’appartiennent pas à cet ensemble et font donc partie de l’ensemble implicite des fonctions. Quand l’ensemble est vide, ça peut signifier sans problème, par convention, qu’aucune distinction n’est faite entre les constantes, qu’aucun contrôle n’est fait à ce sujet, comme ça, même cette possibilité est couverte.

Le principe peut même s’appliquer au cas où le format des tuples est sans contrainte, c’est à dire autorise des variables ou des tuples même là où une constante est attendue. Dans ce cas, seules les constantes sont vérifiées selon le même principe que plus haut, y compris concernant la convention d’interprétation de l’ensemble vide.

Il n’y a pas besoin de définir deux ensembles s’ils sont disjoints, l’un pouvant être implicitement constitué de ce qui n’est pas inclus dans l’autre. L’ensemble des relations est normalement plus petit que celui des fonctions et probablement plus stable aussi. Les constantes des relations sont celles qui ressortent le plus, étant les constante des termes les plus englobants (les moins internes). Ça justifie la préférence de poser l’ensemble des constantes des relations, plutôt que l’ensemble des constantes des fonctions.

Ça fait une convention commodément praticable et couvrant tous les cas possibles.

Note : il est courant de voir une fonction comme relation, ici, il faut distinguer fonction et relation. Les relations, dans la sémantique de Herbrand, c’est ce à partir quoi des inférence sont faites. Les fonctions sont structurelles, à la manière des constructeurs d’un type somme en SML (ex. l’exemple pédagogique des arbres). Les constantes qui ne sont pas des relations et n’ont pas d’argument(s), peuvent être comprises comme des constructeurs d’arité zéro (ex. nil, true, false, etc). Les relations peuvent quand‑même être interprétées comme des fonctions dans un domaine d’interprétation, ça ne l’empêche pas, à condition de ne pas confondre.

Encore un retour sur les manières de lire une implication. Encore des remarques qui font s’interroger, mais avec une conclusion, cette fois.

Il avait été relevé que dans A ==> B, comme B peut être sans que A ne soit, B est plus permanent que A et pourrait donc se voir plutôt un contexte dans lequel A est une possibilité, plus que comme une conséquence de A. Il avait été relevé l’apparente contradiction que ça présente avec une autre lecture, celle qui dit que si on a A est on peut avoir B, dans le sens où on peut produire B avec A, ce qui est en contradiction avec l’idée de voir B comme un contexte. Puis il avait été remarqué que l’implication ne distingue pas relation de corrélation, de cause, de nécessité et de possibilité, pas plus qu’elle ne distingue la succession de la simultanéité.

L’idée, en dehors d’une exception où A est une nécessité de B, était de faire des interprétations sur la base que B peut être sans que A ne soit.

Justement, il avait été omis de relever que B peut tout aussi bien ne pas être quand A n’est pas, ce qui se produit quand B n’apparaît jamais autrement que dans A ==> B. Dans ce cas, A se lit plus facilement comme une condition de B, ce qui est plus conforme à l’interprétation qui semblait contradictoire, celle de voir A comme une nécessité.

Plus encore, toujours en contradiction apparente avec la première lecture de A ==> B où B peut être sans que A ne soit, A peut avoir plus d’occurrences que B, si A apparaît dans A ==> B et dans A ==> C, dans ces cas, A semble plus « permanent » que B ou C. Ou une variante plus de retour, en accord avec la première lecture, B peut apparaître plusieurs fois mais avec différentes prémisses, comme A1 ==> B, A2 ==> B.

Donc, tantôt A semble être une condition, tantôt B semble être un contexte, tantôt B semble plus permanent que A, tantôt l’inverse, les différentes lectures semblent se contredire.

Dans l’idée du principe de base de Prolog, A ==> B se noterait B :- A (le :- c’est deux points verticaux et un tiret, que la police de caractère n’affiche pas très bien). On peut déjà noter la notation dans le sens inverse, de même qu’était proposée une lecture en sens inverse de l’implication. Il y a plus. Avec à l’esprit les opérations implicites que désigne cette notation, B est un contexte et A est une condition, les deux ensemble, sans contradictions comme il semblerait. C’est expliqué juste plus loin, et des subtilités en plus.

En parlant de Prolog, par contexte, il faut comprendre une ensemble d’associations entre variable et valeur (une variable, une valeur, et plusieurs de telles associations). Quand un terme T contient des variables dont les valeurs sont données par un contexte, on dit qu’il est instancié dans ce contexte. Surtout aussi, une instantiation de T, à partir d’un contexte, crée un nouveau contexte, un contexte dérivé d’un contexte précédent. La notation B :- A est un exemple de règle Prolog. L’application de la règle commence par l’instanciation de B à partir d’un contexte, disons C1, produisant un nouveau contexte dérivé, C2. À noter que cette instantiation peut échouer et alors ça ne va pas plus loin (ou alors avec une autre règle). Quand B est instancié, A est instancié à son tour, cette fois, à partir de C2, produisant un contexte dérivé C3, si l’instanciation réussi. Si tout ce passe bien jusqu’au bout, C3 est le contexte dérivé par la règle, à moins qu’un autre terme ne se trouve à la suite de A, auquel cas, il faut poursuivre jusqu’à obtenir un contexte C4 et ainsi de suite s’il le faut.

On peut déjà remarquer ni A ni B n’ont de status particulier ici, ce qui distingue B est ailleurs, mais ce ne sera pas abordé ici. B signifie bien un contexte, puisqu’un contexte en est dérivé, mais A aussi, désigne un contexte. Cependant, B peut exister sans A, comme l’instanciation a put se faire avant que l’instanciation de A n’ai lieu. A n’est pas une condition de B, puis que B est instancié avant, mais A est bien une condition, une condition de la règle. Si l’instanciation de A échoue, la règle échoue. Ceci dit, B aussi, est une condition, puisque si l’instantiation de B échoue, celle de A ne sera même pas tenté.

Les deux, chacun de A et B, signifie à la fois un contexte et une condition. A est un contexte dans le contexte de B, en accord avec l’interprétation de A ==> B disant que les cas de A sont inclus dans les cas de B. En temps que contexte initial d’entrée dans la règle, B est une condition de A, mais A est un condition plus stricte encore pour la règle que ne l’est B, parce que à mesure qu’on avance dans les termes de la règle, le contexte est de plus en plus contraint par l’accroissement du nombre de variables instanciées, moins nombreuses à pouvoir être fixées librement (une fois fixée, une variable ne l’est plus autrement, modulo quelques subtilités).

On retrouve bien tout ce qui semblait précédemment ambivalent. Tout ce qui semblait contradictoire, ne l’est pas, tout ça est, en même temps.

Le contexte B peut certes exister sans le contexte A dans B, mais il est abandonné si le contexte A dans B ne peut pas être produit. La subtilité est là. Le contexte B pourra cependant éventuellement être produit ailleurs, mais tout autant que le contexte A, mais qui ne sera plus alors un contexte A dans B, peut être un contexte A dans autre chose ou même un contexte A comme contexte initial d’une règle autant que B peut l’être (ça dépend des règles posées).

Ah, une dernière chose … ce B :- A ne fait pas penser à quelque chose quelque part ? … ben si … ce :- qui ressemble tellement à ce ⊢ et il y a bien un rapport entre les deux, comme l’a montré sans le dire ce qui a été dit ici (les histoires de contexte autour de ⊢ ).

Encore une petite dernière chose. Pour l’histoire de celle qui sent bon la meuh‑meuh, Vache ==> Prairie pour dire que la présence de la vache implique la présence de la prairie et qui a donné l’idée d’une lecture de A ==> B comme signifiant que A est une possibilité dans le contexte B. Cette relation là, se noterait mal comme prairie :- vache ou vache ⊢ prairie, elle se noterait mieux comme presence(prairie, vache), qui est justement plutôt une relation, qui se lirait par exemple comme « présence possible dans la prairie, d’une vache ». Si on voulait en faire une règle, on devrait dire pourquoi la vache a besoin de la prairie, la prairie serait bien la tête de la règle, et la vache participerait bien à une des conditions les plus strictes de la règle, mais l’exemple, tel qu’il avait été donné, est plutôt une relation.

En trois messages : des précisions sur le vocabulaire (ce message), des précisions sur le message précédent, puis on commence à aborder les notions d’interprétation et de modèle.

Jusque maintenant, en parlant du principe de base de Prolog et de la sémantique de Herbrand, j’ai parlé de termes au sens large. Il a été précisé que les constantes peuvent se distinguer en deux catégories, celles des relations et celles des fonctions.

Ce que j’ai appelé les constantes des relations, est plutôt appelé des relations, tout‑court, et ce que j’ai appelé les constantes des fonctions, est plutôt appelé des constantes, tout‑court. Les deux sont des constantes, qui se distinguent en deux groupes, mais il n’y a pas de mot pour en parler en général, le mot qui conviendrait pour en parler en général, étant déjà utilisé pour désigner un de ces deux groupes. C’est à voir selon ses préférences personnelles, mais il faut connaitre cette convention courante.

Même chose avec les termes. J’ai distingué les termes les plus englobants commençant toujours par une constante de relation (ou relation, tout‑court) et les termes internes (inclus dans les termes les plus englobants), commençant toujours par une constante de fonction (ou constante, tout‑court). Les premiers sont plutôt appelés des atomes, et les seconds sont plutôt appelés des termes tout‑court. Donc là aussi, le mot que j’utilise pour en parler en général, est couramment utilisé pour parler d’une des deux catégories et il ne semble pas y avoir de mot distinct pour parler des deux en général. Comme précédemment, c’est à voir selon ses préférences personnelles, mais il faut connaitre cette convention.

En résumé : un atome c’est en gros, relation(fonction(…)) et un terme c’est en gros fonction(…).

Les constantes tout‑court (fonction) sans arguments, comme par exemple la constante 0 (zéro), ne sont pas distinguées, elles sont simplement d’arité zéro, mais elles se distinguent syntaxiquement quand‑même par l’absence de parenthèses associées. De même, les relations sans arguments, ne seraient pas distinguées, mais c’est moins important à remarquer, elles sont peut probables (elles peuvent avoir un sens et une utilité quand‑même).

Avant le deuxième message annoncé, une convention de notation divergente de celle habituelle, mais qui est celle que j’utilise et avec laquelle je vérifierai les examples que seront donnés à l’avenir.

Au lieu de noter relation(fonction(…)), la notation sera (relation (fonction …)). La relation ou la constante, au lieu d’être collée à gauche de la parenthèse ouvrante, est collée à droite de la parenthèse ouvrante. Quand une fonction ou une relation a plusieurs arguments, le séparateur des arguments ne sera pas une virgule, mais seulement un espace. Ex: relation(a, b), sera noté (relation a b). Il y a une raison à ces divergences, mais cette raison n’est pas rapportée. Comme le :- (deux points verticaux suivit d’un tiret) s’affiche mal avec la police de caractères du forum, le symbol ：- sera utilisé à place (deux points verticaux plus visibles). Ex. au lieu de r1(X) :- r2(X), la notation sera (r1 X) ：- (r2 X). La conjonction sera notée avec & au lieu d’une virgule, une convention utilisée parfois ailleurs aussi et qui souligne mieux le fait que c’est une conjonction. Ex. au lieu de r1(X) :- r2(X), r3(X) la notation sera (r1 X) ：- (r2 X) & (r3 X).

Utiliser cette syntaxe personnelle ici, évitera les erreurs pendant des réécritures et cette syntaxe est autant lisible que la syntaxe classique, ou j’espère.

Précédemment il a été expliqué comment dans B ：- A qui est l’équivalent en Prolog de A ==> B, autant B que A forme un contexte. Il a été dit que la seule chose qui distingue B et A, c’est que le contexte que représente A est inclus dans celui de B et que le contexte que représente B, est le contexte d’entrée dans la règle.

Pour ne pas être trop long, ce sera complété ici, il n’avait pas été dit que A peut lui‑même être un contexte d’entrée dans une règle. Ceci efface totalement le distinction qui pourrait être faite entre A et B en général, les distinctions n’étant que de circonstances.

Dans ce qui suit, les lettre majuscules comme A, B, C, etc, représentent des expression d’une manière abstraite, sans les détails. Par exemple A pourrait être en fait (r (f X b)), mais sera noté A, pour dire n’importe quelle expression, pouvant contenir une ou plusieurs variables ou aucune. Les lettres majuscules X, Y, Z, sont utilisées pour représenter des variables, pas des expressions abstraites. Par ailleurs, les conventions utilisées pour les notations dans ce message et ceux à venir, sont celles introduites dans le message précédent. On peut maintenant poursuivre.


Si dans B ：- A, l’atome B est la condition d’entrée dans la règle, qu’est‑ce qui a bien put faire qu’on est allé chercher cette règle, en premier lieu ?

Une réponse peut être devinée si on pose ceci :

B ：- A.
C ：- B.

On voit que B se trouve avoir le même status dans la seconde règle, que A dans la première règle. Mais B est‑il alors une condition à l’intérieur d’une règle ou une condition d’entrée dans une règle ? Il est les deux, de même que A pourrait l’être.

Si on entré dans la règle C ：- B, la condition B est alors rencontrée, et cette condition désigne une règle, qui est B ：- A. On ne change pas de règle, c’est plutôt que la règle B ：- A vient en quelque sorte s’insérer dans la règle C ：- B, à la place de B. Je dis en quelque sorte, parce que ce n’est pas une copie littérale, ce n’est pas comme copier/coller du texte, c’est une instantiation (le mot a deux sens, ils sont distingués plus loin), c’est à dire une copie dans laquelle une nouvelle variable est créée pour chaque variable d’origine dans la règle, ceci pour chaque variable y apparaissant, le reste restant inchangé, parce que le reste, ce sont des constantes, qui ont toujours la même valeur dans tous les contextes.

Ainsi, si la règle est (p X) ：- (q X), une instantiation pourrait être (p X2) ：- (q X2). Si la règle était (p A) ：- (q A B), une instanciation pourrait être (p A2) ：- (q A2 B2). À chaque variable dans la règle d’origine, correspond une nouvelle variable avec un nom unique dans la copie de règle, mais si deux variables sont les mêmes dans la règle d’origine, elles doivent rester les mêmes dans sa copie. Ex. si (p X2) ：- (q X2) est une copie correcte de (p X) ：- (q X), au contraire, (p X2) ：- (q X3) n’est pas une copie correcte de (p X) ：- (q X), parce que dans (p X) ：- (q X), les deux X sont les mêmes, mais ils ne sont plus les mêmes dans (p X2) ：- (q X3) ; cependant, les deux X restent bien les mêmes dans (p X2) ：- (q X2).

Si c’est ainsi, c’est pour que quand une valeur sera donnée à X2, ça ne donne pas automatiquement une valeur permanente au X de la règle d’origine, ce qui enlèverait son sens à la variable, puisque que le X d’origine ne serait alors plus une variable et contraindrait tous les cas où la règle est utilisée à avoir la même valeur pour X. Si une autre copie doit être faite, elle doit être encore différente de la précédente, et toujours en vérifiant les mêmes conditions, dont (p X3) ：- (q X3) pourrait être un exemple.

On a une copie de la règle qui est propre à un contexte et qui n’existe que dans ce contexte. C’est important pour la suite, et on le devine d’avance quand on se souvient comme précédemment dit, qu’un contexte, c’est une collection d’associations variable / valeur.

Ceci étant dit, on peut revenir à ce que devient C ：- B quand on rencontre B et que la règle B ：- A a été trouvée. Une copie de B ：- A est faite, et son contenu, c’est à dire A, remplace B dans C ：- B, qui devient donc C ：- A (ici, les lettre majuscules sont abstraites, elles ne montrent pas les noms des variables). Mais la règle d’origine, reste, elle n’est pas changée, c’est une nouvelle version de la règle qui n’existe que pour un temps, surtout qu’il s’agit d’ailleurs d’une insertion dans une copie de la règle d’origine.

Une règle contient toujours un atome qui est la tête de la règle. Dans C ：- B, la tête de la règle, c’est C. Le reste de la règle est appelé le corps de la règle. Dans C ：- B, le corps de la règle, c’est B. Quand B est rencontré et que la règle B ：- A est trouvée et qu’une copie en a été faite, il est tenté de mettre en correspondance le B venant de C ：- B et le B venant de B ：- A. Il ne faut pas oublier que les variables du premier B ne sont pas les mêmes que les variables du second B, puisque le second B est celui d’une copie de B ：- A et que le premier B est celui d’une copie de C ：- B. Plus encore, les deux règles sont des règles différentes et des variables apparaissant dans des règles différentes, ne sont pas les mêmes variables. Ex. si on a la règle (r1 X) ：- … et la règle (r2 X) ：- …, les deux X ont le même nom mais ne sont pas les mêmes variables. Mais dans une même règle, les variables du même nom, sont une même variable. Par exemple dans (r3 X) ：- (r4 X), les deux X sont la même variable.

Pour mettre deux termes en correspondance, il faut qu’ils soient d’abord compatibles. On peut intuitivement comprendre qu’on peut mettre (r1 a) en correspondance avec (r1 a), puisque c’est la même expression, et qu’on ne peut pas mettre (r1 a b) en correspondance avec (r1 a), parce que (r1 a b) a un b qui n’a pas de correspondance dans (r1 a). On peut aussi mettre en correspondance (r1 a) et (r1 X). Si on oublie pas que X est une variable, on devine alors pourquoi elle s’appel une variable : on pourrait mettre (r1 X) en correspondance avec (r1 a) (ou dans l’autre direction, le résultat est le même, c’est commutatif), si on donnait à X la valeur a, et c’est justement ce qu’il se passe. Mais mettre (r1 X) en correspondance avec (r1 a b), ne collera pas, parce que b n’aura pas de correspondance, et on ne peut pas dire que la valeur de X serait “a b”, mais elle pourrait être (a b), ce qui est différent. C’est différent, parce que “a b”, c’est deux termes, tandis que (a b), c’est un seul terme. Si on a mis (r1 X) en correspondance avec (r1 a), que X = a, qu’on a donc un contexte dans lequel X = a, que se passe‑t‑il alors si dans ce contexte, on essaie de mettre (r1 X) en correspondance avec (r1 b) ? Ben ça ne colle pas, parce que X = a, et donc (r1 X) est alors équivalent à (r1 a), qui ne peut pas être mis en correspondance avec (r1 b). Cette mise en correspondance, comme elle est appelée ici, s’appel couramment, l’unification et on parle de l’unification de deux termes ou de deux atomes.

Quand une variable a une valeur dans un contexte, cette valeur ne peut plus être modifiée. Il n’est possible de donner une valeur à une variable que si la variable n’a pas encore été associée à une valeur.

Une subtilité quand‑même. Si on met (r1 X) en correspondance avec (r1 (f Y)), on a un contexte ou X = (f Y). La valeur de X ne peut plus être changé, certes, mais la valeur de Y, si elle n’était pas fixée, peut encore l’être. Si une valeur est donnée à Y, ça change la valeur concrète de X, mais sans défaire l’association entre X et (f Y). Donc si dans un contexte on arrive à Y = (a b c), alors la valeur concrète de X sera finalement (f (a b c)), mais au fond, toujours (f Y), (f (a b c)) étant une vue en expansion de (f Y).

Revenons à notre premier B qui est celui d’une copie de C ：- B et à notre second B qui est celui d’une copie de B ：- A. Les deux sont différents, ils n’ont pas les mêmes variables, mais les deux B, s’ils sont mis en correspondance, peuvent avoir des variables de la même valeur.

Example. Si le premier B est (r X1) et que le second B est (r X2), les deux peuvent être mis en correspondance aisément si ni X1 ni X2 n’ont encore de valeur, ce qui est toujours le cas d’une variable juste après la copie d’une règle, ou peuvent être mis en correspondance si X1 et X2 désignent chacune deux valeurs (celle de X1 et celle de X2), qui peuvent être mise en correspondance. La suite est la même que expliqué plus haut, en poursuivant le principe récursivement.

Revenons maintenant à C ：- B dans lequel on a rencontré B qui a aboutit à trouver B ：- A. Les deux B ont été mis en correspondance, et et si une variable dans A est une des variables de B, elle a la valeur que la mise en correspondance lui a donné. Ex. Si le second B était (r X), que la mise en correspondance lui a donné la valeur b, et si A était (s X Y), alors le X de (s X Y), a aussi la valeur b, parce que les variables du même nom dans une même règle, sont une même variable. Ici, j’omets les numéros qui représentent les copies, pour que ce soit plus léger à lire.

Donc le A de B ：- A peut avoir des variables fixées par la mise en correspondance des deux B, celui de C ：- B et celui de B ：- A. Donc quand on insère A à la place de B dans C ：- B, on insère pas n’importe quoi n’importe où, on insère un A dont les variables ont reçue des valeurs (ou aussi on put rester sans valeur associée) provenant de la mise en correspondance de deux B, dont l’un provient de C ：- B. C’est à dire que ce A, a pris le train qui est passé par C ：- B, il est dans le fil, dans le contexte.

Et ce fil, il est peut être long. Si une règle commence toujours par un seul terme, ou plus précisément, un atome, le corps de la règle en contient typiquement plusieurs, parfois un seul ou parfois aucun. Par exemple :

A.
A ：- B.
A ：- C D E F ….

Le A tout seul suivit d’un point, c’est comme “A ：- .”, c’est à dire que le corps de la règle est vide. Il est parfois noté “A ：- true.” mais je trouve cette notation trompeuse et je ne l’utilise donc pas, préférant simplement dire que le corps de la règle est vide, qu’il n’y a pas de condition supplémentaire à celle de la mise en correspondance avec la tête de la règle.

Quand le corps de la copie d’une règle est insérée à la place d’un atome dans le corps de la copie d’une autre règle, ce qui est inséré peut être plus ou moins long. Mais ça ne se poursuit pas toujours indéfiniment, comme existe normalement toujours des règles avec un corps vide, faisant qu’à un moment, l’insertion ne va récursivement pas plus loin. Je dis récursivement, parce que si dans A ：- B C, on remplace B par, disons D E, et que D correspond à une règle dont le corps, sera, disons F G H, alors on aura d’abord B C, puis D E C, après l’insertion en vertu de la règle correspondante pour B, puis F G H E C, après l’insertion en vertu de la règle correspondante pour D. Si par contre le cors de la règle de D est vide, alors au lieu, à partir de D E C, d’obtenir F G H E C, on aurait E C, puisque à la place de D on insérerait un corps vide, c’est à dire rien. À ce moment là, on rencontre E, et on continue. La règle a aboutit quand les substitutions ont finit par laisser une chaîne vide. Ça signifie que toutes les conditions ont été vérifiées, récursivement et qu’il ne reste plus rien à vérifier, et quand il ne reste plus de conditions à vérifier dans une règle, la règle est vérifiée tout‑court. Le contexte tel qu’il est à ce moment là, est la solution par la règle. Comme c’est un long fil qui s’est allongé puis réduit progressivement par mise en correspondance successive de termes et de tête de règle, on peut aussi voir comme résultat de l’application de la règle, cette succession de mise en correspondance.

Pendant toutes ces étapes, des mises en correspondance par la tête de la règle sont effectuées. Il faut relire ce qui précède en essayant de s’en faire une idée. Bien que la principe soit simple, c’est laborieux, fastidieux à suivre, mais avec l’informatique, c’est faisable, c’est ce que font les interpréteurs Prolog ou Prolog‑like.

Pour finir, il reste quelques précisions à ajouter. Quand une règle est recherchée par correspondance entre un terme et la tête d’une règle, il peut y avoir plusieurs règles candidates, la correspondance peut se faire avec une ou plusieurs ou aucune. Comme il y a plusieurs alternatives, c’est la raison pour laquelle on parle d’arbre de recherche, alors que une solution, c’est à dire une règle qui a put être suivie jusqu’au bout, correspond pourtant à un fil ou à une chaîne. Cette chaîne, on peut l’appeler une chaîne d’inférences, ou même un preuve dans certains usages. Si une seule mise en correspondance échoue pendant le fil d’une règle (et récursivement, les corps des règles qui y sont inséré), toute la règle échoue. Il peut arriver que la succession d’insertion n’aboutisse jamais à un chaîne vide à la fin, elle peut s’allonger indéfiniment ou toujours garder la même longueur, etc. Il n’est pas garanti que ça se termine, le processus peut se trouver piégé dans une récursion ou une boucle infinie.

Ce qu’il faut surtout retenir : quand une règle fait référence à une autre règle via un de ces atomes, que le corps de cette autre règle est insérée dans la règle y faisant référence, c’est toujours en mettant le corps inséré dans le contexte, dans le fil, de la règle y faisant référence. Les règles ne sont pas insérée par copié/collé, elles sont instanciées, elles ont leur propre variables, mais toujours en accord avec le schéma d’origine, celui écrit dans la règle. Les variables apparaissant dans un atome, se voient associé une valeur pendant la mise en correspondance de cet atome avec la tête d’une règle et cette mise en correspondance peut échouer. Cette mise en correspondance s’appel l’unification. En entrant dans une règle, on finit récursivement par visiter d’autres règles. Quand on a finit de récursivement visiter toutes les règles en partant d’une règle initiale, on a suivit une chaîne d’inférences et souvent elle est longue.

Le troisième message qui avait été annoncé comme introduisant les notions d’interprétation et de modèle, une porte d’entrée dans le domaine de la sémantique, est reporté à plus tard ; il faudra d’abord présenter des exemples d’illustration, pour donner un ancrage plus concret à ce qui ne doit pas être compris que comme théorique.