#!/usr/bin/env python3 # -*- coding: utf-8 -*- """ idioma_classe.py — La classe Idioma, avec termes générateurs. Un objet Idioma représente un système de langages algébriques, chacun présenté par ses TERMES GÉNÉRATEURS : des schémas de termes dont les feuilles peuvent être - un nom de langage (L, H, ou "." pour 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 strictement positif) : un terme quelconque de son langage, mais LE MÊME à chaque occurrence de la variable dans le schéma ; - un symbole littéral, éventuellement imbriqué : il appartient à la structure du schéma sans être un générateur autonome. Exemples : L = g exige deux arguments identiques K = engendre g(a,r(a)), g(f(a),r(f(a))) mais r(a) seul n'est pas un terme L'ancien formalisme est le cas particulier des schémas de profondeur 1 sans variable répétée. """ import re import random from itertools import product # ====================================================================== # Lexique commun # ====================================================================== _ANONYME = "T" # nom interne d'un langage présenté sans nom _IDENT = r"[A-Za-z_][A-Za-z_0-9]*" def _decoupe(chaine, avec_point=False): """Découpe une chaîne en lexèmes : identificateurs, ( ) , [.].""" motif = re.compile(_IDENT + (r"|[(),.]" if avec_point else r"|[(),]")) lexemes, pos = [], 0 while pos < len(chaine): if chaine[pos] in " \t\n": pos += 1 continue m = motif.match(chaine, pos) if not m: raise ValueError(f"caractère illisible {chaine[pos]!r} " f"dans {chaine!r}") lexemes.append(m.group(0)) pos = m.end() return lexemes def _lit_arbre(lexemes, i, avec_point=False): """ Lit un arbre symbole ou symbole(arbre, ..., arbre) à partir de la position i. Retourne (arbre, position) avec arbre = (symbole, tuple des enfants). Le lexème "." est admis comme feuille si avec_point. """ if i >= len(lexemes): raise ValueError("fin d'entrée : un terme était attendu") symbole = lexemes[i] if symbole in "(),": raise ValueError(f"symbole attendu, {symbole!r} trouvé") if symbole == "." and not avec_point: raise ValueError("'.' inattendu") i += 1 if i < len(lexemes) and lexemes[i] == "(": i += 1 enfants = [] while True: enfant, i = _lit_arbre(lexemes, i, avec_point) enfants.append(enfant) if i < len(lexemes) and lexemes[i] == ",": i += 1 continue if i < len(lexemes) and lexemes[i] == ")": return (symbole, tuple(enfants)), i + 1 raise ValueError("',' ou ')' attendu") return (symbole, ()), i # ====================================================================== # Analyse des présentations : les termes générateurs # ====================================================================== # Un schéma est un arbre dont les noeuds sont : # ("op", symbole, (enfants...)) symbole littéral du schéma # ("sorte", langage) feuille : terme quelconque # ("var", langage, nom) feuille : variable partagée # ====================================================================== def _analyse_presentation_brute(presentation): """Retourne (nom_du_langage, [arbres bruts des schémas]).""" m = re.match(r"\s*(?:(" + _IDENT + r")\s*=\s*)?<(.*)>\s*$", presentation, re.DOTALL) if not m: raise ValueError(f"Présentation illisible : {presentation!r}") langage = m.group(1) or _ANONYME lexemes = _decoupe(m.group(2), avec_point=True) arbres, i = [], 0 while i < len(lexemes): if lexemes[i] == ",": i += 1 continue arbre, i = _lit_arbre(lexemes, i, avec_point=True) arbres.append(arbre) if not arbres: raise ValueError(f"Le langage {langage} n'a aucun terme générateur.") return langage, arbres def _variable_de(symbole, langues): """Le langage dont `symbole` est une variable muette, sinon None.""" for lg in langues: if re.fullmatch(re.escape(lg) + r"[1-9][0-9]*", symbole): return lg return None def _classe_schema(arbre, courant, langues): """ Transforme un arbre brut en schéma : classe chaque feuille en sorte / variable / littéral, et vérifie les noeuds appliqués. """ symbole, enfants = arbre if enfants: # noeud appliqué : littéral if symbole in langues: raise ValueError(f"Le nom de langage {symbole!r} ne peut être " f"appliqué à des arguments.") if _variable_de(symbole, langues): raise ValueError(f"{symbole!r} a la forme d'une variable " f"muette : nom de symbole interdit.") return ("op", symbole, tuple(_classe_schema(e, courant, langues) for e in enfants)) if symbole == ".": return ("sorte", courant) if symbole in langues: return ("sorte", symbole) lg = _variable_de(symbole, langues) if lg is not None: return ("var", lg, symbole) return ("op", symbole, ()) # constante littérale def _schema_en_chaine(schema): """Écriture canonique d'un schéma (sert de nom de règle).""" genre = schema[0] if genre == "sorte": return schema[1] if genre == "var": return schema[2] _, symbole, enfants = schema if not enfants: return symbole return f"{symbole}({','.join(_schema_en_chaine(e) for e in enfants)})" def _qualification(ecrit, langues): """ Si `ecrit` est un nom long Langage_operateur, retourne le couple (langage, operateur) ; sinon None. Les noms de langages étant sans '_', le langage est la partie avant le premier '_'. """ if "_" not in ecrit: return None prefixe, _, suite = ecrit.partition("_") if prefixe in langues and re.fullmatch(_IDENT, suite): return prefixe, suite return None def _identite(ecrit, courant, langues, operateurs): """ L'identité complète d'un symbole écrit `ecrit` dans un schéma du langage `courant`, en tête (tete=...) ou imbriqué : (langage, nom) opérateur du langage (None, nom) pièce du système Un nom long désigne l'opérateur d'un autre langage ; un nom court désigne un opérateur du langage courant s'il en est un, une pièce sinon. """ q = _qualification(ecrit, langues) if q is not None: return q if ecrit in operateurs.get(courant, ()): return (courant, ecrit) return (None, ecrit) def _stats_schema(schema): """ (c, indep, variables) où c est le nombre de symboles littéraux du schéma, indep la liste (ordre de lecture) des sortes des feuilles indépendantes, variables le dict {nom: (sorte, occurrences)}. """ c, indep, variables = 0, [], {} def parcours(n): nonlocal c if n[0] == "op": c += 1 for e in n[2]: parcours(e) elif n[0] == "sorte": indep.append(n[1]) else: _, sorte, nom = n variables[nom] = (sorte, variables.get(nom, (sorte, 0))[1] + 1) parcours(schema) return c, indep, variables def _analyse_systeme(presentations): """ Analyse un système de présentations en termes générateurs. Retourne (systeme, operateurs, pieces) : systeme { langage : [schémas] } operateurs { langage : ensemble des opérateurs du langage } (les têtes courtes de ses termes générateurs) pieces ensemble des pièces du système (symboles imbriqués qui ne sont opérateurs d'aucun langage) après vérifications : noms sans collision, noms longs valides, arités cohérentes par identité, langages tous habités. """ brutes = [] for p in presentations: langage, arbres = _analyse_presentation_brute(p) if langage == _ANONYME and len(presentations) > 1: raise ValueError("Une présentation anonyme n'est admise que " "seule ; nommez les langages du système.") if any(langage == lg for lg, _ in brutes): raise ValueError(f"Le langage {langage} est présenté deux fois.") brutes.append((langage, arbres)) langues = [lg for lg, _ in brutes] # -- noms de langages : sans '_' (réservé aux noms longs), sans # collision avec les variables muettes ----------------------------- for lg in langues: if "_" in lg: raise ValueError(f"Le nom de langage {lg!r} contient '_', " f"réservé aux noms longs Langage_operateur.") for lg1 in langues: for lg2 in langues: if lg1 != lg2 and _variable_de(lg2, [lg1]): raise ValueError( f"Les langages {lg1} et {lg2} sont en collision : " f"{lg2} a la forme d'une variable muette de {lg1}.") systeme = {} for langage, arbres in brutes: schemas = [_classe_schema(a, langage, langues) for a in arbres] for s in schemas: if s[0] != "op": raise ValueError( f"Le terme générateur {_schema_en_chaine(s)!r} de " f"{langage} est réduit à une sorte ou une variable : " f"il doit comporter au moins un symbole.") systeme[langage] = schemas # -- opérateurs de chaque langage : les têtes courtes ------------------- operateurs = {lg: set() for lg in langues} for langage, schemas in systeme.items(): for s in schemas: if _qualification(s[1], langues) is None: operateurs[langage].add(s[1]) # -- validation des noms longs, arités par identité, pièces, # emprunts -------------------------------------------------------------- arites = {} # identité (langage|None, nom) -> arité pieces = set() empruntes = {lg: {} for lg in langues} # {nom: {langages d'origine}} def verifie(n, courant, en_tete): if n[0] != "op": return _, ecrit, enfants = n q = _qualification(ecrit, langues) if q is not None: autre, nom = q if nom not in operateurs[autre]: raise ValueError( f"Le nom long {ecrit!r} désigne l'opérateur {nom!r} " f"du langage {autre}, qui ne le possède pas " f"(opérateurs de {autre} : " f"{sorted(operateurs[autre])}).") if autre != courant: empruntes[courant].setdefault(nom, set()).add(autre) ident = _identite(ecrit, courant, langues, operateurs) if ident[0] is None and not en_tete: pieces.add(ident[1]) if ident in arites and arites[ident] != len(enfants): proprietaire = ident[0] or "pièce du système" raise ValueError( f"Le symbole {ident[1]!r} ({proprietaire}) apparaît avec " f"les arités {arites[ident]} et {len(enfants)}.") arites[ident] = len(enfants) for e in enfants: verifie(e, courant, False) for langage, schemas in systeme.items(): for s in schemas: verifie(s, langage, True) # -- résolution contextuelle des noms courts : 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 du système ------------------------------------------ resolution = {} # {C: {nom: identité}} for C in langues: res = {} for y in operateurs[C]: res[y] = (C, y) for y, origines in empruntes[C].items(): if y not in res and len(origines) == 1 and y not in pieces: res[y] = (next(iter(origines)), y) for y in pieces: res.setdefault(y, (None, y)) resolution[C] = res # -- raccourcis par langage : le nom long se réécrit en nom court # dans tout contexte où le nom court le désigne sans ambiguïté -------- raccourcis = {C: {} for C in langues} for C in langues: for y in operateurs[C]: raccourcis[C][f"{C}_{y}"] = y for y, ident in resolution[C].items(): if ident[0] not in (None, C): raccourcis[C][f"{ident[0]}_{y}"] = y # -- normalisation : les noms longs raccourcissables du contexte # sont réécrits ; les termes générateurs devenus identiques sont # fusionnés (l'énumération ne répète alors aucun terme) --------------- def normalise(n, courant): if n[0] != "op": return n _, ecrit, enfants = n ecrit = raccourcis[courant].get(ecrit, ecrit) return ("op", ecrit, tuple(normalise(e, courant) for e in enfants)) for langage in systeme: vus, uniques = set(), [] for s in systeme[langage]: s = normalise(s, langage) if s not in vus: vus.add(s) uniques.append(s) systeme[langage] = uniques # -- habitation : point fixe croissant ---------------------------------- habites = set() progres = True while progres: progres = False for langage, schemas in systeme.items(): if langage in habites: continue for s in schemas: _, indep, variables = _stats_schema(s) sortes = list(indep) + [v[0] for v in variables.values()] if all(x in habites for x in sortes): habites.add(langage) progres = True break vides = set(systeme) - habites if vides: raise ValueError(f"Langage(s) vide(s), aucun terme constructible : " f"{sorted(vides)}") return systeme, operateurs, pieces, empruntes, resolution # ====================================================================== # Petits utilitaires # ====================================================================== def _compositions_ponderees(n, poids): """ Tuples (s_1, ..., s_k), s_i >= 1, tels que somme(poids_i * s_i) = n : les répartitions d'un budget de taille entre les trous d'un schéma, une variable à p occurrences pesant p fois sa taille. """ if not poids: if n == 0: yield () return w = poids[0] if len(poids) == 1: if n >= w and n % w == 0: yield (n // w,) return minimum_restant = sum(poids[1:]) s = 1 while w * s <= n - minimum_restant: for suite in _compositions_ponderees(n - w * s, poids[1:]): yield (s,) + suite s += 1 def _rayon_spectral(M, iterations=2000): """Rayon spectral d'une matrice positive (itération de la puissance).""" d = len(M) v = [1.0] * d rho = 0.0 for _ in range(iterations): w = [sum(M[i][j] * v[j] for j in range(d)) for i in range(d)] norme = max(abs(x) for x in w) if norme == 0.0: return 0.0 rho, v = norme, [x / norme for x in w] return rho def _resoudre(A, b): """Résout A x = b par élimination de Gauss (petits systèmes).""" d = len(b) M = [ligne[:] + [b[i]] for i, ligne in enumerate(A)] for c in range(d): pivot = max(range(c, d), key=lambda r: abs(M[r][c])) if abs(M[pivot][c]) < 1e-12: raise ValueError("Système singulier.") M[c], M[pivot] = M[pivot], M[c] for r in range(d): if r != c: coef = M[r][c] / M[c][c] M[r] = [M[r][k] - coef * M[c][k] for k in range(d + 1)] return [M[i][d] / M[i][i] for i in range(d)] class _ProfondeurDepassee(Exception): """Tirage : la récursion excède le garde-fou de profondeur.""" # ====================================================================== # La classe Idioma # ====================================================================== class Idioma: """ Un système de langages algébriques présentés par termes générateurs, et les trois parcours de ses automates : reconnaissance par filtrage, énumération, génération aléatoire. >>> I = Idioma("L = ") >>> I("g(f(a), f(a))") True >>> I("g(a, f(a))") # arguments distincts : rejeté False >>> K = Idioma("K = ") >>> K("g(f(a), r(f(a)))") True >>> K("r(a)") # r n'est pas un générateur autonome False """ # ------------------------------------------------------------------ # Construction # ------------------------------------------------------------------ def __init__(self, *presentations): if not presentations: raise ValueError("Il faut au moins une présentation.") (self.systeme, self._operateurs, self._pieces, self._empruntes, self._resolution) = _analyse_systeme(presentations) self._ordre = sorted(self.systeme) self._stats = {lg: [_stats_schema(s) for s in schemas] for lg, schemas in self.systeme.items()} self._strates = {} # mémo énumération : (langage, n) self.probabilites = None # posées par probabilise() self._tirage = None self.profondeur_max = 500 self.alea = random.Random() def _langage(self, langage): if langage is not None: if langage not in self.systeme: raise ValueError(f"Langage inconnu : {langage!r} " f"(langages du système : {self._ordre})") return langage if len(self.systeme) == 1: return next(iter(self.systeme)) raise ValueError(f"Le système compte plusieurs langages " f"{self._ordre} : précisez lequel est visé.") @property def langages(self): """Les langages du système.""" return list(self._ordre) def regles(self, langage=None): """Les termes générateurs du langage visé, en écriture canonique.""" langage = self._langage(langage) return [_schema_en_chaine(s) for s in self.systeme[langage]] def operateurs(self, langage=None): """ Les opérateurs du langage visé : les têtes (en nom court) de ses termes générateurs. Un générateur coiffé d'un nom long emprunte l'opérateur d'un autre langage sans l'ajouter ici. """ langage = self._langage(langage) return sorted(self._operateurs[langage]) def pieces(self): """ Les pièces du système : les symboles imbriqués dans des termes générateurs sans être opérateurs d'aucun langage. """ return sorted(self._pieces) def empruntes(self, langage=None): """ Les opérateurs qu'emprunte le langage visé, avec leur provenance : {nom_court: [langages d'origine]}. Ils s'écrivent en nom court dans les termes dès que celui-ci est sans ambiguïté dans le système. """ langage = self._langage(langage) return {nom: sorted(origines) for nom, origines in sorted(self._empruntes[langage].items())} # ------------------------------------------------------------------ # I. Reconnaissance — le filtrage contre les termes générateurs # ------------------------------------------------------------------ def _arbre(self, chaine): """Analyse une chaîne en arbre (symbole, enfants).""" lexemes = _decoupe(chaine) arbre, fin = _lit_arbre(lexemes, 0) if fin != len(lexemes): raise ValueError("entrée en excès après le terme") return arbre def _identite_ctx(self, langage, ecrit): """L'identité désignée par l'écriture `ecrit` dans le contexte du langage : nom long explicite, sinon résolution contextuelle du nom court.""" q = _qualification(ecrit, self._ordre) if q is not None: return q return self._resolution[langage].get(ecrit, (None, ecrit)) def _ecritures(self, langage, ecrit): """ Les écritures admises, dans un terme, du symbole écrit `ecrit` dans un schéma du langage : le nom long toujours, le nom court quand le contexte le résout vers cette même identité ; une pièce n'a que son nom. """ proprietaire, nom = self._identite_ctx(langage, ecrit) if proprietaire is None: return (nom,) # pièce du système admises = [f"{proprietaire}_{nom}"] if self._resolution[langage].get(nom) == (proprietaire, nom): admises.append(nom) # court non ambigu return tuple(admises) def _reconnait_arbre(self, arbre, langage): """ L'automate du langage : l'arbre est un terme du langage s'il est une variable muette du langage, ou s'il se filtre contre l'un de ses termes générateurs. Retourne le terme RÉSOLU EN IDENTITÉS — chaque symbole remplacé par son identité (langage, nom), (None, nom) pour une pièce, ('var', nom) pour une variable muette — ou None si l'arbre n'est pas un terme du langage. C'est sur ces termes résolus que se juge l'égalité des variables : f(a) et L_f(a) y sont un seul et même terme. """ symbole, enfants = arbre if not enfants and _variable_de(symbole, [langage]): return (("var", symbole), ()) # variable muette for schema in self.systeme[langage]: # parcours des règles resolu = self._filtre(schema, arbre, {}, langage) if resolu is not None: return resolu return None def _filtre(self, schema, arbre, liaison, courant): """ Filtrage de l'arbre contre le schéma, lu dans le langage `courant` (qui résout l'identité des symboles courts). `liaison` lie chaque variable du schéma au sous-arbre de sa première occurrence ; les occurrences suivantes exigent l'égalité syntaxique. """ genre = schema[0] if genre == "op": # structure littérale _, ecrit, enfants_s = schema symbole, enfants_a = arbre if symbole not in self._ecritures(courant, ecrit) \ or len(enfants_a) != len(enfants_s): return None resolus = [] for es, ea in zip(enfants_s, enfants_a): r = self._filtre(es, ea, liaison, courant) if r is None: return None resolus.append(r) return (self._identite_ctx(courant, ecrit), tuple(resolus)) if genre == "sorte": # terme quelconque : return self._reconnait_arbre(arbre, schema[1]) # appel récursif _, sorte, nom = schema # variable partagée resolu = self._reconnait_arbre(arbre, sorte) if resolu is None: return None if nom in liaison: # égalité des termes return resolu if liaison[nom] == resolu else None # résolus liaison[nom] = resolu return resolu def reconnait(self, chaine, langage=None): """True si `chaine` est un terme du langage visé.""" langage = self._langage(langage) try: arbre = self._arbre(chaine) except ValueError: return False return self._reconnait_arbre(arbre, langage) is not None def __call__(self, chaine, langage=None): return self.reconnait(chaine, langage) def variables(self, chaine, langage=None): """ Les variables muettes du terme, rangées par langage : {langage: liste triée}. Lève ValueError si la chaîne n'est pas un terme du langage visé. """ langage = self._langage(langage) arbre = self._arbre(chaine) if self._reconnait_arbre(arbre, langage) is None: raise ValueError(f"{chaine!r} n'est pas un terme du langage " f"{langage}.") vues = {} def collecte(n): symbole, enfants = n if not enfants: lg = _variable_de(symbole, self._ordre) if lg is not None: vues.setdefault(lg, set()).add(symbole) for e in enfants: collecte(e) collecte(arbre) return {lg: sorted(vs) for lg, vs in sorted(vues.items())} def est_clos(self, chaine, langage=None): """True si le terme est clos (sans variable muette).""" return not any(self.variables(chaine, langage).values()) # ------------------------------------------------------------------ # II. Énumération — les termes générateurs en génération exhaustive # ------------------------------------------------------------------ @staticmethod def _instancie(schema, indep, var_map): """Écrit l'instance du schéma, les trous remplis par les chaînes de `indep` (itérateur, ordre de lecture) et `var_map`.""" genre = schema[0] if genre == "sorte": return next(indep) if genre == "var": return var_map[schema[2]] _, symbole, enfants = schema if not enfants: return symbole return (symbole + "(" + ",".join(Idioma._instancie(e, indep, var_map) for e in enfants) + ")") def termes(self, n, langage=None): """Liste des termes clos du langage visé, de taille exactement n (taille : nombre de symboles, une variable à p occurrences comptant p fois la taille du terme qui l'instancie).""" langage = self._langage(langage) if n < 1: return [] if (langage, n) in self._strates: return self._strates[(langage, n)] strate = {} # dict : dédoublonnage for schema, (c, indep, variables) in zip(self.systeme[langage], self._stats[langage]): noms = sorted(variables) poids = [1] * len(indep) + [variables[nom][1] for nom in noms] for tailles in _compositions_ponderees(n - c, poids): t_indep = tailles[:len(indep)] t_vars = tailles[len(indep):] listes = ([self.termes(ti, sorte) # appels récursifs for sorte, ti in zip(indep, t_indep)] + [self.termes(tv, variables[nom][0]) for nom, tv in zip(noms, t_vars)]) for choix in product(*listes): var_map = dict(zip(noms, choix[len(indep):])) t = self._instancie(schema, iter(choix[:len(indep)]), var_map) strate[t] = None strate = list(strate) self._strates[(langage, n)] = strate return strate def iterer(self, langage=None): """Énumère tous les termes clos du langage visé, par taille croissante ; équitable : chaque terme apparaît une fois.""" langage = self._langage(langage) n = 1 while True: for terme in self.termes(n, langage): yield terme n += 1 def premiers(self, m, langage=None): """Les m premiers termes de l'énumération du langage visé.""" resultat = [] for terme in self.iterer(langage): resultat.append(terme) if len(resultat) == m: return resultat return resultat def compte(self, n, langage=None): """Nombre de termes clos du langage visé de taille exactement n.""" return len(self.termes(n, langage)) # ------------------------------------------------------------------ # III. Génération aléatoire — les termes générateurs aux dés # ------------------------------------------------------------------ def probabilise(self, probabilites, profondeur_max=500, graine=None): """ Munit chaque terme générateur d'une probabilité. `probabilites` : {langage: {règle: proba}} — ou, pour un seul langage, directement {règle: proba}. Une règle se désigne par son écriture canonique ("g(L1,L1)") ou, si c'est sans ambiguïté, par son symbole de tête ("g"). Chaque table doit sommer à 1. Retourne self (chaînable). """ if len(self.systeme) == 1 and probabilites and \ not isinstance(next(iter(probabilites.values())), dict): probabilites = {next(iter(self.systeme)): probabilites} if set(probabilites) != set(self.systeme): raise ValueError( f"Il faut une table de probabilités par langage : " f"attendus {self._ordre}, reçus {sorted(probabilites)}.") validees = {} for langage, table in probabilites.items(): schemas = self.systeme[langage] noms = [_schema_en_chaine(s) for s in schemas] tetes = {} # tête -> nom si unique for s, nom in zip(schemas, noms): tetes.setdefault(s[1], []).append(nom) correspondance = {} for cle in table: if cle in noms: nom = cle elif cle in tetes and len(tetes[cle]) == 1: nom = tetes[cle][0] else: raise ValueError( f"{langage} : règle inconnue ou ambiguë {cle!r} " f"(règles : {noms})") if nom in correspondance.values(): raise ValueError(f"{langage} : la règle {nom!r} reçoit " f"deux probabilités.") correspondance[cle] = nom normalisee = {correspondance[cle]: p for cle, p in table.items()} manquantes = set(noms) - set(normalisee) if manquantes: raise ValueError(f"{langage} : probabilité absente pour " f"{sorted(manquantes)}") if any(p < 0 for p in normalisee.values()): raise ValueError(f"{langage} : probabilités négatives.") total = sum(normalisee.values()) if abs(total - 1.0) > 1e-9: raise ValueError(f"{langage} : les probabilités doivent " f"sommer à 1 (somme = {total}).") validees[langage] = normalisee self.probabilites = validees self.profondeur_max = profondeur_max self.alea = random.Random(graine) self._tirage = {} for langage in self._ordre: noms = [_schema_en_chaine(s) for s in self.systeme[langage]] self._tirage[langage] = ( list(range(len(noms))), [validees[langage][nom] for nom in noms]) return self def _exiger_probabilites(self): if self.probabilites is None: raise ValueError("Appelez d'abord probabilise({...}) pour munir " "les termes générateurs de probabilités.") def _terme_tire(self, langage, profondeur): if profondeur > self.profondeur_max: raise _ProfondeurDepassee indices, poids = self._tirage[langage] k = self.alea.choices(indices, weights=poids)[0] schema = self.systeme[langage][k] _, indep, variables = self._stats[langage][k] choix_indep = [self._terme_tire(sorte, profondeur + 1) # un tirage for sorte in indep] # par trou var_map = {nom: self._terme_tire(sorte, profondeur + 1) for nom, (sorte, _) in sorted(variables.items())} return self._instancie(schema, iter(choix_indep), var_map) # une variable n'est tirée qu'une fois puis dupliquée def tirer(self, langage=None): """Engendre au hasard un terme clos du langage visé ; les tirages excédant le garde-fou sont recommencés.""" self._exiger_probabilites() langage = self._langage(langage) while True: try: return self._terme_tire(langage, 0) except _ProfondeurDepassee: continue def echantillon(self, m, langage=None): """Engendre m termes du langage visé au hasard.""" return [self.tirer(langage) for _ in range(m)] # -- analyse de terminaison et de taille -------------------------------- def matrice_moyenne(self, genre="tirages"): """ M[S,S'] : nombre moyen, par règle tirée en S, de - genre="tirages" : tirages ouverts en S' (une variable ne compte qu'une fois) — gouverne la TERMINAISON ; - genre="occurrences" : occurrences de S' dans l'instance (une variable à p occurrences compte p fois) — gouverne la TAILLE. """ self._exiger_probabilites() if genre not in ("tirages", "occurrences"): raise ValueError("genre : 'tirages' ou 'occurrences'.") d = len(self._ordre) indice = {lg: i for i, lg in enumerate(self._ordre)} M = [[0.0] * d for _ in range(d)] for S in self._ordre: for schema, (c, indep, variables) in zip(self.systeme[S], self._stats[S]): p = self.probabilites[S][_schema_en_chaine(schema)] for sorte in indep: M[indice[S]][indice[sorte]] += p for sorte, occ in variables.values(): M[indice[S]][indice[sorte]] += \ p * (1 if genre == "tirages" else occ) return M def rayon(self, genre="tirages"): """Rayon spectral de la matrice de moyennes du genre demandé.""" return _rayon_spectral(self.matrice_moyenne(genre)) def regime(self): """Régime de terminaison, lu sur la matrice des tirages.""" rho = self.rayon("tirages") if rho < 1 - 1e-9: return "sous-critique" if rho > 1 + 1e-9: return "sur-critique" return "critique" def tailles_moyennes(self): """ Taille moyenne du terme tiré, par langage de départ : le vecteur T solution de T = C + M_occurrences * T, où C[S] est le nombre moyen de symboles littéraux d'une règle tirée en S. Infini si rho(M_occurrences) >= 1 — ce qui peut arriver alors même que la génération termine (duplication des variables). """ self._exiger_probabilites() if self.rayon("occurrences") >= 1 - 1e-9: return {lg: float("inf") for lg in self._ordre} M = self.matrice_moyenne("occurrences") d = len(self._ordre) C = [] for S in self._ordre: C.append(sum(self.probabilites[S][_schema_en_chaine(sch)] * c for sch, (c, _, _) in zip(self.systeme[S], self._stats[S]))) A = [[(1.0 if i == j else 0.0) - M[i][j] for j in range(d)] for i in range(d)] return dict(zip(self._ordre, _resoudre(A, C))) # ------------------------------------------------------------------ # Affichage # ------------------------------------------------------------------ def __repr__(self): lignes = [] for langage in self._ordre: regles = ", ".join( "|--" + _schema_en_chaine(s) + (f" [{self.probabilites[langage][_schema_en_chaine(s)]:g}]" if self.probabilites else "") for s in self.systeme[langage]) lignes.append(f"automate {langage} : {{{regles}}}") return "\n".join(lignes) # ====================================================================== # Programme principal # ====================================================================== SYNOPSIS = """ ====================================================================== 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 = ") K = Idioma("K = ") S = Idioma("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. 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 = ") 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 = ", "H = ") 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=", "H=", "K=") 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 = ", "H = ") 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 a 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 = ")("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 = ").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("") (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 = ), 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, 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]) 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, 51 5. 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-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) < 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 Idioma(pres1 [,pres2, ...]) construction, vérifiée .langages .regles([lg]) consulter le système .operateurs([lg]) .pieces() opérateurs et pièces .empruntes([lg]) emprunts et provenance .reconnait(t [,lg]) / I(t [,lg]) reconnaissance .variables(t [,lg]) .est_clos(t [,lg]) .termes(n [,lg]) .compte(n [,lg]) énumération par taille .premiers(m [,lg]) .iterer([lg]) .probabilise(p [,profondeur_max] [,graine]) -> self .tirer([lg]) .echantillon(m [,lg]) tirages aléatoires .matrice_moyenne(genre) .rayon(genre) .regime() .tailles_moyennes() diagnostic de terminaison 7. 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 sous vos yeux. ====================================================================== """ if __name__ == "__main__": print(SYNOPSIS) # ------------------------------------------------------------------ print("--- 1. Contrainte d'égalité : g(L1,L1) contre g(L,L) ---\n") E = Idioma("L = ") D = Idioma("L = ") print(E) print(D, "\n") for t in ["g(a,a)", "g(f(a), f(a))", "g(a, f(a))", "g(g(a,a), g(a,a))", "g(L2,L2)", "g(L1,L2)"]: print(f" {t:<22} : " f"{'accepté' if E(t) else 'rejeté '} par g(L1,L1) " f"{'accepté' if D(t) else 'rejeté '} par g(L,L)") print("\nÉnumération — 8 premiers avec g(L1,L1) :", ", ".join(E.premiers(8))) print("Énumération — 8 premiers avec g(L,L) :", ", ".join(D.premiers(8))) print("Comptage par taille (1..7), g(L1,L1) :", ", ".join(str(E.compte(n)) for n in range(1, 8))) print("Comptage par taille (1..7), g(L,L) :", ", ".join(str(D.compte(n)) for n in range(1, 8))) # ------------------------------------------------------------------ print("\n--- 2. Schéma profond : K = ---\n") K = Idioma("K = ") print(K, "\n") for t in ["g(a, r(a))", "g(f(a), r(f(a)))", "g(f(a), r(a))", "r(a)", "g(a, a)", "f(g(a, r(a)))"]: print(f" {'accepté' if K(t) else 'rejeté '} : {t}") print("\nLes 8 premiers termes de K :", ", ".join(K.premiers(8))) # ------------------------------------------------------------------ print("\n--- 3. Opérateurs, pièces et noms longs ---\n") P = Idioma("L = ") print(P) print(f" opérateurs de L : {P.operateurs()} pièces : {P.pieces()}\n") Q = Idioma("L = ", "H = ") print(Q) print(f" opérateurs de L : {Q.operateurs('L')} " f"de H : {Q.operateurs('H')} pièces : {Q.pieces()}") for lg, t in [("L", "H_f(a)"), ("L", "f(a)"), ("L", "f(e)"), ("H", "f(e)"), ("L", "g(a, r(b))"), ("H", "r(a)")]: print(f" {'accepté' if Q(t, lg) else 'rejeté '} dans {lg} : {t}") print(" règles de L (écriture courte) :", Q.regles("L")) print(" emprunts de L :", Q.empruntes("L")) print(" premiers de L :", ", ".join(Q.premiers(5, "L"))) W = Idioma("L = ", "H = ") print("\n" + str(W)) print(f" a = L_a : accepté dans L et dans H sous la même écriture : " f"{W('a','L')} et {W('a','H')}") print(" premiers de H :", ", ".join(W.premiers(4, "H"))) S3 = Idioma("L = ") print(f" f = L_f jusque dans l'égalité : " f"g(f(a), L_f(a)) accepté : {S3('g(f(a), L_f(a))')}") # ------------------------------------------------------------------ print("\n--- 4. L'ancien formalisme reste un cas particulier ---\n") S = Idioma("L = ", "H = ") print(S, "\n") essais = [("L", "g(j(e,e), f(e))"), ("L", "f(a)"), ("L", "g(H1, L1)"), ("H", "k(H1, f(H2), H1)")] for lg, t in essais: print(f" {'accepté' if S(t, lg) else 'rejeté '} dans {lg} : {t}") # ------------------------------------------------------------------ print("\n--- 5. Hasard : terminaison contre taille ---\n") E.probabilise({"a": 0.5, "f": 0.3, "g": 0.2}, graine=2026) print(f"{E}\n") print(f"rayon(tirages) = {E.rayon('tirages'):.3f} ({E.regime()})") print(f"rayon(occurrences) = {E.rayon('occurrences'):.3f}") tailles = E.tailles_moyennes() print(f"taille moyenne théorique : {tailles['L']:.3f}") def taille(t): return len(re.findall(_IDENT, t)) N = 10_000 moyenne = sum(taille(t) for t in E.echantillon(N)) / N print(f"taille moyenne observée ({N} tirages) : {moyenne:.3f}") print("trois tirages :", ", ".join(E.echantillon(3))) print("\nEn poussant g : {a:.42, f:.08, g:.5} — tirages sous-critiques," "\noccurrences sur-critiques : la duplication gonfle les termes") E2 = Idioma("L = ").probabilise( {"a": 0.42, "f": 0.08, "g": 0.5}, graine=2026) print(f" rayon(tirages) = {E2.rayon('tirages'):.3f} ({E2.regime()})," f" rayon(occurrences) = {E2.rayon('occurrences'):.3f}," f" tailles moyennes infinies : " f"{E2.tailles_moyennes()['L'] == float('inf')}") # ------------------------------------------------------------------ print("\n--- 6. Contrôles croisés internes ---\n") K.probabilise({"a": 0.5, "f": 0.3, "g(K1,r(K1))": 0.2}, graine=2026) ok = True for objet, nom in [(E, "L(egalite)"), (K, "K")]: ok &= all(objet(t) for t in objet.premiers(200)) ok &= all(objet(t) for t in objet.echantillon(200)) ok &= all(S(t, lg) for lg in S.langages for t in S.premiers(150, lg)) ok &= not any(S(t, "H") for t in S.premiers(50, "L")) print(f" termes énumérés et tirés tous reconnus, sortes " f"étanches : {ok}")