Implémentation des langages d'opérateurs

1) Introduction

Les intuisionnistes remettent au premier plan le principe mécanique comme base du raisonnemment. Le raisonnement est mécanique, une mécanique classique idéale ou les rouages s'imbriquent parfaitement sans le moindre jeu ni frottement. A notre époque, on peut dire cela de toute science exacte. Le raisonnement est ramené à un calcul qui en constitue sa fondation. Un calcul exacte est une démonstration.

L'implémentation des langages d'opérateurs et de l'univers de Herbrand, va mettre en oeuvre des préceptes purement mécaniques et programmatifs, que l'on pourra sous traiter à la machine en les structurant. Cette reflexion programmative va nous permettre de décentraliser les tâches et les responsabilités, et de privilégier la constructions des objects plutôt que celle des démonstrations. Une démonstration faite en dehors de la construction des objets a quelque chose de monstrueux, comme une sorte d'autopsie froide et inerte, alors que les objects sont vivants et s'auto-démontre par le seul fait de leur existence.

Nous ramenons donc les fondations de notre mathématique à l'informatique. Elles consistent en le developpement de frameworks. Et les démonstrations sont des calculs, c'est à dire des programmes dont l'execution se termine en un temps fini. Les différents paradigmes de programmation, object, aspect..., vont nous rapprocher encore de la conception physique de la machine, qui la conçoit dans sa généralité comme un système physique, un ensemble d'interactions corpusculaires, structurable dans une hierarchie d'échelle...

2) Developpement de framworks

Le développement d'un framework, comme tout programme, se heurte à une difficultée structurelle, dés qu'il atteint une certaine taille ne permettant plus au développeur de vérifier la cohérence de l'ensemble ni même des parties puisque liées entres elles, du fait d'une complexité trops grande pour être apréhendé par l'esprit humain dans son ensemble. Pour remédier à cela, on exploite l'aspect modulaire du langage de programmation, pour décomposer le frameworks en module formants un maillage flêché transitif et antisymétrique, des modules autonomes capables de vérifier leur propre cohérence et de présenter leurs pouvoirs programmatifs au travers une synopsie.

Quand le framwork est réellement au point, alors il intègre le langage de programmation pour le transformer en un langage de programmation plus évolué. Mais avant cela, il doit prouver sa pertinence. Et pour cela, il doit se faire connaitre et permettre son utilisation sous des modalités les plus diverses et les plus simples à tous les publiques, et permettre aussi son développement à tous les publiques développeurs. C'est pourquoi de tels projets sont le plus souvent sous des licences libres de droits.

Un énoncé mathématique ne produit rien ce qui peut rendre l'étude ingrate et détourner nombre de disciples, mais il n'en est pas de même de la programmation informatique, le programme produits des résultats sources de motivation, capable de surprendre et de satisfaire la curiosité, débuts d'explications bases à des hypothèses inductives, et qui constitue déjà un élément de preuve. C'est pourquoi il faut attacher une importance à ce que produisent les programmes, et qu'il faut donc pour cela toujours choisir des arguments par défauts les plus révélateurs, ceux qui vont mettre à l'epreuve tous les mécanismes de calculs du programmes et être les plus démonstratifs.

Le programme d'un module est composée d'une entête, d'un corps et d'une synopsie. L'entête comprend les instructions "include" nécessaire pour le raccorder aux modules en amont dont il a besoin ainsi que les déclaration des types et fonctions programmées par le module. Le corps constitue le programme proprement dit. Et la synopsie sert d'auto-vérification et d'exemples, présentant le pouvoir de programmation qu'apporte le module. Pour chaquie module, la synopsie commentée fait office de documentation.

3) Langage et opérateurs

Les niveaux contextuels en terme de langages d'opérateurs, permettant de masquer un opérateur par un autre de même nom, ne sont pas nécessaire pour commencer notre étude. Mais il le deviendront, car tout langage digne de se nom utilise un contexte évolutif permetant d'écrire l'essentiel sans être noyé dans les détailles qui sont remis au domaine de l'implicite resultant justement de ce contexte.

Si on conçoit plusieurs langages d'opérateurs, alors le langage que nous utilisons au premier abord est le langage union de ces langages. Il existe donc un langage mère qui comprend les autres langages, et tout opérateur est un opérateur de ce langage mère. On peut définir un opérateur sans préciser à quel langage il appartient, puisqu'il appartiendra au langage mère. Et il n'y a qu'un langage mère qui joue ce rôle. Le langage mère est donc un langage particulier, élément de la classe des langages d'opérateurs, qui s'agrandie à chaque création d'opérateur.

On conçoit l'opérateur comme un object à part entière. Pour l'instant il ne possède que deux attributs, son nom et son arité. Lorsque l'on crée un opérateur, il est automatiquement ajouté au langage mère.

L'implémentation devient le coeur de notre recherche. L'affichage d'un objet constitue un type particulier d'implémentation de l'objet sous forme de String. Et il y a évidement plusieurs implémentations String possibles, plusieurs traductions possibles, une dans chaque langue possible. L'affichage est un programme de conversion en String avec comme arguments l'objet x sujet de la traduction, et la langue n de traduction. Cela permet de définire plusieur modes d'affichages, plusieur modes d'implémentations String. On réprésente le programme sous forme d'un opérateur binaire to_s(.,.) que l'on munie d'une syntaxe centré. Ainsi L'expression  (x to_s 0), (x to_s 1), (x to_s 2)..., exprime une liste de différentes traductions de l'objet x. Puis on considère l'opérateur unaire de même nom to_s(.) qui utilise la langue de traduction par défaut, et qui doit être la langue la plus démonstrative et la plus pratique..

Le premier module "Langages_et_operateurs" définie : les opérateurs, les langages d'opérateurs, le langage mère union de tous les langages créés, et définie un opérateur unaire point "." appelé Meta et qui joura un rôle particulier.

Langages_et_operateurs
a = newOp("a",0)   // Création de l'opérateurs a
b = newOp("b",0)   // Création de l'opérateurs b
f = newOp("f",1)     // Création de l'opérateurs f(.)
g = newOp("g",2)   // Création de l'opérateurs g(.,.)
h = newOp("h",2)   // Création de l'opérateurs h(.,.)

L = newLang   // Création du langage L vide
L << a             // Ajout de l'opérateur a dans le langage L
L << f              // Ajout de l'opérateur f(.) dans le langage L
L << g             // Ajout de l'opérateur g(.) dans le langage L

H = newLang([a,b,f,g,h])     // Création du langage H = {a,b,f(.),g(.,.),h(.,.)}

nom g      // Retourne "g"
air g        // Retourne 2

to_s g      // Affiche "g"
g to_s 0    // Affiche "g"
g to_s 1   // Affiche "g(.,.)"
L to_s 1   // Affiche "{a, f(.), g(., .)}"
L2 to_s 1  // Affiche "{a, b, f(.), g(.,.), h(.,.)}"
to_s Mere // Affiche "{a,b,f,g,h}"

clearLang L     // Vide le langage L
clearLang L2     // Vide le langage L2
clearLang Mere     // Vide le langage Mere

Meta = newOp(".",1)   // Création de l'opérateurs .(.)

4) Séquence et composition

Un opérateur agit dynamiquement. C'est une application qui prend plusieurs arguments selon son arité, efffectue un calcul qui se termine en un temps fini, pour produire un terme résultat. Et en l'absence de précision sur cette dynamique, sur ce calcul, il adopte une dynamique par défaut qui est la construction de termes par emboitements d'opérateurs. Par exemple l'opérateur binaire g est définie par défaut comme l'application g : (x,y)-->g(x,y) qui, appliqué à deux arguments x et y, produit le terme g(x,y) sans même avoir évalué x et y.

Les termes de l'univers de Herbrand sont les compositions closes d'opérateurs. Il y deux implémentations intéressantes de l'univers de Herbrand que sont l'implémentation séquencielle et l'implémentation en arbre. Prenons par exemple le langage suivant :

L = {a, b, f(.), g(.,.)}

Le terme g(f(a),g(a,b)) se présente sous forme d'une séquence notée [g,f,a,g,a,b] et sous forme d'un arbre notée [g,[f,a],[g,a,b]]. La représentation séquentielle est importante à cause de sa simplicité et à cause de la logique polonaise. Mais elle ne peut pas se dispenser de la définition préalable de l'arité des opérateurs. La représentation en arbre permet de représenter facilement des structures partagées, des graphes orienté, et permet facilement de programmer l'unification avec une complexité linéaire. Elle se dispenser de la définition préalable de l'arité des opérateurs. Elle peut s'appliquer avec un simple alphabet en considérant tous les opérateurs d'arités variables.

On veut implémenter les termes de l'univers de Herbrand, les structurer, en faire les objects informatique. Mais il existe une classe d'objets plus générale qui est celles des séquences d'opérateurs, ce sont des séquences quelconques d'opérateurs appartenants au langage. Et on les perçoit sous un autre regard, comme des succesions de compositions d'opérateurs sur les premières entrés disponibles, obéissant ainsi à la logique polonaise, et lorsque il y a davantages de termes que d'entrées, elles sont concaténées en séquence et constituent alors des séquences de termes, où le dernier terme peut être incomplet. Cette nouvelle perception ne modifie pas physiquement l'object, mais met déjà en oeuvre la composition harmonique. Les séquences de termes où le dernier terme peut être inachevé, constitue une application unaire, appelé ver1, agissant dans ce nouvel univers. Par exemple le ver1 [ag] qui correspond à la séquence du mot a et du mot inachevé g(.,.) peut se composer avec un autre ver1 [faaf] = f(a), a, f(.) par simple concatenation pour donner [agfaaf] = a, g(f(a),a) ,f(.) et on remarquera que la concaténation va placer les mots du deuxièmes ver1 dans les places libre du premier ver1 selon la logique polonaise, et les termes supplémentaires seront inchangés et simplement concaténés en une séquence. L'application des ver1 dans l'univers des ver1 coïncide avec la composition des ver1. On vérifit l'associativité.

Dans Langage et calcul, nous avons décrit deux modes de composition d'opérateurs. Dans le mode non harmonique, l'opérateur d'arité n est une application qui prend n termes comme arguments, les arguments supplémentaires sont perdus, occasionnant une perte d'information. Dans le mode harmonique, l'opérateur est une application qui agit sur l'ensemble des séquences de termes de taille quelconque. Appliqué à une séquence de termes, il retourne une séquence de terme, en retournant à l'identique les termes supplémentaires, n'occasionant aucune perte d'information. C'est ce dernier mode qui est mis en oeuvre lorsqu'on s'intéresse aux séquences.

On a ainsi définie un premier type d'application appelé ver1. Bien que unaire puisque s'appliquant à une séquence, on redéfinie son attribut "arité", appelé rayon, comme égale au nombre de places libres qu'il possède à sa fin. Ainsi le ver1 [ggg] = g(g(g(.,.).).) possède une arité ou un rayon égale à 4.

On généralise le ver1 en utilisant le méta-opérateur "."  tel que dans l'exemple du mot g(.,g(a,.)) qui correspond à l'application (x,y) --> g(x,g(a,y)) et on appel cela un ver2. La liste des places vides n'est pas forcement à la fin comme pour les ver1, mais reste toute fois lue de gauche à droite. Ce sont des séquences quelconques d'opérateurs avec le meta-opérateur zero-air "." qui joue le rôle des trous (places libres).  Par exemple :

[g.ga.] = g(.,g(a,.))

Les ver2 sont aussi vue comme des applications unaire s'appliquant à une séquence quelconque et retournant une séquence, dans le mode harmonique. Exemple :

[f.f.]°[ga.b] = [fga.fb]
(f(.),f(.))°(g(a,.), b) = (f(g(a,.),f(b))

L'application des ver2 dans l'univers des ver2 coïncide avec la composition des ver2. On vérifit l'associativité.

Dans une formule, un calcul intermédiaire peut être utilisé plusieurs fois s'en avoir à le recalculer. Par exemple la transformation x --> g(f(x),f(x)) ne nécessite pas d'évaluer f(x)deux fois. Ce mécanisme de duplication s'implémente simplement en partageant la structure de donnée f(x), faisant que g(.,.) va chercher ses 2 arguments au même endroit. le partage de termes peut s'implémenter dans une séquences d'opérateurs en ajoutant un méta-opérateur entier n qui effectue un jump de n cases en arrière pour récupérer le mot s'y trouvant.  Par exemple l'application x --> g(f(x),g(f(x),a)) se note [gfxg3a]. On définie ainsi les ver2 avec partage appelé ver2p.

 

--- 31 Août 2014 ----

Pour permettre les modifications physiques sur les séquences avec une complexité linéaire, il faut concevoir la séquence comme une chaine de mailles liées dans les deux sens. Puis il faut ajouter à la structure de ver2p, la liste des références des entrées pour ne pas avoir à les rechercher à chaque opération de composition. C'est une liste de pointeurs, ou chaque pointeur désigne dans le ver2p, une maille distincte correspondant à une entré. La structure de ver2p ressemble alors par exemple à (x,y,z)-->[gxgyfz] où x,y,z joue ce rôle de pointeur, et sont appelées variables muettes. Une dernière généralisation permet le changement de l'ordre des références des entrés, et comme les projections sont déja misent en oeuvre du fait du partage, on pourra construire par exemple le ver3 avec partage (y,x)-->[gxgy3] qui est identique à (x,y)-->g(y,g(x,y)) et que l'on appellera ver3p. Les variables x, y tissent des liens entre pointeurs et mailles lors de la construction du ver3p, puis disparaissent en laissant ces liens, c'est pourquoi on les appels variables muettes, et l'information supplémentaire qu'elles apportent consiste uniquement en une permutation des variables.

5) Arbre et composition

La représentation sous forme d'arbre est plus proche de l'écriture avec niveau de parenthèse. De même que pour les séquences, elle devra être enrichie de la liste des références sur les entrés, pour ne pas devoir les rechercher à chaque composition et perdre, par la même occasion, la complexité linéaire qu'apporte cette structure à l'opération d'unification. On remarque que la notation constructive de l'application (x,y) --> g(x,f(y)) procède de même, en plaçant en premier une liste de référence de ses entrés (x,y). Les variables muettes x et y établissent les liens entre pointeurs et cases, et leur liste procéde ainsi à une permuttation, et les noms des variables disparaissent. La représentation de l'arbre partagé avec liste d'entré comprend deux séquences [ [.],[.] ]-->[ g,[.],[f,[.]] ] dans les quelles les cases [.] sont pour certaines d'entres-elles partagées, et sont positionnée selon la place des variables x et y dans la première liste, c'est à dire exactement selon une permutation. Les cases [.] ne sont pas les seuls à pouvoir être partagées, les sous-termes peuvent aussi être partagés, et la structure d'arbre fait qu'il n'y a pas besoin de créer de niveau d'emboitement supplémentaire pour ce partage, puisqu'il existe déjà. Cependant après des affectations de variables muettes à des sous-termes, des niveaux  d'emboitement supplémentaires apparaissent, et ils peuvent être multiples comme une cascade de pointeurs finissant sur l'object désigné, un sous-terme, une séquence commençant par un opérateur. Il se peut également que la cascade de pointeurs se mordent la queue et, tournant en rond, ne s'arrète jamais. Un des aspects qui explique la complexité linéaire de l'unification consiste en la création de racourcis court-circuitant ces niveaux d'emboitements superflux lors des passages.

Notre recherche d'implémentation aboutie à cette object qu'est l'arbre partagé avec liste d'entrés. La constitution de la liste des entrés de gauche à droite ce fait en parcourant l'arbre et en répertoriant chaque nouvelle entré. Il faut donc pour chaque variable rencontrée vérifier qu'elle n'est pas déjà répertoriée. Si le nombre de variables est limité alors cette tâche reste de complexité linéaire, et il n'est pas opportun de concevoir un object spécifique pour les arbres partagés avec liste d'entrés canonique différent de celui des arbres patagés tout-courts. Plus exactement on les conçoit comme des objects à plusieur états, pouvant être enrichie d'une information supplémentaire que constitue la permutation des variables.

Une séquence partagée ou un arbre partagé représente mathématiquement un ver partagé (ver1p, ver2p, ver3p), aussi nous l'appellerons ver partagé en laissant le soin au contexte de déterminer si c'est un arbre ou une séquence d'opérateurs. Et nous programmerons une méthode pour constituer la liste des entrés de gauche à droite si celle-ci n'est pas déja construite et mémorisée, et un attribut supplémentaire pour mémorisé l'éventuelle permutation.

Cet object possède une dynamique, une physique particulière, des propriétés physiques.... Nous recherchons alors les transformations fondamentales que l'on peut opérer sur cet object appelé ver partagé, les intéractions entre ver partagés, et comment appréhender un systèmes de ver partagés en intéraction, pour pouvoir piloter les différentes constructions possibles grace à un langage qui s'apparentera, de faite, à un langage de programmation. Voilà comment Mathématiques, Physique et Informatique sont intimement liées.

Considérons le ver3p A : (x,y)-->g(y,f(x)) où x, y sont des variables muettes représentés par des cases partagées [.] contenant le symbôle "." qui signifie que la variable est libre. Le ver3p comprend deux parties qui se chevauchent par partage, que sont sa tête (x,y) et son corps g(y,f(x)). On peut affecter la première entré x à un autre ver3p B: (u,v)-->g(v,u) et obtenir après composition le ver3p (u,v,y)-->g(y,f(g(v,u))) où x représente une case mémoire unique partagée contenant à cet instant g(v,u). Les deux ver3p sont entrés en intéraction. Le ver3p A s'est modifé physiquement en A : (u,v,y)-->g(y,f(g(v,u))) et ne possède plus de référence sur x. Le ver3p B a un coprs qui fait partie du corps de A et il possède toujours sa tête (u,v), pourtant son statut a changé, il est inclus dans A. Ce qui signifie que toute modification du corps de B modifira le corps de A. Par contre si on modifie la tête de B sans altérer le contenue de ses variables muettes, cela n'a pas d'effet sur A.

Si maintenant B entre à son tour en intéraction. Si sa variable u est affectée au ver3p C : t-->g(t,t) alors B se modifie en (t,v,y)-->g(v,g(t,t)) et A se modifie en (u,v,y)-->g(y,f(g(v,g(t,t)))) avec u=f(t,z) et A n'a pas actualisé sa tête, une de ses variables muettes est maintenant liée et contient f(t,t). A désigne maintenant un object plus générale qui se note (f(t,t),v,y)-->g(y,f(g(v,g(t,t)))), et qui est un couple de termes avec partage.

6) Application, fonction & ensemble de définition

La construction d'application ver3p se fait couramment avec des variables muettes x,y... telle que l'application :

(x,y)-->g(y,g(a,x))

Dans cette construction on utilise une séquence de méta-opérateurs distincts x et y qui représentent des variables universelles capables de prendre comme valeur tous les mots du langages. On les appelles variables muettes de l'application. En logique intuitionniste il n'y a pas de différence entre constante et variable. Les méta-opérateurs x et y sont identifiés à des opérateurs d'arité zéro du langage. Autrement dit on utilise des opérateurs d'arité zéro du langage comme variables muettes de l'application, que l'on quantifie universellement ∀x, ∀y. Cela pose des limites à la construction. Par exemple si le langage n'a qu'un seul opérateur zéro-aire, on ne peut construire par ce procédé que des applications unaires. Une autre approche intuitionniste consiste à considérer les variables x,y,z comme différentes des opérateurs constant du langage, et que l'on rajoute au langage, effectuant ainsi une extenssion L+{x,y,z} et opérant une distinction entre opérateurs constants et variables. On peut ainsi s'affranchire des quantificateurs en quantifiant une fois pour toutes les opérateurs variables. On pose le langage avec trois opérateurs zéro-aire variables supplémentaires :

L = {a, b, f(.), g(.,.), Variable x, Variable y, Variable  z}

L'application (x,y)-->g(y,g(a,x)) peut devenir un nouvel opérateur à condition qu'on la nomme. Le méta-opérateur --> n'est pas intégré au langage, c'est pourquoi l'opération de nommage et d'ajout d'une application au langage est décisive. Elle change le pouvoir d'expression du langage.

Une fois nommée, la définission de l'opérateur est équivalente à sa règle d'égalité. Par exemple :

φ : ∀x ∀y  (x,y)-->g(y,g(a,x))
∀x ∀y   φ(x,y)=g(y,g(a,x))

La fonction inverse φ-1 correspond à l'unification, et est notée ∀x ∀y  g(y,g(a,x))-->(x,y). On réintroduit le concepte de séquence, où tous est séquence d'un seul niveau, et on généralise la construction en faisant opérer le méta-opérateur "-->" sur deux mots ou deux séquences d'opérateurs quelconques du langages appelés tête et corps. On obtient une fonction, possèdant un domaine de définition égal à l'ensemble des séquences d'opérateurs du langage unifiable à sa tête. Et nous concidérons trois modes possibles : le mode exacte, le mode tronqué non harmonique, et le mode harmonique. Prenons par exemple l'application ψ définie par 

ψ : ( x, g(x,a) )-->( f(x), f(x) )

Dans le mode exacte ψ ne prend que des séquences de deux mots unifiables à sa tête tel que par exemples (a,g(a,a)), (b,g(b,a)) , (f(a),g(f(a),a)).... Dans le mode tronqué ψ prend toutes les séquences dont les deux premiers mots sont unifiables à sa tête, et ne retourne qu'une séquence de deux mots. Dans le mode harmonique ψ prend toutes les séquences dont les deux premiers mots sont unifiables à sa tête et retourne la séquence modifiée en son début, et les arguments supplémentaires non utilisés sont inchangés et mis à la suite dans la même séquence.

Si on convient que la fonction retourne le symbôle FAIL lorsque l'unification échoue, alors on obtient une application, appelée fonction. Le meta-symbôle FAIL, par défaut, obéit au propriété suivante : Tout opérateur qui possède FAIL parmis un de ses arguments retourne immédiatement FAIL. Parcontre une séquence contenant un FAIL n'est pas remplacée par FAIL, la séquence ne s'évalue pas, seul l'opérateur s'évalue. Dans le langage, la séquence jour un rôle spécifique, une sorte d'echo des algorithmes dont elle est l'object, une pile.

On peut s'affranchir du nom des variables muettes, toujours en limitant leur nombres comme le demande la logique intuitionniste, en utilisant la liste des variables qui apparaissent dans l'ordre de leur première apparition, lorsque l'on parcours la séquence d'opérateurs de gauche à droite, c'est à dire en profondeur d'abord, et en les numérotant à partir de 1. On obtient ainsi une notation avec numéros, où la première occurence de chaque entier apparaissant dans la séquence de mots, doit s'inscrire dans l'ordre des entiers sans saut. Ces applications sans permutation correspondent aux ver2p, sauf que les sous-termes ne sont pas partagés, seul les variables muettes peuvent être partagées. Exemples :

1                  =     x --> x
g(1,1)           =     x --> g(x,x)
g(1,2)           =     (x,y) --> g(x,y)
g(1,g(2,1))    =     (x,y) --> g(x,g(y,x))

(1,1)             =     x --> (x,x)
(1,2)             =     (x,y) --> (x,y)

Les ver3p s'obtiennent à partir des ver2p, en ajoutant une permutation sur la liste des variables, tel que par exemple :

g(1,g(2,3)) ° µ
µ : (x,y,z)-->(z,x,y)

ici encore les sous-termes ne sont pas partagés, seul les variables muettes peuvent être partagées.

Pour une application à n variables, il y a n! permutations possibles. Dans une certaine mesure les ver2p peuvent être ajoutées au langage, comme peuvent l'être les mots inachevées décrits au chapitre 4. Les ver2p utilisent une numérotation bornée par le nombre de variables muettes autorisées, et si un nombre n est présent alors les nombres 1 à n doivent être présents et correspondent à n variables libres.

Un ensemble de mots est définis comme l'ensemble image d'un ver2p. Le ver3p n'apporte pas plus, la permutation des entrés de l'application ne modifiant pas l'ensemble image de l'application. On peut donc intégre au langage ces ensembles image comme le sont les applications ver2p dans la limite du nombre de variables autorisées. Par exemple l'application x-->g(x,x), notée par g(1,1), peut désigner l'ensemble des mots : g(a,a), g(b,b), g(f(a),f(a)), g(g(b,a),g(b,a)).... Et cet ensemble est constructif car il existe un procédé qui énumère tous ses mots, qu'est l'énumérateur du langage passé à travers l'application x-->g(x,x).

(x-->g(x,x)) ° ζ

où ζ est l'énumérateur du langage L={a, b, f(.), g(.,.)}.

La complexité du calcul dépend évidement du partage. Mais de plus, si nous ne partageons pas les structures, les ver2 sont moins expressifs, en particulier la fonction x--> g(x,x) n'est pas un ver2, c'est un ver2p, le ver2 sans partage ne permet de construire que l'application (x,y)-->g(x,y), et il faut une permutation-projection callée sur les premières variables telle que x-->(x,x) ¤ (x,y)-->g(x,y). La composition est désignée par ¤ en notation française, et par ° en notation anglaise :  f¤h = h°f

Les variables d'entrés d'un ver2 sont numérotées de 1 à n et sont toutes significatives. Un ver2 est injectif dans la structure libre du langage. Dans le mode de composition harmonique, les arguments supplémentaires sont simplement concaténés à la suite dans la séquence. Une permutation-projection callée est une application qui prend les k premières variables pour les placer à une ou plusieurs endroits sur une séquence de taille n sans en omettre aucune. Deux représentations sont possibles. Une permutation-projection callée est représentée par une séquence de numéros de 1 à k, sans en ommettre aucun, et pouvant les répéter à différents endroits, et les placés dans n'importe quel ordre. Elle est aussi représentée de façon harmonique en s'interdisant de placer k uniquement à la seul dernière place, cela pour assurer l'unicité de la représentation harmonique. On défini ainsi le rayon de sortie égale à la taille de cette séquence. Par exemple la permutation-projection (x,y)-->(x,x,y) noté (1,1,2) est identique à x-->(x,x) noté (1,1) car dans la composition harmonique la deuxième variable supplémentaire "y" sera de toute façon concaténée à la fin, et a finalament qu'un rayon de sortie égal à 2. Par contre la représentation harmonique de (x,y)-->(x,y,y)  est bien (1,2,2) et a bien un rayon de sortie égale à 3.

Les ver3 sont obtenue ainsi en composant exactement une permutation-projection callée de rayon de sortie inferieur ou égale au rayon d'entré d'un ver2.

7) Atome

On pose un langage d'opérateurs sans variable L = {a,b,f(.),g(,.,.)}. La séquence d'un seul niveau joueant un rôle important dans les algorithmes d'énumération, on définie l'atome comme une séquence de termes, où un terme est un arbre partagé d'opérateurs du langage L et du méta-opérateur "." qui constitue une case mémoire libre [.] et qui peut également être partagé.  

Un atome à une composante tel que ( g(x,f(x)) ), peut repésenter l'ensemble des mots qui lui sont unifiables, et qui constitue l'ensemble image de la fonction x-->g(x,f(x)). Mais c'est aussi l'ensemble de toutes les séquences qui commencent par un mot unifiable à g(x,f(x)) où x est une variable libre. Et c'est aussi l'ensemble image de la fonction x-->g(x,f(x)) perçu comme s'appliquant aux séquences de mots de façon harmonique, et finalement aux atomes eux-mêmes.

Un atome à deux composantes tel que ( g(x,x), f(x) ) peut représenter la fonction g(x,x)-->f(x), ou représenter la fonction f(x)-->g(x,x), ou bien encore reprrésenter l'ensemble des couples de mots qui lui sont unifiables et qui constitue l'ensemble image de la fonction  x-->( g(x,x), f(x) ), etc...

La construction va s'opérer dans un langage au dessus des atomes, leur donnant un rôle plus précis. Une des opérations les plus importantes est sans conteste l'unification, qui est l'inverse d'une application (l'inverse d'un ver3p). L'unification de n atomes va produire l'atome intersection qui désignera l'ensemble intersection des n ensembles désignés par les n atomes.

8) L'unification

L'algorithme d'unification de plusieurs atomes est de complexité linéaire grace à la structure partagée des atomes qui est entretenue au cours de l'algorithme par un aspect consistant à simplifier les successions de pointeurs par un pointeur raccourcis, lors des passages.

Unification2
Synoptie Corps
a=Op.new("a",0)   # Création des opérateurs
b=Op.new("b",0)
f=Op.new("f",1)
g=Op.new("g",2)
h=Op.new("h",2)

x=[:_]   # Création des variables et des mots
y=[:_]
z=[:_]
m1=[ [f,x],     [g,x,[g,a,y]] ]
m2=[ [f,[f,b]], [g,y,[g,a,z]] ]

t=[

unifit2(m1,m2),    # Unification de m1 et m2
x==[[f, b]],
y==x,
z==x,
m1 == [[f, [f, b]], [g, [f, b], [g, a, [f, b]]]],
m1==m2

]
print("Unification2 : ".rjust(30),
  (not t.include?(false)),"\n")
Mere.L.clear
require "./Lang"
        
def unifit2(a,b)
  t=[a.size, b.size].min()
  return true if t==0
  for i in 0..(t-1)
    as=a[i]
    bs=b[i]
    while as.class!=Op and as[0]!=:_ and as.size==1; as=a[i]=as[0] end 
    while bs.class!=Op and bs[0]!=:_ and bs.size==1; bs=b[i]=bs[0] end 
    next if as==[] or bs==[]
    if as.class==Op then 
      if bs.class==Op then return false if as!=bs
      elsif bs[0]==:_ then b[i]=as
      else return false; end
      elsif as[0]==:_ then a[i]=bs
      else 
        if bs.class==Op then return false
        elsif bs[0]==:_ then b[i]=as
        else return false if not unifit2(as,bs) 
        end
      end
    end
    true
  end 

On remarque que l'arité des opérateurs n'intervient pas dans la constitution des atomes. Un atome est une séquence de termes. Un terme est soit un opérateurs, ou une variables [.], ou une séquence d'opérateurs et de variables [.] de taille au moins égale à 2 car sinon elle est considéré comme un pointeur de pointeur et le niveau d'emboitement est racourci lors d'un passage. Cela induit un nouveau langage qu'est le langage de caractère avec niveau de parenthèse où les sous-séquences ont une taille au moins égale à 2. On l'identifie au langage d'opérateurs avec un seul opérateur d'arité variable supérieur ou égale à 2 noté (A+{S(.,.,...)})° , où A={a,b,f,g} est l'alphabet et où l'opérateur S(.,.,...) est le seul opérateur d'arité supérieur à zéro. Tous les autres opérateurs sont d'arité nulle. S est d'arité variable supérieur ou égale à 2, et est appelé le séquenceur. Par exemple le mot (a,b,(f,a),g) est traduit dans le langage (A+{S(.,.,...)})° par le mot S(a,b,S(f,a),g).

La cohérence du système de calcule exige que l'évaluation ne dépende pas de l'ordre dans lequel il se fait. Par exemple dans l'expression S(a, b, S(f, a), g), quelque soit l'ordre dans lequel on effectue l'évaluation des opérateurs S, le résultat doit être le même. L'aspect dynamique du langage tient dans la seul définition applicative de l'opérateur S(.,.,...) d'arité variable supérieur ou égale à 2.

Pour revenir à notre langage d'opérateurs, on définie S comme retournant son premier argument si celui-ci est d'arité nulle, et cela correspond à la mise en oeuvre du raccourcie de pointeurs, puis comme retournant son premier argument appliqué à son second argument si il est d'arité un, puis retournant son premier argument appliqué à son second argument et à son troisième argument si il est d'arité deux, et ainsi de suite..... Nous avons par exemples avec le langage L={a,b,f(.),g(.,.)} :

S(a) = a      Correspond au raccourcie.
S(a,b) = a      Tronque les arguments supplémentaires.
S(f)                   Non autorisé.
S(f,a) = f(a)        Sous terme.
S(f,a,b) = f(a)       Tronque les arguments supplémentaires.
S(g,a)                      Non autorisé.
S(g,a,b) = g(a,b)        Sous terme.
S(g,a,b,a) = g(a,b)      Tronque les arguments supplémentaires.

9) Les énumérateurs de ver1

Les énumérateurs sont des objects qui énumèrent des séquences (ou des mots) à partir d'une séquence initiale (ou d'un mot initial). Ils définissent constructivement des ensembles pouvant être infini mais énumérable par définition.

Le plus simple d'entre eux est l'énumérateur de séquences d'opérateurs. Il énumère les ver1 selon la taille et l'ordre lexicographique induit par un ordre des opérateurs qu'il faut choisir au départ. Puis vient l'énumérateur des ver2 en ajoutant le méta-opérateur ".". Puis celui des ver3 en énumérant toutes les permutations-projections callée. Puis vient l'énumérateurs des séquences de mots, puis l'énumérateurs des mots...

L'énumérateur contient une liste d'opérateurs dans un ordre choisi L, et une séquence initiale m0 transcrite en liste de numéros indices dans L. La séquence en cours transcrite en liste de numéros est notée m. Et H désigne le hash permettant de retrouver rapidement l'indice d'un opérateur dans L. On définie plusieurs méthodes standarts, la méthode rewind qui initialise l'énumérateur en son début, la méthode next qui cacule le mot suivant et le mémorise dans m sous sa forme de liste d'indices. La méthode peek qui cacule le mot suivant sans le mémoriser faisant que le mot courant est inchangé. La méthode get qui retourne le mot courant, et la méthode set qui fixe le mot courant à une valeur passée en argument.

Exemple L = {a,b,c}

Séq.
Décomposition
Code


0
a
1*3⁰ 1
b
2*3⁰ 2
f
3*3⁰ 3
aa
1*3¹+1*3⁰
4
ab
1*3¹+2*3⁰ 5
af
1*3¹+3*3⁰ 6
ba
2*3¹+1*3⁰ 7
bb
2*3¹+2*3⁰ 8
bf
2*3¹+3*3⁰ 9
fa
3*3¹+1*3⁰ 10
fb
3*3¹+2*3⁰ 11
ff
3*3¹+3*3⁰ 12
aaa
1*3²+1*3¹+1*3⁰ 13
aab
1*3²+1*3¹+2*3⁰ 14
aaf
1*3²+1*3¹+3*3⁰ 15
aba
1*3²+2*3¹+1*3⁰ 16

On remarque que l'énumération des ver1 peut se coder facilement. On ajoute donc deux autres méthodes, la méthode code qui retourne l'entier correspondant au mot en cours ou au mot passé en argument, et la méthode decode qui appliqué à un entier retourne le mot correspondant.

Enumerateur_des_ver1
Synoptie
Corps
a=Op.new("a",0)
b=Op.new("b",0)
f=Op.new("f",1)
eE = Ver1.new([a,b,f])

s=[ ];
for i in 1..119; s << eE.next end
eE.rewind

t=[

eE.next == [a],
eE.next == [b],
eE.next == [f],
eE.next == [a,a],
eE.next == [a,b],
eE.next == [a,f],
eE.next == [b,a],
eE.next == [b,b],
eE.next == [b,f],
eE.next == [f,a],
eE.next == [f,b],
eE.next == [f,f],
eE.next == [a,a,a],
eE.next == [a,a,b],
eE.next == [a,a,f],
eE.next == [a,b,a],
eE.get == [a,b,a],
eE.code() == 16,
eE.code([f,f,f,b])==119,
eE.decode(119)==[f,f,f,b],
s[-1]==[f,f,f,b],
s.size == s.uniq.size,
Proc.new{
  eE.set([f,f,f,b])
  eE.next
  eE.code==120
}.call

]
print("Ver : ",  (not t.include?(false)),"\n")
Mere.L.clear
require "./Lang.rb"
       
class Ver1
  attr :L
  attr :n
  attr :m,true
  attr :m0
  def initialize(l,m0=[])           # l = [a,f,g],  m0 =[f,a]
    @L = l
    @H = Hash[l.to_enum.with_index.to_a]  # @H = { a=>0, f=>1, g=>2}
    @Ln = l.size                    # @Ln = Nombre d'opérateurs
    @F = l.size-1                   # @F = la dernière valeur d'indice 
    @m0 = m0.collect{|x| @H[x]}     # @m0 = [1,0]
    rewind
  end
  def rewind() @m=@m0; @n=m0.size; self; end
  def next()
    if @m.empty? then @m=[0]; @n=1; return [@L[0]] end
    i=1
    while @m[-i]==@F and i<=@n; @m[-i]=0; i+=1 end
    if i>@n then @m.unshift(0); @n+=1
    else @m[-i]+=1
    end
    @m.collect{|x| @L[x]}
  end
  def peek()
    km=@m
    kn=@n
    if km.empty? then km=[0]; kn=1; return [@L[0]] end
    i=1
    while km[-i]==@F and i<=kn; km[-i]=0; i+=1 end
    if i>kn then km.unshift(0); kn+=1
    else km[-i]+=1
    end
    km.collect{|x| @L[x]}
  end
  def code(m=nil)
    if m==nil then mm=@m else mm=m.collect{|x| @H[x]} end
    if mm.empty? then return 0 end
    t=mm.size
    s=0
    mm.each_with_index{|x,i| s+= (x+1)*@Ln**(t-i-1)}
    s
  end
  def decode(i)
    mm=[]
    while i>0;
      mm << @L[(i-1)%@Ln]
      i=(i-1)/@Ln
    end
    mm.reverse
  end
  def set(m) @m = m.collect{|x| @H[x]} end
  def get() @m.collect{|x| @L[x]} end
end

Les énumérateurs constituent une facette primordiale des langages qui est leur aspect dynamique. Recherchons un langage de programmation, simulant une machine ou d'une façon plus générale un système physique, un ensemble de corpuscules intéragissant entre eux. La vision corpusculaire de la physique correspond à la vision object de l'informatique. Recherchons un tel langage avec lequel la programmation de cet énumérateur serait particulièrement simple. Et essayons que ce langage de programmation soit un langage d'opérateurs.

On concoit un object compteur comprenant une séquence d'entier non vide et un curseur caractérisé par son indice commençant à 0 et désignant un élément de la séquence. Et on lui ajoute les méthodes de base suivantes :

Compteur#rewind Initialise la séquence en une séquence d'une case contenant 0, et initialise le curseur à l'indice zéro pointant sur cette case.
Compteur#croit Ajoute une case initialisée à 1, à la fin de la séquence. Cette case est d'indice égale à la nouvelle taille de la séquence moins 1.
Compteur#inc Incrémente modulo N, la valeur sous le curseur, et retourne cette valeur
Compteur#dep Déplace le curseur en incrémentant son indice modulo la taille de la séquence, et retourne son indice.

On complète ce compteur, pour le transformer en un énumérateur, en lui ajoutant la méthode Compteur#next qui incrémente la valeur du compteur et qui se programme ainsi :

class Compteur
  def next 
    while inc==0
      if dep==0 then croit end
    end
    self
  end
end

Pour réécrire ce programme itératif à l'aide d'un pure langage d'opérateurs, il nous faut d'abord implémenter un mécanisme récurcif dans le langage d'opérateur. Nous reprenons les travaux du chapitre Langage récurcif.

10) Le calcul récursif

La récurrence est la répétition d'un calcul réutilisant des résultats intermédiaires, jusqu'à ce qu'une condition soit satifaite, la condition étant une données résultant de calcul intermédiaire. Cela correspond à l'utilisation dans un langage de programmation basique aux boucles while. En s'inspirant des travaux de Herbrand, on peut représenter le détail du calcul récursif par un arbre de taille variable ou infini, et on peut factoriser cet arbre en une représentation finie avec des méta-opérateurs, appelé itérateurs, et permettant de programmer des calculs récurcifs. Cela définie un langage de programmation qui est à la fois un langage d'opérateur.


D. Mabboux-Stomberg

























L'énumération des ver2 se fait en ajoutant le meta-opérateur zéro-aire ".". Soit le langage L= {a,g(.,.),.}. Les séquences [.,g], [.,g,.] et [.,g,.,.] désigne le même ver2, mais pas la séquence [.,g,.,.,.] sauf si on choisi comme mode de composition le mode harmonique. Dans le mode harmonique l'ajout de point à la fin d'un ver ne le change jamais. Lorsque l'on calcul le mots suivant si celui-ci à un point à la fin alors on le saute en calculant le mot suivant.

Exemple L = {a,g,.}

Séq.
Décomposition
Code


0
a
1
1
g
2
2
aa
1*(2) + 1
3
ag
1*(2) + 2
4
ga
2*(2) + 1
5
gg
2*(2) + 2
6
.a
3*(2) + 1
7
.g
3*(2) + 2
8
aaa
1*(3*2) + 1*(2) + 1
9
aab
1*(3*2) + 1*(2) + 2 10
aba
1*(3*2) + 2*(2) + 1 11
abb
1*(3*2) + 2*(2) + 2 12
a.a
1*(3*2) + 3*(2) + 1 13
a.b
1*(3*2) + 3*(2) + 2 14
baa
2*(3*2) + 1*(2) + 1 15
bab
2*(3*2) + 1*(2) + 2 16
bba
2*(3*2) + 2*(2) + 1 17



..a
3*(3*2) + 3*(2) + 1 25
..b
3*(3*2) + 3*(2) + 2 26
aaaa
1*(3*3*2) + 1*(3*2) + 1*(2) + 1 27

L'énumération des ver2 peut se coder facilement. 

Enumerateur_des_ver2
Synoptie
Corps
a=Op.new("a",0)
b=Op.new("b",0)
f=Op.new("f",1)

eE = Ver2.new([Meta,a,b,f])

s=[ ];
for i in 1..85; s<< eE.next end
eE.rewind

t=[

eE.next == [a],
eE.next == [b],
eE.next == [f],
eE.next == [Meta,a],
eE.next == [Meta,b],
eE.next == [Meta,f],
eE.next == [a,a],
eE.next == [a,b],
eE.next == [a,f],
eE.next == [b,a],
eE.next == [b,b],
eE.next == [b,f],
eE.get == [b,f],
eE.next == [f,a],
eE.next == [f,b],
eE.next == [f,f],
eE.peek == [Meta,Meta,a],
eE.next == [Meta,Meta,a],
eE.code() == 16,
eE.code([Meta,a,f,a])==85,
eE.decode(85)==[Meta,a,f,a],
s[-1]==[Meta,a,f,a],
s.size == s.uniq.size,
Proc.new{
  eE.set([Meta,Meta,a])
  eE.next;eE.next;eE.next
  eE.code==19
}.call

]

print("Enumerateur_des_ver2  : ".rjust(30),
  (not t.include?(false)),"\n")
Mere.L.clear

require "./Langages_et_operateurs.rb"

class Ver2
  attr :L
  attr :n
  attr :m,true
  attr :m0
  def initialize(l,m0=[])       # l = [a,.,f],  m0 =[f,.]
    @L = l
    @H = Hash[l.to_enum.with_index.to_a]
                                            # @H = {a=>0, .=>1, f=>2}
    @L0 = l.clone
    @L0.delete(Meta)
    @H0 = Hash[@L0.to_enum.with_index.to_a]       
                                           # @H = {a=>0, f=>1}
    @P = @H[Meta]         # @P = indice de l'opérateur Meta (".")
    @Ln = l.size                 # @Ln = Nombre d'opérateurs
    @F = l.size-1                # @F = la dernière valeur d'indice
    if @P==nil then
      @L << meta
      @P = @Ln
      @Ln +=1
      @F +=1
    end
    @m0 = m0.collect{|x| @H[x]}  # @m0 = [1,0]
    rewind
  end
  def rewind() @m=@m0; @n=m0.size; self; end
  def next()
    if @m.empty? then
      @m=[0]
      @n=1
      if @m[0]!= @P then return [@L[0]] end
    end
    i=1
    while @m[-i]==@F and i<=@n; @m[-i]=0; i+=1 end
    if i>@n then @m.unshift(0); @n+=1
    else @m[-i]+=1
    end
    if @m[-1]==@P then self.next end
    @m.collect{|x| @L[x]}
  end
  def peek(km=nil)
    if km==nil then km=@m.clone end
    kn=@n
    if km.empty? then
      km=[0];
      kn=1;
      if km[0]!= @P then return [@L[0]] end
    end
    i=1
    while km[-i]==@F and i<=kn; km[-i]=0; i+=1 end
    if i>kn then km.unshift(0); kn+=1
    else km[-i]+=1
    end
    if km[-1]==@P then peek(km) end
    km.collect{|x| @L[x]}
  end
  def code(m=nil)
    if m==nil then mm=@m.clone else mm=m.collect{|x| @H[x]} end
    if mm.empty? then return 0 end
    a=mm.pop
    t=mm.size
    s=@H0[@L[a]]+1
    mm.each_with_index{|x,i| s+= (x+1)*@F*@Ln**(t-i-1)}
    s
  end
  def decode(i)
    mm=[]
    if i>0 then
      mm << @L0[(i-1)%@F]
      i=(i-1)/@F
    end
    while i>0;
      mm << @L[(i-1)%@Ln]
      i=(i-1)/@Ln
    end
    mm.reverse
  end
  def set(m) @m = m.collect{|x| @H[x]} end
  def get() @m.collect{|x| @L[x]} end
end

L'énumération des ver3 en mode composition harmonique se fait en énumérant les ver2 et toutes les permutations-projections callées qu'il est possible de composer avec, et de façon significative, c'est à dire telle que le rayon de sortie soit égal ou inférieur au rayon d'entré du ver2, ou que l'arité de sortie soit égale à l'arité d'entré du ver2.

Une permutation-projection callée de rayon d'entré n est une liste de numéros dans laquelle tous les numéros de 1 à n sont présents au moins une fois. Elle admets une deuxiéme représentation dite harmonique dans laquelle si le dernier numéros est n, alors celui-ci doit être placé dans un deuxième endroit. Son rayon de sortie est égale à la taille de sa représentation harmonique, qui est nécessairement égale ou supérieur à n.

Nombre
d'entrés
Type
Permutation-projection
Représentation
simple
Représentation
harmonique
Dénombrement
1
1-->1
x-->x
(1)
( )
1
2
2-->2
(x,y)-->(x,y)
(x,y)-->(y,x)
(1,2)
(2,1)
( )
(2,1)
2
1-->2
x-->(x,x)
(1,1)
(1,1)
1
3
3-->3
(x,y,z)-->(x,y,z)
(x,y,z)-->(x,z,y)
(x,y,z)-->(y,x,z)
(x,y,z)-->(y,z,x)
(x,y,z)-->(z,x,y)
(x,y,z)-->(z,y,x)
(1,2,3)
(1,3,2)
(2,1,3)
(2,3,1)
(3,1,2)
(3,2,1)
( )
(1,3,2)
(2,1)
(2,3,1)
(3,1,2)
(3,2,1)
3*2
2-->3
(x,y)-->(x,x,y)
(x,y)-->(x,y,x)
(x,y)-->(x,y,y)
(x,y)-->(y,x,x)
(x,y)-->(y,x,y)
(x,y)-->(y,y,x)
(1,1,2)
(1,2,1)
(1,2,2)
(2,1,1)
(2,1,2)
(2,2,1)
(1,1)
(1,2,1)
(1,2,2)
(2,1,1)
(2,1,2)
(2,2,1)
3*2
1-->3
x-->(x,x,x) (1,1,1)
(1,1,1)
1

On range les permutation-projections callées selon 4 ordres possibles obtenue en combinant différents ordres.

1) Lordre croissant des arités de sortie, l'ordre croissant des arités d'entré, l'ordre lexicographique de la représentation simple
2) L'orde croissant des arités de sortie, l'ordre lexicographique de la représentation simple

3) L'orde croissant des rayons de sortie, l'orde croissant des rayons d'entré, l'ordre lexicographique de la représentation harmonique
4) L'orde croissant des rayons de sortie, l'ordre lexicographique de la représentation harmonique

Ces 4 ordres aboutissent à 4 codages distincts.

Représentation
simple
Arité
sortie
Arité
entré

Représentation
simple
Arité
sortie
( )
0
0
( )
0
(1)
1
1
(1)
1
(1,1)
2
1
(1,1)
2
(1,2)
2
2
(1,2)
2
(2,1)
2
2
(2,1)
2
(1,1,1)
3
1
(1,1,1)
3
(1,1,2)
3
2
(1,1,2)
3
(1,2,1)
3
2
(1,2,1)
3
(1,2,2)
3
2
(1,2,2)
3
(2,1,1)
3
2
(1,2,3)
3
(2,1,2)
3
2
(1,3,2)
3
(2,2,1)
3
2
(2,1,1)
3
(1,2,3)
3
3
(2,1,2)
3
(1,3,2)
3
3
(2,1,3)
3
(2,1,3)
3
3
(2,2,1)
3
(2,3,1)
3
3
(2,3,1)
3
(3,1,2)
3
3
(3,1,2)
3
(3,2,1)
3
3

(3,2,1)
3
(1,1,1,1)
4
1

(1,1,1,1)
4
(1,1,1,2)
4
2

(1,1,1,2)
4
(1,1,2,1)
4
2

(1,1,2,1)
4
(1,1,2,2)
4
2

(1,1,2,2)
4
(1,2,1,1)
4
3

(1,1,2,3)
4

Représentation
harmonique
Rayon
sortie
Rayon
entré

Représentation
harmonique
Rayon
sortie
( )
0
0
( )
0
(1,1)
2
1
(1,1)
2
(2,1)
2
2
(2,1)
2
(1,1,1)
3
1
(1,1,1)
3
(1,2,1)
3
2
(1,2,1)
3
(1,2,2)
3
2
(1,2,2)
3
(2,1,1)
3
2
(1,3,2)
3
(2,1,2)
3
2
(2,1,1)
3
(2,2,1)
3
2
(2,1,2)
3
(1,3,2)
3
3
(2,2,1)
3
(2,3,1)
3
3
(2,3,1)
3
(3,1,2)
3
3
(3,1,2)
3
(3,2,1)
3
3
(3,2,1)
3
(1,1,1,1)
4
1
(1,1,1,1)
4
(1,1,2,1)
4
2
(1,1,2,1)
4
















le meta-opérateur zéro-aire ".". Soit le langage L= {a,g(.,.)}. Les séquences [a,g], [a,g,.] et [a,g,.,.] désigne le même ver2, mais pas la séquence [a,g,.,.,.] sauf si on choisi comme mode de composition le mode harmonique. Dans le mode harmonique l'ajout de point à la fin d'un ver ne le change pas. Lorsque l'on calcul le mots suivant si celui-ci à un point à la fin alors on calcule le mot suivant.



Synoptie
Corps
a=Op.new("a",0)          # Création d'un opérateur
b=Op.new("b",0)
f=Op.new("f",1)
g=Op.new("g",2)
h=Op.new("h",2)

eE = Enumerateur.new([a,b,f,g,h])        # Création d'un énumérateur eE

s=[ ];for i in 1..100; s<< eE.next end
eE.rewind

t=[

eE.next == [a],
eE.next == [b],
eE.next == [f,a],
eE.next == [f,b],
eE.next == [f,f,a],
eE.next == [f,f,b],
eE.next == [g,a,a],
s.size == s.uniq.size

]
print("Enumerateur : ",  (not t.include?(false)),"\n")
Mere.L.clear

require "./Lang.rb"

class Enumerateur
  attr :g
  attr :F
  attr :n,true
  attr :m,true
  def initialize(l)
    @g = l.collect{|x| x.air}
    @S = l.collect{|x| x}
    @F = g.size-1
    @n = 1
    @m = []
  end
  def rewind() @m=[]; @n=1; self; end
  def next()
    if @m.empty? then @m=[0]; return [@S[0]] end
    a=0
    t=@m.size
    v=@g[@m[-1]]
    while t+@g[@m[-1]+1]-v>@n
      t-=v
      a+=1-v
      @m.pop
      if @m.empty? then @n+=1; @m=[0]; a=v=0; t=1 end
      v=@g[@m[-1]]
      while @m[-1]==@F
        t-=v
        a+=1-v
        @m.pop
        if @m.empty? then @n+=1; @m=[0]; a=v=0; t=1 end
        v=@g[@m[-1]]
      end
    end
    if @m[-1]==nil then @n+=1; @m=[0]; a=v=0; t=1
    else
      a+= @g[@m[-1]+1]-v
      @m[-1]+=1
      a.times {@m<< 0}
    end
    if @m.size==@n then return @m.collect{|x| @S[x]} else self.next() end
  end
end





Comme le veut la tradition intuissioniste, l'élément dans l'absolu est inatteignable, seul le mot qui le désigne est manipulable

10) Les énumérateurs récurcifs

Parcours de l'arbre des termes





L'implémentation d'une tel structure, pour être efficace, neécessite de lister les places mémoires correspondant au point pour ne pas à avoir à les rechercher dans le mots complet.

Autre règle, l'opérateur n'est qu'une identification, une étiquette, et son arité peut être distincte d'un langage à un autre. Aussi il n'est pas opportun d'en faire un object complexe. Le Langage associe à l'opérateur une fonction, ou plutôt, il associe à l'étiquette un opérateur. Nos opérateurs deviennent des étiquettes c'est à dire dans ruby des symboles, et on utilise le nom d'opérateur pour désigner autre chose, pour désigner l'application associée à l'étiquette.

Le langage est donc une liste d'association étiquette-application. Reste à choisire la façon de représenter l'application.  Il y a beaucoup de façon de représenté une application. La plus simple consiste en l'arité pour désigner l'application par défaut en le mot de définition. Ainsi la séquence [[:a,0],[:f,1],[:g,2]] désigne le langage {a,f(.),g(.,.)}et l'application associé à f est x-->f(x). La seul contrainte sur la séquence est que les étiquettes doivent être distinctes et les applications doivent être des applications.

l'object [:f,1] ne doit pas être dupliqué

La première méthode importante du langage, est son énumérateur de mots. Car en logique intuissioniste un langage est avant tout un énumérateur de mots. Un algoritme simple consiste à calculer le mot suivant, dans l'énumération des mots de taille bornée à n du langage L, selon l'ordre lexicographique.

L'algorithme, comme la démonstration, a besoin d'être décentralisé et de s'appuyer sur la construction d'objects autonomes.

La taille d'un mot est le nombre d'opérateurs dont il est composé. Un mot applati m est une séquence d'indice entre 0 et F. Le langage possède un ordre d'alphabet qui est L et qui respecte l'ordre des arités.








Mais on peut ne pas créer d'object opérateur de base, et faire porter toute la complexité de l'object des opérateurs de base du langage au langage lui-même, en le structurant. Les deux voies doivent être empruntées. On créer ainsi deux classes, la classe des langages dans lesquels les opérateurs archétypes sont des objects, et qui s'appelle Langage. Et celle dans lesquels les opérateurs archetype ne sont pas des objects, et qui s'appelle Lang.

3.1) Lang

Soit le langage L={a, b, f(.), g(..,), h(.,.)}. Le langage L contient 5 opérateurs ayant chacun une arité, mit dans un ordre respectant l'ordre des arités. L'implémentation du langage consiste simplement en une liste d'arités. L = [0,0,1,2,2] où le symbol est remplacé par l'indice. Pour garder les symbols, on ajoute deux méthodes de traduction auxilières liant indices et symbôles, que l'on applique qu'à la fin et au début des calcules. L'ensemble des calcules se fait avec les expressions d'indices et non de symbols (pour des questions d'efficacité et de simplicité algorithmique). Par exemple, le mot g(a,f(b)), applati en la séquence gafb, est implémenté par la liste [3,0,2,1]. Cela correspond à prendre comme symbôles les entiers 0,1,2,3,4.

Titre : Langage d'opérateurs

Contexte :

Int           F : indice du dernier opérateur archétipe. F = 4, l'opérateur archétipe g(.,.)
Int           n : Taille d'un mot. Le mot [3,1] est de taille 2
[{0..F}]  m : Mot applati. m = [3,1], le mot f(a)
[Int]        g : Liste des arités. g = [0,0,1,2,2]
[Symbol] l : Liste des symbôles. l = [:a,:b:,:f,:g,:h]
Hash       h : Hashage. h = {:a=>0, :b=>1, :f=>2, :g=>3, :h=>4}

classe Lang : Langage sans symbole

[{0..F}]  Lang#A : Liste des arités. @A = [0,2] pour un langage comprenant un opérateur zéro-air et un opérateur binaire.
Lang       Lang.new(g) : Langage ayant des opérateurs d'arité décrit par g
String      Lang#to_s : Conversion en String. Lang.new([0,1,2]).to_s ==> "[0,1,2]"

class LangS : Langage avec symbôles

[Symbol]  LangS#S : Liste des symboles. @S = [:a,:b:,:f,:g,:h]
Hash        LangS#N : Codage des symbôle. @N = {:a=>0, :b=>1, :f=>2, :g=>3, :h=>4}
Lang        LangS.new(g,l) : Langage ayant la liste d'opérateurs d'arité g et de symbole l.
String       LangS#to_s : Conversion en String. LangS.new([0,0,1,2,2],[:a,:b,:f,:g,:h]).to_s ==> "{a ,b ,f(.), g(.,.), h(.,.)}"

Synoptie :

LS = LangS.new([0,0,1,2,2],[:a,:b,:f,:g,:h])
s = LS.to_s                                                   ==> "{a ,b ,f(.), g(.,.), h(.,.)}"
g = LS.A                                                      ==> [0, 0, 1, 2, 2]
l = LS.S                                                       ==> [:a, :b, :f, :g, :h]
h =LS.N                                                      ==>
{:a=>0, :b=>1, :f=>2, :g=>3, :h=>4}
LS.A[LS.N[ :f ] ]                                         ==> 1. C'est l'arité du symbole :f dans le langage LS

L = Lang.new([0,0,1,2,2])
s = L.to_s                                                 ==> [0,0,1,2,2]

Corps :

class Lang
    attr :A
  def initialize(p=[]) @A=p end
  def to_s; @A.to_s end
end

class LangS < Lang
  attr :S
  attr :H
  def initialize(p=[],q=[])
    super(p)
    @S=[]
    @N=Hash[];i=0
    q.each do |s|  @S<< s; @N[s]=i; i+=1 end
  end
  def to_s
    if @S.empty? then return "{}" end
    s="{"
    @S.each do |x|
      s<< x.to_s
      if @A[@N[x]]>0 then
        s << "(";
        @A[@N[x]].times {s << ".,"}
        s.chop!;
        s << ")"
      end
      s <<", "
    end
    s.chop!
    s.chop!
    s<< "}"
  end
end

Agencement
Etant donné un langage d'opérateurs {a, f(.), g(.,.)} ou chaque opérateur correspond à un petit programme. Le langage de programmation utilisant ces petits programmes, sans boucle ni répétition, est appelé composition générale ou agencement. Dans ce langage, un programme s'apparente à un flux de donner traité par un réseau de neurones, où chaque neurone correspond à un opérateur. un résultat partiel

---

Pour chaque module, on formalise une documentation exhaustive en 5 parties (titre, contexte, méthodes, synopsie, corps). Le titre comprend le nom de l'unité avec une description. Le contexte reprend toutes les variables et objects mentionnées dans les deux parties suivantes (méthodes et synoptie), et précise leurs classes et leurs significations physiques. Cela permet d'écrire une formule sans avoir à préciser le type des variables ni leur sense physique puisque cela est déjà écrit dans le contexte. Les méthodes comprennent autant de partie qu'il y a de portions de classe. Chaque partie commence par un titre comprenant le nom de la classe suivi d'une description précisant l'aspect développé. Puis sont énumérées les méthodes en rappelant le nom de la classe. On précise à chaque fois la classe du résultat, ce que produit la méthode, les éventuelles modifications physiques qu'elle cause, et les éventuelles contraintes auquelles l'utilisateur doit se soummettre. Les méthodes sont exposées dans un ordre, on expose d'abord les attributs, puis on expose les méthodes de classe selon le shémat Classe.Méthode avec l'éventuelle méthode initialize puis on expose les méthodes d'instances selon le shémat Classe#Méthode. La synopsie présente un exemple de code reprenant les différentes méthodes, ainsi qu'un teste d'auto-cohérence et se termine en affichant le nom de l'unité et le résultat du test, puis efface toutes ses modifications (les variables locales n'ont pas besoin d'être effacées car elle nont pas de portée au dela du fichier). Le corps contient le programme (les variables qui n'apparaissent que dans le corps doivent faire l'object d'un commentaire dans le programme, qui complète ainsi le contexte).