Les langages algébriques multi-sortes sont la base des interpréteurs multilangages. Néanmoins les expressions avec nom d'opérateur, parenthèse et virgule correspondent à des schémas d'emboitement développés explicitement, et non à la notation la plus lisible pour un humain. C'est là qu'interviennent les syntaxes alternatives, préfixe, infixe, postfixe et délimité, qui nous permettent de définir un véritable langage de programmation mutable, vues précédement.
La programmation assistée par l'IA, nous permet de mettre facilement en oeuvre les constructions d'algèbre multi-sortes ainsi que toutes sortes d'algorithmes applicable à ces structures. Cela modifit l'ordre des pertinences dans les constructions et les conceptions mathématiques. On s'attardera dans le choix d'une nomenclature de structures et d'une formalisation des opérations sur ces structures, provenant des traitements informatiques possibles sur ces structures. Cela révèle un nouvel attrait pour le constructivisme par le bas.
La construction ayant quelque prétention à l'universlité, l'ordre des constructions et des concepts à définir revête une plus grande importance. Le premier prompt est celui définissant une algèbre libre engendrée par des opérateurs internes.
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ée occasionnellement par le suffixe (.) pour unaire, (.,.) pour binaire, (.,.,.) pour ternaire. Exemple :
L = <a, b, f(.), g(.,.), h(.,.,.,.)>
Il convient de proposer à l'utilisateur les outils les plus démonstratifs avec les arguments par défaut, necéssaire pour cela. Puis il est préférable de regouper l'information d'une structure dans la structure elle-même. C'est pourquoi l'ajout de poids assiociés à chaque générateur se fait dès la définition de la structure.
On ajoute un poids à chaque générateur. Le suffixe :p fixe le poids, positif, nul autorisé, 1 par défaut. Exemple :
L = <a:9, b, f(.):3, g(.,.), h(.,.,.,.)>
Notre vision étant par essence récursive, on orientera notre agent IA dans cette vision d'un traitrement récurcif.
On définit un automate récursif qui reconnaît 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. .
Programme en python dans @idioma.py une fonction idioma("<a,b,f(.), g(.,.),h(.,.,.,.)>") qui retourne cet automate capable de reconnaître un terme du langage.
A = idioma("<a:9,b,f(.):3, g(.,.)>")
Attributs :
A.regles = {'|--g(.,.)', '|--b', '|--a', '|--f(.)'} Régles de production A.generateurs = {'a':9, 'b':1} Eléments générateurs A.operateurs = {'f':(1,3), 'g':(2,1)} Opérateurs générateurs A.symboles = [('a', 0, 9), ('b', 0, 1), ('f', 1, 3), ('g', 2, 1)] Symboles générateurs
Méthodes :
A.reconnait("g(f(a),b)") = True Teste si le terme appartient au langage.
On crée des énumérateurs de termes, et un générateur de termes au hasard.
Créer une méthode termes() énumérant tous les termes du langage dans l'ordre de leur taille (nombre d'opérateurs et d'éléments). Créer une méthode termes_taille_fixe(n) énumérant tous les termes du langage de taille n.
Créer une méthode termes-poids() énumérant tous les termes du langage dans l'ordre de leur poids (sommes des poids des opérateurs et des éléments). Vous utiliserez l'algorithme de Dijkstra appliqué à un arbre.
Créer une méthode termes_poids_fixe(n) énumérant tous les termes du langage de poids n.
Créer une méthode terme_hasard() qui génère un terme aléatoire où la probabilité de choisir chaque règle de production (générateur ou opérateur) est proportionnelle à son poids.
Méthodes :
A.termes() Enumérateur des termes par taille croissante (taille = nombre de symboles). A.termes_taille_fixe(n) Enumérateur des termes de taille exactement n A.termes_poids() Enumérateur des termes par poids croissant via Dijkstra sur l'arbre des termes : A.termes_poids_fixe(n) Enumérateur des termes de poids exactement n terme_hasard() Terme au hasard en choisissant d'une règle ∝ son poids, puis récursion sur les arguments.
liste(A.termes_taille_fixe(n)) Liste des termes par poids croissant via Dijkstra sur l'arbre des termes for x in A.termes_poids_fixe(n):
print(x)Affiche les termes de poids exactement n A.termes_poids_fixe(n) Terme au hasard selon la graine 10.
Le n-uplet est de taile fixe, la séquence est de taille variable et peut être vide.
Le procédé d'unification de termes (à la base de tout raisonnement) qui est de complexité linéaire s'étend aux séquences finales de termes, aux séquences finales de séquence finales de termes, aux séquences finales de séquences finales de séquences finales de termes, etc..
On note une variable représentant une séquence finale de termes avec un préfixe étoile `"*"x`. Elle peut être vide. Les séquences finales ne peuvent contenir une autre séquence finale qu'à la dernière place. Exemple :
`"*"t = (x,y,"*"z)`
On la note aussi sous forme vectorielle `vec x`. Exemple :
`vec t = (x,y,vec z)`
Pour séparer les séquences de séquences entres-elles, on utilise un autre symbole de virgule `"།"` qui ne peut être placé que après une séquence. Exemple de séquence de séquences. On note une variable représentant une séquence de séquences de termes avec un préfixe double étoile `"**"x`. Elle peut être vide. Les séquences de séquences ne peuvent contenir une autre séquence de séquence qu'à la dernière place. Exemple :
`"**"t = (x,y,"*"z། "*"c ། a,"*"b ། **z)`
`(x།y)` n'est pas autorisé, il s'écrira `(x,y)`. parcontre `"*"(x།y)` et `(a,b,"*"x།y)` sont autorisés.
Pour séparer les séquences de séquences de séquences entres-elles, on utilise un autre symbole de virgule `"༎"`. On note une variable représentant une séquence de séquences de séquence de termes avec un préfixe triple étoile `"***"x`. Elle peut être vide. Les séquences de séquences de séquences ne peuvent contenir une autre séquence de séquences de séquences qu'à la dernière place. Exemple :
`"***"t = ("*"x།"**"y༎"***"z)`
Le procédé peut être répété avec à chaque fois un nouveau symbole de virgule.
Tous les raisonnments passeront par le procédé d'unification qui reste ici de complexité linéaire, c'est pourquoi il est pertinent d'étendre le langage dans ce sens, c'est à dire, autoriser des opérateurs prenant comme argument une séquence finale de termes, une séquence finale de séquences finales de termes, une séquence finale de séquences finales de séquences finales de termes, etc..
On ajoute les opérateurs d'arité variable (qui attendent une séquence finale de termes en entrée),
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 :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 par :`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),...`
le suffixe `"(.,*)"` pour une arité `>= 1`,
le suffixe `"(.,.,*)"` pour une arité `>= 2`,
le suffixe `"(.,.,.,*)"` pour une arité `>= 3`,
etc.Les opérateurs d'arité variable (et aussi ceux d'arité variable `>= "n"`) possède un poids `"p"` qui est par défaut `1`, et ils possèdent un deuxième paramètre réel `"r"` qui est par défaut `0.5`, déclaré avec le poids par le suffixe `:"p":"r"`.
le paramètre réel `"r"` représente la probabilité d'augmenter l'arité de `"+"1`. Par exemple, dans le langage `"<"a,h"(*)":1:0.25">"` la probabilité de tirer `a` vaut `1"/"2`, et celle de tirer `h("*")` est `1"/"2`, puis dans cette dernière possibilité, la probabilité de tirer `h(".")` vaut `1 - 0.25` tandis que celle de tirer `h(".,*")` vaut `0.25`, puis dans cette dernière possibilité, la probabilité de tirer `h(".,.")` vaut `1 - 0.25` tandis que celle de tirer `h(".,.,*")` vaut `0.25`, et ainsi de suite.
modifier idioma et la méthode terme_hasard() pour tenir compte de cela.
On ajoute un second symbole de virgule `"།"` pour séparer les séquences de tailles variables. On ajoute les opérateurs d'arité variable multiple.
On ajoute la possibilité de déclarer des opérateurs générateurs d'arité variable multiple. Le symbole `"།"` désigne une séparation entre séquences d'arguments de taille variable. Le suffixe `"(*)"` désigne un opérateur à 1 séquence d'entrée de taille variable.
Le suffixe `"(*།*)"` désigne un opérateur à 2 séquence d'entrées de taille variable.
Le suffixe `"(*།*།*)"` désigne un opérateur à 3 séquences d'entrées de taille variable.Le suffixe `"(.,*།.,.,.།*)"` désigne un opérateur à `2` séquences d'entrée dont l'une est de taille `>=1`, et l'autre est detaille `>= 3`
Le suffixe `"(.,.,*།.,*)"` désigne un opérateur d'arité variable à `2` séquences d'entrées l'une de taille variable `>= 2`, l'autre de taille variable `>=1`.
Par exemple les premiers termes de `L = "<"h("*།*")">"` sont :`h, h(h), h(h,h), h(h"།"h), h(h(h)), h(h,h,h), h(h,h"།"h), h(h(h)"།"h), h(h"།"h,h), h(h"།"h(h)), h(h(h"།"h)),...`
Un triplet de séquence se note `("*"x"།""*"y"།""*"z)` et il ne s'agit pas de concaténation, ce qui oblige à utiliser un second type de virgule `"།"`
Le procédé d'unification de termes de complexité linéaire s'étend aux opérateurs d'arité variable multiple et variable. C'est pourquoi il est pertinent d'étendre le langage dans ce sens.
On ajoute la possibilité de déclarer de tels opérateurs générateurs par le suffixe `"(**)"`.
Par exemple les premiers termes de `L = "<"a,h("**")">"` sont :
`h, h(h), h(h,h), h(h"།"h), h(h(h)), h(h,h,h), h(h,h"།"h), h(h(h)"།"h), h(h"།"h,h), h(h"།"h(h)), h(h(h"།"h)),h(h"།"h"།"h)...`
La séquence de séquences de termes peut être vide. elle se note dans la littérature avec un double préfixe étoile `"**"x`, ou bien encore sous forme d'un double vectoriel `vec(vec x)`.
Ces composantes peuvent avoir une arités variable supérieur ou égale à une arité de base. Par exemple `"(.,*།.,.,*།*)"`
Par exemple les premiers termes de `L = "<"h("*།*")">"` sont :
`h, h(h), h(h,h), h(h"།"h), h(h(h)), h(h,h,h), h(h,h"།"h), h(h(h)"།"h), h(h"།"h,h), h(h"།"h(h)),h(h(h"།"h)),...`
On ajoute la possibilité de déclarer des opérateurs générateurs d'arité variable multiple variable indiquée occasionnellement par le suffixe `"(***)"` pour un opérateur d'arité variable 2 fois,
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 :
Le suffixe `"(*།**)"` pour une arité `>= 1`,
Le suffixe `"(*།*།**)"` pour une arité `>= 2`,
Le suffixe `"(*།*།*།**)"` pour une arité `>= 3`,
etc..
par le suffixe `"(...།**)"` pour un opérateur d'arité variable 3 fois,etc..
Ces composantes peuvent avoir une arités variable supérieur ou égale à une arité de base. Par exemple `"(.,...།.,.,...།...)"`
Par exemple les premiers termes de `L = "<"h("...།...")">"` sont :
`h, h(h), h(h,h), h(h"།"h), h(h(h)), h(h,h,h), h(h,h"།"h), h(h(h)"།"h), h(h"།"h,h), h(h"།"h(h)),h(h(h"།"h)),...`
---- 18 août 2026 ----
L'automate dispose maintenant de :
- termes_poids(max_poids=oo, max_termes=oo, max_memoire=1000000) : générateur infini énumérant tous les termes selon leur poids croissant, en parcourant règles de production et compositions des poids des sous-termes. _termes_poids mémorise les poids pour éviter les re-calculs.
- termes_de_poids(n) : liste des termes de poids exactement n (opérateurs + éléments).
L'automate dispose maintenant de :
Exemples :
- termes_hasard(max_niveau=oo, max_poids=oo, graine=None) : génère un terme aléatoire où la probabilité de choisir chaque règle de production (générateur ou opérateur) est proportionnelle à son poids.
from idioma import idiomaauto = idioma("<a:9,b:1,f(.):3, g(.,.):1, h(.,.,.):3>")
# Génération simple
term = auto.terme_hasard()
# Ex: "f(a)" ou "g(b,f(b))" ou "h(a,a,a)"# Avec limite de profondeur
term = auto.terme_hasard(max_depth=2)# Avec limite de poids
# Reproductible
term = auto.terme_hasard(max_weight=10)
import random
term = auto.terme_hasard(rng=random.Random(42))
Considérons deux langages L et H définit par des opérateurs pouvant être externes.
L = <a:2,b:2,f(H),g(H,L)>
L'opérateur f prend comme argument un terme du langage H, c'est pourquoi on le note f(H) au lieu de f(.)
L'opérateur g 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 = <a ,b:3, j(H,H),k(L,L)>
L'opérateur k prend comme arguments deux termes du langage L, c'est pourquoi on le note k(L,L) au lieu de k(.,.)
L'opérateur j 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 {|--a,|--b,|--j(H,H),|--k(L,L)}
Chaque argument d'un opérateur est toujours écrit dans le langage attendu par l'opérateur.
Perfectionne idioma afin que l'on puisse définir plusieurs langages s'interopérant tel que par exemple :idioma("L = <a,b,f(H), g(H,L)>", "H = <a,b, j(H,H),k(L,L)>")
Le module idioma.py a été perfectionné pour supporter plusieurs langages mutuellement récursifs. Voici un résumé :
Nouveauté : idioma multi-langages
Usage:
from idioma import idiomasystem = idioma(
"L = <a:2,b:2,f(H),g(H,L)>",
"H = <a,b:3,j(H,H),k(L,L)>"
)L = system.get_automaton('L')
H = system.get_automaton('H')# Reconnaissance croisée
L.recognizes("f(j(a,b))") # True : f(H) avec j(a,b) ∈ H
L.recognizes("g(j(a,a),b)") # True : g(H,L) avec j(a,a) ∈ H, b ∈ L
H.recognizes("k(f(a),g(b,a))") # True : k(L,L) avec f(a),g(b,a) ∈ L# Isolation : chaque langage rejette les opérateurs de l'autre
L.recognizes("j(a,b)") # False
H.recognizes("f(a)") # False
Syntaxe des définitions
"L = <a:2,b:2,f(H),g(H,L)>"
Nom du langage avant =
Générateurs: nom[:poids]
Opérateurs: nom(arg1,arg2,...)[:poids]
Arguments = noms de langages : f(H), g(H,L), k(L,L), j(H,H)
Notation legacy f(.) toujours supportée (argument du même langage)
Méthodes disponibles (par langage)
Méthode : Description
recognizes(term) : Vérifie validité avec vérification croisée
terme_hasard(max_depth, max_weight, rng) : Génération aléatoire pondérée
enumerate_terms_poids(max_weight, max_terms) : Énumération par poids (Dijkstra)
enumerate_terms(max_size) : Énumération par taille (limité pour multi-langages)
Tests validés
✅ Reconnaissance correcte avec arguments de langages différents
✅ Isolation stricte entre langages
✅ Distribution des poids respectée (a:33%, b:33%, f:17%, g:17% pour L)
✅ Reproductibilité avec seed RNG
✅ Énumération par poids fonctionnelle cross-langages
faites un synopsis des méthodes avec exemple pour l'utilisateur final
Module idioma — Synopsis utilisateur
Le module idioma permet de définir et manipuler des langages algébriques mutuellement récursifs avec poids, et d'en générer, reconnaître ou énumérer les termes.1. Création du système de langages
from idioma import idiomasystem = idioma(
"L = <a:2,b:2,f(H),g(H,L)>",
"H = <a,b:3,j(H,H),k(L,L)>"
)
Syntaxe d'une définition :"Nom = <générateurs, opérateurs>"
Générateur : nom[:poids] — ex: a:2, b (poids 1 par défaut)
Opérateur : nom(arg1,arg2,...)[:poids] — ex: f(H), g(H,L):3
Arguments : noms de langages (H, L, etc.) — notation legacy f(.) acceptée (même langage)
Retour : un objet LanguageSystem avec .get_automaton(nom).2. Récupération d'un automate
L = system.get_automaton('L')
H = system.get_automaton('H')
Chaque automate est attaché à un langage précis et connaît les autres via le système.3. Méthodes de l'automate
recognizes(terme) — Reconnaissance
L.recognizes("f(j(a,b))") # True : f(H), j(a,b) ∈ H
L.recognizes("g(j(a,a),b)") # True : g(H,L), j(a,a) ∈ H, b ∈ L
H.recognizes("k(f(a),g(b,a))") # True : k(L,L), f(a),g(b,a) ∈ LL.recognizes("j(a,b)") # False : j appartient à H
H.recognizes("f(a)") # False : f appartient à L
terme_hasard(max_depth=None, max_weight=None, rng=None) — Génération aléatoire pondérée
La probabilité de choisir une règle ∝ son poids.# Génération simple
term = L.terme_hasard() # ex: "f(j(a,b))"# Avec limite de profondeur (évite l'infini)
term = L.terme_hasard(max_depth=3)# Avec limite de poids total
term = L.terme_hasard(max_weight=15)# Reproductible
import random
term = L.terme_hasard(rng=random.Random(42))
Distribution respectée (ex: L = <a:2,b:2,f(H):1,g(H,L):1>)Symbole Poids Probabilité
a 2 33%
b 2 33%
f 1 17%
g 1 17%
enumerate_terms_poids(max_weight=None, max_terms=None) — Énumération par poids (Dijkstra)
Génère les termes par poids croissant (somme des poids des règles utilisées).for weight, term in L.enumerate_terms_poids(max_weight=10):
print(f"poids={weight}: {term}")# Sortie:
# poids=2: a
# poids=2: b
# poids=5: g(a,a)
# poids=5: g(a,b)
# ...
Paramètres :Paramètre Description
max_weight Poids max (None = illimité)
max_terms Nb max de termes (None = illimité)
enumerate_terms(max_size=None) — Énumération par taille
Génère les termes par taille croissante (nb de nœuds).for term in L.enumerate_terms(max_size=3):
print(term)
# a, b, f(a), g(a,a), f(f(a)), ...
⚠️ Pour les langages mutuellement récursifs, l'énumération par taille est limitée (ne construit que les termes du langage courant sans croiser les autres).4. Exemple complet
from idioma import idioma
import random# 1. Définition de deux langages mutuellement récursifs
system = idioma(
"L = <a:2,b:2,f(H),g(H,L)>", # f unaire (H), g binaire (H,L)
"H = <a,b:3,j(H,H),k(L,L)>" # j binaire (H,H), k binaire (L,L)
)L = system.get_automaton('L')
H = system.get_automaton('H')# 2. Reconnaissance
print(L.recognizes("f(j(a,b))")) # True
print(H.recognizes("k(f(a),g(b,a))")) # True
print(L.recognizes("j(a,b)")) # False (isolation)# 3. Génération aléatoire
for _ in range(5):
print("L:", L.terme_hasard(max_depth=3))
print("H:", H.terme_hasard(max_depth=3))# 4. Énumération par poids
print("\nTermes L jusqu'au poids 10:")
for w, t in L.enumerate_terms_poids(max_weight=10):
print(f" {w}: {t}")# 5. Reproductibilité
rng = random.Random(123)
print(L.terme_hasard(rng=rng)) # Toujours le même terme
5. Résumé des poids dans les définitions
"L = <a:5, b, f(H):3, g(H,L)>"
# générateur # générateur # opérateur # opérateur
# poids 5 # poids 1 # poids 3 # poids 1
Élément Syntaxe Poids défaut
Générateur a ou a:5 1
Opérateur f(H) ou f(H):3 1
Argument opérateur H, L, H,L —
6. Points clés
Fonctionnalité Description
Multi-langages Définition simultanée, références croisées
Isolation Chaque langage rejette les opérateurs des autres
Poids Sur générateurs ET opérateurs, utilisés pour proba/énumération
Arguments typés f(H), g(H,L), k(L,L) — vérifiés à la reconnaissance
Legacy f(.) = f(ce_langage) pour compatibilité
On procède d'abord explicitement, en utilisant seulement les noms long des opérateurs.
Fait. Ajouté à l'automate :
La synopsis affiche maintenant ces commandes avec un exemple interactif reproductible (random.seed(9)), et la démo génère 10 termes aléatoires pondérés.
.Un élément générateur est un opérateur générateur d'arité nulle.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 opérateurs pouvant être externes.
L = <a,b,f(H), g(H,L)>
L'opérateur f prend comme argument un terme du langage H, c'est pourquoi on le note f(H) au lieu de f(.)
L'opérateur g 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 = <a,b, j(H,H),k(L,L)>
L'opérateur k prend comme arguments deux termes du langage L, c'est pourquoi on le note k(L,L) au lieu de k(.,.)
L'opérateur j 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 {|--a,|--b,|--j(H,H),|--k(L,L)}
Chaque argument d'un opérateur est toujours écrit dans le langage attendu par l'opérateur.
perfectionne idioma afin que l'on puisse définir ainsi plusieurs langages s'interopérant
idioma gère désormais plusieurs langages s'interopérant.
Exemples de la démo : g(k(a, b), f(a)) vrai dans L (k ∈ H, f ∈ L), f(g(a, b)) faux (g(a,b) ∉ H).
.Si à la place d'un élément générateur figure le nom d'un langage, cela signifie que tous les éléments de ce langage sont à ajouter. Par exemple :. ling = idioma({"L": "<a,f(.), g(.,.)>","H": "<e,L, h(.,.)>"})
L'automate de L est L={|--L_a, |--L_f(L), |--L_g(L,L)}
L'automate de H est H={|--H_e, |--L, |--H_h(H,H)} où la règle |--L signifie parcourir le langage L
le terme h(f(a),e) fait bien partie du langage H
Vérifions le cas limite d'inclusion cyclique (L↔H) et la forme séquence des probabilités : Voir shell
Les inclusions cycliques sont maintenant gérées. Vérifions aussi le tirage aléatoire dans un cycle et le cas d'argument d'opérateur (récursion sur position) : Voir shell
Tout fonctionne. Récapitulatif des changements dans idioma.py :
Les probabilités (poids positifs non normés) des règles de production se font lors de la déclaration du langage. Par exemple : idioma({"L":"<a:3,f(.):3,g(.,.),h(.,.):2>",})
La valeur par défaut vaut 1. Ainsi la probabilité non normée de la règle |--g(.,.) vaut 1. La méthode terme_aleatoire n'a plus besoin d'arguments puisqu'ils sont déjà en mémoire dans le système.
Fait. Les poids sont maintenant déclarés dans la définition du langage :
La synopsis a été complétée (section « Poids des règles de production », auto.poids, exemples interactifs sans argument de probabilités) et les démos utilisent les poids déclarés.
Les probabilités nulles sont acceptées
Fait. Les probabilités nulles sont maintenant acceptées :
Quel est la bonne notation pour définir une algèbre multi-sorte ? Elle doit permettre de nommer les opérateurs avec un nom court qui dépend soit d'un sous langage ou soit du langage hors sous-langage de l'algèbre multi-sorte, le plus simple est de copnsidérer que l'algèbre multi-sortre est un langage, et de définir dans ce langage des qouq-langages.
Le langage alpha est engendré par un unique opérateur `alpha` qui est à la fois d'arité `1` et `0`, et qui respecte les deux axiomes suivant :
Exemples de terme du langage alpha : `alpha`, `alpha(alpha)`, `alpha(alpha(alpha))`, `alpha(alpha)(alpha)`, `alpha(alpha)(alpha(alpha))`. Il convient de bien distinguer les parenthèses d'appel accolées à un terme jouant le rôle d'opérateur, des prenthèses de priorisation. Ici, il n'y a que des parenthèses d'appel.
C'est le langage utilisé pour exprimer un calcul, le terme est parcouru en profondeur d'abord et on commence par évaluer les feuilles, puis on évalue les noeuds dont tous les arguments ont été évalué, puis on fini par évaluer la racine du terme qui donne le résultat final du calcul.
Nommons le langage alpha par la lettre `A`. La structure `A` est engendré par l'unique élément `alpha` ce qui se note :
`A="<"alpha">"` (égalité d'ensemble)
Mais pour parfaire la définition, le type de `alpha` doit être défini. Et il s'agit d'une définition récurcive :
`A = (A->A)` (égalité de type)
On note `(A->B)` le type d'une application de `A` vers `B`, et aussi selon le contexte, l'ensemble des applications de `A` vers `B`. La streucture `A` induit une application `varphi` de `A` vers `(A-A)` définit comme suit : `AAa in A,`
`varphi(a) = (x|->a(x))`
Où (x|->a(x)) désigne une application, qui est le second rôle de `a`.
Peut-t-on définir le langage alpha libre ? Oui en appliquant la règle que chaque terme désigne un élément distinct. Dans ce cas, l'application `varphi` est injective.
D'un point de vue classique, cela se traduit par une application `varphi` de `A` vers `(A->A)` permettant d'utiliser un élément `x` quelconque de `A` dans deux rôles :
`A="<"alpha, varphi^(L->(L->L)) >"`
Il y a une autre façon simple de rendre classique cette structure en utilisant un opérateur binaire `"⁎(.,.)"`. Le langage alpha est identifiable à un magma monogène. On défini l'opérateur `"⁎(.,.)"` qui applique le premier terme sur son second terme. Et on le munit d'une syntaxe infixe. Ainsi nous avons :
`x(y) = x"*"y`
Le langage alpha est donc représenté par la structure de magma monogène suivante :
`L="<"alpha, "⁎"(".,.")">"`
Ainsi apparait trois notations, l'écriture dynamique est celle du langage alpha, l'écriture classique avec un opérateur binaire est celle de l'aglèbre, l'écriture classique avec un opérateur unaire en est une copie car `x"⁎"y` `=` `varphi(x)(y)`
Langage alpha
deuxième rôle `varphi`
Algèbre libre
On peut associer à chaque élément `a "∈" A`, l'application `varphi(a) = (x|->a"⁎"x)` qui appartient bien à `(A"→" A)`. Et réciproquement, on peut ajouter l'opérateur binaire `"⁎"` défini par `x"⁎"y = varphi(x)(y)` qui appartient bien à `(A"×"A"→" A)`, de telle sorte que : `AAaAAx,`
`a(x) = varphi(a)(x) = a"⁎"x`
Notez que l'application `varphi` coïncide avec un élément `e` de `A` si quelque soit un élément `x` nous avons `varphi(e)(x) = varphi(x)`
et cela se traduit aussi par un opérateur binaire `"⁎(.,.)" tel que `x"*"y = varphi(x)(y)`
Les opérateur être ajouter au magma `A` sans rien modifier de la structure. Ainsi, Chaque élément `a` du langage alpha possède comme valeur par défaut l'application suivante qui constitue sont second rôle :
`a = (x|->a"⁎"x)`
C'est le langage alpha d'arité variable. C'est le langage engendré par un unique opérateur `alpha` qui est d'arité variable, et qui respecte les deux axiomes suivants :
Le langage alpha multi-aire est plus compliqué à définir classiquement. Il nécessite de concevoir l'ensemble des séquences non vides de termes, où la séquence singleton est identifiés au terme qu'il contient. On défini l'opérateur de concaténation d'un terme et d'une séquence en utilisant le symbole d'addition `"+"("L,S")` que l'on munie d'une syntaxe infixe et d'une priorité à droite d'abord. Ce qui fait que :
`x"+"y"+"z = x"+"(y"+"z)`
Ainsi nous avons l'algèbre multi-sorte libre suivante :
`L = "<" alpha, "*"(L,S) ">"`
`S = "<"L, "+"(L,S) ">"`
`L sube S`
Il y a deux types d'éléments, Le type `L` des termes de `L` et un type `S` plus générale contenant le premier, qui est le type des séquences de termes. On note les variables de type séquence avec une flêche au dessus, et on applique l'inférnce de type pour connaitre la taille de la séquence. Ainsi par exemples si le terme `g(vecx)` apparait, alors `vecx=x_1"+"x_2`. Si le terme `f(vecx)` apparait, alors `vecx=x_1`.
Remarquez que l'associativité de la concaténation de deux séquences est évoqué ici sous forme d'une structure non quotientée qui est une algèbre multisorte libre.
Les opérateurs `"*"` et `"+"` sont de syntaxe infixe.
L'opérateur `"+"` est d'une priorité à droite d'abord, ce qui permet de concevoir une concaténation associative.
L'opérateur `"*"` est également d'une priorité à droite d'abord, `x"*"y"*"z"="x"*"(y"*"z)`, ce qui permet de concevoir la composition d'application qui est associative.
Généralement on donne une priorité plus faible aux opérations fondamentales n'apportant pas d'information telle que la concaténation de séquence, `"+"`. Ainsi par exemple l'alpha terme `alpha(alpha,alpha,alpha(alpha))` s'écrit dans l'algèbre multi-sorte libre comme suit :
`alpha"*"(alpha+alpha+alpha"*"alpha)`
On souhaite regrouper ces deux ensembles que sont les termes et les séquences de termes. Autrement dit ajouter les séquences de termes de taille >1 à l'ensemble des termes, il faut pour cela étendre les opérateurs `"*"` et `"+"`. Il faut étendre l'opérateur `"+"` sans perte d'information en l'opération de concaténation de séquences, dont la seul contrainte est d'être associative :
`AAxAAyAAz, (x"+"y)"+"z = x"+"(y"+"z)`
Il faut étendre l'opérateur `"*"` sans perte d'information c'est à dire en une application potentiellement réversible. L'approche la plus simple est vectorielle. Chaque composante va se comporter comme un opérateur. Autrement dit l'opération `"*"` est distributive à droite :
`AAxAAyAAz, (x"+"y)"*"z = x"*"z "+" y"*"z`
La structure résultante est une algèbre à deux opérations binaires, l'une étant ssociative, et l'autre étant distributive à droite sur la première :
`L = ("<" alpha , "*"(".,."), "+"(".,.") ">") / ( { {:( (x"+"y)"+"z = x"+"(y"+"z) ) , ( (x"+"y)"*"z = x"*"z"+" y"*"z ):} } )`
On impose une première restriction importante. Les termes possèdent un unique type, qui précise le type de chaque argument et le type du résultat, et dont la définition est un terme du langage `"<"Omlega,×(.,.),->(.,.)">"`. Ainsi Omega représente l'ensemble des termes du langage
On note ne s'intéresse qu'aux types d'opérateurs internes retournant un élément :
Opérateur interne unaire `L->L` `f(".")` Opérateur interne binaire `L"×"L->L` `f(".,.")` Opérateur interne ternaire `L"×"L"×"L->L` `f(".,.,.")` Opérateur interne multi-aire`>=`1 `L^"+"->L` `f("...")` Opérateur interne multi-aire`>=`2 `L"×"L^"+"->L` `f(".,...")` .Opérateur interne multi-aire`>=`3 `L"×"L"×"L^"+"->L` `f(".,.,...")`
Dans le langage monotype, l'opérateur peyt retourner un autre opérateur mais toujours du même type. Considérons des monotypes quelconques `A,B,C` c'est à dire appartenant au langage
Si le type est de la forme A -> B×C alors la fonction de ce type paut être séparé en une fonction de type A->B et une fonction de type A-> C. On peut donc supprimer ce genre de type ayant une séquence en sortie.
Si le type est de la forme A×B->C alors on peut l'identifier au type A->(B->C) en appliquant la currification.
Si le type est de la forme A×B en appliquant la currification.
Pour pouvoir utiliser le mécanisme d'unification de terme de complexité linéaire, on conçoit des opérateurs d'arité fixe, où d'arité d'arité variables supérieur à un entier non nul. On note les types d'opérateurs internes retournant un élément :
Opérateur interne unaire `L->L` `f(".")` Opérateur interne binaire `L"×"L->L` `f(".,.")` Opérateur interne ternaire `L"×"L"×"L->L` `f(".,.,.")` Opérateur interne multi-aire`>=`1 `L^"+"->L` `f("...")` Opérateur interne multi-aire`>=`2 `L"×"L^"+"->L` `f(".,...")` .Opérateur interne multi-aire`>=`3 `L"×"L"×"L^"+"->L` `f(".,.,...")`
Dans le langage monotype, l'opérateur peyt retourner un autre opérateur mais toujours du même type. Considérons des monotypes quelconques `A,B,C` c'est à dire appartenant au langage `"<"Omlega,×(.,.),->(.,.)">"`
Si le type est de la forme A -> B×C alors la fonction de ce type paut être séparé en une fonction de type A->B et une fonction de type A-> C. On peut donc supprimer ce genre de type ayant une séquence en sortie.
Si le type est de la forme A×B->C alors on peut l'identifier au type A->(B->C) en appliquant la currification.
Si le type est de la forme A×B en appliquant la currification.
C'est un langage `L` dans lequel chaque terme est typé. Ou les types sont des termes du langage `"<" L , ->(".,.") ">"` où `L` est pris comme un élément désignant l'ensemble des termes du langage `L`. On note le monotype en exposant des élémets générateurs. Par exemple :
L= <e^(L->L->L
. C'est le langage engendré par un unique opérateur `alpha` qui est d'arité variable, et qui respecte les deux axiomes suivants :
`alpha` est un terme.
Tout terme `x` peut s'appliquer à une séquence non vide de termes `y_1,y_2,...y_n` pour former par emboitement le terme `x(y_1,y_2,...y_n)`.
---- 11 août 2026 ----
On appelle une concrétisation, l'association à un élément de `L` d'une d'application de `L->L` différente de celle définie par le langage alpha, et qui définit son second rôle. L'absence de second rôle correspond à l'application définie par le langage alpha. Sans concrétisation, chaque terme distinct désigne un élément distinct et la structure est libre. Mais dès qu'une concrétisation à lieu, par exemple :
`alpha(alpha(alpha)) = alpha`
Cela entraine une succession d'égalité entre d'autres alpha-termes. On traduit l'équation dans le magma associé : `alpha"*"(alpha"*"alpha) = alpha` et la structure résutante se note sous forme d'un quotient du magma libre par la relation d'équivalence induite par cette égalité :
`("<"L,"*>")/("{"alpha"*"(alpha"*"alpha) "=" alpha"}")`
La relation d'équivalence est définit par `x"~"y` si et seulement si `T|--x"="y` où `T "=" {alpha(alpha(alpha)) "=" alpha}`
Considérons le langage `L"=<"a,f("."),g(".,.")">"`. Chaque opérateur `a,f("."),g(".,.")` est en faite une application respectivement nullaire, unaire, binaire, vers l'ensemble des termes, car les opérateurs sont internes.
On définie un premier opérateur spécial, qui est unaire et de syntaxe prefixe qui force l'évaluation du terme sur lequel il est appliqué, mais d'une façon superficiellement sans évaluer ses arguments. Par exemple considérons la définition de l'opérateur g, une définition qui constitue sont deuxième rôle :
`g = ((x,y)|->g(f(y),f(x))`
L'opérateur spéciale `"§"` va forcer immédiatement l'évaluation superficielle du terme. Par exemple :
`§g(x,y) = g(f(y),f(x))`
Il ne s'agit pas d'une simple égalité, le terme §g(x,y) est immédiatement remplacé par le terme g(f(y),f(x)). L'opérateur spéciale peut s'appliquer plusieurs fois, ainsi :
`§§g(x,y) = g(f(f(x)),f(f(y)))`
Pour tout terme `x`, on désigne par `§x` le terme évalué. L'évaluation du terme consiste à appliquer la racine du terme sur ses arguments sans préalablement les évaluer, et d'en retrouner l'image. Lorsque l'opérateur racine n'a pas de définition, cela consiste à retourner le terme constituant l'appel. Autrement dit, les définitions par défaut sont :
`a = (|->a)`
`f = (x|->f(x))`
`g = ((x,y)|->g(x,y))`
La concrétisation de la structure passe par définir une autre application autre que celle par défaut pour un de ses éléments. Par exemple :
`g = ((x,y)|->g(f(y),f(x))`
Apparait alors deux niveaux d'interprétation qui dans le cas des définitions d'application par défaut, est identique :
Lorsque les définitions d'application ne sont pas par defaut, considérons par exemple l'application `b = (x|->g(x,a))` où `b` n'est pas forcement un élément de `L`, il y a deux modes d'appel : le mode impératif, noté préfixé par `§` où l'appel de b est évalué et se substitue par son résultat, et le mode libre où l'appel de `b` retourne le terme constitué par cette emboitement et qui appartient à la structure étendue `L[b(".")]`
Ainsi `b(f(a))` sera mémorisé `b(f(a))`, tandis que `§b(f(a))` sera mémorisé `g(f(a),a)`
On définit l'opérateur `varphi(".,.")` qui met en oeuvre l'axiom n°2. Il applique son premier argument qui est un terme, sur son second terme qui est une séquence non vides de termes, que l'on présente aussi sous une forme unaire qu'est l'application d'évaluation superficielle `§(".")`. Elle transforme un terme`x(y_1,y_2,...y_n)` en le résultat de `varphi("x,(y_1,y_2,...y_n))"`
Chaque opérateur `a,f("."),g(".,.")` est en faite une application respectivement nullaire, unaire, binaire, vers l'ensemble des termes, car les opérateurs sont internes. Pour tout terme `x`, on désigne par `§x` le terme évalué. L'évaluation du terme consiste à appliquer la racine du terme sur ses arguments sans préalablement les évaluer, et d'en retrouner l'image. Lorsque l'opérateur racine n'a pas de définition, cela consiste à retourner le terme constituant l'appel. Autrement dit, les définitions par défaut sont :
`a = (|->a)`
`f = (x|->f(x))`
`g = ((x,y)|->g(x,y))`
Exemple de définition :
`g = ((x,y)|->g(f(y),f(x))`
La notation ici n'est pas classique car la variable `x` contient un terme du langage récupéré lors de l'unification de l'appel, et que l'on n'évalue pas. De même pour la variable `y`. Ainsi par exemple `g(f(b),g(a,b))` retourne le terme `g(f(g(a,b)),f(f(b))` sans autre évaluation.
Si on définit un operateur binaire de syntaxe centré défini dans L[x] et produisant un opérateur unaire de L->L , alors le type de l'opérateur |-> est :
L×L->
`§g(vecx) = varphi(g,vecx)`
Cela permet de définir l'évaluation au sens classique où les arguments sont préalablement évalué au sens classique. Exemple :
`§g(vecx)=varphi(g, §vecx)`
Voici l'outils fait par ChatGPT : automates_langages_multisortes.py
---- 31 juillet 2026 ----