Langage de programmation
par opérateurs

    1. Introduction
    2. Le typage
    3. Curryfication et permutation
    4. L'inférence de type
    5. La syntaxes des opérateurs

     

1) Introduction

Tout est langage. La moitier d'un problème est résolu par le choix du langage. Comment concevoir un langage de programmation qui possèderait l'interopérabilité et la créativité des langages mathématiques ?

Le langage formel de programmation que nous allons décrire est avant tout un langage d'opérateurs d'arité variables et possèdant une syntaxe adaptable, dans lequel on introduit une notion de contexte qui prédisposent des valeurs par défauts, évitant ainsi de noyer toute formule dans les détailles. Les expressions sont analysées comme des arbres que l'on parcourt, et tiennent compte de contextes emboités également comme des arbres.

Comment programmer un moteur capable d'analyser une expression écrite dans un tel langage d'opérateurs ? Ce moteur constituera l'essentiel d'un interpréteur ou d'un compilateur, et il s'appuit sur deux colonnes ; une base de données sémantiques qui gouvernera le typage des opérateurs, et une base de données syntaxique qui gouvernera la forme syntaxique des opérateurs.

2) Le typages

On se place dans un cadre formel. On pose par exemples des types `A, B, C`. Un type désigne un ensemble de données possibles, cela peut être les entiers relatifs, les entiers modulo `256`, les booléens, les caractères, les chaines de caractères, etc...

On dira qu'un élément `e` est de type `A` s'il appartient à l'ensemble `A`, ce qui se note :

`e"∈"A`

Et on dira qu'un opérateur `f` posséde un type de départ `A` et un type d'arrivé `B`, s'il s'applique à un élément de type `A` et retourne comme résultat un élément de type `B`, autrement dit si c'est une application de `A` vers `B`. L'opérateur `f` est lui même un élément de type `A"→"B`, ce qui se note :

`f"∈"(A"→"B)`

L'ensemble des éléments se note `bbbE`. L'ensemble des types se note `bbbT`. Le symbole `"→"` constitue un opérateur qui permet de construire d'autre type. Cet opérateur est lui même un élément de type `(bbbT"×"bbbT)"→"bbbT`. Le symbole `"∈"` constitue un opérateur. Cet opérateur est lui même un élément de type `(bbbE"×"bbbT)"→"B``B` représente le type des booléens, c'est à dire l'ensemble des booléens.

Pour alléger l'écriture, une priorité syntaxique est donné à l'opérateur `"×"` sur l'opérateur `"→"` faisant que l'expression `(bbbE"×"bbbT)"→"B` est égale à l'expression `bbbE"×"bbbT"→"B`. Et on donnera à l'opérateur `"∈"` une priorité syntaxique plus faible que celle de `"×"` et de `"→"`.

Les opérateurs binaires `"→"` et `"∈"` ont une syntaxe dite centrée car leurs arguments sont placés, le premier à gauche et le second à droite. Pour lever des difficultés de lecture et peut être même certaine ambiguité, il peut être pertinent d'utiliser une notation spécifique pour évoquer un opérateur binaire de syntaxe centré en tant qu'élément. On l'encadre simplement entre crochet `[]`. Dé lors nous avons :

`"[→]" ∈ bbbT"×"bbbT"→"bbbT`
`"[∈]" ∈ bbbE"×"bbbT"→"B`

Le symbole `"×"` constitue un opérateur qui permet de construire d'autre type.

`"[×]" ∈ bbbT"×"bbbT"→"bbbT`

On remarque que les types sont des éléments, et donc que le type élément contient tous les types.

`bbbT "⊂" bbbE`
`AA x"∈"bbbT, x "⊂" bbbE`

3) Curryfication et permutation

Une application de `A"×"B"→"C` à un comportement inclus dans le comportement d'une application de `A"→"(B"→"C)`. C'est donc une amélioration en terme de liberté d'action que d'inclure le type `A"×"B"→"C` dans le type `A"→"(B"→"C)`.

Un élément de type `A"×"B` se transcript en un élément de `B"×"A` en permutant les composantes. Il existe une bijection canonique entre `A"×"B` et `B"×"A`, faisant qu'il est possible de considérer ces deux types comme constituant un seul type.

4) L'inférence de type

Les opérateurs peuvent posséder des noms identiques si leur définition d'ensemble de départ et d'arrivé diffère. Et les éléments peuvent aussi posséder des noms identiques si leur type diffère. Car l'identification d'un élément ou d'un opérateur se fait par son nom et son type.

Une variable possède donc deux données inconnues que sont le nom de l'élément qu'elle contient et le nom du type de l'élément quelle contient.

L'interpréteur va analyser une formule en typant les éléments, les opérateurs et les variables sans type, par un mécanisme d'inférence de type, en fonction d'un contexte qui comprend la connaissance d'éléments, d'opérateurs et de variables typées, ainsi que des choix par défauts.

Si le type d'une variable reste indéfinie ou valable pour plusieurs types différents, cela signifie que cela s'applique pour ces différents types. La compilation va exiger le typage complet, et pour compléter le programme elle précisera simplement le type voulu en démultipliant les cas. Par contre si un élément ou un opérateur ou une variable se voit attribuer par inférence, 2 types différents, dans un premier temps on exclura ce cas comme constituant une erreur de syntaxe.

5) La syntaxes des opérateurs

Tout est opérateur, et les éléments eux-mêmes peuvent constituer des opérateurs. Les opérateurs ont donc un type et peuvent être le résultat d'une expression. Comme dans le langage alpha, le résultat d'une expression peut constituer un opérateur et être appliqué à son tour à une liste d'arguments, selon une syntaxe prédéfinie par le type (ou par une données supplémentaire qu'est la forme).

Puisque tout est opérateur, il convient de définir précisement ce que peut être la syntaxe d'un opérateur selon son arité :

Syntaxe
Nom
Exemple
Chaine
`abc`
`abc`
Caract
`+`
`+`

Syntaxe
Nom
Caractère
de début
Caractère
de fin
Exemple
Gauche
`-`
`-x`
Droit
`!`
`x!`
Enveloppant
`"<"">"`
`"<"`
`">"`
`"<"x">"`

Syntaxe
Nom
Caractère
de début
Caractère
de séparation
Caractère
de fin
Exemple
Gauche
`f`
`(`
`,`
`)`
`f(x,y)`
Droit
`f`
`[`
`,`
`]`
`"["x,y"]"f`
Central
`+`
`x"+"y`
Enveloppant
`"<"`
`,`
`>`
`"<"x,y">"`
Exponentielle
`"^"`
     
`x^y`
Indicielle
`"_"`
     
`x_y`

Syntaxe
Nom
Caractère
de début
Premier
Caractère
de séparation
Second
Caractère
de séparation
Caractère
de fin
Exemple
Gauche
`f`
`(`
`,`
`,`
`)`
`f(x,y,z)`
Droit
`f`
`<`
`:`
`!`
`>`
`"<"x:y!z">"f`
Central
`?:`
`?`
`:`
`x?y:z`
Enveloppant
`"<"">"`
`"<"`
`,`
`,`
`>`
`"<"x,y,z">"`
Exponentielle
`"=^"`
 
`"="`
   
`x=^yz`
Indicielle
`"=^"`
 
`"="`
   
`x=_yz`

Et d'arité variable :

Syntaxe
Nom
Caractère
de début
Caractère
de séparation
Caractère
de fin
Exemple
Gauche
`f`
`(`
`,`
`)`
`f(x,y,z)`
Droit
`f`
`<`
`:`
`>`
`"<"x:y:z">"f`
Central
`:`
`x:y:z`
Enveloppant
`"<"">"`
`"<"`
`,`
`>`
`"<"x,y,z">"`

Et il convient de définir les règles de séparation d'opérateurs :

  1. Par des caractères blancs.
  2. Par certaines alternances de classe de caractères.
  3. Selon la liste des opérateurs déjà définis.

Un opérateur peut avoir plusieurs noms avec des syntaxes différentes. La syntaxe peut être liée au nom. Par exemple si `f(a)` produit l'addition `"+"`, on peut noter `x"+"y` mais l'expression `af(a)y` sera plus difficile à lire. Si on n'autorise pas cette syntaxe, alors c'est que la syntaxe centrée de l'opérateur `"+"` est liée à son nom `"+"` et non à son type. Dans d'autre cas la syntaxe sera liée au type.

 

---- 18 mars 2018 ----


Dominique Mabboux-Stromberg