On discute avec l'IA sur les langages algébriques et les automates reconnaissant ces langages. Puis on étend progressivement en plusieurs langages imbriqués avec leur automates les reconnaissant.
On étend les langages pour pouvoir programmer les automates eux-mêmes, et pour finalement proposer un interpréteur multilangage modifiable à volonté.
Comme nous somme soucieux de rendre moins ingrate ces recherches pour ne pas décourager les disciples, nous proposerons à chaque étape des résultats intermédiaires sous forme d'outils concrets.
On définit un langage algébrique en présentant ses éléments générateurs et ses opérateurs générateurs entre crochet `"<...>"`. Chaque opérateur possède une arité indiqué occasionnellement par le suffixe `(".")` pour unaire, `(".,.")` pour binaire, `(".,.,.")` pour ternaire. Exemple :
`"<"a,b,f("."), g(".,."),h(".,.,.")">"`
Sans développer davantage la conception du langage on peut demander à Claude de programmer une fonction idioma("<a,b,f(.), g(.,.),h(.,.,.)>") qui retourne l'automate capable de reconnaitre un élément du langage. On demande que le programme principal débute par une petite synopsie à destination de l'utilisateur final.
Voici l'outils : idioma.py
idioma — reconnaissance des termes d'un langage algébrique
=====================================================================
Un langage est présenté par ses générateurs entre < et > :<a, b, f(.), g(.,.), h(.,.,.)>
un symbole nu est une constante (arité 0)
f(.) est un opérateur unaire (arité 1)
g(.,.) est un opérateur binaire (arité 2)
h(.,.,.) est un opérateur ternaire (arité 3)
A=idioma(présentation) Retourne un automate à pile A
A("terme") -> True si et seulement si le terme est bien formé
On définit un automate récurcif qui reconnait les termes du langage `"<"a,b,f("."), g(".,."),h(".,.,.")">"`. L'automate est représenté par un ensemble de règles de production : `{|--a, |--b, |--f("."), |--g(".,."), |--h(".,.,.")}`. Chaque élément de cet ensemble est une règle de production possible. Le symbole point "." désigne un terme quelconque du langage, et constitue un appel récursif de cet automate.
Voici l'outils : idioma_recurcif.py
idioma_recursif — automate récursif pour un langage algébrique
===================================================================
Le langage est présenté par ses générateurs entre < et > :<a, b, f(.), g(.,.), h(.,.,.)>
L'automate associé est l'ensemble de règles de production :
{ |--a, |--b, |--f(.), |--g(.,.), |--h(.,.,.) }
Le symbole lu sélectionne la règle à appliquer ; chaque point "." désigne un terme quelconque et constitue un appel récursif de l'automate. Une chaîne est reconnue si l'appel initial réussit en consommant exactement toute l'entrée.
A=idioma_recursif(présentation) Retourne un automate A
A("terme") -> True si et seulement si le terme est bien formé
L'automate peut être transformé en générateur énumérant de tous les termes. Il parcourt les différentes règles de productions pour énumérer les termes par taille croissante.
Voici l'outils : idioma_recurcif.py
idioma_generateur — énumération des termes d'un langage algébrique
================================================================
Le langage est présenté par ses générateurs entre < et > :<a, b, f(.), g(.,.), h(.,.,.)>
L'automate { |--a, |--b, |--f(.), |--g(.,.), |--h(.,.,.) } est parcouru en génération : toutes les règles de production sont explorées, chaque point "." étant un appel récursif du générateur.
L'énumération est stratifiée par taille (nombre de symboles de la signature) : chaque terme du langage apparaît une fois et une seule, au bout d'un temps fini.
G=idioma_generateur(présentation) Retourne un générateur G
for t in G : ... Énumère le langage entier G.termes(n) Liste des termes de taille n G.premiers(m) Les m premiers termes G.compte(n) Nombre de termes de taille n
L'automate peut être transformé en un générateur de termes aux hasard. Il choisit au hasard selon des probabilités transmise en argument la règle de production qu'il met en oeuvre.
Voici l'outils : idioma_hasard.py
idioma_hasard — génération aléatoire de termes d'un langage
=================================================================
Le langage est présenté par ses générateurs entre < et > :<a, b, f(.), g(.,.), h(.,.,.)>
L'automate { |--a, |--b, |--f(.), |--g(.,.), |--h(.,.,.) } est parcouru au hasard : à chaque appel une règle de production est tirée selon les probabilités transmises en argument, chaque point "." de la règle déclenchant un appel récursif du générateur.
C'est un processus de branchement (Galton-Watson) : le nombre moyen de descendants m = somme des p_s * arité(s) décide de la terminaison.
m < 1 sous-critique : taille moyenne finie = 1/(1-m)
m = 1 critique : termine, mais taille moyenne infinie
m > 1 sur-critique : risque de non-terminaison (garde-fou)
G=idioma_hasard(présentation, probabilités) Retourne un générateur G
G() ou G.tirer() Un terme au hasard G.echantillon(m) m termes au hasard G.regime() Sous-critique / critique / sur-critique G.taille_moyenne() Espérance de la taille des termes
Jusqu'à présent on a définit des langages où les opérateurs sont des applications internes au langage. Considérons deux langages L et H définit par des éléments générateurs et des opérateurs internes et des opérateurs externes.
L = <a,b,f(H), g(H,L)>
L'opérateur f du langage L prend comme argument un terme du langage H, c'est pourquoi on le note f(H) au lieu de f(.)
L'opérateur g du langage L prend comme argument un terme d'un langage H et un terme du langage L, c'est pourquoi on le note notera g(H,L) ou g(H,.) au lieu de g(.,.)
H = <e, j(H,H),k(H,L,H)>
L'opérateur k du langage H prend comme argument un terme d'un langage H, un terme du langage L et un terme du langage H, c'est pourquoi on le note k(H,L,H) ou k(.,L,.) au lieu de k(.,.,.)
L'opérateur j du langage H prend comme argument deux termes du langage H, c'est pourquoi on le note j(.,.) ou j(H,H).
L'automate reconnaissant L est {|--a,|--b,|--f(H),|--g(H,L)}
L'automate reconnaissant H est {|--e,|--j(H,H),|--k(H,L,H)}
Les arguments sont toujours écrit dans le langage attendu par l'opérateur
Les opérateurs générateurs d'un langage (un élément générateur est un opérateur générateur d'arité nulle) se comportent comme des objets de la classe du langage en question.
Un opérateur f définie dans le langage L, et un opérateur f définie dans le langage H sont distinct. Aussi pour désigner complètement un opérateur il faut désigner un langage et un nom d'opérateur.
Voici l'outils : idioma_sortes.py
idioma_sortes — langages algébriques multi-sortes mutuellement récursifs
================================================================
Plusieurs langages sont présentés simultanément ; chaque opérateur déclare le langage attendu à chaque position d'argument :L = <a, b, f(H), g(H,L)> (g(H,.) est aussi admis)
H = <e, j(H,H), k(H,L,H)>Un point "." en position d'argument désigne le langage en cours de définition : g(H,.) équivaut à g(H,L) dans la présentation de L.
Les automates associés sont mutuellement récursifs :
automate L : { |--a, |--b, |--f(H), |--g(H,L) }
automate H : { |--e, |--j(H,H), |--k(H,L,H) }Chaque position d'argument est un appel récursif de l'automate du langage désigné. Un opérateur est complètement désigné par le couple (langage, nom) : un f de L et un f de H sont distincts.
idioma_sortes(présentation1, présentation2, ...)
Retourne le système S :
S("L", "terme") Reconnaissance dans le langage L S.automate("L") L'automate de L, seul, en fonction
Les automates peuvent être transformés en générateur énumérant tous les termes des langages, en parcourant les différentes règles de productions. On procède par startification par taille (nombre total d'opérateurs, toutes sortes confondues). Puis on énumère les termes par taille croissante.
Voici l'outils : idioma_sortes_generateur.py
idioma_sortes_generateur — énumération des termes d'un système de langages multi-sortes
=========================================================
Le système est présenté comme pour la reconnaissance :L = <a, b, f(H), g(H,L)>
H = <e, j(H,H), k(H,L,H)>Les automates sont parcourus en génération : toutes les règles de production sont explorées, chaque position d'argument étant un appel récursif du générateur du langage désigné à cette position. Les générateurs sont donc mutuellement récursifs, comme les automates dont ils proviennent.
L'énumération est stratifiée par taille : chaque terme de chaque langage apparaît une fois et une seule, au bout d'un temps fini.
idioma_sortes_generateur(présentation1, ...)
Retourne le système G
for t in G.iter("L") : ... Énumère le langage L entier G.termes("L", n) Termes de L de taille n G.premiers("L", m) Les m premiers termes de L G.compte("L", n) Nombre de termes de L de taille n
L'automate peut être transformé en un générateur de termes aux hasard. Il choisit au hasard, selon des probabilités transmise en argument, la règle de production qu'il met en oeuvre.
Voici l'outils : idioma_sortes_hasard.py
idioma_sortes_hasard — génération aléatoire de termes d'un système de langages multi-sortes
=================================================
Le système est présenté comme pour la reconnaissance :L = <a, b, f(H), g(H,L)>
H = <e, j(H,H), k(H,L,H)>Les automates sont parcourus au hasard : à chaque appel dans le langage S, une règle de production de S est tirée selon les probabilités transmises en argument, chaque position d'argument de la règle choisie déclenche un appel récursif du générateur du langage désigné.
C'est un processus de branchement MULTI-TYPE : un tirage dans S ouvre en moyenne M[S,S'] positions de sorte S', avec M[S,S'] = somme des p_op * (occurrences de S' dans le profil). La terminaison se lit sur le rayon spectral de la matrice M :
rho(M) < 1 : terminaison presque sûre, tailles moyennes finies, données par le vecteur T = (I - M)^(-1) * 1 ;
rho(M) = 1 : terminaison presque sûre, tailles moyennes infinies ;
rho(M) > 1 : probabilité strictement positive de non-terminaison, un garde-fou de profondeur est nécessaire.
idioma_sortes_hasard(présentations, probabilités)
Retourne G
G("L") ou G.tirer("L") Un terme de L au hasard G.echantillon("L", m) m termes de L au hasard G.matrice_moyenne() La matrice M G.rayon(), G.regime() Rayon spectral et régime G.tailles_moyennes() Espérances de taille par langage
On regroupe tous ces outils dans une même classe sous forme de méthode
Idioma — langages algébriques : reconnaître, énumérer, engendrer
======================================================================
1. L'OBJET
Un langage algébrique est l'ensemble des termes que l'on peut construire, en un nombre fini d'étapes, à partir de générateurs : des constantes (arité 0) et des opérateurs (arité 1, 2, 3, ...).Un objet Idioma représente un tel langage — ou un système de plusieurs langages se définissant mutuellement — et offre les trois parcours de son automate { |--a, |--b, |--f(.), ... } : le lire (reconnaissance), le dérouler (énumération exhaustive), le tirer aux dés (génération aléatoire).
2. PRÉSENTER UN LANGAGE
Un seul langage : les générateurs entre < et >, l'arité d'un opérateur étant figurée par ses points.
I = Idioma("<a, b, f(.), g(.,.), h(.,.,.)>")
a, b constantes
f(.) opérateur unaire : f(t) avec t un terme
g(.,.) opérateur binaire : g(t1,t2)
h(.,.,.) opérateur ternaire : h(t1,t2,t3)Plusieurs langages : chaque présentation est nommée, et chaque position d'argument désigne le langage attendu — le point "." abrégeant le langage en cours de définition.
S = Idioma("L = <a, b, f(H), g(H,L)>","H = <e, j(H,H), k(H,L,H)>") L.f attend un terme de H ;
L.g un terme de H puis un de L ;
H.k un terme de H, un de L, un de H.Un opérateur est désigné par le couple (langage, nom) : un f de L et un f de H seraient distincts. À la construction, Idioma vérifie la présentation : langages tous définis, aucun langage vide.
Dans toutes les méthodes ci-dessous, l'argument lg (nom du langage visé) s'omet quand le système n'en compte qu'un.
3. RECONNAÎTRE — l'automate en analyse
I.reconnait(t) ou I(t)
-> True / False S.reconnait(t, "L") ou S(t, "L") -> True / False I("g(a, f(b))") -> True I("f(a, b)") -> False (f est unaire) S("g(e, a)", "L") -> True S("f(a)", "L") -> False (f attend un terme de H) 4. ÉNUMÉRER — l'automate en génération exhaustive
L'énumération est équitable : classée par taille croissante (nombre de générateurs dans le terme), elle atteint chaque terme du langage au bout d'un temps fini, une fois et une seule.
I.termes(n [,lg]) La liste des termes de taille n I.compte(n [,lg]) Leur nombre I.premiers(m [,lg]) les m premiers termes de l'énumération I.iterer([lg]) Itérateur infini sur tout le langage I.premiers(6) -> ['a','b','f(a)','f(b)','f(f(a))',...] for t in S.iterer("H"): ... 5. TIRER AU HASARD — l'automate parcouru aux dés
On munit d'abord chaque règle d'une probabilité (une table par langage, chaque table sommant à 1) :
I.probabilise({"a":.3,"b":.3,"f":.2,"g":.15,"h":.05}, profondeur_max=500, graine=None) S.probabilise({"L": {...}, "H": {...}}) puis on tire :
I.tirer([lg]), profondeur_max=500, graine=None) un terme au hasard, toujours fini I.echantillon(m [,lg]) m termes au hasard La taille des termes tirés relève d'un processus de branchement : chaque tirage d'une règle d'arité k ouvre k tirages. Idioma en donne le diagnostic complet :
En régime critique ou sur-critique, le garde-fou profondeur_max abandonne et recommence les tirages divergents : tout terme rendu reste fini (au prix d'un biais vers les petits termes). L'argument graine rend les tirages reproductibles.
I.matrice_moyenne() M[S,S'] : nombre moyen de positions desorte S' ouvertes par un tirage en S I.rayon() Rayon spectral rho de M I.regime() rho < 1 "sous-critique" : tailles moyennes finies
rho = 1 "critique" : termine, tailles moyennes infinies
rho > 1 "sur-critique" : risque de non-terminaisonI.tailles_moyennes() Espérance de taille par langage de départ, T = (I-M)^(-1)*1 si rho < 1
6. GARANTIE CROISÉE
Les trois parcours décrivent le même langage : tout terme énuméré ou tiré au hasard est reconnu — dans son langage, et dans aucun autre. Le programme ci-dessous le vérifie.
On ajoute au langage L des variables muettes L1, L2, L3,.... qui ont comme nom, celui du langage suivit d'un entier strictement positif. Elles sont dites muettes car elles ne correspondent pas à de nouveaux éléments générateurs, ce sont juste des inconnues appartenant au langage L, et qui donc jouent le rôle de terme quelconque de L. Exemple de terme avec variable : g(L2,g(L1,g(a,L2))).
On modifie les automates afin qu'il reconnaissent aussi les termes avec variables de chaque langage.
La convention de nommage crée des risques de collision qu'il faut exclure à la construction : un opérateur ne peut porter un nom de forme « langage + entier » (un opérateur L1 serait indiscernable d'une variable), et un langage ne peut être le nom d'un autre suivi d'un entier (si L et L1 coexistaient, L12 serait ambigu — variable 12 de L ou variable 2 de L1 ?).
On perfectionne la génération de langage an introduisant des termes générateurs. Exemple :
L=<a,f(L),g(L1,L1)>
L'automate correspondant est { |--a, |--f(L), |--g(L1,L1) }. Les deux arguments de g doivent être identique, alors que dans l'automate { |--a, |--f(L), |--g(L,L) }. Les deux arguments de g peuvent être distinct tout en appartenant à L.
Autre cas : K=<a,f(K),g(K1,r(K1))> le terme générateur g(K1,r(K1)) engendre par exemple g(a,r(a)) et g(f(a),r(f(a))), alors que le terme générateur g(K,r(K)) engendre par exemple g(f(a),r(a)). L'opérateur `g` est un opérateur générateur de `K` dont la génération est restreinte en un terme générateur `g(K1,r(K1))`.
Le système comprend plusieurs langage et opérateurs supplémentaire hors langage. Il représente une structure libre engendré par tous ces opérateurs.
On fait une synopsis détaillée avec exemples de la classe Idioma pour l'utilisaeur final.
Idioma — langages algébriques présentés par termes générateurs, reconnaître . énumérer . engendrer au hasard
=============================================================================
1. L'OBJET EN DEUX MOTS
Un langage algébrique est l'ensemble des termes que l'on peut construire, en un nombre fini d'étapes, à partir de ses TERMES GÉNÉRATEURS : des schémas de termes à trous.Un objet Idioma représente un tel langage — ou un système de langages se définissant mutuellement — et sait parcourir son automate { |--a, |--f(L), |--g(L1,L1) } de trois façons : le lire (reconnaissance par filtrage), le dérouler (énumération exhaustive), le tirer aux dés (génération aléatoire).
2. CONSTRUIRE UN IDIOMA
E = Idioma("L = <a, f(L), g(L1,L1)>")
K = Idioma("K = <a, f(K), g(K1, r(K1))>")
S = Idioma("L = <a, b, f(H), g(H,L)>","H = <e, j(H,H), k(H,L,H)>")Chaque présentation nomme un langage et liste ses termes générateurs entre < et >. Dans un terme
générateur, une feuille peut être :
- un nom de langage : L, H, ou "." (le langage courant) : un terme quelconque de ce langage, choisi INDÉPENDAMMENT à chaque occurrence ;
- une variable : L1, H2, ... (nom du langage suivi d'un entier > 0) : un terme quelconque de son langage, mais LE MÊME à chaque occurrence dans le schéma ;
- un symbole toute autre écriture : pièce littérale du schéma, qui n'est pas un générateur autonome.
Trois lectures sur les exemples ci-dessus :
- g(L1,L1) n'engendre que les g(t,t) à arguments IDENTIQUES ; g(L,L) engendrerait tous les g(t1,t2) ;
- dans K, g(K1,r(K1)) engendre g(a,r(a)), g(f(a),r(f(a))), ... mais r(a) SEUL n'est pas un terme de K : r n'est qu'une pièce du schéma ;
- dans S, les langages L et H se définissent mutuellement, et un opérateur est désigné par le couple (langage, nom) : un f de L et un f de H seraient distincts.
L'ancienne écriture par arités reste valable — c'est le cas des schémas de profondeur 1 sans variable répétée
Idioma("<a, b, f(.), g(.,.), h(.,.,.)>") (présentation anonyme : le langage est nommé T en interne)
À la construction, Idioma vérifie tout et refuse avec un message explicite : opérateur ou langage dont le nom a la forme d'une variable (un opérateur L1, des langages L et L1), symbole employé avec deux arités, langage mentionné mais non défini, langage vide (aucun terme fini constructible, ex. V = <p(V)>), terme générateur réduit à une sorte ou une variable.
I=Idioma("<a, b, f(.), g(.,.), h(.,.,.)>") Retourne le langage I
I.langages -> Les langages du système I.regles([lg]) -> Les termes générateurs, ex. pour E : ['a', 'f(L)', 'g(L1,L1)'] Dans toutes les méthodes, l'argument lg (nom du langage visé) s'omet quand le système n'en compte qu'un : E("f(a)") mais S("f(e)", "L").
3. RECONNAÎTRE — le filtrage contre les termes générateurs
I.reconnait(t [,lg]) ou, plus court, I(t [,lg]) -> True / False Le terme est analysé en arbre puis filtré contre chaque terme générateur : les pièces littérales doivent coïncider, une feuille de sorte appelle récursivement l'automate du langage désigné, une variable est liée au sous-terme de sa première occurrence et les occurrences suivantes exigent l'ÉGALITÉ syntaxique.
E("g(f(a), f(a))")
-> True E("g(a, f(a))") -> False arguments distincts K("g(f(a), r(f(a)))") -> True même terme sous g et sous r K("g(f(a), r(a))") -> False termes différents K("r(a)") -> False r n'est pas un générateur S("g(j(e,e), f(e))", "L") -> True composition croisée L/H S("f(a)", "L") -> False f attend un terme de H Variables muettes des termes analysés : dans un terme soumis à la reconnaissance, une variable Sn tient lieu de terme quelconque du langage S — acceptée partout où un terme de S est attendu, et là seulement. Deux variables distinctes ne sont jamais réputées égales (rien ne garantit qu'elles désignent le même terme).
E("f(L3)") -> True E("g(L2, L2)") -> True deux occurrences égales E("g(L1, L2)") -> False égalité non garantie S("g(H1, L1)", "L") -> True variables bien sortées S("g(L1, H1)", "L") -> False sortes interverties
I.variables(t [,lg]) -> Les variables du terme, par langage I.est_clos(t [,lg]) -> True si le terme est sans variable
S.variables("g(H1, g(H2, f(H1)))", "L") -> {'H': ['H1', 'H2']} 4. ÉNUMÉRER — la génération exhaustive
L'énumération est ÉQUITABLE : classée par taille croissante (nombre de symboles ; une variable à p occurrences compte p fois la taille du terme qui l'instancie), elle atteint chaque terme clos au bout d'un temps fini, une fois et une seule.
I.termes(n [,lg]) La liste des termes de taille n I.compte(n [,lg]) Leur nombre I.premiers(m [,lg]) Les m premiers termes I.iterer([lg]) Itérateur infini sur tout le langage
E.premiers(6) -> ['a','f(a)','f(f(a))','g(a,a)','f(f(f(a)))','f(g(a,a))'] K.premiers(7) -> ['a','f(a)','f(f(a))','f(f(f(a)))','g(a,r(a))','f(f(f(f(a))))','f(g(a,r(a)))'] g(a,r(a)) : taille 5 = 3 symboles + 2 fois a
Le comptage rend visible la contrainte d'égalité — la diagonale {g(t,t)} est infiniment plus maigre que le carré {g(t1,t2)} :
tailles 1..7 avec g(L1,L1) : 1, 1, 2, 2, 3, 3, 5
tailles 1..7 avec g(L,L) : 1, 1, 2, 4, 9, 21, 515. TIRER AU HASARD — la génération aléatoire
On munit d'abord chaque terme générateur d'une probabilité — une règle se désigne par son écriture canonique ("g(L1,L1)") ou, si elle est seule à la porter, par sa tête ("g") ; une table par langage, chaque table sommant à 1 :
E.probabilise({"a": .5, "f": .3, "g": .2}, graine=2026) S.probabilise({"L": {"a":.3,"b":.3,"f":.25,"g":.15},"H": {"e":.6,"j":.25,"k":.15}}) puis on tire — une variable n'est tirée qu'UNE fois, puis dupliquée à chacune de ses occurrences :
I.tirer([lg]) Un terme clos au hasard, toujours fini I.echantillon(m [,lg]) m termes au hasard
E.tirer() -> 'g(f(a),f(a))' (par exemple) La taille des termes relève d'un processus de branchement, et la duplication dissocie deux matrices de moyennes M[S,S'] :
I.matrice_moyenne("tirages") une variable = UN tirage I.rayon("tirages"), I.regime() -> Gouverne la TERMINAISON :
rayon < 1 "sous-critique" termine, tailles moyennes finies
rayon = 1 "critique" termine, tailles moy. infinies
rayon > 1 "sur-critique" risque de non-terminaisonI.matrice_moyenne("occurrences") Une variable = p occurrences I.rayon("occurrences") -> Gouverne la TAILLE I.tailles_moyennes() Espérances par langage de départ, finies si rayon(occurrences) < 1 Avec {a:.5, f:.3, g:.2} : rayon(tirages) = 0.50, rayon(occurrences) = 0.70, taille moyenne = 3.333
Avec {a:.42, f:.08, g:.5} : rayon(tirages) = 0.58 mais rayon(occurrences) = 1.08 — la génération termine presque sûrement et pourtant les tailles moyennes sont infinies : la duplication gonfle les termes sans allonger la récursion.Le garde-fou profondeur_max (500 par défaut) abandonne et recommence les tirages divergents : tout terme rendu est fini, au prix d'un biais vers les petits termes en régime critique ou sur-critique. L'argument graine rend les tirages reproductibles.
6. AIDE-MÉMOIRE
I = Idioma(pres1 [,pres2, ...]) Construction, vérifiée 7. GARANTIE CROISÉE
I.langages Consulter le système I.regles([lg]) I.reconnait(t [,lg]) / I(t [,lg]) Reconnaissance I.variables(t [,lg]) I.est_clos(t [,lg]) I.termes(n [,lg]) énumération par taille I.compte(n [,lg]) I.premiers(m [,lg]) I.iterer([lg]) I.probabilise(p [,profondeur_max] [,graine]) -> self I.tirer([lg]) tirages aléatoires I.echantillon(m [,lg]) I.matrice_moyenne(genre) I.rayon(genre) I.regime() diagnostic de terminaison I.tailles_moyennes()
Les trois parcours décrivent le même langage : tout terme énuméré ou tiré au hasard est reconnu — dans son langage, et dans aucun autre. Le programme ci-dessous le vérifie sous vos yeux.
Voici l'outils : idioma_classe.py
Jusqu'à présent, dans chaque langage, chaque opérateur générateur apporte un nouvel opérateur générateur distinct pour le sytème, et chaque opérateurs hors langage distinct apporte un nouvel opérateur générateur distinct pour le sytème (risque de masquage avec un opérateur d'un langage). On permet de partager les opérateurs de même nom court entre plusieurs langage.
Un langage peut utiliser comme générateur un opérateur d'un autre langage qui est alors explicité en utilisant le nom long de l'opérateur qui composé du nom du langage, du signe "_" et du nom de l'opérateur.
Dans l'exemple suivant : L=<a,b,H_f(.)> et H=<L_a,f(.)>, le langage L comprend les opérateurs a,b,f, et le langage H comprend les opérateurs a,f. Mais certains opérateurs sont partagés : L_a=H_a et L_f=H_f
Dans l'exemple suiavnt : L=<a,f(.),L_f(.)>, l'énumération des termes de L produit les termes f(a) et L_f(a) qui sont identiques. Évitez ces répétitions.
Dans l'exemple suivant : L=<a,f(.)> et H=<L_a,f(.)>, l'opérateur a est un objet de L, et c'est aussi un objet de H. Car dans le contexte de H nous avons a=L_a, c'est à dire dans le contexte du système H_a=L_a. Et lorsque cet opérateur est évoqué dans un contexte du langage L, il doit être écrit a. Et lorsque cet opérateur est évoqué dans un contexte du langage H, il doit être aussi écrit a .
Dans l'exemple suivant : L=<a,f(.)> et H=<a,L_f(.)>, l'opérateur f est un objet de L, et c'est aussi un objet de H. Car dans le contexte de H nous avons f=L_f, ( ce qui signifie que quelque soit un terme µ du système f(µ)=L_f(µ). Et lorsque cet opérateur est évoqué dans un contexte du langage L, il doit être écrit f . Et lorsque cet opérateur est évoqué dans un contexte du langage H, il doit être aussi écrit f .
Dans l'exemple suivant : S=Idioma("L=<a,f(.)>", "H=<a,L_f(.)>", "K=<L_a,L_f(.)>"), l'instruction S.premiers(1,"K") doit retourner ['a'] et non ['L_a']. Choisissez toujours le nom cours lorqu'il n'y a pas d'ambiguité.
. Idioma — langages algébriques présentés par termes générateurs
reconnaître . énumérer . engendrer au hasard
======================================================================
1. L'OBJET EN DEUX MOTS
Un langage algébrique est l'ensemble des termes que l'on peut construire, en un nombre fini d'étapes, à partir de ses TERMES GÉNÉRATEURS : des schémas de termes à trous. Un objet Idioma représente un tel langage — ou un système de langages se définissant mutuellement — et sait parcourir son automate { |--a, |--f(L), |--g(L1,L1) } de trois façons : le lire (reconnaissance par filtrage), le dérouler (énumération exhaustive), le tirer aux dés (génération aléatoire).
2. CONSTRUIRE UN IDIOMA
E = Idioma("L = <a, f(L), g(L1,L1)>")
K = Idioma("K = <a, f(K), g(K1, r(K1))>")
S = Idioma("L = <a, b, f(H), g(H,L)>", "H = <e, j(H,H), k(H,L,H)>")Construction, vérifiée Chaque présentation nomme un langage et liste ses termes générateurs entre < et >. Dans un terme générateur, une feuille peut être :
- Un nom de langage L, H, ou "." (le langage courant).
- Un terme quelconque de ce langage, choisi INDÉPENDAMMENT à chaque occurrence.
- Une variable L1, H2, ... (nom du langage suivi d'un entier > 0).
- Un terme quelconque de son langage, mais LE MÊME à chaque occurrence dans le schéma.
- Un symbole toute autre écriture : pièce littérale du schéma, qui n'est pas un générateur autonome.
Trois lectures sur les exemples ci-dessus :
- g(L1,L1) n'engendre que les g(t,t) à arguments IDENTIQUES.
- g(L,L) engendrerait tous les g(t1,t2).
- Dans K, le terme g(K1,r(K1)) engendre g(a,r(a)), g(f(a),r(f(a))), ... mais r(a) SEUL n'est pas un terme de K : l'opérateur r n'est qu'une pièce du schéma.
- Dans S, les langages L et H se définissent mutuellement, et un opérateur est désigné par le couple (langage, nom) : un f de L et un f de H seraient distincts.
OPÉRATEURS, PIÈCES ET NOMS LONGS. Les opérateurs d'un langage sont les têtes de ses termes générateurs ; les symboles seulement imbriqués, opérateurs d'aucun langage, sont des PIÈCES du système, hors de tout langage. Un langage peut employer comme générateur l'opérateur d'un autre langage, explicité par son NOM LONG Langage_operateur (les noms de langages sont donc sans '_') ; il l'emprunte sans se l'approprier. Dans un terme, un opérateur s'écrit indifféremment en nom court ou en nom long ; une pièce n'a que son nom.
P = Idioma("L = <a, b, f(.), g(., r(.)), g(L1,L1)>")
P.operateurs() -> ['a','b','f','g'] P.pieces() -> ['r'] (r est une pièce : r(t) seul n'est pas un terme)
Q = Idioma("L = <a, b, H_f(.), g(., H_r(.))>", "H = <e, f(.), r(.)>")
Q.operateurs("L") -> ['a','b','g'] (H_f n'ajoute pas f à L) Q.operateurs("H") -> ['e','f','r'] Q.pieces() -> [] Q("H_f(a)","L") -> True le f de H, appliqué à un terme de L Q("f(a)","L") -> True même opérateur, écriture courte Q("f(e)","L") -> False l'argument doit être un terme de L Q("f(e)","H") -> True ... et voici le f natal de H La cohérence des arités est vérifiée PAR IDENTITÉ à travers tout le système : H_f employé dans L doit avoir l'arité du f de H.
ÉCRITURE DES OPÉRATEURS DANS LES TERMES. Le nom long n'appartient qu'à la présentation : dans les termes, un opérateur s'écrit par son NOM COURT dans tout contexte où celui-ci le désigne sans ambiguïté. La résolution est CONTEXTUELLE : dans le contexte du langage C, un nom court désigne l'opérateur propre de C s'il existe, sinon l'unique opérateur que C emprunte sous ce nom, sinon la pièce. Un opérateur emprunté est ainsi un objet des deux langages, sous la même écriture :
S = Idioma("L=<a,f(.)>", "H=<a,L_f(.)>", "K=<L_a,L_f(.)>")
S.premiers(1,"K") -> ['a'] K n'a pas de a propre : le a emprunté à L s'y écrit court S.premiers(1,"H") -> ['a'] le a PROPRE de H
même écriture, autre opérateur ; L_a reste long dans H
W = Idioma("L = <a, f(.)>", "H = <L_a, f(.)>")
W.regles("H") -> ['a', 'f(H)'] a = L_a W.empruntes("H") -> {'a': ['L']} provenance mémorisée W("a","L"), W("a","H") -> True, True l'opérateur a est objet de L et de H W.premiers(3,"H") -> ['a','f(a)','f(f(a))'] et f = L_f vaut jusque dans l'égalité des variables : celle-ci se juge sur les termes RÉSOLUS EN IDENTITÉS par le filtrage, si bien que `f(µ)` et `L_f(µ)` sont le même terme :
Idioma("L = <a, f(.), g(L1,L1)>")("g(f(a), L_f(a))") -> True Quand deux langages possèdent le même nom (le f de L et le f de H dans W), les deux opérateurs restent distincts et le nom long demeure leur seule désignation mutuelle. Enfin les termes générateurs devenus identiques après normalisation sont fusionnés — l'énumération ne répète aucun terme :
Idioma("L = <a, f(.), L_f(.)>").regles() -> ['a', 'f(L)'] L'ancienne écriture par arités reste valable — c'est le cas des schémas de profondeur 1 sans variable répétée :
Idioma("<a, b, f(.), g(.,.), h(.,.,.)>")
(présentation anonyme : le langage est nommé T en interne) À la construction, Idioma vérifie tout et refuse avec un message explicite : opérateur ou langage dont le nom a la forme d'une variable (un opérateur L1, des langages L et L1), symbole employé avec deux arités, langage mentionné mais non défini, langage vide (aucun terme fini constructible, ex. V = <p(V)>), terme générateur réduit à une sorte ou une variable.
I.langages -> les langages du système I.regles([lg]) -> les termes générateurs I.regles('E') -> ['a', 'f(L)', 'g(L1,L1)']
Dans toutes les méthodes, l'argument lg (nom du langage visé) s'omet quand le système n'en compte qu'un : E("f(a)") mais S("f(e)", "L").
3. RECONNAÎTRE — le filtrage contre les termes générateurs
I.reconnait(t [,lg]) -> True / False I(t [,lg]) -> True / False Le terme est analysé en arbre puis filtré contre chaque terme générateur : les pièces littérales doivent coïncider, une feuille de sorte appelle récursivement l'automate du langage désigné, une variable est liée au sous-terme de sa première occurrence et les occurrences suivantes exigent l'ÉGALITÉ syntaxique.
E("g(f(a), f(a))") -> True E("g(a, f(a))") -> False arguments distincts K("g(f(a), r(f(a)))") -> True même terme sous g et sous r K("g(f(a), r(a))") -> False termes différents K("r(a)") -> False r n'est pas un générateur S("g(j(e,e), f(e))", "L") -> True composition croisée L/H S("f(a)", "L") -> False f attend un terme de H Variables muettes des termes analysés : dans un terme soumis à la reconnaissance, une variable Sn tient lieu de terme quelconque du langage S — acceptée partout où un terme de S est attendu, et là seulement. Deux variables distinctes ne sont jamais réputées égales (rien ne garantit qu'elles désignent le même terme).
E("f(L3)") -> True E("g(L2, L2)") -> True deux occurrences égales E("g(L1, L2)") -> False égalité non garantie S("g(H1, L1)", "L") -> True variables bien sortées S("g(L1, H1)", "L") -> False sortes interverties
I.variables(t [,lg]) les variables du terme, par langage S.variables("g(H1, g(H2, f(H1)))", "L") -> {'H': ['H1', 'H2']} I.est_clos(t [,lg]) True si le terme est sans variable 4. ÉNUMÉRER — la génération exhaustive
L'énumération est ÉQUITABLE : classée par taille croissante (nombre de symboles ; une variable à p occurrences compte p fois la taille du terme qui l'instancie), elle atteint chaque terme clos au bout d'un temps fini, une fois et une seule.
I.termes(n [,lg]) la liste des termes de taille n I.compte(n [,lg]) leur nombre I.premiers(m [,lg]) les m premiers termes I.iterer([lg]) itérateur infini sur tout le langage
E.premiers(6) -> ['a','f(a)','f(f(a))','g(a,a)','f(f(f(a)))','f(g(a,a))'] K.premiers(7) -> ['a','f(a)','f(f(a))','f(f(f(a)))','g(a,r(a))','f(f(f(f(a))))','f(g(a,r(a)))'] ( g(a,r(a)) : taille 5 = 3 symboles + 2 fois a)
Le comptage rend visible la contrainte d'égalité — la diagonale {g(t,t)} est infiniment plus maigre que le carré {g(t1,t2)} :
tailles 1..7 avec g(L1,L1) : 1, 1, 2, 2, 3, 3, 5
tailles 1..7 avec g(L,L) : 1, 1, 2, 4, 9, 21, 515. TIRER AU HASARD — la génération aléatoire
On munit d'abord chaque terme générateur d'une probabilité — une règle se désigne par son écriture canonique ("g(L1,L1)") ou, si elle est seule à la porter, par sa tête ("g") ; une table par langage, chaque table sommant à 1 :
E.probabilise({"a": .5, "f": .3, "g": .2}, graine=2026) S.probabilise({"L": {"a":.3,"b":.3,"f":.25,"g":.15}, "H": {"e":.6,"j":.25,"k":.15}}) puis on tire — une variable n'est tirée qu'UNE fois, puis dupliquée à chacune de ses occurrences :
I.tirer([lg]) un terme clos au hasard, toujours fini I.echantillon(m [,lg]) m termes au hasard
E.tirer() -> 'g(f(a),f(a))' (par exemple) La taille des termes relève d'un processus de branchement, et la duplication dissocie deux matrices de moyennes M[S,S'] :
I.matrice_moyenne("tirages") une variable = UN tirage I.rayon("tirages") rayon < 1 "sous-critique" termine, tailles moyennes finies
rayon = 1 "critique" termine, tailles moy. infinies
rayon > 1 "sur-critique" risque de non-terminaisonI.regime() -> gouverne la TERMINAISON I.matrice_moyenne("occurrences") une variable = p occurrences I.rayon("occurrences") -> gouverne la TAILLE I.tailles_moyennes() -> espérances par langage de départ,
finies si rayon(occurrences) < 1Avec {a:.5, f:.3, g:.2} : rayon(tirages) = 0.50, rayon(occurrences) = 0.70, taille moyenne = 3.333
Avec {a:.42, f:.08, g:.5} : rayon(tirages) = 0.58 mais rayon(occurrences) = 1.08 — la génération termine presque
sûrement et pourtant les tailles moyennes sont infinies : la duplication gonfle les termes sans allonger la récursion.
Le garde-fou profondeur_max (500 par défaut) abandonne et recommence les tirages divergents : tout terme rendu est fini, au prix d'un biais vers les petits termes en régime critique ou sur-critique. L'argument graine rend les tirages reproductibles.
6. AIDE-MÉMOIRE
Idioma(pres1 [,pres2, ...]) construction, vérifiée 7. GARANTIE CROISÉE
.langages consulter le système .regles([lg]) .operateurs([lg]) opérateurs et pièces .pieces() .empruntes([lg]) emprunts et provenance .reconnait(t [,lg]) reconnaissance I(t [,lg]) .variables(t [,lg]) .est_clos(t [,lg]) .termes(n [,lg]) énumération par taille .compte(n [,lg]) .premiers(m [,lg]) .iterer([lg]) .probabilise(p [,profondeur_max] [,graine]) -> self .tirer([lg]) tirages aléatoires .echantillon(m [,lg]) .matrice_moyenne(genre) .rayon(genre) .regime() diagnostic de terminaison .tailles_moyennes()
Les trois parcours décrivent le même langage : tout terme énuméré ou tiré au hasard est reconnu — dans son langage, et dans aucun autre. Le programme ci-dessous le vérifie sous vos yeux.
Voici l'outils : idioma_classe.py
On ajoute la possibilité de déclarer des opérateurs générateurs d'arité variable indiquée occasionnellement par le suffixe `"(...)"`.
Par exemple les premiers termes de `L = "<"a,h("...")">"` sont :
`a, h, h(a), h(h), h(a,a), h(h,a), h(a,h), h(h,h), h(h(a)), h(h(h)),h(a,a,a),...`
Puis on ajoute la possibilité de déclarer des opérateurs générateurs d'arité variable supérieur ou égale à une arité de base indiquée occasionnellement par :
le suffixe `"(.,...)"` pour une arité `>= 1`,
le suffixe `"(.,.,...)"` pour une arité `>= 2`,
le suffixe `"(.,.,.,...)"` pour une arité `>= 3`,
etc.
L'usage des chaines de caractères comme stockage de données constitue un compromis pertinent entre densité des données et lisibilité par un humain, qui même... la plus part du temps accentue la lisibilité en utilisant moins de parenthèses et de virgules. Le termes ne sert plus seulement d'instruction, il peut ainsi constituer une donnée pour un stockage suffisament dense. C'est pourquoi on s’intéresse à différentes syntaxe permettant de densifier le terme. Mais cela ne change pas l'arborescence des emboitements d'opérateurs. C'est un sucre syntaxique qui permet de condenser l'écriture, et qui va être utilisé davantage encore pour augmenter sa lisibilité.
Dans un premier temps, comme la prudence nous invite à séparer les traitements, la syntaxe alternative est utilisé que pour l'entré et la sortie des termes, le terme est mémorisé en mémoire sous sa forme décompressée. Ce n'est qu'au moment de l'affichage qu'il applique la syntaxe alternative, et au moment de la saisie qu'il interprète la syntaxe altérnative pour mémoriser le terme décompressé.
Cette syntaxe alternative s'applique identiquement à tous les opérateurs de même nom cours. Cela permet plus facilement de lever les ambiguités lorsqu'un terme comprend des arguments de différents langages.
On ajoute dans le créateur Idioma un argument facultatif supplémentaire qui va indiquer les syntaxes alternatives pour chaque nom court d'opérateur concerné.
Voici les différentes syntaxes altérnatives :
Une gestion des priorités des opérateurs lève les ambiguités de la façon suivante :
Puis on ajoute une syntaxe alternative, la syntaxe délimité, pour les opérateurs d'arité variable. Cette syntaxe comprend un symbole de début et un symbole de fin non déjà utilisé ni utilisé comme nom d'opérateur dans un même langage. Exemple :
Idioma( "L=<a,b,f(...)>", "H=<c,d,f(...)>", syntaxes={ "f": ("delimite", "|", "">"), } )
Dans `L` nous avons `f(a,b,a,b) = |abab>`
Dans `H` nous avons `f(c,d,c,d) = |cdcd>`
1- Une autre syntaxe délimitée peut se différentier par seulement le délimiteur de début, le délimiteur de fin étant identique dans les deux syntaxes délimitées.
2- Juste une exception, le délimiteur de début peut correspondre au nom de l'opérateur. Exemple :
syntaxes={ "f": ("delimite", "f", ">"), "g": ("delimite", "g", ">") }3- Juste une exception, le délimiteur de fin peut être le caractère blanc.