La conception d'un langage de programmation idéal va de paire avec la conception de l'interpréteur capable de l'interpréter et de l'exécuter. Et nous souhaitons développer cet interpréteur par le bas, c'est à dire à partir des éléments rudimentaires de programmation que nous offre un système d'exploitation tel que Linux.
Ainsi, nous voulons programmer un interpréteur universel en commençant notre développement par en bas, en proposant des versions du plus simple interpréteur jusqu'au plus évolué des interpréteurs, tel le developement 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.
Procédant ainsi, on subordonne l'introduction de nouveaux concepts aux seules possibilités de construction offertes par la couche logiciel en cours.
L'émergence d'un nouvel interpréteur correspond à l'émergence d'un nouveau langage formel.
Le langage d'opérateurs d'arité fixe constitue notre premier choix, une première étape, incontournable dans l'appréhension des langages formels.
A chaque étape, l'interpréteur 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 développement, voir développement holistique.
A chaque étape, se présentera un interpréteur et son langage de nom `sfL_n`, complété ainsi par un numéro d'étape `n`. À certaine étapes nous rencontrerons différents choix possibles exclusifs, formant une fourche dans l'évolution des versions.
Pour les choix suivants, il convient évidement de préparer le terrain, d'explorer différentes notions et concepts loin devant afférents aux langages formels, d'entretenir une reflexion éclectique, ce qui s'est fait aux cours des discussions ci-dessous :
Un opérateur est un nom c'est à dire une chaine de caractères. Il possède une arité fixe, et peut prendre plusieurs formes comme par exemple `f(x,y)` ou bien `xfy` ou bien `f x y`. Nous allons aborder la syntaxe en regardant les premières constructions qu'il est possibles de faire. La syntaxe par défaut consiste en la forme fonctionnelle anglaise telle qu'illustée par l'exemple `f(x,y)`.
L'opérateur nullaire possède un nom tel que `e` et ne possède pas d'autre rôle. Donc la formule `e()` n'est pas autorisée.
La première sémantique à laquel on pense est celle obtenue sans effort : L'opérateur n'est qu'un alias. Il y a deux mondes : le monde réel constitué par la couche logiciel de base, et le monde idéal constitué par notre langage formel.
L'opérateur d'arité `n` qui fait partie du monde idéal est associé à une procédure d'arité `n` qui fait partie du monde réel. L'interpréteur va simplement traduire chaque opérateur rencontré par la procédure qui lui est associé et procéder à l'appel de fonction en remplaçant chaque argument par un argument réel et retournant un résultat réel.
Tous les arguments et résultats réels sont de même type réel, et tous les opérateurs de notre langage sont de type `E` ou d'un type de la forme `E^n"→"E` où `E` représente l'unique type de base dans notre langage `L_1`.
L'opérateur nullaire est associé à une procédure réelle sans argument produisant une donnée réelle. De là, apparaît le concept de donnée réel.
On est sous l'ère de Linux. La première forme d'implémentation s'appuit sur le système d'exploitation et le terminal de commande en shell Bash. Chaque opérateur du langage idéal constitue un alias d'une commande réel présente dans le shell (qui est un nom de programme accessible via le PATH) et qui doit avoir le même nombre d'arguments que l'arité de l'opérateur, et dont les arguments et le résultat sont des données d'un même type réel unique.
Une première difficulté apparaît dans la transmission des arguments réel à la procédure réel. En effet, le shell ne prévoit que des arguments de petite taille et en petit nombre transmis dans la ligne de commande, et un argument de grande taille transmis par l'entrées standart.
Cette contrainte technique nous oblige à concevoir une première version de notre interpréteur n'utilisant que des arguments réels de petite tailles, mais pouvant quant-même interprété une formule de taille gigantesque.
Le langage est alors défini dans un dictionnaire qui est une liste de triplets. Chaque triplet contient un nom d'opérateur idéal, un entier désignant l'arité de l'opérateur, et le nom d'une procédure réel ayant le même nombre d'arguments. Mais attention, les arguments et les résultats doivent tous être des données d'un même type réel unique.
Une autre contrainte technique concerne la forme des données réels qui doivent être des chaines de caractères ne comprenant pas de guillemet car dans sa forme la plus pratique, le guillemet est utilisé pour délimité la chaine de caractère servant d'argument dans une ligne de commande.
On met en oeuvre cet interpréteur L1 sous forme d'une ligne de commande en shell Bash s'executant dans un terminal possédant un environnement. L'interpréteur agit pour le compte de ce terminal. Il utilise le langage `L_1` qui doit être mémorisé dans l'environement du terminal. Il interprète une formule et l'exécute dans le terminal. Si la formule est de petite taille, elle peut être transmise comme argument en ligne, sinon elle doit être transmise par l'entrée standard. Puis l'exécution de la formule sera susceptible de modifier l'environnement du terminal et le langage lui-même.
Une troisième difficulté alors apparaît pour modifier l'environnement du terminal. Car dans la conception même du système Linux, un processus ne peut pas changer l'environnement de son processus père. L'interpréteur est un progamme à part entière qui s'exécute dans un processus fils du terminal.
On contourne la difficulté en utilisant un environnement partagé qui est un fichier temporaire, et donc, qui est accessible en lecture-écriture par tout processus mais de façon non-simultanée. Pour assurer la rapidité d'accès, on crée ce fichier temporaire en mémoire vive comme suit :
mkdir /home/martin/ram
sudo mount -t tmpfs -o size=1000M none /home/martin/ram
Et pour le démonter :
sudo umount /home/martin/ram
Notez que la taille de ce fichier temporaire est limitée arbitrairement.
La première opération consiste à mémoriser le dictionnaire du langage dans l'environnement partagé, ce qui se fait par exemple par la commande suivante :
echo "f 2 F g 3 G h 0 H" > /home/martin/ram/L1
Le shell Bash utilise les redirections ce qui permet de mettre les données arguments dans des fichiers textes. On peut donc pré-enregistrer le langage dans un fichier local L1 puis après, le recopier :
echo "f 2 F g 3 G h 0 H" > data
cat data > /home/martin/ram/L1
La seconde opération est l'interpréteur lui-même qui porte comme nom L1 et qui prend en argument une formule. Par exemple :
L1 "f(g(h,h,h),f(h,f(h,h)))"
et si la formule est de grande taille, elle est transmise par l'entrée standard :
echo "f(g(h,h,h),f(h,f(h,h)))" > F cat F > L1
ou avec un pipe :
echo "f(g(h,h,h),f(h,f(h,h)))" | L1
Nous programmons la commande L1 qui constitue notre interpréteur, en utilisant le langage de programmation Go. Le dictionnaire du langage idéal `L_1` est mémorisé dans le fichier /home/martin/ram/L1. On le récupère sous forme d'une string s par l'instruction
s, e := ioutil.ReadFile("/home/martin/ram/L1")
La première contrainte technique sur le shell nous oblige à deux formes d'appel de notre interpréteur. La formule à executer est transmise soit comme paramètre en ligne de commande, ou soit par l'entrée standart si sa taille est trop grande pour tenir en ligne de commande.
Le programme L1 commence par ces lignes. Le dictionnaire du langage est mémorisé dans la variable m de type dictionnaire :
package main import (
"errors"
"fmt"
"io/ioutil"
"os"
"strconv"
"strings"
)type Proc struct {
n int
p string
}func main() {
// Pour la foncion panic et errors.New
// Pour afficher, fmt.Println
// Pour la fonction ioutil.ReadAll
// Pour l'entrrée standart, os.Stdin
// Pour la fonction strconv.Atoi
// Pour la fonction strings.Fields et le tpe string
// n = arité de l'opérateur
// p = nom de la procédure
//----- Charge le dictionnaire du langage ---------------------------------------------------------------------------------------------
s, e := ioutil.ReadFile("/home/dmabboux/ram/L1")
if e != nil {
panic(e)
}
m := map[string]Proc{}
k := strings.Fields(string(s))
n := len(k)
if n%3 != 0 {
panic(errors.New("Langage incomplet"))
}
for i := 0; i < n; i += 3 {
j, e := strconv.Atoi(k[i+1])
if e != nil {
fmt.Println(e)
}
m[k[i]] = Proc{j, k[i+2]}
}
// Récupère dans s le langage L1
// Émet l'éventuel erreur d'entrée/sortie
// Crée un dictionnaire
// Transforme " f 2 F g 3 G " en [f 2 F g 3 G]
// Nombre de mots dans la définition du langage
// Si n n'est pas un multiple de 3 alors on émet une erreur.
// Pour i = 0. 3. 6. 9, ... , n
// j = l'entier correpondant à la chaine k[i+1]
// Émet l'éventuel erreur de reconnaissance d'un entier
// Ajouter au dictionaire le mot k[i] associé au couple {j,k[i+2]}
//------ Lit la formule ---------------------------------------------------------------------------------------------------------------------- f := ""
if len(os.Args) == 1 {
v, e := ioutil.ReadAll(os.Stdin)
if e != nil {
panic(e)
}
f = string(v)
} else {
u := os.Args[1]
f = string(u)
}
// S'il n'y a pas d'argument en ligne
// Récupère dans v la formule arrivant par l'entrée standart
// Émet l'éventuel erreur d'entrée/sortie
// Récupère la formule arrivant par la ligne de commande
//------ Test ---------------------------------------------------------------------------------------------------------------------- fmt.Println(m)
fmt.Println(f)for f != "" && f[0] == byte(' ') {
f = f[1:]
}
fmt.Println(f)r := []rune(f)
fmt.Println(r)
}
// Retire les premier caractères blancs
// Convertit la chaine en un tableau de mots de 32 bits
On utilise la norme internationale Unicode qui codifie le plus vaste jeux de caractères provenant du monde entier, comprenant toutes les langues et les jeux de symboles. Et on utilise la norme UTF-8 qui permet pour les caractères courant de tenir que sur un seul octet, puis sur 2 ou 3 ou 4 octets pour des caractères qui s'avèrent moins utilisés.
Pour faciliter la programmation, on a besoin d'une liste de caractères de même taille c'est pourquoi on procède à une convertion de la chaine de catactères en un tableau de runes, où une rune est un mot de 32 bits (4 octects), comme si nous utilisions la norme UTF-32.
Il y a deux solutions, l'une dite récurcive qui s'applique sur des formules de taille suffisament raisonnable pour que la pile d'appels ne déborde pas, l'autre dite progressive qui s'applique à des formules de taille gigantesques. La solution récurcive lit la formule en lançant un processus récurcif. Par exemple, considérons la formule `f(g(h,h,h),f(f(h,h),h))`. L'interpéteur `varphi` lit le premier opérateur `f` et lance la commande F appliqué aux arguments qui sont le résultat d'une lecture par l'interpréteur des sous-formules correpondantes. Nous obtenons :
`varphi( f(g(h,h,h),f(f(h,h),h)) ) = sfF( varphi( g(h,h,h) ), varphi( f(f(h,h),h)) ) )`
`varphi(h) = H`
La solution progressive lit la formule et convertit les feuilles, c'est à dire les opérateurs nullaires, et converti les opérateurs dont tous les arguments sont des données réels. Puis on recommence l'opération jusqu'à n'avoir qu'un seul résultat réel. Considérons par exemple la formule `f(g(h,h,h),f(f(h,h),h))`. L'interpéteur `varphi` fait une première lecture et convertit toutes les feuilles.
`varphi( f(g(h,h,h),f(f(h,h),h)) ) = f(g(H,H,H),f(f(H,H),H))`
`varphi( f(g(H,H,H),f(f(H,H),H)) ) = f(A,f(B,H))`
`A=G(H,H,H)`
`B= F(H,H)``varphi( f(A,f(B,H)) ) = f(A,C)`
`C= F(B,H)``varphi( f(A,C) ) = D`
`D = F(A,C)`
On remarque que les deux solutions passent par un langage élargie incorporant les données réel avec la même syntaxe idéale.
A ce stade, l'interpréteur reconnait le premier opérateur comme la chaine sans caractère blanc se situant collée au caractère "(". Puis il reconnait les arguments séparés par des virgules au premier niveau de parenthèse et qui peuvent être espacés par des caractères blancs. Plusieur erreurs de syntaxes peuvent se produirent :
Deslors, l'appel `g(h,,)` désigne l'appel de l'opérateur `g` avec trois arguments dont le premier est `h` et le second ainsi que le troisième est l'argument vide. Il existe donc un argument vide, et qui n'est pas référencé dans le dictionnaire, et qui s'écrit comme donnée réel par la chaine vide "".
L'interpréteur, après avoir repéré l'opérateur acollé à la parenthèse ouvrante, va énumérer les sous-formules correspondant aux arguments qui sont séparées par des virgules au premier niveau de parenthèse et par la parenthèse fermant ce premier niveau.
Apparait la notion de données textes ou binaires. La donnée se présente sous forme d'un bloc contiguë d'octets formant une chaine de caractère.
Une donnée binaire possède une taille fixe exprimés en nombre d'octets et admet toutes les valeurs possibles. Un octet admet 256 valeurs possibles.
Une données texte est une chaine de caractères au format unicode/utf8 et qui est délimité. Il existe plusieurs sortes de délimitation. Celle utilisée par les arguments d'une fonction dans une commande ligne du shell, consiste le plus simplement en l'entourage de l'argument par des guillemets, faisant que le guillemet ne doit pas être utilisé dans la chaine de caractères. L'usage du caractère guillemet est ainsi réservé par le protocole de bas niveau.
La résolution passe par une extension du langage idéal en introduisant les données réels
---- 9 novembre 2022 ----