Dans une approche naïve, on peut penser qu'il existe une démarche constructive qui s'impose, amenant à la conception d'un langage informatique universel, la pierre philosophale des informaticiens. La voix en est l'ensemencement par les mathématiques qui ont déjà un langage universel et qui sont déjà ensemencés par l'informatique au point où de nombreux concepts informatiques se retrouvent en mathématiques et vice versa. Il suffit de prolonger cette fusion. Cela consiste en un langage de calcul formel généraliste. Le paradigme existe, il est là, à porté de main, nous en voyons les effets dans les différents langages de calcul formel qui se sont développés dans le monde du libre, et dans les démonstrations mathématiques qui ont recours de plus en plus à l'informatique. C'est en cherchant à chaque fois le caractère unique, la rainure qui réunit toutes ces démarches constructives en une seule construction que l'on découvrira cette pierre philosophale supposée. Et ce sera aussi celle des mathématiciens car ce langage informatique universel constituera un démonstrateur de théorème aux capacités démultipliées. Le mariage de l'informatique et de la logique produira un langage informatique universel. C'est le pari que nous faisons. Mais pour l'instant, nous sommes loin de produire un résultat unificateur. Il nous faut d'abord convaincre de nombreux homologues de vouloir développer ces langages de calcul formel en explorant ce paradigme, et cela se fait en proposant des éléments concrets. Pour ceux qui sont davantage théoricien que praticien, on pourra commencer à lire le livre de Gilles Dowek & Jean-Jacques Lévy "Introduction à la théorie des langages de programmation" qui explore les différents paradigmes programmatifs. Mais il est possible même pour des personnes non-initiés de tout-de-suite se plonger dans une telle construction, et c'est ce que nous allons faire pour en donner le goût.
La conception d'un langage de programmation idéal va de paire avec celle du compilateur qui peut le traduire en langage machine. Mais le langage machine n'est pas-du-tout pratique à utiliser. En appliquant l'adage linuxien suivant : "Tout problème complexe doit pouvoir se subdiviser en plusieurs problèmes plus simples", on voit qu'il est possible de passer par un langage intermédiaire, et donc de procéder à une première compilation transformant le langage idéal en ce langage intermédiaire, puis de compiler en suite ce dernier à l'aide d'un compilateur déjà existant et qui a fait ses preuves.
On choisie comme langage intermédiaire le langage Golang car il possède les mêmes qualités essentielles que le langage C avec lequel Linux a été programmé, tout en étant beaucoup plus pratique. Et si on s'intéresse non pas à des programmes mais à des shells et à l'aspect interpréteur, alors on choisie comme langage intermédiaire le langage de script Ruby utilisant le shell irb (Interactive Ruby Shell) qui est orienté objets et qui est beaucoup plus patique que le shell Bash propre à Linux. Nous souhaitons développer un compilateur universelle d'une façon progressive à partir de quelques éléments de programmation de base que nous offre un système d'exploitation Linux, et qui sont :
1- Le compilateur Golang
2- Le shell Ruby
Et on proposera des versions du plus simple compilateur jusqu'au plus évolué des compilateurs, tel le développement d'un organisme passant d'une mue à l'autre, se transformant par étape, pour acquérire des fonctionnalités nouvelles et mettre en oeuvre des mécanismes linguistiques nouveaux.
1- L'étude des langages formels nous propose comme première étape, le langage terminologique monotype, aussi appelé une terminologie monotype, composer d'opérateurs d'arité fixée se combinant en des compositions closes appelés termes. Et au départ on ne conçoit qu'un seul type d'argument appelé valeur. C'est le premier choix, une première étape incontournable dans l'appréhension des langages formels, la maitrise du langage terminologique monotype. Voir Logique. Un tel langage engendre une structure mathématique libre composé d'un unique ensemble sous-jacent puisque le langage est monotype.
2- Puis le langage se perfectionne pour utiliser des variables qui sont toutes de même type. Le langage devient déclaratif, introduisant la déclaration de variable, étendant ainsi le langage dans des sous-contextes qui s'emboitent, formant des arbres de contextes déclaratifs. La variable contient une valeur ou un terme qui doit être évalué en une valeur. La variable comme le terme peut produire un terme et nécessiter de réiterer l'évaluation. Le rapport à la logique est directe : Le langage engendre la structure libre, la variable constitue une extension libre de la structure.
3- Un terme représente un calcul produisant une valeur. Comme nous souhaitons optimiser la complexité des calculs, on ne peut pas rester sur un modèle de calcul ne proposant qu'un seul résultat à la foi. Le troisième choix sera une extension du langage terminologique permettant des séquences de valeurs comme résultat, et donc en donnant également un moyen pour ré-aiguiller arbitrairement ces valeurs dans les différentes entrées des opérateurs.
4- Les opérateurs peuvent être variable constituant des variables d'arité non-nulle, permettant ainsi de définir des applications. Puis ces opérateurs peuvent proposer d'abord une unification de la liste de leurs arguments avec un modèle, définissant ainsi des fonctions, et peuvent se définir par morceau. Comme le langage se veut monotype il ne peut y avoir de distinction syntaxique entre termes du langage, et donc tout terme est suceptible de s'appliquer à une séquence d'arguments pour produire une séquence d'arguments.
5- Le langage change de nature et devient le langage alpha monotype. Le langage se définit par une grammaire ou une axiomatique. Plusieurs choix de grammaire ou d'axiomatique sont possibles selon les propriétés que l'on exige.
6- Les opérateurs peuvent être compilés constituant alors des valeurs. Apparaît alors un langage de bas niveau que sont toutes ces valeurs obtenues par compilations et dont l'exécution se comporte comme un moteur de bas niveau de protocole, faisant que notre langage universel se construit sur un sous-langage de niveau de protocole plus bas.
7- Puis le concept de variable engendre celui de pointeur. La variable contient alors une valeur, un terme ou une addresse qui désigne soit une valeur, un terme ou encore une addresse, construisant ainsi une branche d'un arbre convergeant sur une racine qui sont toutes des valeurs ou des termes puisque nous sommes dans une terminologie monotype. Le septième choix est d'implémenter ces pointeurs qui permettront la conception de nombreux algorithmes de complexité linéaire.
8- Puis on ajoute les spécificitées propres à un shell que sont la gestion des processus, des mémoires partagées, et des canaux entre processus. Voir La machine vue par le haut. C'est le huitième choix, introduisant le concept de processus s'exécutant de façon concurrente aux autres processus et qui descend d'un processus père, et introduisant le concept de mémoire partagée entre plusieurs processus, et introduisant le concept de canal entre processus assurant le transfère de données d'un processus à un autre.
La variable s'identifie à un canal qui ne transmet et qui ne reçois qu'un seul terme ou qu'un seul pointeur ou qu'une seule valeur. La séquence d'argument peut également s'identifier à un canal qui en entrée reçoit les arguments (termes ou pointeurs ou valeur), et en sortie transmet les résultats (termes ou pointeurs ou valeur). Nous appellerons ce nouveau type de langage simplement un langage shell monotype alpha ou polonais.
9- Le langage que nous voulons définir est polymorphe c'est-à-dire qu'il change de forme en cours de route selon le contexte, pouvant ainsi toujours s'adapter au problème. C'est le neuvième choix majeur que nous ferons et qui consiste à déclarer des opérateurs constants qui peuvent masquer les précédant et à introduire une définition modifiable de leur syntaxe dans le contexte en cours. Et cela doit pouvoir s'établir par de simples instructions. D'où le caractère universelle prétendu de notre compilateur.
A chaque étape, le compilateur proposé doit constituer un outils pertinant, bien fait, bien programmé, utilisable telle quelle. Ainsi la construction n'est pas ingrate et motive ses auteurs. C'est là un point essentiel pour la faisabilité et la pérénité du projet de développement, voir développement holistique.
A chaque étape, se présentera un compilateur et son langage, de nom L, complété par un numéro d'étape noté en un seul chiffre. À certaine étapes majeur nous rencontrerons différents choix possibles exclusifs, formant une fourche dans l'évolution des versions et qui sera noté par une lettre majuscule A ou B, ou C... suivi par un numéro d'étape toujours noté en un seul chiffre, etc..., puis le tout pouvant être suivi par un trait d'union et un numéro de version de développement instable.
Pour faire les bons choix il convient évidement de préparer le terrain, d'explorer loin devant différentes notions et concepts afférents aux langages formels, d'entretenir une reflexion éclectique, ouverte, ce que nous faisons dans les discussions ci-dessous :
La terminologie se définit en énumérant les opérateurs générateurs qui doivent être d'arité fixe. Par exemple considérons le langage `E` de présentation suivante :
`a,b,f"(.)",g"(.,.)"`
La présentation est une séquence d'opérateurs générateurs du langage. Le suffixe `"(.)"` rappelle que l'opérateur est unaire, et le suffixe `"(.,.)"` que l'opérateur est binaire. Le langage `E` est l'ensemble des termes qu'il est possible de composer avec ces opérateurs répliqués autant de fois que l'on veut :
`E = {a,b,f(a),f(b),g(a,a),g(a,b),g(f(a),a),...,g(f(b),g(a,a)),...}`
On définie un meta-langage permettant de définir le langage. La liste des opérateurs entourés de crochet `"< >"` engendre l'ensemble des termes qu'il est possible de composer avec ces opérateurs répliqués autant de fois que l'on veut :
`E="<"a,b,f"(.)",g"(.,.)>"`
Vous remarquerez que dans ce métalangage les opérateurs énumérés peuvent soit être de nouveaux opérateurs qui initient ce que l'on appelle en mathématique une extension élémentaire qui est ici libre, ou soit être déjà définie dans le contexte. Une autre façon de définir le langage ce fait à l'aide d'une grammaire que l'on note sous forme d'une définition récurcive d'ensembles :
`E={a,b,f(E),g(E,E)}`
L'ensemble `E` désigne l'ensemble sous-jacent de la structure, et donne un moyen de construction de tous les termes du langage. Si `a,b,f("."),g(".,.")` sont de nouveaux éléments et n'ont donc pas de définition, alors `E` est une structure libre.
Afin que le langage exprime autre chose que lui-même, et d'en maitriser toute la liberté, on pose la distinction entre deux mondes, le monde du langage qui est l'ensemble des termes que l'on peut écrire, et le monde des valeurs qui peuvent être désignées par les termes. Le monde des valeurs désignées représente la structure. Le terme est le signifiant, la valeur qui constitue un élément est le signifié. Mais le terme désigne davantage qu'une valeur ou un élément, il désigne un procédé de calcul par composition d'opérateurs qui va produire cette valeur.
`a,b` sont des termes nucléïques et désignent des valeurs, et chaque terme désigne une valeur, et toutes les valeurs sont d'un seul type, c'est pourquoi le langage et dit monotype, et que la structure est basée sur un unique ensemble sous-jacent regroupant toutes les valeurs atteignables. Mais plus précisement, le terme désigne un calcul qui aboutit à cette valeur. Le terme nucléïque `a` fait partie du monde du langage, et sa valeur fait partie du monde réel et constitue un élément de la structure. L'interprétation d'un terme tel que `g(a,g(b,a))` consiste à faire le calcul que représente le terme. Et il se peut que deux termes d'expression différentes dans notre langage désignent la même valeur, et donc soient égaux en valeur. Ainsi `a` et `b` qui constituent des termes nucléïques d'expression différentes peuvent être égaux s'ils désignent la même valeur.
Parcontre, si les opérateurs générateurs n'ont pas de définition, alors ils désignent eux-même, et la structure engendrée est libre, c'est-à-dire que deux termes distincts désignent forcement deux éléments distincts. Dans ce cas, la valeur du terme est le terme lui-même mais perçu comme une chaine de caractères constituant un élément du monde réel et non comme un terme le désignant.
Paralèllement à la structure mathématique du langage, celui-ci s'enrichie de plusieurs syntaxes. Dans les cas simples, l'opérateur est reconnue par un nom court qui est une chaine de caractères, et il possède une arité. Prenons par exemple l'opérateur `g` d'arité 2. Il peut prendre plusieurs formes d'appel comme par exemple `g(x,y)` ou bien `xgy` à condition que des règles syntaxiques permettent de séparer les noms de variable, ou alors en utilisant des blancs comme séparateurs `x g y`. Il peut également prendre la forme `g x y` ou bien encore `x y g`, et aussi d'autres formes utilisant plusieurs chaines de caractères différentes tel que par exemple `"<"x:y">"` utilisant trois chaines de caractère `"<"`, ` ":"`, ` ">"` comme nom. La syntaxe n'est pas superfétatoire, elle permet d'adapter le langage au problème et constitue en cela une étape importante de sa résolution.
L'opérateur possèdera aussi un nom long constitué d'une unique chaine de caractères, et qui pourra servir aussi pour désigner l'opérateur et pour certaines formes d'appel. Nous aborderons la syntaxe en regardant les premières constructions qu'il est possibles de faire. La syntaxe par défaut sera la forme d'appel fonctionnel anglaise utilisant le nom court unique ou le nom long telle que par exemple `g(x,y)`. Chaque opérateur possède une syntaxe qui est ainsi codifiée, et l'ensemble de ces opérateurs avec leurs différents syntaxes choisies constituent la définition du langage.
Dans un ordinateur contemporain, toute donnée binaire brute est une succession contiguë d'octets référencés par l'adresse de son premier octet. Si la donnée est mémorisé dans une mémoire linéïque sans protocole de bas niveau pour indiquer sa taille ou sa fin, alors sa taille doit être préalablement connue et transmise ou alors on doit pouvoir déterminer sa fin lisant la donnée par son début.
Nous avons désigné deux mondes, le monde du langage qui contient les termes, et le monde réel qui contient les valeurs. Un terme calcul une valeur. Mais un terme ou une valeur se mémorise tout deux en une donnée binaire brute répertoriée par l'adresse de son premier octet. Si la suite d'octets est un terme, elle obéïra aux normes unicode et utf-8 et à la syntaxe du langage. Il n'y aura pas besoin d'indiquer la fin du terme puisque celle-ci est indiquée par la syntaxe du terme lui-même. Parcontre, si la suite d'octets est une données, rien n'indique sa fin. C'est cette difficulté qui nous fait vouloir typer les données. A ce stade, on ne fait que reporter sur les procédures traitant les données, la charge d'avoir cette information, de connaitre la taille de la donnée, ou d'avoir un moyen d'en déterminer sa fin.
Il nous faut une méthode pour saisire une donnée binaire brute. On définit l'opérateur spécial `0x` de syntaxe collé préfixe qui appliqué à une succession paire de chiffres hexadécimaux va produire la valeur réel qui est la suite d'octets correspondante. Ainsi l'expression `0x000F` désignera un mot de deux octets contenant 15.
Le résultat d'un programme étant le plus souvent une valeur, on pourra utiliser cet opérateur `0x` pour exprimer le résultat dans notre langage. Ainsi par exemple si l'évaluation du terme `f(a)` produit la valeur d'un mot binaire contenant 15, alors le shell affichera le terme générique `0x000F` comme résultat. Et dans chaque expression où `f(a)` apparait, il pourra être remplacé par sa valeur converti dans notre langage. Ainsi `g(f(a),b)` pourra s'écrire `g(0x000F,b)`. Néamnoins la valeur exprimée ainsi est à la fois plus encombrante et plus difficile à lire. C'est pourquoi on donnera des nom aux valeurs que nous jugerons pertinent de nommées. Ces noms sont des opérateurs nuléïques ajoutés au langage et constituront ainsi des constantes initialisée à ces valeurs. Ces noms seront utilisé automatiquement prioritairement pour remplacer l'expression hexadécimale. Et s'il y a plusieurs noms désignant la même valeur, alors c'est le contexte du langage qui choisira le nom à utiliser.
Puis il faut maintenant considérer les données textes, ce sont des successions de caractères unicodes, une norme internationale qui couvre les écritures du monde entier, et on choisit la norme utf-8 qui occupe le moins de place en nombre d'octets. Ainsi, une donnée brute de texte est une succession d'octets respectant les normes unicode et utf-8, une norme universellement partagée. On définit un opérateur spécial qui va permettre de créer ces valeur de données textes réels. Ce sera simplement un constructeur de chaine de caractères avec une syntaxe habituelle de définition en entourant la chaine de caractères par des sortes de guillemets, mais on n'utilisera pas des guillemets ordinaires, on utilisera l'apostrophe encadré ⍞. Ainsi l'expression ⍞a$¥b⍞ désignera la valeur réel qui est une suite d'octets correspondants à cette chaine de caractères. La seul contrainte de cette méthode, c'est que le caractère apostrophe encadré ne doit pas être utilisé dans la chaine de caractères.
On peut avoir l'impression de bégayer. Pourquoi vouloir générer de l'unicode utf-8 alors que notre langage utilise déjà l'unicode comme alphabet et est implémenté en utf-8 ? C'est la distinction entre le terme appartenant au langage qui ne se préocupe pas de savoir sous quel forme binaire il est implémenté dans la machine, et la forme sous la quelle il est mémorisé, une donnée brute faisant partie du monde réel, une valeur réel, et ainsi que la valeur réelle qu'elle désigne et qui n'a acune raison d'être la même.
Comme nous faisons le choix d'un langage monotype et que nous procédons à des extensions toujours monotype, la distinction ne peut s'opèrer que par des états différents de la procédure de traitement. L'absence de type ne veut pas dire qu'il n'y a pas de type mais que c'est la procédure de traitement qui gère de façon transparante les types de telle sorte que pour l'utilisateur il n'y a pas de type. Ainsi un terme, selon la procédure qui la traite, peut être vu pour l'instant de trois façons possibles :
Mais ce n'est pas l'utilisateur qui le décide, c'est la procédure.
Ainsi débute la remise en cause de la pertinence de la distinction entre fichier texte et fichier binaire pour proposer des fichiers mélangeant textes et binaires. Cette remise en cause s'appuit sur l'importance d'une construction dense des données. Un texte n'est pas dense, mais notre langage étant polymorphe le texte pourra quand même être réduit en taille, et constituer le compromis pertinent entre densité, être lisible par un humain, et programmacité. La notion de programmacité désigne la capacité à intégrer dans la donnée elle-même des éléments programmatifs.
La construction du langage terminologique monotype va nous permettre de percevoir des principes de base et leurs développement possibles, liant le langage (l'ensemble des termess) et le monde réel (l'ensemble des éléments). Dans notre langage, le terme correspond à une instruction et donc à un programme. S'il est compilé, il correspond alors à une valeur et à donc à un élément.
L'opérateur normal retourne une valeur sauf s'il n'arrive pas à évaluer l'un de ses arguments ou lui-même, auquel cas il retourne le terme qu'il engendre en remplaçant tous les arguments évaluables par leur valeur. Et certains opérateurs spéciaux retourne non pas une valeur mais un terme. Donc un terme retourne une valeur ou un terme. On accorde donc cette faculté également aux variables. On agrandit ainsi le langage en donnant la possibilité aux variables et aux opérateurs de retourner non-pas une valeur mais un terme. Cela signifit que le résultat peut être un terme et donc un programme, et donc qu'il peut subire une deuxième évaluation (qui est une interprétation) si on attend de lui une valeur. Et dans ce cas, comme nous somme dans un langage monotype, cette seconde évaluation s'effectue automatiquement afin de retrouver une valeur du même type. Et si cette évaluation redonne un terme alors il faut réitérer l'évaluation du résultat jusqu'à obtenir une valeur, ou bien considérer que le calcul ne peut pas aboutir et retourner dans ce cas le terme engendré en remplaçant les arguments évaluables par leur valeur. Et de façon plus complète, il engendre un ensemble de tels termes qui lui sont égaux.
Pour l'utilisateur, il ne peut y avoir de distinction entre un terme produisant un terme et un terme produisant une valeur, ou plus exactement, c'est l'opérateur qui mettra en oeuvre des traitements différents selon que l'argument est un terme ou une valeur, et selon les attendus.
On introduit les variables comme suit. Tout nouveau nom d'opérateur qui ne fait pas partie des noms d'opérateur générateur désignera une variable. C'est un moyen qui évite des déclarations verbeuses, mais ces déclariations existent belles et biens, ce qui étend le langage terminologique en un langage déclaratif.
On commence par décrire la variable globale c'est à dire dont la déclaration est global au programme. Chaque déclaration de variable va ajouter au langage un opérateur nullaire, mais variable, c'est à dire que cet opérateur nullaire possède un comportement supplémentaire, celui de pouvoir changer la valeur qu'il désigne. Autrement-dit, les opérateurs nullaires du langage initial sont qualifiés de constants, tandis que les opérateurs nullaires déclarés après coup comme variable sont qualifiés de variables.
La variable contient une valeur ou un terme, qui peut être soit mémorisé ou soit le résultat d'un calcul. Dans ce dernier cas la variable mémorise un programme qui calcul sa valeur.
Lorsque la variable est effacée, on peut considérer qu'elle contient par défaut elle-même. Ainsi la variable `x` une fois déclarée contient le terme `x`. Ce choix programmatif mineur n'a pas de pertinence particulière sauf dans le cas où l'on veut donner plus-tard un sens à des contenues récurcifs tel une variable `x` contenant le terme `f(x)`. Lorsque la variable `x` est libre, elle constitue un nouvel élément telle une extension élémentaire dont la valeur par défaut est initialisée à la chaine de caractère du nom du terme en question `⍞x⍞`.
L'affectation d'une valeur à une variable se fait par une instruction d'égalité. On utilise l'opérateur spécial d'affectation, de nom long affectation, et qui s'applique à deux arguments. Le premier argument est une variable, et le second argument est un terme. Puis on le dote d'une syntaxe centrée de priorité faible avec comme nom court `"="`. Par exemple :
`x"="g(x,a)`
Dans cette instruction, la valeur calculée par `g(x,a)` est affecté à la variable `x`.
Lorsqu'un opérateur normal reçoit comme argument une variable et un terme, il commence d'abord par les évaluer, il les remplace tout deux par leur valeur, et s'il n'arrive pas à les évaluer ni à s'évaluer lui-même alors il va retourner le terme qu'il engendre en remplaçant les arguments évaluables par leur valeur. Et de façon plus complète s'il passe par plusieurs niveaux d'évaluation, il engendre un ensemble de termes qui lui sont égaux.
L'opérateur d'affectation se comporte différemment puisqu'il ne va pas remplacer son premier argument par sa valeur. L'opérateur d'affectation modifie le contenue de la variable transmis en premier argument. On verra plus-tard qu'il est possible d'affecter à une variable non pas directement une valeur mais un programme calculant cette valeur.
Le teste d'égalité en valeur entre deux termes est l'équivalent passif, c'est l'opérateur binaire de nom long `égal?` et de nom court `"=="` avec une syntaxe centrée et qui retourne vrai ou faux. Par exemple :
`f(x)"=="g(a,y)`
Les variables peuvent être déclarée localement c'est à dire dans un contexte ou un environnement dont la portée est limitée à un bloc de code entre accolade `{ }`, ainsi le langage s'y trouve augmenté d'une variable, et cette variable peut venir masquer une variable de même nom prééxistante définie dans un bloc parent. Les blocs de codes s'emboitent les uns dans les autres et forme un arbre. La portée des variables s'étend par héritage aux sous-blocs tant que le sous-bloc ne redéfinit pas une nouvelle variable de même nom auquel cas celle-ci masque et remplace la précédente.
Délors pour déclarer une variable dont le nom est éventuellement déjà pris, il nous faut utiliser un opérateur spécial var, où const, et si on souhaite que la variable local soit pérenne c'est-à-dire qu'elle soit global mais accessible que dans le bloc de code en question (et ceux descendants), on utilise l'opérateur spécial static pour définir un attribut. Ces opérateurs sont unaires et retournent la variable nouvellement déclarée. Leur syntaxe est préfixe avec caractère blanc comme séparateur. Exemple :
static `x`
var `x`
const `x`
Chaque nouvelle variable mentionnée agrandit le langage. De tel sorte que la variable se comporte comme un terme nucléïque, à-part qu'il peut changer de valeur. Et nous sommes toujours dans un langage monotype, la variable, le terme et la valeur sont de même type. Déclarer une variable va ajouter un nouvel élément inconnu, sachant que cet élément peut être égal à un élément déjà connu ou non, son introduction a le même effet qu'une extension libre de structure que nous décrivons dans la partie 3. Mais avant d'explorer cette partie mathématique il convient de décrire l'autre face de la variable qu'est le pointeur, ce que nous ferons dans la partie 2.
Une approche de la programmation des opérateurs peut être faite par le bas à travers la notion de bloc de code. On enrichi le langage pour pouvoir désigner une succession de terme en utilisant l'opérateur binaire point-virgule. Chaque terme est une instruction. L'opérateur binaire point-virgule désigne une succession série de termes, tandis que l'opérateur binaire virgule désigne une succession parallèle de termes. Le bloc de code est délimiter par des accolades, et est associé à un contexte. Le bloc de code représente un programme. Il peut avoir plusieur arguments d'entrée qui sont listés en premier avant l'opérateur spécial |, et il peut avoir plusieurs arguments de sortie qui sont transmis par l'opérateur return ou directement. Par exemple :
`{x,y | "instruction1"; "instruction2" ; ... ; "return" (a,b,c)}`
Ce bloc de code prend deux arguments en entrée et retourne 3 arguments. Le bloc de code peut contenir des variables statics qui se comporte comme des variables globals mais accessible uniquement à l'intérieur du bloc. L'appel d'un bloc de code se fait de la même manière que l'appel d'un opérateur appliqué à ses arguments. On mémorise le bloc de code dans une variable B. Puis on appelle le bloc de code avec ses arguments s'il en a :
`B={x,y | "instruction1"; "instruction2" ; ... ; "return" (a,b,c)}`
`B(u,v)`
ou directement
`{x,y | "instruction1"; "instruction2" ; ... ; "return" (a,b,c)}(u,v)`
Il est possible de perfectionner la notion de bloc de code en lui permettant plusieurs instantiations distinctes. Ainsi il commence à ressembler à la définition d'une classe. Le bloc de code peut alors contenir des variables attributs qui se comporte comme des variables globals mais accessible uniquement à l'intérieur d'une instance précise du bloc. On utilise l'opérateur spécial attr pour définir un tel attribut. Cet opérateur est unaire et retourne la variable nouvellement déclarée. Sa syntaxe est préfixe avec caractère blanc comme séparateur. Exemple :
attr `x`
L'appel d'une instance de bloc de code se fait de la même manière que l'appel d'un opérateur indicé par un numéro d'instance et appliqué à à ses arguments. On mémorise le bloc de code dans une variable `B`. Puis on appelle le bloc de code avec un numéro d'instance `n` comme suit `B⦗n⦘(u,v)`. Une variable statics est par principe une variable communes à toutes les instances. Un attribut est par principe une variable distincts pour chaque instance.
Il est possible de perfectionner encore la notion de bloc de code multi-instance en lui ajoutant des noms de méthode. On appelle le bloc de code avec un numéro d'instance `n` et un nom de méthode comme suit `B⦗n⦘."methode1"(u,v)`. Cela définit une classe sans méthodes de classe. Notez que le nom methode1 ne fait pas parti du langage mais est mémorisé dans `B`. C'est le début d'une typologie.
Puis on ajoute une méthode de classe, la méthode new. De telle sorte que `B."new"` crée une instance de `B`. On peut laisser au ramasse miette le soin de libérer la mémoire inaccessible, mais on ajoutera une méthode de classe qui est la méthode `"delete"`. De telle sorte que `x."delete"` libérera la mémoire occupée par une instance `x` de `B`.
Un tel bloc se présente comme suit et définit une classe :
`{`
`"static const new" ={" x,y | ....}`
`"static const delete" = {...}`
`"attr const methode1" = { x,y | ....}`
`"attr const méthode2" = {x | ...}`
`}`
L'opérateur point, s'il est appliqué à un bloc, va chercher une variable static dans ce bloc, et s'il est appliqué à une instance c'est à dire un couple composé d'un bloc et d'un numéro d'instance sous la forme du terme `B⦗n⦘`, alors il va chercher une variable attribut associée à l'instance n°`n` du bloc `B`.
On voit donc comment par généralisation et unification des procédures et des formes de constructions possibles on arrive à construire par étape, et découlant presque de source, le principe de la programmation objet et sa forme d'implémentation.
La science de notre ére a cette capacité unificatrice, de réunir toutes les questions fondamentales une seule, en un seul principe qu'est la loi qui généralise..., et qui rammène toutes les explications en une seule explication. Elle est la cause de l'avènement des religions monothéistes sur celles plurithéistes, et elle constitue un argument en faveur de cette unicité dans la démarche de construction des sciences et de notre langage informatique idéal.
Les formes d'implémentation à la fois rudimentaires et fondamentales correspondent à des mécanismes de raisonnement à la fois rudimentaires et fondamentaux. On commence par exhiber le principe de l'égalité et de la transitivité qui joue un rôle fondamental en logique du premier ordre. Comment implémenter efficacement l'égalité et sa transitivité ? On le fait en utilisant les pointeurs, et en chaînant ces pointeurs pour procéder à des affectations permanentes.
Par exemple, `x"='ga'"`, `y"='bu'"` et `z"='zo'"`. Ces variables possèdent chacune un premier pointeur dont l'adresse n'est pas modifiable et qui pointe respectivement sur les valeurs `"'ga'","'bu'","'zo'"`. Un pointeur peut pointer une valeur ou un autre pointeur. La valeur de `x` s'obtient en regardant ce que pointe `x` et si c'est un pointeur, en regardant ce qu'il pointe à son tour et ainsi de suite jusqu'à arriver sur une valeur, ou si on tourne en rond alors la valeur de `x` est posée égale au pointeur nil. Ainsi chaque variable constitue une chaine de pointeur avec un premier pointeur et un dernier pointeur pointant sur une valeur, ou le pointeur nil.
On obtient une modification de `x` qui établit un lien d'égalité permanent, notée `x":="y`, en raccordant le dernier pointeur de `x` sur le premier pointeur de `y`. En procédant Ainsi, qu'avec ce type opérande `":="`, il n'y a aucune perte d'information sur l'égalité entre variable. Puis de surcroît, un apsect simplificateur est mis en oeuvre qui consiste à chaque parcourt d'un chemin de pointeurs, à faire pointer tous les pointeurs du chemin sauf le dernier sur ce dernier pointeur. Cet aspect applique la transitivité de l'égalité pour racourcir les chemins. De nombreux algorithmes vont devenir de complexité linéaire grace à cette simple astuce.
On ne rentre pas dans les détailles de l'implémentation, de ce que fait le bas niveau de protocole, on donne seulement les degrés de liberté suffisants pour que le protocole de bas niveau est au moins la possibilité de le faire, à défaut de préciser comment il le fait.
La densité des données est liée à l'entropie. La recherche de structures de données néguentropiques aboutit naturellement aux structures de données mémorisant des lois de composition.
Ces structures de données contiennent des liens internes, des pointeurs reliant directement chaque composition d'éléments à un élément. Elles transportent des informations dites introspectives et rapides d'accès, qui peuvent se refléter, comme des miroirs en vis-à-vis, jusqu'à l'infini. La structure acquère de par ces liens sur elle-même et cette reflexivité efficace, une capacité d'organisation qui lui est propre, et qui, utilisé d'une certaine façon, permet de réduire l'entropie, d'où le qualificatif de structure néguentropique.
On considère les lois de composition d'arité fixe `p` totalement dense c'est à dire sur un ensemble de `2^n` éléments. Cela correspond à une application de `E^p` vers `E` où `E` est un ensemble de `2^n` éléments.
`E^p→E`
`|E|=2^n`
La structure de données est composé d'une table de `2^(np)` briques de `n` bits chacune. La taille des structures est de `n 2^(np)` bits. Le monde réel contient ainsi des structures néguentropiques, mémorisant des lois de composition, et ayant une série de tailles optimales.
|E| |
`E"→"E`
|
`E^2→"E`
|
`E^3"→"E`
|
`E^4"→"E`
|
`E^5"→"E` |
`E^6"→"E` |
`E^7"→"E` |
`E^8"→"E` |
`E^9"→"E` |
`E^10"→"E` |
`E^11"→"E` |
`E^12"→"E` |
|
n
|
`2^n` |
`n2^n "b"` |
`n2^(2n) "b"` |
`n2^(3n) "b"` |
`n2^(4n) "b"` |
`n2^(5n) "b"` |
`n2^(6n) "b"` |
`n2^(7n) "b"` |
`n2^(8n) "b"` |
`n2^(9n) "b"` |
`n2^(10n) "b"` |
`n2^(11n) "b"` | `n2^(12n) "b"` |
`1`
|
`2`
|
`2 "b"`
|
`4 "b"`
|
`1 "o"`
|
`2 "o"`
|
`4 "o"`
|
`8 "o"`
|
`16 "o"`
|
`32 "o"`
|
`64 "o"`
|
`128 "o"`
|
`256 "o"`
|
`510 "o"`
|
`2`
|
`4`
|
`1 "o"`
|
`4 "o"`
|
`16 "o"`
|
`64 "o"`
|
`260 "o"`
|
`1 "ko"`
|
`4.1 "ko"`
|
`16 "ko"`
|
`66 "ko"`
|
`260 "ko"`
|
`1 "Mo"`
|
`4.2 "Mo"`
|
`3` |
`8` |
`3 "o"` |
`24 "o"` |
`190 "o"` |
`1.5 "ko"` |
`120 "ko"` |
`98 "ko"` |
`79 "ko"`
|
`6.3 "Mo"` |
`50 "Mo"` |
`400 "Mo"` |
`3.2 "Go"` |
`26 "Go"` |
`4`
|
`16`
|
`8 "o"`
|
`130 "o"`
|
`2 "ko"`
|
`33 "ko"`
|
`520 "ko"`
|
`8.4 "Mo"`
|
`134 "Mo"`
|
`2.1 "Go"`
|
`34 "Go"`
|
|||
`5` |
`32` |
`20 "o"` |
`640 "o"` |
`20 "ko"` |
`660 "ko"` |
`21 "Mo"` |
`670 "Mo"` |
`21 "Go"` |
|||||
`6`
|
`64`
|
`48 "o"`
|
`3.1 "ko"`
|
`200 "ko"`
|
`13 "Mo"`
|
`805 "Mo"`
|
`52 "Go"`
|
||||||
`7` |
`130` |
`110 "o"` |
`14 "ko"`
|
`1.8 "Mo"` |
`230 "Mo"`
|
`30 "Go"` |
|||||||
`8`
|
`260`
|
`260 "o"`
|
`66 "ko"`
|
`17 "Mo"`
|
`4.3 "Go"`
|
||||||||
`9` |
`510` |
`580 "o"` |
`290 "ko"`
|
`150 "Mo"` |
|||||||||
`10`
|
`1 "k"`
|
`1.3 "ko"`
|
`1.3 "Mo"`
|
`1.3 "Go"`
|
|||||||||
`11` |
`2 "k"` |
`2.8 "ko"` |
`5.8 "Mo"` |
`12 "Go"` |
|||||||||
`12`
|
`4.1 "k"`
|
`6.1 "ko"`
|
`25 "Mo"`
|
||||||||||
`13` |
`8.1 "k"` |
`13 "ko"` |
`109 "Mo"` |
||||||||||
`14`
|
`16 "k"`
|
`29 "ko"`
|
`470 "Mo"`
|
||||||||||
`15` |
`33 "k"` |
`61 "ko"` |
`2 "Go"` |
||||||||||
`16`
|
`66 "k"`
|
`130 "ko"`
|
`8.6 "Go"`
|
||||||||||
`17` |
`130 "k"` |
`279 "ko"` |
`37 "Go"` |
||||||||||
`18`
|
`260 "k"`
|
`590 "ko"`
|
|||||||||||
`19` |
`520 "k"` |
`1.2 "Mo"` |
|||||||||||
`20`
|
`1 "M"`
|
`2.6 "Mo"`
|
|||||||||||
`21` |
`2.1 "M"` |
`5.5 "Mo"` |
|||||||||||
`22`
|
`4.2 "M"`
|
`12 "Mo"`
|
|||||||||||
`23` |
`8.4 "M"` |
`24 "Mo"` |
|||||||||||
`24`
|
`17 "M"`
|
`50 "Mo"`
|
|||||||||||
`25` |
`34 "M"` |
`100 "Mo"` |
|||||||||||
`26`
|
`67 "M"`
|
`218 "Mo"`
|
|||||||||||
`27` |
`130 "M"` |
`450 "Mo"` |
|||||||||||
`28`
|
`270 "M"`
|
`940 "Mo"`
|
|||||||||||
`29` |
`540 "M"` |
`1.9 "Go"` |
|||||||||||
`30`
|
`1.1 "G"`
|
`4 "Go"`
|
|||||||||||
`31` |
`2.1 "G"` |
`8.3 "Go"` |
|||||||||||
`32`
|
`4.3 "G"`
|
`17 "Go"`
|
|||||||||||
`33` |
`8.6 "G"` |
`35 "Go"` |
On peut imaginer des variantes mais celles-ci perdent toujours soit en rapidité où soit en densité ou les deux à la fois, faisant que ces maximums néguentropiques présentés ici sont voués à jouer un rôle important.
Un pointeur est une variable anonyme contenant une addresse désignant une case mémoire pouvant contenir une valeur, un terme ou un autre pointeur. Le concept de pointeur ouvre un nouvel horizon permettant de définir des arbres convergeant vers leurs racines. On conçoit dans notre langage terminologique monotype différents opérateurs spéciaux permettant de gérer ces arbres.
Comme nous sommes dans un langage monotype, la variable, la valeur, le terme et le pointeur doivent être de même type, seul le mécanisme de calcul présidé par les opérateurs change.
La notion de variable évolue, elle doit toujours commencer par un premier pointeur. Ainsi la variable peut toujours être perçu comme un pointeur. Et l'adresse de cette permière case mémoire contenant ce pointeur, et qui est identifié à la variable, ne change pas sauf si on détruit la variable et qu'on la recrée. Ce choix se justifie par le fait que la taille des valeurs désignés par une variable est de taille variables, et qu'il est donc plus pratique de procéder à un adressage indirecte passant d'une table des variables de taille fixe pour aller dans un empilement de données de taille variable.
L'aspect pointeur d'une variable `x` sera évaluée de trois façons différentes selon que l'on attend une valeur (ou un terme), un premier pointeur ou un dernier pointeur :
Toute variable peut être vue comme une valeur, un terme ou bien comme le premier pointeur ou bien comme le dernier pointeur, et c'est l'opérateur qui précice comment est perçu chacun de ses arguments et comment est perçu chacun de ses résultats. Les pointeurs ainsi définis vont permettre de concevoir des algorithmes de complexité linéaire qui n'auraient pas pu être facilement mis en oeuvre sans cette artifice.
L'instruction `x"="y` modifie le premier pointeur de `x` pour le faire pointer sur ce que désigne `y`. C'est l'affectation classique des variables. L'inconvénient de cette affectation, c'est qu'il y a une perte d'information. Les instructions `x"="y; y"="z` ne vont pas nécessairement entrainer que `x"=="z`. On conçois une autre modification de `x` qui se fait sans perte d'information sur les égalités, notée `x":="y` qui raccorde le dernier pointeur de `x` s'il n'est pas le dernier pointeur de `y`, sur le premier pointeur de `y`. Puis on effectue un aspect qui modifie tous les pointeurs du chemin de `x` ainsi parcouru pour les faire pointer sur son le dernier pointeur.
L'unification de termes joue un rôle fondamental dans la logique du premier ordre, et également en informatique car elle est de complexité linéaire grâce à l'usage des pointeurs comme nous allons le voir. La meilleur façon d'expliquer ce qu'est l'unification de deux termes est de prendre un exemple. On définit le langage `"<"a,b,f"(.)",g"(.,.)>"`. A ce stade, `a,b,f"(.)",g"(.,.)"` sont des opérateurs constants et toute autre nom est un opérateur variable. On considère deux termes
`g(g(x,g(y,z)),y)`
`g(g(x,x),g(a,x))`
Il y a donc 3 opérateurs variables `x, y, z` qui sont initialement des variables libres. L'unification peut se programmer en une fonction récurcive. On construit un langage de programmation dans le quel cet algorithme s'écrit le plus simplement possible. Un terme se décompose en une racine et une séquence d'arguments. On note X une métavariable contenant le terme. On note A(X) la racine du terme et S(X) la séquences des arguments. On note nb(S(X)) la taille de la séquence S(X) et S(X)[i] le ième argument de la séquence S(X). L'unification pourrait s'écrire ainsi :
unifier =
X,Y ? X==nil |-> X=Y;true ||
X,Y ? Y==nil |-> Y=X;true ||
X,Y |-> S(X)==S(Y) &&
n=nb(S(X));n==nb(S(Y)) &&
b=true;for(i=0,i<n,i++){b=b && unifier(S(X)[i],S(Y)[i])};b
L'affectation d'un terme à une variable se fait par une instruction d'égalité plus forte. On utilise l'opérateur spécial d'affectation, de nom long affectationForte, et qui s'applique à deux arguments. Le premier argument est une variable, et le second argument est un terme. Puis on le dote d'une syntaxe centrée de priorité faible avec comme nom court `"≡"`. Par exemple :
`x"≡"g(a,y)`
Dans cette instruction, ce n'est pas la valeur calculée par `g(a,y)` qui est affectée à la variable `x` mais le terme lui-même `g(a,y)` qui est affecté à `x`. Ainsi la variable `x` contiendra un programme d'expression `g(a,y)`. Considérons maintenant le cas où le second argument est simplement une variable `y`, nous avons l'instruction suivante :
`x"≡"y`
Et c'est le terme `y` qui est affecté à `x` et non sa valeur. Considérons maintenant l'instruction suivante :
`x"≡"x`
Cette instruction rend libre la variable `x`. Considérons maintenant l'instruction suivante :
`x"≡"f(x)`
Alors on est dans une situation récurcive. L'évaluation de `x` va produire le terme `f(x)` qu'il faudra à son tour évaluer si on attend une valeur, pour produire `f(f(x))` et ainsi de suite. La valeur de x sera mutliple, elle sera `x,f(x),f(f(x))...`
Comme nous souhaitons optimiser la complexité des calculs, on ne peut pas rester sur un modèle de calcul ne proposant qu'un seul résultat à la fois. Il convient de prévoir des séquences de termes ou de valeurs comme résultat, et de se donner un moyen pratique pour ré-aiguiller arbitrairement ces sorties vers les différentes entrées des opérateurs.
D'une manière générale, une suite que l'on n'aplatit pas peut contenir des sous-suites et donc peut former un arbre. Or cela recouvre le principe de construction d'un terme que l'on a déjà mis en oeuvre et qui correspond à l'opérateur binaire virgule.
Une suite que l'on aplatit constitue une séquence, un flux de termes. Et il y a trois distinctions à faire :
On s'en tient d'abord à une arité de sortie fixe sous une forme symétrique de l'arité d'entrée. L'opérateur possède une arité d'entrée qui est le nombre d'argument qu'il prend, et il possède une arité de sortie qui est le nombre d'arguments qu'il produit. Et nous devons pouvoir rediriger chaque sortie vers une entrée de notre choix. Prenons par exemple un opérateur `f` d'arité (2,3) c'est-à-dire d'arité d'entrée 2 et d'arité de sortie 3. Et considérons l'instruction d'affectation suivante :
`(x,y,z)=f(a,b)`
Cela signifie que les valeurs d'entrées de l'opérateur sont celle de `a` et `b`, et qu'une fois le calcul fait, le résulttat est une séquence de trois valeurs de sortie affecté à la séquence des trois variables `x,y,z` respectivement.
On peut alors représenter l'opérateur `f` comme un composant possédant 2 entrées et 3 sorties, et au lieu de donner des noms à ces entrées et sorties, on trace des lignes reliants, comme dans un circuit electrique, les sorties de certains composants vers les entrées d'autres composants, mais sans faire de cycle, formant juste un arbre.
On voit ici l'ébauche d'une nouvelle notation dite "notation de l'informaticien" qui se distingue de la "notation du physicien" identifiant le nom de la fonction à celui de la variable contenant le résultat de la fonction. Pour l'informaticien, le processus `f` est un composant qui prend deux entrées et qui retourne trois sorties.
L'opérateur peut également être variable. Autrement dit, la variable peut posséder une arité non-nulle d'entrée et une arité de sortie. Une variable d'arité `(n,m)` contient un terme particulier qui est un programme écrit dans le langage idéal, qui prend `n` arguments en entrée et qui retourne `m` résultats en sortie. Et il peut contenir une valeur qu'est le programme compilé c'est à dire un exécutable écrit en langage machine, qui prend `n` arguments en entrée et qui retourne `m` résultats en sortie. On perçoit donc plusieurs entrées qui se raccordent à l'opérateur et qui produit plusieurs sorties.
Pour définir sous la forme d'un terme un programme d'arité `(2,2)`, on utilise l'opérateur de définition de fonction de nom long fonction et de nom court `|->` d'arité variable, avec une syntaxe centrée et où les arguments sont séparés par des virgule. Par exemple :
`x,y |-> g(x,f(x)),g(y,x)`
Les termes de gauche forment l'entête de l'opérateur et correspondent à des déclaration de nouvelles variables dont la portée est limitée à l'opérateur. Les termes de droite forment le corps de l'opérateur et correspondent aux résultats. La priorité syntaxique de l'égalité étant plus faible, nous pouvons écrire :
`h ≡ x,y |-> g(x,f(x)),g(y,x)`
La variable `h` est alors modifiée pour contenir le terme `x,y |-> g(x,f(x)),g(y,x)` qui correspond à un programme d'arité (2,2) c'est à dire d'arité d'entrée 2 et d'arité de sortie 2. Déjà il est possible d'écrire des fonctions récurcives telle que par exemple :
`f ≡ x |-> g(f(x),x)`
L'évaluation de `f(a)` va produire le terme `g(f(a),a)` qu'il faudra à son tour évaluer pour produire `g(g(f(a),a),a)` et ainsi de suite. Le contexte contiendra la méthode à appliquer lors d'appel récurcif, qui, par défaut, consiste à retourner le terme engendré en remplaçant les argument évaluables par leur valeur.
L'opérateur spécial de compilation est `ℭ`.
`f=ℭ(x |-> g(g(x,b),x))`
Le programme ainsi compilé pourra s'exécuter dans le même contexte c'est à dire dans le même bloc de code ou dans un sous-bloc de code sachant que si la variable `x` est masquée dans un sous bloc, la compilation n'en tiendra pas compte et le `x` du programme correspondra au `x` du bloc parent où a eu lieu la compilation. Les composantes du programmes compilés doivent avoir été déclarées dans un bloc parent ou de manière static, sinon leur référence pointe dans le décor !. On voit ainsi la distinction entre l'exécution d'un programme compilé qui ne consulte pas le contexte et l'interprétation d'un programme qui dépend du contexte :
`f=ℭ(x |-> g(f(x),x))`
`f(a)``f ≡ x |-> g(f(x),x))(a)`
`f(a)`
Le langage machine s'abstraitise. C'est en fait un langage de bas niveau de protocole dont nous avons tout loisir de définir et qui permet de construire le langage universel par dessus. Le protocole de bas niveau constitue un moteur à l'image du runtime java par exemple.
Pour effacer un opérateur ternaire `f` on pourra écrire :
`f≡x,y,z|->f(x,y,z)` ou `f"≡"ℭ (x,y,z|->f(x,y,z))`
On étend la définition de fonction en ajoutant un mécanisme d'unification des argments lors de l'appel de la fonction qui constitue un filtre des données d'entrée. On utilise pour cela, l'opérateur de définition de fonction avec pré-unification de nom long fonctionUnification et de nom court `↬` d'arité variable, avec une syntaxe centrée et où les arguments sont séparés par des virgules. Considérons la fonction suivante :
`h = g(x,x),y ↬m(x,y)`
Le calcul de `h(z,t)` va d'abord procéder à l'unification de `z,t` et de `g(x,x),y`. Puis si l'unification réussit alors le calcul va retourner `m(x,y)` en remplaçant `x` et `y` par leur valeur issue de l'unification. Et si l'unification échoue alors le calcul va retourner fail, ce qui signifie que les données sont en dehors du domaine de définition de `h` et que la fonction est arrivé à le déterminer.
Si on souhaite créer une variable dont le nom est déjà présent, on ajoute simplement l'opérateur `tt"var"` devant. Et l'opérateur `tt"var"` sera distributif vis à vis de l'opérateur virgule faisant que var `tt"var" x,y,z` sera identique à `tt"var" x, tt"var" y , tt"var" z`. Notez que dans cette exemple `g` peut être une variable libre dont l'arité sera déduite par la forme d'appel standart utilisée.
On ajoute comme filtre une condition. On utilise l'opérateur `?` `↬` :
`h = g(x,x),y ? f(x)"=="y ↬m(x,y)`
Délors il ne suffit pas que l'unification réussisse mais il faut également que la condition retourne vrai.
On autorise la définition par morceau. On utilise l'opérateur "ou" représenté par le symbole `||`. Par exemple :
`h = f(x),g(y,x) |->m(x,y) "||"`
`f(y),y |->g(y,y) "||"`
`a,x ? g(a,x)"=="g(x,a)|->f(x)`
Les unifications sont testées dans l'ordre jusqu'à obtenir une réussite, et on s'arrète à la première réussite pour retourner le corps correspondant et l'évaluer.
Le développement de ce langage marie l'informatique aux mathématiques, développant une mathématique éminemment constructive. Une présentation est une liste d'opérateurs telle que `(a,b,f"(.)",g"(.,.))`. Et si les opérateurs en question n'ont pas de définition c'est à dire si
`a"≡"a` ou `a"≡"ℭ(a)`
`b"≡"b` ou `b"≡"ℭ(b)`
`f"≡"x|->f(x)` ou `f"≡"ℭ(x|->f(x))`
`g "≡"x,y|->g(x,y)` ou `f"≡"ℭ(x,y|->g(x,y))`
Alors elle engendre un langage libre. L'ensemble des valeurs désignées par les termes engendrés constitue une structure libre.
`E="<"a,b,f"(.)",g"(.,.)>"`
L'ajout d'opérateurs libres tel que `x, h"(.)"` constitue une extension libre de la structure.
Afin de rester conforme au paradigme et ainsi de pouvoir bénéficier de toutes les interopérabilités possibles, toute construction d'élément doit passer par la construction d'une telle structure qui l'engendre.
La première difficulté que rencontre les concepteurs du langage idéal, et qui peut en décourager certains, tient dans l'inefficacité des entiers naturels construit sous forme d'une structure de Péano. Pour franchir cette difficultée il faut pousser le procédé plus loin en dotant la structure d'une base et en compilant ses méthodes. Le langage idéal se construit par lui-même en compilant ses propres composantes, tout en laissant encore indéfini le langage de bas protocole sur lequel il se construit.
Mais ne sautons pas les étapes, les entiers seront construit lorsque nous introduirons plusieurs types. Pour l'instant, il n'y a qu'un seul type et donc qu'une seul structure, et un seul ensemble sous-jacent qui regroupe les valeurs désignées par les termes. L'introduction des opérateurs variables c'est à dire l'introduction des variables d'arité d'entrée non-nulle et/ou d'arité de sortie différente de 1 va entrainant la propriété syntaxique commune à tous les termes, de pouvoir s'appliquer à n'importe qu'elle séquence d'arguments pour produire une séquence d'arguments. Le langage change alors de nature en devenant le langage alpha multi-aire monotype.
Le langage met en oeuvre un mécanisme de récurrence générale pour se construire. Le langage permet de définir les fonctions récurcives. Pour être sûre d'avoir atteint le degrès de généralité maximal, on reprendra l'exemple de la fonction d'Ackermann-Péter `A"(.,.)"` qui est un exemple simple de fonction récursive non récurcive primitive. Mais pour l'instant, on définit la structure des entiers naturels par la structure de Péano.
On pose la présentation `0,s"(.)"`. Les entiers `1,2,3` correspondent aux termes `s(0)`, `s(s(0))`, `s(s(s(0)))`. L'évaluation de `s(n)` consiste à calculer `n"+"1`. On obtient par récurrence l'ensemble des entiers naturels :
`NN=<0,s"(.)>"`
Les crochets signifient la cloture par compositions closes, c'est à dire l'ensemble de toutes les compositions possibles d'opérateurs parmi `{0,s}` avec autant d'occurences que l'on veut. Il s'agit ici d'une récurrence primitive. On peut y définir l'addition par une fonction de récurrence primitive :
`"syntaxe"("+") = "centrée"`
`"+" ≡ x,0 |-> x "||"`
`x,s(y) |->s(x)"+" y`
Et on peut y définir la multiplication par une fonction de récurrence primitive :
`"syntaxe"("∗") = "centrée"`
`"priorité"("∗","+")`
`"∗"≡ x"∗"0 |-> 0 "||"`
`0"∗"x |-> 0 "||"`
`1"∗"x |-> x "||"`
`s(x)"∗"y |->x"∗"y"+" y`
Voyons comment on peut traduire la fonction d'Ackermann définie dans `NN` comme suit :
`AAn, A(0,n) = n"+"1`
`AAm!=0, A(m,0) = A(m"-"1,1)`
`AAm!=0,AAn!=0, A(m,n) = A(m"-"1,A(m, n"-"1))`
On définit dans notre langage la fonction `A` comme suit :
`A ≡ 0,n|->s(n) "||"`
`s(m),0 |->A(m,s(0)) "||"`
`s(m),s(n) |->A(m,A(s(m),n))`
Chaque opérateur `f` peut définir une fonction distincte selon le nombre d'arguments d'appel. Et donc lorsqu'il n'est pas définie, nous devrions avoir comme valeur par defaut :
`f ≡ |-> f() "||"`
`x |-> f(x) "||"`
`x,y |-> f(x,y) "||"`
`x,y,z |-> f(x,y,z) "||"`
...
Cette expression est un terme de taille infinie qui ne peut donc pas s'écrire pour l'instant. On définie un nouveau type de variable qu'est la séquence variable de termes que l'on note `x"*"`. Chaque opérateur `f` à pour valeur par défaut : `x"*" |-> f(x"*")`. L'expression précédente peut donc s'écrire come suit :
`f ≡ x"*" |-> f(x"*")`
Si on redéfinit `f` par exemple comme suit : `f ≡ x,y|->f(x,y)` On supprime toutes les autres formes d'appel, et donc `f(x)` et `f(x,y,z)` échoue et retourne fail.
La séquence variable joue un rôle important car les algorithmes d'unifications des termes avec séquences variables uniques et placés toujours tout en fin ou toujours tout en début, sont encore de complexité linéaire.
Un langage se définit par un ensemble d'opérateurs et par une axiomatique. Et il se définit aussi par une grammaire.
Le langage terminologique monotype engendré par les 4 opérateurs suivants `a,b,f"(.)",g"(.,.)"`, est définie par la grammaire suivante notée sous forme d'une définition récurcive d'ensembles :
`E={a,b,f(E),g(E,E)}`
Comme le langage est monotype, l'ajout de variable ayant une arités d'entrée et de sortie quelconque, entraine que tout terme peut s'appliquer à une séquence de termes pour produire une sequence de termes. Cette nouvelle fonctionnalité transforme le langage terminologique monotype en un langage alpha multi-aire monotype
Appliqué aux seuls opérateurs générateurs `a,b,f,g` cela correspond à la grammaire suivante notée sous forme d'une définition récurcive d'ensembles. On note `E"*"` l'ensemble des séquences finies d'éléments de `E` :
`E={a,b,f,g,a(E"*"),b(E"*"),f(E"*"),g(E"*")}`
Le concept de séquence peut s'inclure dans celui de terme. Toute séquence peut être vue comme un terme utilisant l'opérateur binaire virgule. Délors, tout opérateur peut être considéré comme prenant qu'un seul argument et ne produisant qu'un seul argument. Cela définie le langage alpha monotype.
On note l'opérateur virgule `"𐎟"`. Considérons les opérateurs `a,b,f,g,"𐎟"` Ceux-ci engendrent le langage de grammaire suivante notée sous forme d'une définition récurcive d'ensembles :
`E={a,b,f,g,E"𐎟"E,E(E)}`
Ainsi par exemple le terme `a"𐎟"(b"𐎟"(a"𐎟"b))` désignera la séquence `a,b,a,b`. On remarque que l'opérateur virgule `"𐎟"` est le seul opérateur binaire, tous les autres opérateurs sont à la fois unaires et nullaires. Il existe un second opérateur binaire, mais encore abstrait en dehors du langage, qui est l'application d'un terme sur un terme. On le note par le symbole `"@"` et on l'appelle combine. En intégrant cet opérateur dans le langage on peut rendre nullaires tous les autres opérateurs à l'exception de la virgule. Le langage se ramène à un langage d'opérateur nullaires avec deux opérateurs binaires, la virgule et la combine.
Considérons les opérateurs `a,b,f,g,"𐎟","@"` Ceux-ci engendrent le langage de grammaire suivante notée sous forme d'une définition récurcive d'ensembles :
`E={a,b,f,g,E"𐎟"E,E"@"E)}`
Reste à définir les valeurs par défaut. Un opérateur `x` non initalisé représente par défaut une variable nullaire, un élément inconnu. Mais le même nom `x` représente un opérateur pouvant s'appliquer à un terme `u` quelconque pour produire le terme `x(u)`. Alors se pose la question en quoi va être évalué ce terme ? La réponse en est trés simple. L'opérateur unaire `x` n'étant pas définie, il vaut par défaut `x ≡ |-> x "||" u|->x(u)` et donc l'évaluation de `x` donne le terme `x` et l'évaluation de `x(u)` donne le terme `x(u)` dans le quel on a remplacé `u` par son évaluation.