Langage de programmation idéal

1) Introduction

Tout est langage. La moitier d'un problème est résolu par le choix du langage. Le langage de programmation doit pouvoir épouser le problème.

Le langage de programmation doit posséder une forte interopérabilité et être capable de créer des structures, comme le langage mathématique.

Le langage de programmation que nous allons définir est un langage d'opérateurs d'arité fixe, et aussi d'arité variables car possèdant une syntaxe adaptable appelée "sucre syntaxique".

Le langage de programmation est le langage logique du second ordre. Il manipule des structures. Et ces structures peuvent être isomorphes offrant ainsi une traduction 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 internes correspondent aux opérateurs internes.

Le langage d'opérateurs induit un langage de types, et un mécanisme de typage par inférence.

Le langage introduit des contextes qui prédisposent le langage localement, évitant la nécessité de précisions verbeuses et évitant ainsi de noyer la formulation dans les détailles. Ces contextes sont emboités dans l'arbre des appels et dans l'arbre des déclarations ce qui entraine deux genres de contexte.

Le langage d'opérateurs doit pouvoir définir la syntaxe de ses opérateurs, de tel sorte que les contextes contiendront la syntaxe des opérateurs.

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çus 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.

2) Les types fondamentaux

Quel est le premier type que nous devons définir ? Déjà 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 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.

Alors, il apparaît un type beaucoup plus général, qui est le type le plus général qui soit, et qui 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"`.

Souvent, 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 second symbole plus court.

2.1) Le type élément, `Omega`

Le développement est orienté objet. Considérez pour l'instant que l'objet est synonyme de l'élément, et que 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 des éléments. Il est désigné par le symbole `"Élément"`. Notez alors que ce type constitue le premier élément.

Mais déjà la question de la syntaxe se pose. Ne faut-il pas un nom plus court ? une lettre telle que `Omega`, et qui puisse être retirée des contextes, car on ne va pas parler de `Omega` tout le temps.

Considérons un élément `e` et un type `E`, nous dirons que `e` appartient à `E`, noté `e "∈" E`, si et seulement si `E` comprend dans son extension l'élément `e`, où autrement dit, si et seulement si `e` est de type `E`. Le type se comporte comme un ensemble et nous avons :

`Omega in Omega`

2.2) Les données brutes

Le langage désigne autre chose que lui même. Il n'utilise donc, par défaut, que des variables et opérateurs variables. La donnée brute est l'exception. On définit les données brutes, et on commence par les symboles.

Pour créer un symbole, on utilise l'opérateur unaire `:"(.)"` avec une syntaxe allégée qu'il faudra préciser. Appliqué à un mot sans caractère blanc, il défini le symbole correspondant au mot en question. Par exemples, `:"x", :"titi", :14`.

Puis on définie les chaines de caractères. Pour créer une chaine de caractère, on utilise l'opérateur unaire `”"(.)"` avec comme syntaxe, celle où l'argument est entouré de guillemet. Par exemples, `”"x"”, ”"titi"”, ”"14"”`.

La différence conceptuelle qui existe entre un symbole et une chaine est la suivante : L'ensemble des symboles, répertoriés dans un contexte, est haché dans une table de hachage appelé table des symboles, afin de pouvoir transcrire efficacement un symbol en une adresse. Puis la syntaxe choisie veut que le symbole ne contiennent pas de caractère blanc. Les symboles vont donc jouer un rôle important dans le définition de la syntaxe du langage par lui-même.

Puis on défini les entiers, pour l'instant seulement positifs, écrit en décimale à l'aide de chiffres qui sont dix opérateurs unaires `0"(.)"`, `1"(.)"`, `2"(.)"`, `3"(.)"`, `4"(.)"`, `5"(.)"`, `6"(.)"`, `7"(.)"`, `8"(.)"`, `9"(.)"` avec une syntaxe allégée qu'il faudra préciser. Par exemples, `10, 1234`.

Et en dehors de ce genre d'expression, tout est par défaut variable, constitué de variables, d'opérateurs variables, qui sont évidement de type élément puisque le type élément contient tout.

Ces trois formes de données brutes donnent lieu à trois types : le type `"Symbole"`, le type `"Chaine"` et le type `"Entier"`. Ainsi par exemple, une variable `x` qui mémorise un symbole aura le type `"Symbole"`.

Remarquez les formes grammaticales : On dit le type élément pour désigner `"Élement"` qui est un type. Et on dit le type d'élément pour désigner le type que peut avoir un élément, autre que `"Élement"`, c'est à dire un type plus précis. Les types s'emboitent entre-eux, certain sont inclus dans d'autres, et la relation d'inclusion forment un arbre dans la structure des types.

 

2.3) Le type pointeur, `&Omega`

Puis le second type le plus général 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 `&"(.)"`, qui signifie "adresse de". Cette opérateur, avec une syntaxe allégée que l'on précisera, transforme le type `"Élément"` en le type pointeur d'élément `&"Élément"`, ou dit de façon plus courte, en le type `&Omega`.

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.

2.4) Le type programme, `frP`

Le troisième type le plus général qu'il convient de définir, semble être l'instruction ou le programme impératif. C'est un bloc de code écrit séquentiellement dans notre langage de programmation, et dont la signification dépend du contexte dans lequel il se trouve. On le désigne par le nom commun, programme, puis dans le langage de programmation par le symbole `"Programme"`, et par le symbole court `frP`.

Il y a deux genres de contexte, le contexte déclaratif et le contexte d'appel. 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; f"="(x"↦"a"∗"x); a"="3; "return" f(5)`

La fonction `f` qui y est définie évoque un paramètre `a`. Celui-ci a pour valeur `2` dans le contexte déclaratif, mais au cours de l'intruction `f(5)`, le paramètre `a` a pour valeur `3` dans le contexte d'appel. Par défaut c'est le contexte déclaratif qui s'impose, et pour faire prévaloire le contexte d'appel on soulignera la variable ou l'opérateur variable d'un trait. Ainsi Considérons la fonction suivante :

`f"="(x"↦"underline a"∗"x)`

Celle-ci possède un paramètre `a` souligné pour indiquer que sa valeur est celle du contexte d'appel, une valeur qui peut évoluer au cours de l'execution mais qui n'est pas empilée dans la pile d'appel lors de l'appel de la fonction car seuls les arguments de la fonction y sont empilés.

On remarque alors qu'il n'y a pas de différence entre un programme, aussi appelé bloc de code, et une fonction zéro-aire. Une fonction `n`-aire est un bloc de code dans lequel on a jouté une fonctionnalité supplémentaire qui est l'appel avec passage d'argument. On reprend la syntaxe de Ruby, un bloc de code avec une déclaration des arguments d'entrées tel que par exemple `{x,y|x"∗"y"+"1}`. Ce bloc de code est identique à la fonction `(x,y)"↦"x"∗"y"+"1`. On enrichie ainsi le type programme d'une caractéristique qui est son arité d'entrées.

2.5) Le type type, `frT`

Le quatrième type fondamental qu'il convient de définir, c'est le type de type, de symbole `"Type"`, et de symbole court `frT`.

Un type est un ensemble décrit compréhensivement et munie d'opérateurs et de propriétés. Le type `frT` représente l'ensemble des ensembles, il est donc élément de lui-même. Et c'est un élément, `frT "∈" Omega`. Et c'est un type, `frT "∈" frT`. On dira que `frT` est inclus dans `Omega`, noté `frT "⊆" Omega`.

Mais il est possible de le rendre égale à `Omega`. Il suffit pour cela de considérer chaque élément qui n'est pas un type, comme étant le type singleton se contenant. Dans ce cas, tous les éléments sont rendus de type type, et il n'y a plus de distinction entre le type élément et le type type.

`Omega=frT`

Tout deux sont alors dénommés par le même symbole `frT` qui possède le plus d'opérateurs (méthodes) et propriétés.

2.6) Qu'est-ce qu'un type

Le type est une structure mathématique, il possède des opérateurs internes qui sont des opérateurs prenant comme argument des éléments du type en question pour produire des éléments du type en question. Le type possède des prédicats internes qui sont des opérateurs prenant comme argument des éléments du type en question pour produire un booléen.

Le type possède des opérateurs dit "constructeur" qui retourne comme résultat des éléments du type en question. Le type est dit "avec énumérateur" si ses opérateurs constructeurs sont capablent de créer tous ses éléments. Et il est dit "avec énumérateur interne" si ses opérateurs constructeurs internes sont capablent de créer tous ses éléments.

Le type possède des propriétés, et il peut-être récusé s'il contredit ses propriétés, ce qui normalement ne se produit pas sauf dans le cas du fonctionnement en mode démonstrateur de théorèmes, comme lorsque l'on récuse une hypothèse pour des raisons logiques.

2.7) Les types produits, `"×"`

Le type produit `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`. Néanmoins. Si les types en question sont disjoints, on s'aperçoit alors qu'il est inutile de préciser l'ordre des composantes du couple puisque celui-ci est déterminé par les type des composantes. On introduit un aspect qui agit entre la class et l'objet, et qui va déterminer la permutation systématique qu'il convient de faire.

Ainsi, en implémentant cet aspect, dans le langage des types disjoints, l'opérateur `"×"` devient commutaif. C'est à dire pour tout type `A,B`, nous avons `A"×"B = B"×"A`. Cela signifie qu'un couple composée d'un premier élément de type `A` et d'un second élément de type `B` est de type identique à celui d'un couple composé d'un premier élément de type `B` et d'un second élément de type `A`. Cela peut surprendre car on ne pense pas à l'apect qui effectue une permutation des composantes.

Notez que l'égalité de deux éléments est dépendante de leur type. Et en particulier, les éléments se différencient dans le type le plus générale, ce qui est tout à fait attendu. En effet dans une structure, les deux termes qui désignent respectivement les deux éléments en question sont rendus égaux par la théorie de la structure mais, dans le type le plus générale qui est le langage des termes, ils se différencient.

Puis dans la même trempe, on met en oeuvre l'associativité de l'opérateur `"×"`. Ainsi pour tout type `A,B,C`, nous avons `A"×"(B"×"C) = (A"×"B)"×"C` que nous notons `A"×"B"×"C` et qui constitue une liste. L'associativité va aplanir les arguments en une liste d'arguments qui ne sont pas des listes, pour former une liste dont la taille correspondra à une arité.

Ainsi, il apparait deux genres de type, les types de genre `"List"` et les types de genre `"No-List"`.

Les éléments de type disjoint sont énumérés sans ordre, tandis que les éléments de type égaux sont énumérés dans un ordre précis. Par exemple, considérons l'élément `a` de type `A`, l'élément `b` de type `B`, les deux éléments `x` et `y` de type `X`, et les deux éléments `u` et `v` de type `V`. La liste `(u,a,x,b,y,v)` peut alors se noter explicitement par `{(u,v),a,(x,y),b}` où les éléments entre `{}` sont disposés sans ordre, et les éléments entre `()` sont disposés dans un ordre précis. Et c'est l'aspect agissant entre l'élément et son type, qui déterminera l'ordre des composantes.

2.8) Les types d'application, `"→"`

Le type d'application `A"→"B` désigne l'ensemble des foncrions 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 les applications unaires. 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`

Quelle différence y-a-t-il entre une application binaire `f in A"×"B"→"C` et l'application unaire `g in A"→"(B"→"C)` telle que `g(x)(y)"="f(x,y)` ? On identifie ces deux applications c'est à dire qu'on les considére comme étant égales. 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.

On définit la façon dont une application `f` de type `A"×"B"→"C` va s'appliquer à un élément de `A`. On procéde à la curryfication de `f`, puis on applique.

On définit la façon dont une application `f` de type `A"×"B"→"C` va s'appliquer à un élément de `B`. C'est l'aspect décrit au chapitre précédent qui se charge de procéder à la permutation entre la place de l'argument de type `A` et la place de l'argument du type `B`, puis on procéde à la curryfication de `f`, puis on applique.

On définit la façon dont une application `g` de type `A"→"(B"→"C)` va s'appliquer à un élément de `A"×"B`. On procéde d'abord à la décurryfication de `g, puis on applique.

Ainsi, c'est le type des arguments qui décide du comportement de l'application.

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`. Et l'ordre des places `A,B,C` n'importe pas si les types `A,B,C` sont disjoints car l'aspect décrit au chapitre précédent se charge d'effectuer la bonne permutation.

Considérons l'ensemble des applications `A"→"B"×"C` ? Quelle différence y-a-t-il entre une application unaire `f in A"→"B"×"C` et le couple d'applications unaires `(g,h) in (A"→"B)"×"(A"→"C)` telle que `(g(x),h(x))"="f(x)` ? On identifie ces deux applications c'est à dire qu'on les considére omme étant égales. En effet `(g,h)` définit naturellement `f` qui définit naturellement `(g,h)`. La transformation d'une applicationà `n` résultats en une liste de `n` application à 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 `"×"`.

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))`.

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`.

2.9) La relation d'inclusion

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 le type `A"→"B` est inclus dans le type `X"→"Y`.

--- 22 avril 2020 ----

 

 

 

2.8) Les types d'opérateur

Les type d'opérateurs sont de la forme `A"→"B`, et désignent l'ensemble des opérateurs unaires qui appliqués à un élément de `A` produisent un élément de `B`.

 

 

2.3) Polymorphisme, union extensive disjointe de types, `+`

La première opération de construction de type est le polymorphisme en tant qu'union disjointe d'ensembles. Etant donnés deux types `A` et `B`. Il est possible de définir le type polymorphique `A"+"B` qui contient les éléments de type `A` et les éléments de type `B`, si et seulement s'il existe un critère de séparation entre les élément de type `A` et les éléments de type `B`.

Si on ne connait pas de critère séparateur, ou que celui-ci est jugé trop lourd à calculer, on peut en ajouter un en complétant les données de l'élément. L'élément s'enrichit d'une donnée dynamique binaire spécifiant s'il est de type `A` ou de type `B`. Le type polymorphique s'écrit alors

`A"×"{0,1}+B"×"{0,1}`

admettant par défaut les plongements suivants :

`A"↪"A"×"{0,1}`
`x"↦"(x,0)`

`B"↪"B"×"{0,1}`
`x"↦"(x,1)`

2.4) Plongement

Un type `A` se plonge dans un type `B`, ce qui se note `A"↪"B`, si et seulement s'il existe un traducteur de `A` vers `B`, c'est à dire :

Vérifiant les 2 propriétés suivantes :

L'application `f` est injective :

   `AA(x,y) in A^2, f(x)=f(y) =>x=y`   

L'application `f uu sigma_1 uu sigma_2 uu sigma_3` est un morphisme :

   `AAx in "Dép"(f), AAo in "Dép" (f_1), f(q(x)) = sigma_1(q)(f(x))`
`AA(x,y) in "Dép"(f)^2, AAo in "Dép" (f_2), f(q(x,y)) = sigma_2(q)(f(x),f(y))`
`AA(x,y,z) in "Dép"(f)^3, AAo in "Dép" (f_3), f(q(x,y,z)) = sigma_2(q)(f(x),f(y),f(z))`
`...`    

2.5) Opérateur interne

--- 20 avril 2020 ---

2.4) Union compréhensive disjointe de types, `"⊕"`

La compréhension du type désigne l'ensemble des propriétés, des méthodes et des données définissant le type en tant que classe d'objets.

Etant donné deux types `A` et  `B`. La compréhension des types peut toujours être rendu disjointe en complétant les nom des propriétés, des méthodes et des données, par le nom du type. De tel sorte qu'un élément à la fois `A`-compatible et `B`-compatible peut être perçu selon un type plus riche réunissant de façon disjointe les propriétés, les méthodes et les données des types `A` et `B`.

La définition cumulative peut être posée telle quelle, faisant que l'élément est de type `A"⊕"B` où le `"⊕"` désigne une union disjointe s'appliquant à la compréhension des types

2.8) Les types composés

On a vue l'union extensive disjointe `A"+"B` qui correspond à l'union disjointe des ensembles.

On a vue l'union compréhensive disjointe `A"⊕"B` qui cumules les données globales et méthodes et propriétés de `A` et de `B` sur les mêmes éléments. Cette dernière ne s'applique qu'à des types ayant la même extension.

Les types produit `A"×"B` correspondent à l'ensemble des couples.

Les type d'opérateurs sont de la forme `A"→"B`, et désignent l'ensemble des opérateurs unaires qui appliqués à un élément de `A` produisent un élément de `B`.

Les types récurcifs tels que `"<"A, "×>/{"× "est associatif"}`, et qui désigne

`A "+" A^2 "+" A^3 "+"..."+" A^n`

 

 

 

, se qui se note :

`"type"(x)"=Symbole"`

Ainsi avons-nous défini un opérateur de Omega vers Type

 

 

à relire (document obsolète):

  1. informatique/C/metaprogramme.htm
  2. informatique/C/system-list-entier.htm
  3. informatique/formel/automate.htm
  4. informatique/formel/formel.htm
  5. informatique/holistique.htm
  6. informatique/precompilation.htm
  7. informatiqueData/langages.htm
  8. informatiqueData/concepts.html

 

Reprise :

2) Les types dérivés

Qu'est-ce qui est plus général, une application de `A` vers `B`, ou bien une application de `E` vers `E` ? S'il fallait répondre vite à cette question, on répondrait la première, et on ferait une erreur, car chacune contient potentiellement l'autre. En effet les applications de `A` vers `B` couvrent toutes les applications de `E` vers `E` lorsque `A"="B"="E`, et réciproquement lorsque `E"="A"∪"B`, les applications de `E` vers `E` restreintes à `A` couvrent toutes les applications de `A` vers `B`. Et donc la plus générale des deux est la plus simple des deux, c'est à dire l'application de `E` vers `E`. Rappelez-vous cet adage, car il s'appliquera à d'autres situations : « Etant donné deux formes, si chacune est incluse dans l'autre alors la plus générale des deux est la plus simple des deux. »

Dans un ensemble `E`, l'ensemble des applications, défini au sens le plus générale, sera donc `E"→"E`, et l'ensemble les prédicats, défini au sens le plus générale, sera `E"→"{0,1}`. C'est comme cela que l'on construit les types dérivés de `E`. Parcontre `E` et `E"→"E` ne peuvent pas être unifiés, tout au plus peut-on plonger `E` dans `E"→"E` en associant à tout élement `y` l'application constante produisant `y`. Il découle de ce constat l'existence de nouveaux types dérivés `(E"→"E)"→"E`, `E"→"(E"→"E)` et `(E"→"E)"→"(E"→"E)`, et une infinité d'autres encore.

Puis on considère les produits `A"×"B` `A,B` sont des types dérivés de `E`. C'est l'ensemble des couples d'éléments où la première composante appartient à `A` et la seconde composante appartient à `B`.

En logique du premier ordre, ces deux opérations `"×"` et `"→"` vont suffire pour couvrir tous les types dérivés pertinent. Il y en a une profusions. Le langage de types est le langage d'opérateurs `"<"E, {0,1}, "×(.,.)","→(.,.)>"` où les opérateurs en question opérent non pas sur des éléments mais sur des types.

Lorque l'on explore les logiques d'ordres supérieurs, qui incorpore dans le langage la programmation, d'autres opérateurs de création de type apparaîtront, dont l'un des plus simples est l'opérateur de Kleen sans mot vide qui appliqué à un ensemble `A` se note `A^"+"` et constitue l'ensemble des listes finies non vides d'éléments de `A`.

3) Langage de types

À Partir du langage des types `"<"E, {0,1}, "×(.,.)","→(.,.)>"` qui met en oeuvre un paradigme de programmation qu'est la programmation orienté objet, nous allons définir des types plus généraux en les regroupant et en changeant leurs méthodes. On mettra pour cela en oeuvre un autre paradigme de programmation qu'est la programmation orienté aspect, qui va modifier le comportement des applications selon les types des arguments qu'on lui propose, et qui va nous permettre de regrouper des types analogues en un seul type plus général. Nous allons établir des règles d'égalités entre types, pour les regrouper dans des classes d'équivalence et les rendre égaux par la programmation d'aspects. L'ensemble de ces règles d'égalité formera une théorie des types. Et la contrepartie de ces règles constitura un ensemble d'aspects qui définira un mécanisme d'application des applications.

 

3.3) La non-distinction entre prédicat et opérateur

La distinction entre prédicat et opérateur ne doit pas s'opèrer immédiatement. Dans la métaphore du Big-Bang, au départ, tout est indifférencié. Il en est de même dans notre raisonnement. On définit la valeur logique comme un élément. Le prédicat est alors un opérateur de `A"→"E`, où `A` est un type dérivé de `E`

On définit un langage de types plus général obtenu modulo l'associativité de l'opération `"×"`, modulo la curryfication-décurryfication, et modulo la distribution-factorisation, et dans lequel on exclut les types numériques

3.4) La forme série

Une forme normale est obtenue en appliquant à chaque fois que cela est possible la curryfication et la distribution. On élimine ainsi l'opérateur `"×"` ailleurs qu'à la racine. Ainsi aparait deux sortes de type, un type unaire qui n'utilise que l'opérateur binaire de type `"→"`, et un type `n`-aire qui est une liste de `n` types unaires. La forme normale unaire correspond au langage de types `"<"E, "→(.,.)>"` c'est à dire à l'ensemble des types obtenus par compositions closes de l'opérateur binaire `"→"`, et de `E`.

3.5) La forme liste

Une autre forme normale est obtenue en appliquant à chaque fois que cela est possible la décurryfication et la distribution. L'opérateur `"×"` peut encore se trouver à la racine mais pas seulement, on lui interdit d'être à la racine de l'argument de droite d'un opérateur `"→"`. Ainsi aparait deux sortes de type, un type unaire qui utilise les deux opérateur de type `"×", "→"` mais en ne plaçant jamais un `"×"` à droite d'un `"→"`, et un type `n`-aire qui est une liste de `n` types unaires.

3) Langage de type

Il n'est pas pertinant de démultiplier les types pour la même raison que la forme la plus simple parmis deux formes se contenant potentiellement mutuellement est la plus simple des deux. Ainsi une application de `A"→"B``A` et `B` sont des sous-ensemblee de `E` se ramène à une application de `E"→"E` en la complétant n'importe comment.

Puis, le procédé de currification fait qu'une application de `A"→"(B"→"C)` est équivalente à une application de `A"×"B"→"C`.

L'entier `n` désigne le cardinale de `E`, et le nombre `Q` désigne la quantité d'information du type `E` c'est à dire la quantité d'information nécessaire pour choisir un élément dans `E`.

`n=|E|`

`Q"="ln(n)/ln(2)`

La liste des types considérés commence alors comme suit. Dans l'avant dernière colonne se trouve l'ordre de la logique qui quantifie ces types. Dans la dernière colonne se trouve la quantité d'information que représente la détermination d'un élément du type en question, c'est le logarithme en base `2` du cardinale du type pour obtenir une quantité d'information en nombre de bits :

Type
Forme série
Type
Forme liste
Ordre logique
Quantité
d'information
d'un opérateur
1
`E`
`E`
1
`Q`
1
`E"→"E`
`E"→"E`
2
`nQ`
2
`(E"→"E)"→"E`
`(E"→"E)"→"E`
3
`n^nQ`
`E"→"(E"→"E)`
`E"×"E"→"E`
2
`n^2Q`
5
`((E"→"E)"→"E)"→"E`
`((E"→"E)"→"E)"→"E`
4
`n^(n^n)Q`
`(E"→"(E"→"E))"→"E`
`(E"×"E"→"E)"→"E`
3
`n^(n^2)Q`
`(E"→"E)"→"(E"→"E)`
`(E"→"E)"×"E"→"E`
3
`n^(n"+"1)Q`
`E"→"((E"→"E)"→"E)`
`E"×"(E"→"E)"→"E`
3
`n^(n"+"1)Q`
`E"→"(E"→"(E"→"E))`
`E"×"E"×"E"→"E`
2
`n^3Q`
14
`(((E"→"E)"→"E)"→"E)"→"E`
`(((E"→"E)"→"E)"→"E)"→"E`
5
`n^(n^(n^n))Q`
`((E"→"(E"→"E))"→"E)"→"E`
`(E"×"E"→"E)"×"E"→"E`
3
`n^(n^2+1)Q`
`((E"→"E)"→"(E"→"E))"→"E`
`((E"→"E)"×"E"→"E)"→"E`
4
`n^(n^n n)Q`
`(E"→"((E"→"E)"→"E))"→"E`
`E"×"((E"→"E)"→"E)"→"E`
4
`n^(n^n)nQ`
`(E"→"(E"→"(E"→"E)))"→"E`
`(E"×"E"×"E"→"E)"→"E`
3
`n^(n^3)Q`
`((E"→"E)"→"E)"→"(E"→"E)`
`((E"→"E)"→"E)"×"E"→"E`
4
`n^(n^n)nQ`
`(E"→"(E"→"E))"→"(E"→"E)`
`(E"×"E"→"E)"×"E"→"E`
3
`n^(n^2)nQ`
`(E"→"E)"→"((E"→"E)"→"E)`
`(E"→"E)"×"(E"→"E)"→"E`
3
`(n^n)^2Q`
`(E"→"E)"→"(E"→"(E"→"E))`
`(E"→"E)"×"E"×"E"→"E`
3
`(n^n)n^2Q`
`E"→"(((E"→"E)"→"E)"→"E)`
`E"×"((E"→"E)"→"E)"→"E`
4
`n^(n^n)nQ`
`E"→"((E"→"(E"→"E))"→"E)`
`E"×"(E"×"E"→"E)"→"E`
3
`n^(n^2)nQ`
`E"→"((E"→"E)"→"(E"→"E))`
`E"×"(E"→"E)"×"E"→"E`
3
`(n^n)n^2Q`
`E"→"(E"→"((E"→"E)"→"E))`
`E"×"E"×"(E"→"E)"→"E`
3
`(n^n)n^2Q`
`E"→"(E"→"(E"→"(E"→"E)))`
`E"×"E"×"E"×"E"→"E`
2
`n^4Q`
...
...
...
...

`c_0"="1,c_1"="1,c_2"="2,c_3"="5,c_4"="14,c_5"="42,c_6"="132,...` sont les nombres de Catalan. `c_n` est le nombre d'arbres binaires nus à `n"+"1` feuilles.

 

---- 19 avril 2020 ----

à relire (document obsolète):

  1. informatique/C/metaprogramme.htm
  2. informatique/C/system-list-entier.htm
  3. informatique/formel/automate.htm
  4. informatique/formel/formel.htm
  5. informatique/holistique.htm
  6. informatique/precompilation.htm
  7. informatiqueData/langages.htm
  8. informatiqueData/concepts.html

 

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.

 

 

Dominique Mabboux-Stromberg