Les logiques : notes en vrac

Pour la conjonction, les status seraient ordonnés par numéro croissant, en commençant à 1. Le résultat de la conjonction serait le status rencontré, de numéro le plus petit. Le status permettant le court‑circuit, c’est à dire la réduction immédiate de la conjonction, serait le status № 1. L’ordre des status ne devrait pas être défini au hasard, mais en tenant compte de cette règle. Resterait à démontrer la cohérence du choix fait.

Exemple avec ces status :

№ 1 : échec
№ 2 : indéterminé
№ 3 : partiellement déterminé
№ 4 : succès

Au premier terme dont le status est « échec », la conjonction se réduit à « échec ». S’il y a des status « indéterminé », « partiellement déterminé » et « succès », le status de la conjonction est « indéterminé ». Pour que le status soit « succès », le status de tous les termes doit être « succès ».

Modulo une autre option abordée juste ensuite, même chose avec la disjonction, s’appliquant aux status des règles tentées. Les numéros des status s’interprètent dans l’autre sens : le court‑circuit est permis dès la première occurrence du status dont le numéro est le plus élevé dans la liste et la la disjonction se réduit au status dont le numéro est le plus élevé rencontré. Avec la même liste de status que plus haut, le premier status « succès » permet la réduction immédiate à « succès », et si la disjonction a des status « échec », « indéterminé » et « partiellement déterminé », le status de la disjonction est « partiellement déterminé ».

Une autre option est possible pour la disjonction, plus sophistiquée, restant à définir formellement. S’il n’y a qu’un status « succès », elle se réduit à « succès ». S’il y a plusieurs status « succès » (plusieurs vérification pour un même terme), elle se réduit à « succès multiple ». S’il y a des status « succès » et « indéterminé », ça se complique. Si l’idée est de distinguer les cas à succès multiple, il est difficile d’ignorer un status « indéterminé », qui n’est pas « succès » mais pas « échec » non‑plus. Peut être « indéterminé à succès, multiple ». Comme l’interval rapporte plusieurs status, ce qui implique que le status n’est pas un « succès » unique, le « multiple » est redondant et le status pourrait être juste « indéterminé à succès ». C’est à dire, soit l’interval, impliquant la multiplicité, soit le status unique mais rencontré plusieurs fois, en précisant alors « multiple ».

Si la disjonction est interprétée comme plus haut, alors la conjonction doit être revue en conséquence. En effet, le status d’un terme est celui d’une disjonction, comme un terme est vérifié par une ou plusieurs règles. Le status d’une règle elle‑même, est une conjonction de status productibles par la disjonction ; les status productibles et attendus par la disjonction, et ceux productibles et attendus par la conjonction, doivent être dans le même ensemble de possibilités. Le domaine et le codomaine de la conjonction et de la disjonction, doivent être les mêmes, un seul et même ensemble de status possibles.

Le cas de plusieurs vérifications pour un terme peut être important à distinguer. Dans une équation numérique, un cas à plusieurs solutions ne peut généralement pas être confondu avec un cas à une seule solution. Avec des règles décrivant des syntaxes, la confirmation de plusieurs vérifications possibles, signifie que la construction syntaxique est ambiguë. Cette distinction n’est pas une curiosité théorique, elle a un intérêt sémantique pour plusieurs domaines d’interprétation.

Les cas à plusieurs ou à une solution, peuvent devoir être distingués, mais ce n’est pas une obligation. Cela pourrait faire partie de la définition du langage aussi bien qu’être spécifique à un mode d’interprétation d’une requête. Le mode d’interprétation doit se comprendre comme il a été introduit avec la négation.

La distinction entre succès et indéterminé ou partiellement déterminé, n’est pas requise non‑plus, mais le cas indéterminé, serait probablement souvent utile, à moins que la définition du langage ou sa mise en œuvre, ne soit garantie couvrir tous les cas possibles. Ces deux status doivent être expliqués, parce que leur noms prêtent à confusion (il faudrait leur trouver d’autres noms).

Indéterminé, est un status produit par un terme non‑interprété. Par exemple dans une vérification n’interprétant que les variables déterminées, si un terme dans le corps d’une règle, contient une variable n’apparaissant pas dans la tête de la règle, cette variable est indéterminée et alors le terme n’est pas interprétable. Il n’est pas interprétable, mais ne peut pas être considéré comme un échec, comme il pourrait éventuellement être vérifiée avec une interprétation adéquate. Un autre exemple est avec les négations dans une résolution. Une méthode d’interprétation des négation comme résolution, a été présentée. Cette méthode n’est applicable que pour des variables indépendantes les unes des autres, c’est à dire non‑intriquées (une solution plus complète peut exister, c’est seulement un exemple). Si des variables intriqués apparaissent dans un terme en négation, la méthode ne s’applique pas. Le status ne peut pas être l’échec, comme avec une méthode plus complète, le status aurait put être un succès. Dans ce cas, le status indéterminé exprime bien la situation sans être incohérent (le status n’est pas « succès »).

Partiellement déterminé, est le status d’un terme dont la solution n’est pas totalement déterminée, c’est à dire ne se développe pas en un terme constant. Ce status est un status « succès », avec une précision supplémentaire. Si une solution contient une variable laissée indéterminée, le status est quand‑même partiellement déterminé, comme une solution a été produite. Que la variable qui apparaît dans la solution d’un terme, soit partiellement indéterminée ou laissée indéterminée tout‑court, le status est partiellement indéterminé. D’autres mots seraient préférables. Non‑interprétable et non‑constant ?

La distinction entre vérification unique et vérifications multiple, devrait peut‑être se limiter aux cas où le status indéterminé n’existe pas et où la distinction entre entièrement ou partiellement déterminé, n’est pas faite. Cette condition éviterait le cas qualifié de « ça se complique » dans le message précédent.

La distinction entre succès et partiellement déterminé, devrait peut‑être se faire en utilisant un status composé pour « succès », ce qui s’interpréterait plus facilement comme un status « succès » avec un détail supplémentaire.

Dans une définition du langage, une constante peut se réduire à une chose purement structurelle.

Précédemment, avait été mise en balance, deux options pour représenter les constantes. Une première option était de les représenter comme des mots sous forme de liste de lettre, une seconde, comme une chose abstraite.

L’option de la constante comme une chose abstraite a été abandonnée pour une raison déjà décrite. L’option de représenter une constante comme un mot peut se simplifier en une représentation du même type que celle déjà vue pour les entiers naturels.

Il est possible d’aller plus loin et de mettre en pratique l’idée de représenter les entiers naturel, sans constante : (), puis (()), puis ((())), etc.

Une correction avant le point important. Il avait été dit précédemment, que sans la composition horizontale, la composition verticale ne peut rien exprimer d’autres que des choses comme les exemples de termes plus haut. Au passage, ce n’est pas trop pauvre pour représenter des constantes, c’est suffisant, mais surtout, il y avait une erreur. Dans (), la composition horizontale est d’arité zéro ou n’existe pas, selon le point de vu. Mais dans (()), il y a une composition horizontale d’arité 1. Même dans ces termes composés uniquement d’imbrication sans rien d’autre, il y a une arité. En fait, la composition verticale, sans la composition horizontale, est encore plus limitée que mentionnée précédemment, elle se résume au seul terme ().

Après cette correction, le point important est que, si l’interprétation de la composition verticale comme permettant de représenter plusieurs dimensions, la composition horizontale étant comme leurs axes, si cette interprétation est correcte, alors représenter les constantes ainsi, revient à les réduire à une simple position dans un espace. Ors, il avait été remarqué que l’égalité n’existe pas autrement que comme une abstraction, parce que même deux choses identiques, peuvent toujours être distinguées par leurs positions, mais que si elles occupent exactement la même position, plus rien ne permet de les distinguer et elles se confondent alors (à condition d’être identiques par ailleurs).

C’est amusant que la représentation la plus épurée possible pour représenter une constante, est celle de la définir comme une position dans un espace, que la seule interprétation existante pour une constante, est son égalité avec sa propre représentation et que la seule égalité réelle possible qui ne soit pas abstraite, nécessite que les deux choses égales se confondent dans une même position. C’est amusant, mais en oubliant pas que la définition du langage étant écrite dans le langage qu’elle définit, d’autres moyens sont disponibles, une autre représentation pour les constantes est possible (ex. comme une liste de lettres), alors ce n’est peut‑être qu’une chose amusante sans signification réelle. Ou peut‑être que ça en a vraiment une, de signification.

Il a été dit qu’il faut éviter les représentation sans constante caractérisant une relation, pour éviter les risques de mauvaises interprétations. Mais là, il s’agit d’une définition du langage lui‑même, pas d’une définition de règle dans une application du langage. La situation exceptionnelle justifie l’exception à la règle. Surtout que cette représentation épurée est intéressante pour ce qu’elle suggère et a été décrit plus haut.


L’égalité de deux constantes, ou plutôt de l’identité de deux constantes (même représentation pour l’identité d’une variable), se défini ainsi, avec cette représentation :

(eq () ()).
(eq (N1) (N2)) : (eq N1 N2).

La différence :

(neq (N) ()).
(neq () (N)).
(neq (N1) (N2)) : (neq N1 N2).

L’interprétation vérifiant qu’un terme est une représentation de l’identité d’une constante, ce qui correspond à ce que représente son nom :

(name ()).
(name (N)) : (name N).

Cette représentation rend aussi bien visible une chose : bien que les constante et leurs comparaison puisse apparaître ainsi dans une définition du langage, pour une application du langage, le langage n’existe que sous la forme de sa syntaxe, ses représentations internes sont inaccessibles à une application du langage. Ce point avait été souligné à quelques occasions précédemment, l’exemple de cette représentation possible, pour les constantes, dans la définition du langage, illustre à quel point c’est vrai, à quel point la différence entre les deux peut être importante.

Les raisons expliquées plus haut, de voir les constantes comme des objets structurels, est la bonne, je crois. Comme dit, il y a bien une autre manière de définir ce qu’est une constante pour le langage, mais définir la notion d’identité d’une constante à partir de constantes quand on peut le formuler sans, peut au moins laisser l’impression qu’on passe à côté de l’expression d’un fait fondamental, puisqu’une représentation sans, est possible.

Il a été dit plusieurs fois, qu’une constante caractérise une relation ou une interprétation, qui autrement pourrait être confondue avec une autre, si les termes ont la même structure.

Comment ferait‑on pour distinguer des termes sans constantes ? En y ajoutant un détail structurel qui ne servirait qu’à ça. Et c’est justement ce qu’est cette manière de définir l’identité d’une constante. Ça fait une seconde bonne raison d’opter pour la constante comme un objet purement structurel. En fait, trois, si on compte celle du précédent message, dans la partie où était faite une mise en rapport avec l’égalité.

Cette définition sera conservée.

Dans le précédent message, il était dit que la représentation est en fait celle de l’identité d’une constante. C’est parce que la même représentation est utilisée pour l’identité d’une variable. La relation qui vérifie ce type s’appel “ name ” au lieu de “ id ”, parce que “ name ” suggère plus de sens que “ id ”, à cause des usages typiques de ce mot, comme dans les base de données ou les conteneurs. Dit d’une autre manière, “ name ” évoque mieux ce qu’il faut comprendre en parlant d’identité pour une constante ou une variable. C’est aussi la représentation de ce qui est en effet un nom dans la syntaxe.

La distinction entre l’identité d’une variable et d’une constante, est quand‑même exprimé par une constante : (const N) et (var N). Peut‑être que pour les constantes, il serait possible de se passer de (const N), et d’interpréter directement N comme une constante. Mais ce n’est pas nécessaire, la manière dont est représenté ce N est déjà assez pour souligner l’idée que l’identité d’une constante, est en fait une notion purement structurelle.

Il avait été dit qu’il est dommage de représenter la composition horizontale comme une liste, alors qu’il n’y a pas de relation d’ordre entre ses éléments, que leurs positions sont fixées, mais arbitraires.

Pour ne pas donner un status particulier à l’une ou à l’autre, les deux étant indissociables, on pourrait vouloir représenter l’une à partir de l’autre et envisager la réciproque. Mais on peut faire abstraction d’une chose dont on a pas besoin, pas l’inverse, on ne peut pas faire venir de nul‑part une chose qui manque. Pour la composition horizontale, on fait abstraction de l’ordre, qu’on considère comme arbitraire, en intention au moins, parce qu’il faudrait vraiment y trouver beaucoup d’intérêt pour se donner la peine de prouver que c’est le cas. Même sans savoir comment ce serait possible, l’idée de la réciproque, définir la composition verticale à partir de l’horizontale, semble déjà impossible rien qu’en y pensant : il faudrait définir une relation d’ordre à partir de quelque chose qui est censée ne pas en avoir. C’est la première raison, il en reste une seconde, autant importante.

La liste est aussi la seule formulation permettant de dire dans une règle, qu’on se soucie de tous les termes d’une relation, sans en oublier aucun, ce qui à défaut de pouvoir exprimer une forme de parallélisme, ne peut s’exprimer qu’en disant qu’on prend ses termes un par un, l’un après l’autre.

L’idée d’introduire une notion de parallélisme, par exemple la prise en compte de tous les termes simultanément en parallèle, ne fonctionnerait pas pour l’unification, pour la même raison qu’il n’est pas possible de dire qu’on traite tous les termes d’une conjonction en parallèle : les possibles interdépendances le rende impossible. L’unification, comme les termes d’une conjonction, nécessite de traiter les éléments l’un après l’autre, même si l’ordre dans lequel on le fait, est sans importante, c’est nécessairement séquentiel. En marge, il est intéressant de noter cette similitude entre une conjonction et une relation.

Définir la composition horizontale à partir d’elle‑même, n’est pas possible non‑plus, parce qu’elle ne présente aucune notion de séquence, justement parce qu’elle n’a pas de notion de relation d’ordre.

Définir la composition horizontale comme une liste, semble être la seule possibilité. Il n’y pas d’autres options que d’accepter cette relation d’ordre dont on a sémantiquement pas besoin, parce qu’on a quand‑même besoin pour définir cette sémantique, pour formuler une interprétation séquentiel de tous les éléments d’une relation.

Peut‑être qu’une conclusion de portée plus générale, serait qu’il faut parfois faire attention à ne pas confondre la sémantique qu’on veut définir avec ce qui est nécessaire à sa définition. Est‑il possible d’aborder formellement cette relation entre les deux ? Entre une sémantique et ce qui est nécessaire à sa formulation ? Cette relation dit‑elle quelque chose sur l’une ou l’autre ou les deux ?

Le parallélisme pourrait avoir une place quelque part : la vérification d’un terme par un ensemble de règles candidates, pourrait se faire en parallèle, la vérification par une règle étant indépendante de la vérification par une autre règle.

Faut‑il y voir une opportunité d’introduire une notion de parallélisme dans le langage ?

Une recherche de réponse à la question pourrait faire se demander si ça aurait un intérêt sémantique ou si ça n’aurait un intérêt que technique, qui n’a pas sa place dans la sémantique.

Sémantiquement, ça pourrait faire une différence, dans le cas où une règle se termine en récursion infinie et pas une autre. Mais on peut éviter les récursions infinies n’aboutissant à rien, avec les preuves de satisfiabilité. Disons alors que l’intérêt sémantique est faible et que l’introduction de cette notion dans le langage, n’en vaut pas le coût. À moins que d’autres remarques ne viennent remettre cette appréciation en question.

Pour l’ordre des termes dans une conjonction, c’est différent, c’est plus intéressant, au moins pour des raisons techniques. Ces raisons techniques ne sont pas sémantiques, mais nécessitent la démonstration correspondante quand‑même et cette démonstration pourrait avoir un intérêt sémantique. Pour la non‑pertinence de l’ordre des termes d’une conjonction, une preuve informelle avait été donnée, mais une preuve formelle serait encore mieux.

Important : cet ordre n’est pas pertinent seulement si on ne s’intéresse qu’au status d’une vérification ou d’une résolution avec une solution quelconque, parce que comme déjà vu il y a un an, pour la résolution standard, celle qui tente d’énumérer les solutions, l’ordre des termes peut être important.

Une colle : la négation d’une règle doit‑elle avoir une preuve de satisfiabilité ? On pourrait se dire qu’une règle peut toujours être non‑vérifiée. Pourtant, en tenant pour acquise la possibilité qu’un terme ne commence pas nécessairement par une constante, cette règle n’a aucune négation possible :

A.

N’importe quel terme est unifiable à A ; la tête de la règle toute entière, est une variable. Le corps de la règle est vide et alors n’échoue jamais. N’importe quel terme vérifie toujours cette règle, dont la négation ne peut donc jamais être vérifiée.

Ce n’est pas pour dire que cette règle a un intérêt et qu’il est attendu qu’elle soit écrite, c’est pour dire que ce cas est possible et qu’il faudrait le prévoir, pour la cohérence.

Ou cette règle doit‑elle être considérée incorrecte ? Si oui, il faut le formuler explicitement. Mais qu’est‑ce qui pourrait justifier de la considérer incorrecte, en dehors d’un argument faible, comme « elle n’a pas d’intérêt » ?

Si c’est possible ou pas, dépend de la syntaxe. Si les constante étaient littéralement écrites comme elles sont définies (voir le message qui décrit leur représentation interne dans le langage), oui, ce serait possible. Mais humainement, une telle syntaxe n’est pas acceptable, à la place; ont utilise des mots composés de lettres ; la traduction de la syntaxe en termes de la définition du langage, doit donc créer une association 1-1 entre mots composés de lettres et identités de constantes. Si la syntaxe associe abc à (()), par exemple et que dans un terme, on avait un (()) écrit littéralement, il serait interprété comme la constante abc, ce qui serait inattendu. La syntaxe utilisée rend nécessaire l’utilisation de (const N) pour distinguer les constantes. C’est une nécessité pour raison de syntaxe utilisée, ce n’est pas une nécessité formelle.

Rendre incorrecte dans la syntaxe, les constructions de terme de la forme ((…)), serait auto‑contradictoire, puisque la définition du langage est dans le langage lui‑même, et alors il ne pourrait plus lui‑même défini la notion de constante de cette manière.

Ça signifie que la définition de la sémantique et la définition de la syntaxe, ne sont pas totalement indépendantes.

Il y a bien l’exemple d’une somme de nombres ou d’un produit de nombres, qui est nécessairement séquentiel, sans que pourtant l’ordre des nombres ajoutés entre eux ou multipliés entre eux, ne soit important. Mais c’est un exemple en math, pas une construction réelle. Trouver un exemple avec une construction réelle, serait plus intéressant. Mais peut‑être que ce phénomène est vraiment spécifique aux langages formels.

En parlant de parallélisme dans cette question, il faut comprendre entièrement en parallèle. Parce que avec l’exemple d’une somme, on peut faire plusieurs sommes de deux nombres en parallèles, on alors deux fois moins de nombres, on répète ainsi, jusqu’au résultat. On a un mélange d’opérations en parallèle et d’opérations séquentielles (les itérations sont séquentielles). Ce parallélisme là, n’est pas considéré comme un vrai parallélisme dans le sens où il était entendu, puisqu’il y a toujours nécessité d’opérations séquentielles, même si on en économise sur le nombre d’étapes.