La moitier d'un problème est résolu par le choix du langage. Le langage de programmation doit pouvoir épouser le problème. Il doit posséder une forte interopérabilité et doit être capable de créer des structures mathématiques. C'est un langage d'opérateurs, d'arité fixe et aussi d'arité variable. C'est un langage logique d'ordre supérieur. Il manipule des structures qui peuvent se projeter par morphisme entre-elles ou par isomorphisme et ainsi offrir des mécanismes de traduction pouvant être biunivoque. Le langage est orienté objet, fonctionnel, aspect.... La classe d'un objet correspond à son type, l'objet correspond à l'élément, les méthodes correspondent aux opérateurs, les propriétés correspondent aux aspects.
Le langage d'opérateurs induit un langage de types, ainsi qu'un mécanisme de typage par inférence. Le langage introduit des contextes qui prédisposent le langage localement, évitant la nécessité de définitions verbeuses, et évitant ainsi de noyer la formulation dans les détailles. Ces contextes sont emboités dans l'arbre des appels et aussi dans l'arbre des déclarations ce qui entraine deux genres de contexte, l'un dit dynamique qu'est le contexte d'appel, et l'autre dit statique qu'est le contexte déclaratif parent.
Le langage d'opérateurs doit pouvoir définir la syntaxe de ses opérateurs, et mémoriser ces définitions de syntaxe dans les contextes.
Comment programmer un moteur capable d'analyser une expression écrite dans un tel langage ? Le moteur sera conçu comme un interpréteur avec des capacités de compilation. Et il sera conçu par étape dans un souci de développement holistique.
Nous élaborons une sémantique en définissant les premiers types fondamentaux dans une chronologie du Big-Bang, telle la génèse, et ramenons tout au langage, à un mécanisme syntaxique formel, mère de toutes les raisons.
Quel est le premier type que nous devons définir ? Nous ne savons pas trop bien ce que recouvre exactement le concept de type, mais qui recouvre déjà pour l'essentielle le concept de structure mathématique. Nous le construirons donc en cours de route, et plusieurs alternatives vont apparaîtrent.
Nous pourrions vouloir commencer par le type pointeur, le mot d'adresse, qui est de 32 bits sur les anciennes machines permettant d'adresser 4Go de mémoires vives. Ce type apparait effectivement incontournable. Mais nous n'allons pas spécifier sa taille ni même son implémentation, juste dire que c'est une adresse, c'est à dire un pointeur.
Puis, il apparaît alors un type beaucoup plus général, qui est le type le plus général qui soit. C'est le type `"Élément"`, le type de sur quoi pointe le pointeur. On le désigne par le nom commun, élément, et dans le langage de programmation par le symbole `"Élément"`, et le symbole court `Omega`. Le type sera désigné dans le langage courant par un nom commun sans majuscule, et dans le langage de programmation par un symbole reprenant le nom commun mais avec une majuscule, et éventuellement par un second symbole plus court.
Le premier type fondamental qu'il convient de définir est le type élément.
Nous sommes dans un langage orienté objet. L'objet est synonyme d'élément. La classe est synonyme de type. La classe de tous les objets est synonyme du type de tous les éléments. Le type le plus général est le type de tous les éléments, appelé type élément. Il est désigné par le symbole `"Élément"` ou par le symbole `Omega`. Constatez que ce type constitue le premier élément.
Mais déjà la question de la syntaxe se pose. Ne faut-il pas utiliser un nom plus court ? une lettre telle que `Omega`, et qui puisse être retirée des contextes, car on ne va pas parler d'`Omega` tout le temps. Oui, et c'est ainsi que cela se fera.
Le type élément va décrire le comportement de tous les éléments.
Le second type fondamental qu'il convient de définir, est le type des types. On le désigne par le symbole `"Type"`, et par le symbole court `frT`. C'est une abstraction qui permet de mettre en oeuvre le paradigme objet. Le comportement des éléments est définie dans le type `Omega`. Aussi `Omega` est un élément de type plus particulier qui est de type `frT`.
L'appartenance à un type se définit ainsi : Considérons un élément `e` et un type `E`, nous dirons que `e` appartient à `E` si `e` est de type `E`. Le type se comporte à bien des égards comme un ensemble. `Omega` possède donc deux types, le type `Omega` et le type `frT` qui en est une spécialisation.
`Omega in Omega`
`Omega in frT`
Mais attention, le type n'est pas identique à un ensemble. Il peut être à la fois plus large et plus précis qu'un ensemble. Il peut regrouper une large conception d'éléments d'ordre catégoriel, qu'un ensemble ne serait pas capable de faire, et plus important encore, il peut désigner un même ensemble mais avec des caractéristiques comportementales différentes, le munissant de différents opérateurs, attribuant à ses opéateurs ainsi qu'à ses éléments une syntaxe différente. Le type est défini par une compréhension comprenant des opérateurs, une syntaxe, des propriétés et une théorie d'engendrement permettant d'énumérer tous ses éléments qui forme son contenu.
Le type `frT` représente le type de tous les types, il est donc élément de lui-même comme `Omega`. C'est un type, `frT "∈" frT`. Et c'est aussi un élément, `frT "∈" Omega`. On dira que le contenue de `frT` est inclus dans celui de `Omega`.
`frT ⊆ Omega`
Par contre le type `frT` apporte d'autres opérateurs, syntaxes et propriétés que n'a pas `Omega`. On dira que la comprehension de `Omega` est incluse dans celle de `frT` ce qui pourrait s'écrire par :
`Omega ⇐ frT`
Cela n'empêche pas que certaines syntaxes, certaine capacité de langage définie par le type élément peuvent être masqués par le type type. Et donc un contexte devra préciser l'ordre des types pour lever ce genre d'ambiguité. Un élément posséde différents types qui sont autant de plongements calculables dans des structures distinctes.
Vous aurez remarqué que le symbole d'appartenance `"∈"` n'a pas tout à fait la même signification selon qu'il est utilisé avec comme second membre un ensemble ou un type.
L'opérateur binaire `"∈"` de syntaxe centrée, prenant comme arguments un élément et un type dans cet ordre, constitue un opérateur qui lui aussi est un élément. Il possède le type suivant :
`Omega"×"frT → 2`
On lui donne aussi un second rôle d'opérateur nullaire, dans lequel il constitue un élément. Et nous avons `"∈" in Omega`, mais n'allons pas plus loin dans cette voix pour l'instant.
Notez l'apparition du type `2` qui désigne le type des booléens contenant l'entier zéro, `0`, qui désigne la valeur logique « faux », et l'entier un, `1`, qui désigne la valeur logique « vrai ». Et notez l'apparition des opérateurs `"×"` et `->` propres au langage des types.
La priorité syntaxique de `"×"` est fixée plus forte que celle de `"→"` faisant que `Omega"×"frT "→" 2` désigne `(Omega"×"frT) "→" 2` et non `Omega"×"(frT"→"2)`
Le langage doit pouvoir désigner autre chose que lui même. Pour cela, il utilise des opérateurs, qui sont par défaut variables. Le langage est un langage d'opérateurs. La donnée brute est composée d'opérateurs constants. On commence par définir des opérateurs constants. On commence par définir trois types de données brutes : les symboles, les chaines de caractères et les entiers.
Pour créer un symbole, on utilise l'opérateur `_` qui est multi-aire et de syntaxe collée droite, où les arguments sont des caractères non-séparateur collés à droite de l'opérateur. Appliqué à un mot sans caractère séparateurs, il définit le symbole correspondant au mot en question. Par exemples, la séquence `"_"x, "_"titi, "_"14` désigne la séquence des 3 symboles `x, titi, 14`. Notez que parmi les caractères séparateurs, on trouve le caractère blanc, le caractère de fin de ligne, les caractères de types virgule, les caractères de types parenthèses, etc. Les symboles nous permettent de définir la syntaxe c'est à dire le langage.
Puis on définie les chaînes de caractères, simplement appelés chaînes, ou encore strings. Pour créer une chaîne de caractères, on utilise l'opérateur multi-aire `”` de syntaxe collée entourée, où les arguments qui sont des caractères autres que le guillemet de création, sont collés et entourés par le symbole de l'opérateur. Par exemples, la séquence `”"x"”, ”"titi"”, ”"14"”` désigne la séquence des 3 chaînes `x, titi, 14`. Les chaines ont une deuxième représentation dite compilée ou compressée en binaire.
La différence conceptuelle qui existe entre un symbole et une chaîne est la suivante : L'ensemble des symboles sont hachés dans une table de hachage appelée table des symboles, afin de pouvoir transcrire efficacement un symbole en une adresse. Puis le symbole ne contiennent pas de caractère séparateur. Tandis que la chaîne de caractère peut en posséder.
Puis on défini les entiers, pour l'instant seulement positifs, écrit en base `10` à l'aide de chiffres. Pour créer un entier, on utilise les opérateurs multi-aires de syntaxe collée droite, que constitue chaque chiffre, `0,1,2,3,4,5,6,7,8,9`. Appliqué à une succession de chiffres collés, il définit l'entier correspondant à la plus grande succession possible de chiffres en question. C'est le premier chiffre qui sert d'opérateur multi-aire de syntaxe collée droite, et qui interpréte ses arguments en tant que symbole de chiffre (sans évaluation). Les entiers ont une deuxième représentation dite compilée ou compréssée en binaire.
Ainsi, nous avons définit trois types de données brutes, le type `"Symbole"`, le type `"Chaine"` et le type `"Entier"` qui ont deux modes, l'un lisible par un humain, l'autre compilé dans une table de hachage, sous forme de référence ou compréssé. Ainsi, une variable `x` qui mémorise un symbole aura le type `"Symbole"`, une variable `y` qui mémorise une chaine de caractère aura le type `"Chaine"`, et une variable `z` qui mémorise un entier aura le type `"Entier"`.
Remarquez les formes grammaticales : On dit le type élément, ou encore le type de tous les éléments, pour désigner `"Élement"` qui est un type. Et on dit le type des éléments pour désigner le type que peut avoir des éléments, plus précis que `"Élement"`. Les types s'emboitent entre-eux selon leur contenu. Certains sont inclus dans d'autres, et cette relation d'inclusion forment un arbre dans la structure des types.
Ce que l'on désigne par symbole est en faite un nom, qui désigne une entité dans le langage. Et comme le langage est un langage d'opérateurs, il désigne un opérateur, et donc un élément.
Avant d'être intégré dans le langage, et d'être activé, le symbole est noté préfixé par le caractère souligné `"_"`. Une fois intégré dans le langage, et désinhibé, c'est à dire ajouté dans la table des symboles portée par le contexte, le symbole fait parti du langage. Il repreprésente un opérateur et est noté sans utiliser le caractère souligné `"_"` comme préfixe. Mais alors il intéragit comme opérateur. Pour le désigner sans cette interaction on utilise la notation préfixé par le caractère souligné `"_"`.
Chaque symbole désigne un opérateur du langage. Tous ne sont pas actifs. Il y a toujours une part du langage inactivée ou dite inhibée, selon le contexte. Le langage est un langage d'opérateurs. Et tout opérateur peut être désigné par son symbole qui constitue une donnée brute servant de référence. Les symboles permettent ainsi au langage de définir sa propre syntaxe. Tout opérateur admet une forme nullaire de type symbole représentée par son nom préfixé par le caractère souligné `"_"`.
Le symbole se distingue conceptuellement de la chaine de caractère en ce qu'il intègre une table de hachage, la table des symboles. Même s'il est momentanément inhibé c'est à dire s'il ne peut être utilisé sans le caractère souligné `"_"` dans une expression du langage, il désigne un élément statique du langage. Alors qu'une chaine de caractère désigne une donnée brute à l'extérieur au langage.
Si nous créons un symbole sans autre précision, par défaut, le symbole correspondra à un nouvel opérateur nullaire (d'arité nulle) c'est à dire de type élément.
Le troisième type fondamental qu'il convient de définir est l'adresse, qui se définie comme étant un pointeur vers un élément. Mais on ne va pas utiliser un nom spécifique pour le désigner. On utilise directement un opérateur constructeur unaire `&` de syntaxe collée droite, qui appliqué à un type `T` produit le type pointeur vers un élément de type `T`. Dans le langage des types, le type `&Omega` désigne le type des pointeurs pointant sur un élément. Et on peut répéter l'opération. Le type `&&Omega` désigne le type des pointeurs pointant sur un pointeur pointant sur un élément, ou autrement dit, un pointeur de pointeur d'élément. Et ainsi de suite. On verra plus-tard que ces constructions de types peuvent s'enrichir de liens récurcifs.
Le type pointeur le plus générale est le type de pointeur d'élément noté `&Omega`. L'opérateur `&` ainsi décrit, transforme un type `X` en le type des pointeurs de ce type `X`. Donc `&` est de type `frT"→"&frT`.
Par défaut, un opérateur est variable, et donc mémorise une donnée. Mais il en est de même s'il est constant car le nom de l'opérateur ne sert que de référence. L'opérateur constant mémorise donc une donnée brute quelque part mais qui a vocation à ne pas changer contrairement à l'opérateur variable. Par contre si c'est un opérateur symbolique, il ne fait référence qu'à son propre symbole, inscrit dans le langage, telle une extension élémentaire dans une structure mathématique.
L'opérateur constant s'apparente à un opérateur symbolique contenant une donnée brute constante. Et c'est le nom de l'opérateur et non son contenu qui est intégré au langage.
L'opérateur variable s'apparente à un opérateur symbolique contenant d'une donnée brute variable.
Mais l'opérateur symbolique par définition ne contient pas de contenu. C'est un opérateur non initialisé qui, tant qu'il n'est pas identifié à un opérateur constant ou à un opérateur variable, reste un symbole qui enrichit le langage comme une extension élémentaire.
L'opérateur `&` possède un second rôle, il signifie littéralement « adresse de ». Appliqué à une variable `x` qui n'est pas restreinte à un rôle symbolique, il retourne son adresse `&x`. Mais attention, cette adresse dépend de la façon dont est vue la variable, sous quel type elle est vue. La définition d'une variable est intimement liée à son implémentation. La valeur brute d'un élément est un bloc mémoire comprenant une entête désignant le sous-type `A` de l'élément et un corps contenant la données brut. Mais ce corps peut également se subdiviser en une entête désignant un sous-sous-type `B` et un corps. Aussi l'adresse de la variable dépend du type considéré. L'opérateur `&` appliqué à une variable `x` va retourner son adresse `&x`. Il transforme donc un élément de type `"Omega"` en un pointeur d'élément de type qui se note `&Omega`. Donc `&` est de type `Omega"→"&Omega `.
Notez que l'opérateur `&` a deux rôles ; appliqué à une variable il produit son adresse, appliqué à un type il produit le type pointeur de ce type. La façon de lever l'ambiguité consiste à regarder le type du résultat, et le type de l'argument. Néanmoins la confusion persiste si l'argument est une variable contenant un type.
Un type `A` peut se munir d'opérateurs tels que `varphi` de type `A"×"A"→"A `. Il ajoute dans son extension l'opérateur `varphi` et mémorise le programme de calcul associé.
Par principe, une variable non symbolique de type `A` contient une donnée brute de type `A`. Mais il est possible de vouloir mémoriser une expression écrite dans le langage en cours, sans vouloir l'évaluer. Une telle expression dont l'évaluation est de type `A` aura comme type `sf"Exp"(A)`. C'est une donnée brute, qui peut être traduite par le prisme d'un langage en une donnée dynamique.
Puis on peut répéter l'opération. Le type `sf"Exp"(sf"Exp"(A))` désignera une expression qui calcule une expression qui calcule un élément de type `A`. On verra plus-tard comme pour les pointeurs que ces constructions de types peuvent s'enrichir de liens récurcifs.
Si l'expression ne comprend que des opérateurs internes définie dans `A` complété par des opérateurs nullaires symboliques `x,y` de type `A`, les expressions ont alors un type plus précis noté `A[_x,_y]`. De même si on ajoute un opérateur unaire symbolique `f` de type `A"→"A` . Les expressions ont alors un type plus précis noté `A[_x,_y,_f(".")]`, etc.. Et c'est l'analogie aux extensions élémentaires de structure mathématique qui est en oeuvre.
Le quatrième type fondamentale qu'il convient de définir, semble être l'instruction, la séquence d'instruction, le programme ou le sous-programme. C'est un bloc de code écrit séquentiellement dans notre langage de programmation, et dont la signification peut dépendre du contexte dans lequel il se trouve (contexte parent, dit statique), et dans le quel il est appelé (contexte d'appel, dit dynamique). On le désigne par le nom commun de programme, puis dans le langage de programmation par le symbole `"Programme"`, et par le symbole court `frP`.
Par exemple, considérons le programme suivant, présenté sous forme d'une énumération d'instructions séparées par des point-virgules :
`a"="2; b"="3; a"∗"b"+"1`
L'exécution de ce programme retourne la valeur de sa dernière instruction `7`. Un tel programme, que l'on appelle bloc de code, se comporte comme une fonction sans argument, dite nullaire (d'arité nulle).
On perfectionne ce bloc de code en y ajoutant une fonctionnalité supplémentaire qui est l'appel avec passage d'arguments. On reprend la syntaxe de Ruby qui s'inspire du pipe unix, et on ajoute dans le bloc de code une déclaration des arguments d'entrées à l'aide de l'opérateur de séquence virgule et de l'opérateur de séparation d'entête "|". Par exemple :
`x,y|x"∗"y"+"1`
Ce bloc de code est identique à la fonction binaire suivante :
`(x,y) ↦ x"∗"y"+"1`
On enrichie ainsi le type programme d'une caractéristique qui est son arité d'entrée.
On reprend la notation Ruby des blocs de code en entourant le bloc de code par des crochets `{}`, les instructions étant séparées séquentiellement par des points-virgules. Etant donné une variable `f`, celle-ci peut mémoriser ce bloc de code en exécutant l'instruction suivante :
`f"="{x,y|x"∗"y"+"1}`
On note par exemple `f(2,3)` l'application du bloc de code `f` aux arguments `2,3` et cela retourne `7`. Le bloc de code est aussi appelé une fonction. On utilise le signe égal en bleu pour désigner une assignation dans une instruction. Et on utilise le signe égal en noir pour désigner le résultat de l'évaluation. Voici quelques exemples :
`f"="{x,y|x"∗"y"+"1} ; f(2,3)` `=` `7`
`{x,y|x"∗"y"+"1}(2,3)` `=` `7`
`{x|x"+"10}(5)` `=` `15`
Les variables arguments, ici `x`, sont des nouvelles variables locales initialisées par l'appel, et qui sont mémorisées dans la pile d'appel permettant à la fonction de s'appeller elle-même en recréant à chaque fois un nouveau contexte. On peut s'inspirer de la notation Haskel `f 2 3` qui se traduit par `f(2,3)`. Le premier niveau de parenthèse collé à `f` fait partie de la forme d'appel de la fonction `f` qui s'applique à la séquence d'arguments `2,3`.
Dans ce chapitre nous avons découvert les opérateurs suivants :
Séparateur séquentielle d'instruction. Délimiteur de bloc d'instruction. Affectation. Multiplication. Addition. Séparateur séquentiel d'élément. Séparateur d'entête.
Le programme peut posséder un filtre d'entrée, exiger que ses arguments soit d'un type particulier et affubler le résultat d'un type particulier. Dans ce cas le type programme se spécialise. Par exemple si `x` est de type `frP(A"×"B"→"C)` alors c'est un programme qui prend comme argument un élément de type `A` et un élément de type `B` pour calculer un élément de type `C`. Et on note `x(a,b)` l'appel du programme avec comme paramètre d'entrées `a` et `b`.
L'expression `A"×"B` désigne l'ensemble des couples composés d'un premier élément de type `A` et d'un second élément de type `B`. Si le type `A` est inclus dans le type `X`, et que le type `B` est inclus dans le type `Y`. Alors le type `A"×"B` est inclus dans le type `X"×"Y`.
L'expression `A"×"B"×"C"`, qui est l'appliction de l'opérateur `"×"` à `3` arguments `A,B,C`, désigne l'ensemble des triplets composés d'un premier élément de type `A`, d'un second élément de type `B`, et d'un troisième élément de type `C`. Ainsi nous avons :
`A"×"B"×"C != (A"×"B)"×"C`
`A"×"B"×"C != A"×"(B"×"C)`
Et c'est les parenthèses qui vont délimiter les compositions `n`-aire :
`AA a "∈" A, AAb "∈" B, AA c "∈" C,`
`(a,b,c) in A"×"B"×"C`
`((a,b),c) in (A"×"B)"×"C`
`(a,(b,c)) in (A"×"B)"×"C`
Le produit `2`-aire est le produit binaire. Le produit `1`-aire est représenté en entourant l'argument d'une paire de parenthèse. Ainsi nous avons :
`AA a "∈" A,`
`(a) in (A)`
La parnthèse indique un niveau d'emboitement. Le produit `0`-aire est un type unique ne contenant qu'un seul élément noté `()` ou `"nil"`. Les type ne possèdant qu'un élément sont représenté par l'élément en question.
Si le type `A` est inclus dans le type `X`, et que le type `B` est inclus dans le type `Y` et que le type `C` est inclus dans le type `Z`. Alors le type `A"×"B"×"C` est inclus dans le type `X"×"Y"×"Z`. Et cela se généralise à toutes les arborescences.
Le type d'application `A"→"B` désigne l'ensemble des fonctions unaires prenant en argument un élément de type `A` et retournant comme résultat un élément de type `B`.
Dans le langage des types, l'opérateur binaire `"→"` permet de construire des types d'applications. Par convention l'opération `"×"` est syntaxiquement prioritaire sur l'opération `"→"`, faisant que le type `A"×"B"→"C` signifie `(A"×"B)"→"C`, et que le type `A"→"B"×"C` signifie `A"→"(B"×"C")`. Le type `A"×"B"→"C` désigne les programmes prenant comme entrée des élément de type `A"×"B` et retournant un élément de type `C`
On remarque que le type `{0,1}"→"A` est identique au type `A"×"A`, chaque telle application correspondant à un couple d'éléments de `A`. Et on remarque que le type `A"→"{0,1}` est identique au type `ccP(A)`, chaque telle application correspondant à un sous-ensemble de `A`.
Si le type `A` est inclus dans le type `X`, et que le type `B` est inclus dans le type `Y`. Alors le type `A"→"B` est inclus dans le type `X"→"Y`. Et cela se généralise à toutes les combinaisons d'opérateurs `"→"` et `"×"`.
Quelle différence y-a-t-il entre l'application binaire `f` et l'application unaire `g` satisfaisant ce qui suit ?
`f in A"×"B"→"C`
`g in A"→"(B"→"C)`
`AAx "∈" A,AAy"∈"B, g(x)(y)"="f(x,y)`
On identifie ces deux applications comme étant égales, `f=g`. Cela est possible sans exercer de contrainte, car `g` définit `f` et réciproquement `f` définit `g`. La transformation d'une application à plusieurs arguments en une application à un argument qui retourne une application sur le reste des arguments, s'appelle la curryfication. L'opération inverse s'appelle la décurryfication.
La curryfication fait qu'une application binaire `f` peut être appliquée à un seul élément pour produire une application unaire, ou peut être appliqué à une séquence de deux élément. Et c'est la logique polonaise qui prévaut, les arguments sont pris dans l'ordre d'arrivé.
Par convention l'opération `"→"` s'évalue dans le sens inverse de lecture c'est à dire de droite à gauche, faisant que le type `A"→"B"→"C"→"D` correspond au type `A"→"(B"→"(C"→"D))` et donc par décurryfication correspond au type `A"×"B"×"C"→"D`.
Quelle différence y-a-t-il entre une application unaire `f` et le couple d'applications unaires `(g,h)` satisfaisant ce qui suit ?
`f in A"→"B"×"C`
`(g,h) in (A"→"B)"×"(A"→"C)`
`AAx "∈" A, (g(x),h(x))"="f(x)`
On identifie ces deux applications comme étant égales `f=(g,h)`. En effet `(g,h)` définit naturellement `f` qui définit naturellement `(g,h)`. La transformation d'une application à `2` résultats en une liste de `2` applications à un résultat, transformant le type `A"→"B"×"C` en le type `(A"→"B)"×"(A"→"C)` s'appelle la distribution. L'opération inverse s'appelle la factorisation. Ainsi L'opérateur `"→"` devient distributif sur l'opérateur n-air `"×"`.
On définit comment un couple d'applications `(g,h)` appartenant à `(A"→"B)"×"(A"→"C)` s'applique à un élément de `A`. L'application opère une duplication de l'argument pour produire le couple `(g(A),h(A))`.