Nous voulons programmer un interpréteur idéal. Qu'est-ce qu'un interpréteur idéal ? C'est un interpréteur dont la construction découle d'un processus idéal et qui est capable d'interpréter efficacement un langage de programmation idéal. Qu'est-ce qu'un processus de construction idéal ?. C'est une construction qui découle de principes paradigmatiques et qui s'opère en une succession d'étapes qui sont chacune utilisable telle quelle. Ainsi chaque avancée peut être testée et utilisée pour démontrer la pertinence de nouveaux paradigmes. La construction n'est pas ingrate et motive ses auteurs. Qu'est-ce qu'un langage de programmation idéal ? C'est un langage développable permettant de construire facilement des programmes aussi compliqués soient-ils en développant le langage d'autant. Et qu'entendons-nous par efficacité d'inteprétation ? C'est une implémentation exploitant les connaissances introspectives des structures pour améliorer la rapidité d'exécution.
Un paradigme un peu particulier est l'auto-interprétation. L'interpréteur peut s'interpréter lui-même s'il est écrit dans le langage qu'il interpréte. Selon l'adage bien connue, la moitier du problème est résolue lorsque l'on a trouvé le langage approprié pour le transcrire. C'est pourquoi la conception de notre interpréteur ira de paire avec la conception d'un langage dit auto-interprétatif, c'est à dire adapté à programmer un interpréteur de ce même langage.
Les concepts à mettre en oeuvre sont ceux couramment rencontrés. On considèrera le langage impératif, fonctionnel, d'aspets, d'objects, de types, et de contextes. Ainsi on ajoute au dessus de la donnée et du type, quelque niveau supplémentaire appellé contexte. Puis on concidèrera les automates reconnaissant efficacement les langages rationnels. Puis on concidèrera l'unification de complexité linéaire entre termes d'un langage d'opérateurs. Puis on mettra en oeuvre l'inférence des types et des contextes...
Tout est langage et il y a 3 niveau de langage ; le langage rationnel reconnaissable par un automate, le langage d'opérateurs dans lequel l'unification est de complexité linéaire, et le langage d'opérateurs d'arité variable qui est plus vaste.
Notre interpréteur ne veut pas se fixer un langage. Il souhaite interpréter tous les langages possibles dans le cadre de ce schéma à trois niveaux (langages rationelles, langages d'opérateurs, langage d'opérateurs d'arité variable). L'interpréteur commence donc par établir dans un contexte le langage qu'il va interpréter. Et il y a nécessairement un contexte par défaut permettant de commencer la programmation, un commencement.
Puis il y a les trois versants sémantiques du langage que sont le langage de données, le langage de programmation, et le langage de propriétés, qui sont incontournables si on veut atteindre la clef de voute, la pierre philosophale des informaticiens mathématiciens. C'est pourquoi l'interpréteur est de la famille des démonstrateurs de théorèmes.
Tout est langage avons nous dit, même ce que produit le compilateur, le langage machine ou code exécutable. Mais nous pouvons nous appuyer sur un intermédiaire qui a fait ses preuves dans le développement de Linux et qui est le compilateur gcc. Ainsi on compile en deux étapes, une première compilation pour obtenir un programme écrit en langage C (ou C++), et une seconde compilation à l'aide de gcc pour obtenir du code exécutable. Dans les premières étapes l'interpréteur et le compilateur seront étudiés en même temps.
Commençons par un premier niveau ne comprenant aucune variable. L'interpréteur traduit le langage de caractères en langage d'opérateurs en respectant la définition des types regroupés dans une entité plus générale appellée contexte. Nous pourrions nous limiter à appliquer une grammaire syntaxique fixée une fois pour toute, mais comme nous ne voulons rien figer, nous partirons d'un contexte variable qui porte la sémantique pour engendrer une grammaire syntaxique la moins limitative possible. Et comme nous partons d'un contexte générale pour ne le spécialiser qu'en cas de nécessité, les erreurs de syntaxe s'avèreront rares. Un caractère érroné introduira probablement un nouvel élément qui sera interprété commme tel, c'est à dire comme une extension élémentaire et non comme une erreur de syntaxe. D'autres mécanismes de contrôle devront être mis en oeuvre par le programmeur pour le prémunir contre ces erreurs.
S'il n'y a pas de variable poprement dite, il y a quand même des méta-variables que sont les variables d'entré du programme et qui contiennent des chaines de caractères. Selon le principe impératif, le résultat d'un programme en dehors des exceptions est la première instruction return(.) rencontrée évaluée ou, s'il n'y en a pas, la dernière instruction évaluée. Puis les méta-variables d'entrés sont nommée comme dans le shell Bash par $1, $2, $3.... On préfère les nommer x,y,z.... Étant sans variable à ce stade, on ne peut pas manipuler un nombre de méta-variables d'entré qui soit variable. L'arité d'entré du programme est fixé.
Le langage doit permettre de pouvoir appliquer un programme (un sous-programme qui n'est pas le programme principal) sur une liste d'arguments en nombre correspondant à l'arité d'entré du programme. Pour cela, il faut définir dans le langage un constructeur de programme, un constructeur de liste, et l'opération appliquant un programme sur une liste d'arguments. Le programme s'appel une fonction.
Le constructeur de fonction est noté comme un bloque de code, une liste d'instructions séparées par des points virgules et mise entre crochet, telle que par exemple :
{instrution1 ; instruction 2 ; insruction3}
Et comme le programme est écrit dans le même langage que le programme principal, il utilise les mêmes noms de méta-variables d'entré. Mais alors, le langage doit pouvoir permettre de désigner une variable d'entré du programme contenant, et aussi du programme contenant le programme contenant et ainsi de suite. C'est le rôle d'un opérateur particulier, l'anticote, qui va remonter d'un niveau d'environnement de méta-variables d'entrées.
Si une méta-variable n'est pas définie dans un bloc de code, elle fait référence alors à un bloque de code contenant. On perçois donc deux définitions possibles de l'opérateur anticote. Soit il correspond exactement à la remonté d'un envionnement, soit il correspond à la remonté d'un mascage de la méta-variable et cela peut correspondre à la remonté de plusieurs environnements emboités d'un coup. C'est cette dernière définition qui est utilisée dans le langage courant. Lorsqu'un symbole s est redéfinie, l'opérateur anticote permet de faire référence à la première définition antérieur du même symbole, `s, et l'anticote peut s'appliquer plusieurs fois de suite ``s.
Pour éviter la nécessité de cet opérateur qu'est l'anticote, le constructeur de fonction est parfois noté à l'aide de l'opérateur -> avec comme premier argument, les noms des méta-variables toujours nouveaux, tel que :
(u,v,w)->{instrution1; instruction 2; insruction3}
ou selon la syntaxe ruby en intégrant dans le bloque de code la liste des noms des méta-variables :
{|u,v,w| instrution1; instruction 2; insruction3}
Ainsi les noms des méta-variables font partie d'un contexte qui s'agrandie à chaque niveau d'environnement que crée l'opérateur -> sur son argument de droite ou que crée l'ouverture d'un bloque de code. Et on choisie toujours des noms nouveaux faisant que ces méta-variables ne peuvent pas se masquer entre-elles.
Puis grâce à la currification, on remarque qu'un programme d'arité n peut s'appliquer sur un seul argument pour retourner un programme d'arité n-1 sans en altérer la complexité, faisant qu'il est possible d'abandonner les listes d'arguments au profit d'une succession d'opérations appliquant un programme sur un argument telle que par exemple :
P(x,y,z) = P(x)(y)(z)
P = u->{v->{w->{instrution1; instruction 2; insruction3}}}
P = {|u|, {|v|, {|w| instrution1; instruction 2; insruction3}}}
L'opérateur -> s'évalue dans le sens inverse (de droite à gauche). Ce choix syntaxique permet d'écrire cette traduction en une succession d'opération appliquant un programme à un élément sans avoir à utiliser de parenthèses.
Le langage doit alors définir un constructeur de programme à partir de noms de méta-variables toujours nouveaux, et l'opération appliquant un programme sur un argument. Dans de nombreux langages fonctionnels, l'opération appliquant un programme P sur un argument x est simplement notée par l'absence de symbôle et s'évalue dans le sens normal de gauche à droite : Ainsi nous avons :
P(x,y,z) = P x y z
L'absence de symbole est spécifiée ici par un caractère blanc qui assure la séparation des noms mais qui n'est pas nécesaire si la syntaxe effectue déjà cette séparation.
Nous avons définie 3 opérateurs que sont le constructeur "->" qui enrichie à chaque utilisation le contexte d'une nouvelle méta-variable (qui est un élément, un opérateur d'arité zéro), la suite d'instruction ";" et l'appliquant qui est désigné par l'absence de symbole. On constate que les crochets { } joue le même rôle que les parenthèses ( ) pour spécifier une priorités, c'est pourquoi on peut les remplaçer par des parenthèses ou par rien si les priorités des opérateurs conviennent déjà. On fixe les priorités des opérateurs tel que l'usage des parenthèses soit parmi le moins sollicité.
((··)·)·)·) ((·;·);·);·);·) (·->(·->(·->·)))
Considérons deux programmes de bases A(.), B(.,.), d'arité 1 et 2, et pouvant servir également de données. On peut construire un programme à partir d'eux. Voici un exemple de programme d'arité 1 et de méta-variable d'entré x et qui possède un sous-programme d'arité 2 et de méta-variables d'entré (y,z) :
x->(y->z->A y; B z y) (A x) B
Le programme se simplifie en effectuant l'application, c'est à dire en substituant les méta-variables par leur valeur d'affectation et en ne gardant que le corps de la fonction :
A (A x);B B (A x)
Ce langage est le lambda calcul, construit par le bas, et enrichie de la composition série d'instructions ";" et de l'opérateur unaire return propres au paradigme impératif.
Si nous partons d'une hypothèse plus faible où chaque programme ne possède qu'une seul méta-variable d'entré, le raisonnement nous amène pareillement à concevoir un constructeur de programme "->", une composition serie d'instructions ";" et l'opérateur appliquant " ". On remarque alors que la currification utilisée dans le sens inverse nous permet de définir les programmes à plusieurs variables d'entré de la même façon. Parcontre dans le cas où nous choisisons d'utiliser toujours le même nom de méta-variable x et d'utiliser l'anticote pour remonter les différents environnements c'est à dire pour remonter les différentes définitions de cette variable, nous obtenons alors un second langage, composé d'un opérateur unaire λ de construction de programme, d'un opérateur de composition série d'instruction ";", de l'opérateur appliquant un programme à un argument " ", d'un opérateur zéro-aire qu'est le symbole x, et de l'opérateur unaire, l'anticote "`". Mais ces deux derniers sont remplacés par une liste d'opérateurs unaires x,y,z,t... où x=x, y=`x, z=``x, t=```x...
((··)·)·)·) ((·;·);·);·);·)
(λ(λ(λ(λ·))))
Considérons deux programmes de bases A(.), B(.) .On peut construire un programme à partir d'eux. Voici un exemple de programme :
(λAx;λAx;By)(Ax)B
Le programme se simplifie en effectuant les applications, c'est à dire en substituant les méta-variables par leur valeur d'affectation.
A (A x); A B; B (A x)
On appelera ce langage le lambda calcul bis, construit par le bas, et enrichie de la composition série d'instructions ";" et de l'opérateur unaire return propres au paradigme impératif.
Si on garde l'anticote et le seul symbole x comme méta-variable. On obtient un nouveau langage. L'anticote peut s'appliquer à une expression faisant remonter d'un niveau de contexte l'expression en question. Ainsi chaque utilisation de l'opérateur λ crée un contexte pour son argument, et ce contexte s'emboite dans le contexte déjà présent, et chaque utilisation de l'anticote remonte d'un contexte son argument.
Opérateur binaire |
Symbole |
Priorité |
Sens d'évaluation |
|
Appliquant |
6 |
--> |
((··)·)·)·) | |
Série d'instructions |
; |
4 |
--> |
((·;·);·);·);·) |
Opérateur unaire |
Symbole |
Priorité |
Sens |
|
Anticote |
` |
8 |
<-- |
(`(`(`(`·)))) |
Constructeur |
λ |
2 |
<-- |
(λ(λ(λ(λ·)))) |
....
Il n'y a pas de type. Un programme est un argument et réciproquement un argument est un programme. Tous deux sont des chaines de caractères dont l'interprétation dépend d'un contexte qui possède une porté et qui est emboité dans d'autres contextes...
....
Dans un langage idéal, la formulation d'une donnée, d'une fonction ou d'une propriété, écrite dans le langage de la matière concernée, est recopiée à l'identique dans le programme qui l'utilise. On reporte dans le contexte la charge de s'adapter à la matière pour pouvoir lire la formulation dans son scripte d'origine. Cela constitue pour nous, la vrai condition de lisibilité d'un programme.
---- 7 mai 2015 ----
Le langage mathématique utilisé est un langage d'opérateurs d'arité variable opérant sur des opérateurs pour produirent d'autres opérateurs.
L'opérateur peut être typé en spécifiant les types de ses opérandes et le type de son résultat. Dés lors des erreurs de syntaxe peuvent avoir lieu si on fait opérer un opérateur typé sur un argument de type non autorisé ou sur un nombre d'arguments non autorisé.
Des opérateurs typés dont le typage est bien distinct peuvent être nommés par le même nom sans qu'il y ait d'ambiguité.
L'arité d'un opérateur peut être déterminé par son type. Les opérateurs d'arité nulle sont appellés éléments.
Selon le paradigme de la programmation fonctionnelle, et selon le mécanisme de currification, l'application d'un opérateur sur une liste d'arguments se traduit par une séquence. Exemple : f(x,y,z) sera traduit par l'expession f x y z qui est une séquence d'opérateurs avec comme séparateur, le caractère blanc. Et il est reporté dans la syntaxe des opérateurs, les règles permettant de déterminer l'arbre d'évaluation de l'expression.
Les règles syntaxiques portent une partie du fondement, une connaissance topologique intrinsèque du langage en tant que flux de données transitant sur une ligne.
Un opérateur unaire f peut opérer à gauche ou à droite, x f = f(x) ou f x = f(x). On note f(1) l'opérateur unaire droit et f(-1) l'opérateur unaire gauche. Ainsi f(1) représente la fonction x |-> f(x), mais il n'existe pas de telle notation pour f(-1). Si nous délimitons les expressions par des crochets { }, nous avons :
{f(1)} x = f(x)
x {f(-1)}= f(x)
Deux opérateurs unaires droits f et g peuvent se combiner de 3 façons possibles. L'expression f g est égale à f(g(1)) ou autrement dit à x|->f(g(x)) ou bien est égale à f(g) ou bien est égale f(1) g(1) ou autrement dit à x|->f(x) g(x) qui représente l'appel parallèle. L'appel série n'est pas mentionné car inutile puisqu'il peut déjà s'écrire par f x g y = f(x) g(y), alors que l'appel parallèle fait l'économie de répéter l'argument et donc de refaire l'évaluation de l'argument plusieur fois. Aussi simple que cela puisse paraître, l'appel parallèle permet de tenir compte de la complexité du calcul des opérateurs, et donc permet de proposer un langage de programmation efficient.
Deux opérateurs unaires gauches f et g peuvent se combiner de 3 façons possibles. L'expression f g est égale à g(f(-1)) ou bien est égale à g(f) ou bien est égale à f(-1) g(-1) qui représente l'appel parallèle.
x {f(-1) g(-1)} = f(x) g(x)
L'appel série s'écrit comme suit x f y g = f(x) g(y)
Un opérateur unaire droit f suivi d'un opérateur unaire gauche g peuvent se combiner de 5 façons possibles. L'expression f g est égale à f(g(-1)) ou g(f(1)) ou f(g) ou g(f) ou f(1) g(-1), tandis qu'un opérateur unaire gauche g suivi d'un opérateur unaire droit f se combinent d'une seul façon possible, g f = g(-1) f(1).
x{g(-1) f(1)}y = g(x) f(y)
Il reste à trouver des critères syntaxiques parmis les plus appropriés pour réduire l'usage des parenthèses. Chaque opérateur de base possèdera des qualités syntaxiques. Et l'ensemble de ces qualités syntaxiques devront déterminer pour chaque expression un unique arbre de composition.
Pour cela il est nécessaire que les qualités syntaxiques du résultat de l'évaluation d'un opérateur soient déterminées par les qualités syntaxiques de l'opérateur en question (et éventuellement de ses arguments.)
Noter qu'il n'y a pas de distinction entre une composition d'éléments est une séquence d'éléments, et que d'une manière générale il n'y a pas de distinction entre le méta-opérateur d'application et le méta-opérateur de séquence. Cela est pertinent car la currification transcrit un programme sans augmenter sa complexité comme nous l'avons déjà remarqué au début de ce chapitre.
Chaque opérateur de base d'arité supérieur à zéro possède une priorité syntaxique.
Un opérateur binaire f peut opérer à gauche au centre ou à droite, x y f = f(x,y) ou x f y = f(x,y) ou f x y = f(x,y). S'il opère au centre, il possède un sens d'évaluation gauche ou droite.