Le langage propositionnel utilise les connecteurs logiques `{"et", "ou", =>,¬}` et des prédications zéro-aire `a,b,c,...`. En logique classique, les prédications sont des variables booléennes et les connecteurs logiques sont des connecteurs booléens.
On définie un méta-langage à partir de ce langage propositionnel en ajoutant le méta-connecteur de démontrabilité `"(... ⊢ .)"`. Il prend comme argument une ou plusieures propositions `A,B,C,...` placées à sa gauche et une proposition `R` placée à sa droite. Il signifie que le système déductif démontre `R` à partir des propositions `A,B,C,...`.
Le sytème de déduction naturelle comprend les règles suivantes écrites dans ce méta-langage. Quelque soit `A,B,C,D,E,F`, des propositions du langage propositionnel, nous avons 14 règles :
`|-- (A"⊢"A)` `(A"⊢"B),(C"⊢"D) |-- (A,C"⊢"(B" et "D))` `(A"⊢"B" et "C)|--(A"⊢"B)`
`(A"⊢"B" et "C)|--(A"⊢"C)``(A,B"⊢"C) |-- (A"⊢"(B"⇒"C))` `(A"⊢"(B"⇒"C)), (D"⇒"B) |-- (A,D"⊢"C)` `(A,B"⊢""⊥") |-- (A"⊢""¬"B)` `(A"⊢""¬"B), (C"⊢"B) |-- (A,B"⊢""⊥")` `(A"⊢"B) |-- (A"⊢"(B" ou "C))`
`(A"⊢"B) |-- (A"⊢"(C" ou "B))``(A"⊢"(B" ou "C)), (D,B"⊢"E), (F,C"⊢"E)|--(A,D,F"⊢"E)` `(A"⊢"B)|--(A,C"⊢"B)` `(A,B,(B"⊢"C)|--(A,B"⊢"C)` `A,("¬"B"⇒""⊥") |-- (A"⊢"B)`
Cet ensemble de règles de production constitue un moteur. On s'intéresse à la programmation de tel moteur.
On introduit l'aspet dynamique d'une manière un peu plus générale comme suit : On définie d'abord un langage d'opérateurs tel que par exemple `"<"a,b,f"(.)",g"(.,.)",h"(.,.)>"`. Puis on ajoute dans ce langage des variables `A,B,C,...` dites libres. Notez alors que les éléments `a,b` sont des constantes, et qu'il y a donc deux types d'opérateurs zéro-aire, les contantes et les variables. Puis on ajoute les opérateurs de production binaire, ternaire, ou quaternaire..., `"(.→.)"`, `"(.,.→.)"`, `"(.,.,.→.)"` dont la signification est la suivante. Si les premiers arguments s'unifient à des termes alors l'opérateur de production produit un nouveau terme qui est son dernier argument dans lequel les variables libres sont remplacées par leurs valeurs d'affectation obtenues lors de l'unification et où celles restées libres sont remplacées par n'importe quelle terme du langage.
Un terme est une règle de production si et seulement il possède comme racine un opérateur de production. Et alors sont aspect dynamique consiste à unifier ses arguments d'entrés avec d'autre terme (ou lui-même), ce qui entraine la production d'un nouveau terme résultat.
On considère un ensemble de termes comme un mélange chimique. Les termes sont considérés comme des molécules et intéragissent suite à des collisions. Un terme productif peut unifier ses arguments d'entrée avec d'autres termes (ou lui-même) présent dans le mélange et produire un nouveau terme qui s'ajoute au mélange. Par exemple :
`g(A,B),h(A,B)→g(B,f(B))`
`g(a,a)`
`h(A,A)`
Le terme `g(a,a)` et le terme `h(A,A)` que l'on renomme en `h(C,C)` afin que ses variables soient différentes de celles déjà existantes, peuvent s'unifier avec les entrées du terme productif et ainsi produire le résultat suivant : `g(a,f(a))`
Notez que dans d'autres cas, le résultat peut être également un terme productif.
On utilise une structure de données mettant en oeuvre le partage de données afin que là où un seul traitement est nécessaire cela ne nécesssite pas plusieurs traitements. Pour faire cela, on utilse des pointeurs qui peuvent pointer les sous-termes d'un terme. Chaque pointeur pointe soit une constante, soit une variable, ou soit un terme.
Un terme est mémorisé sous forme d'un graphe orienté acyclique composé de noeuds comprenant 2, 3 ou plus de pointeurs selon l'arité maximum utilisée, et de feuilles que sont les variables et les constantes. Par exemple le terme `g(a,g(X,a))` est mémorisé comme suit :
Les variables et les constantes sont des composants symétriques ici respectivement en vert et en orange tandis que les noeuds sont en blanc. Les variables et les constantes sont mémorisés de façon unique, autrement dit il ne peut y avoir deux cases contenant une même variable ou une même constante. Le noeud représente le terme dont il est la racine.
On programme quelques opérations de base :
L'itérateur Lister(A,B) prend en argument deux pointeurs A, B pointant sur des noeuds de même taille et retourne la liste des couples (A[0],B[0]), (A[1],B[1]), (A[2],B[2]),... où A[n] représente le pointeur présent dans la case numéro n du noeud A.
La fonction VariableLibre(P) prend en argument un pointeur et retourne vrai s'il pointe sur une variable libre.
La fonction Taille(P) prend en argument un pointeur pointant sur un noeud et retourne sa taille.
La condition a=b retourne vrai si les pointeurs a et b sont égaux c'est à dire s'ils pointent sur un même endroit.
L'affectation a:=b modifie le contenue de la variable libre pointée par a, en lui attribuant la valeur pointée par b. Une fois affectée, la variable n'est plus libre et à chaque solicitation, elle retourne ce quelle contient, en créant d'éventuels raccourcis au cas où plusieurs variables sont mémorisés en cascades, cette création de raccourcis étant nécessaire pour assurer pleinement la complexité linéaire de l'algorithme.
Unifie(a,b) {
if a=b then return true
if VariableLibre(a) then {a:=b; return true}
if VariableLibre(b) then {b:=a; return true}
if Constante(a) or Constante(b) then return false
if Taille(a) ≠ Taille(b) then return false
Lister(a,b){(u,v) | if not Unifit(u,v) then return false}
return true
}
La fonction Unifie prend en argument deux pointeurs pointant deux termes et les unifie. Elle retourne vrai si l'unification réussie. Après une unification réussie, les variables contiennent le réultat de l'unification. Il faut donc préalablement garder en mémoire ces variables, ceci afin de pouvoir récupérer leur valeur après unification. (L'unification peut aussi s'effectuer à n termes de façons très efficaces par un algorithme analogue).
L'epression du genre f(a){x|g(x)} correspond à une forme de programmation Ruby appellée "bloc de code", où le bloc de code en question est {x|g(x)}. Cela signifie que f(a) produit une listes de valeurs résultats, et pour chaque valeur x ainsi produite on exécute la commande g(x).
On veut créer un framwork pour expérimenter les langages formels à l'aide de divers outils. Ce que l'on cherche dans la conception d'un framwork ou dans un langage de programmation tient en 3 points :
On part d'un langage d'opérateur. Puis il convient d'avoir un second langage plus élégant qui sert à la communication avec l'utilisateur. Ce langage sera appelé langage interface.
Il convient de pouvoir saisire une proposition dans le langage exacte dans laquel elle a été conçue. C'est pourquoi on utilise un langage interface permettant de nombreuse représentations possibles des opérateurs.
On définit ce langage interface en précisant la syntaxe de chaque opérateur, tel que par exemple:
Priorité
Les opérateurs variables d'arité nulle sont notées par les lettres majuscules `A,B,C,...`
La priorité des opérateurs intervient lorsque localement plusieurs interprétations sont possibles. L'interpréteur choisira l'opération mise en oeuvre par l'opérateur le plus prioritaire. C'est pourquoi les priorités doivent toujours être distinctes.
Le choix se fait localement afin que la lecture puisse se faire en un seul jet, sans que l'on est besoin de revenir en arrière pour envisager d'autre solution. Cela entraine une contrainte importante sur la déclaration des opérateurs possibles. Cette limitation sera allégée en introduisant un contexte permettant de changer le langage interface courant.
Le langage d'opérateurs se mémorise de la façon suivante : les opérateurs d'arité nulle sont numérotés de `0` à `n_0`. Les opérateurs d'arité `1` sont numérotés de `0` à `n_1`. etc.. Les opérateurs d'arités `k` sont numérotés de `0` à `n_k`. Les opérateurs variables sont numérotés à partir de `0`.
Ces numéros sont appelés numéro identifiant de l'opérateur pour chaque arité, et également numéro ifentifiant de la variable.
La suite `(n_0,n_1,n_2,...)` s'appel la signature du langage
Un terme sera mémorisé en interne sous forme d'un graphe. On utilise un bloc mémoire c'est à dire une suite de cases numérotés dans l'ordre où chaque numéro correspond à l'addresse de la case. On utilise des pointeurs pour désigner tout objet dans ce bloc mémoire. Chaque case contient soit un pointeur ou soit un entier. Un pointeur, pointe une case, ou bien ne point sur rien et constitue le pointeur `"nil"`.
Chaque constante est représentée par une case exclusive contenant sont numéro identifiant. Chaque variable est représentée par une case exclusive contenant son numéro identifiant. Chaque sous-terme est soit une variable ou une constante ou bien est représenté par une suite consécutive de `n`-case (`n>=1`) où la première case pointe sur une constante désigant un opérateur d'arité `n-1` et où les suivantes pointent sur des sous-termes.
Le terme ne doit pas être récurcif, ou auterment dit le terme doit former un graphe acyclique. C'est à dire que les sous-termes peuvent être partagés mais il n'est pas possible de faire un cycle complet dans le graphe du terme.
On utilise une seconde représentation utilisant la logique polonaise. Pour cela on désigne les opérateurs zéro-aire par les symboles `a,b,c,...` dans cet ordre, et on désigne les opérateurs unaires par les symboles `"|"a,"|"b,"|"c,...` dans cet ordre, et on désigne les opérateurs binaires par les symboles `"||"a,"||"b,"||"c,...` dans cet ordre, etc.. Et on désigne les variables par les symboles `A,B,C,...` dans cet ordre.
Ainsi par exemple l'expression `"|"a"|"b"|"c"||"aBc` désigne le terme `a(b(c(a(B,c)))`
Le langage interface étant définie, on le compile en un automate analyseur syntaxique.
Considérons par exemple le langage utilisteur décrit brièvement par `a, b, f(x), g(x,y), x"∗"y, x"→"y`. L'analyseur syntaxique se compile en la grammaire suivante :
Début = A
A = (A)B
A = aB
A = bB
A = f(A)B
A = g(A,A)B
B = Fin
B = ∗AB
B = →AB
Puis on perfectionne l'analyseur afin qu'il construise en parallèle de la lecture d'un terme, le graphe du terme ou la version simplifiée en logique polonaise du terme.
Ainsi nous avons trois langages; le langage utilisateur, le langage en logique polonaise, le langage en graphe, et nous devons programmer les 6 outils permettant de passer d'un langage à un autre.
---- 1 septembre 2018 ----