Le but de cet essai est de programmer un moteur de calcul formel en commençant par explorer les opérations élémentaires que peut faire un programme en matière de calcul formel, ici écrit en JavaScript pour avoir la portabilité et la diffusion via Internet. On commence donc par traiter les chaînes de caractères et des automates avant d'aller plus loin pour mettre en œuvre des grammaires.
Un moteur de calcul formel est avant tout un interpréteur dont on va concevoir un tout premier embryon : un interpréteur minimal qui interprète un langage de programmation lui-même minimal et que l'on programme dans ce même langage. Ainsi la boucle est bouclée, le programme s'analyse lui-même, obligeant à une politique de développement beaucoup plus cadrée. Cela permet de ne pas se disperser dans les multiples possibilités de perfectionnement qui foisonnent à chaque étape. Car chaque perfectionnement choisi devra s'inscrire dans ce processus réflexif d'un langage qui est interprété par un programme écrit dans ce même langage.
L'ensemble des outils que nous développons formera un framework accompagné d'un catalogue d'applis web interactives destinées aux usagers pour tester et utiliser chacun de ces outils.
Nous optons pour l'Unicode et l'UTF-8 afin de stocker de manière concise les chaînes de caractères qui peuvent contenir des caractères de toutes les langues du monde. L'inconvénient est que tous les caractères n'ont pas la même taille en octets, ce qui rend impossible un saut direct de `n` caractères dans une chaîne. Par conséquent, il faudra envisager un type de tableau différent des chaînes de caractères pour réaliser ce genre d'opération.
Le traitement le plus simple que l'on conçoit sur une chaîne de caractères est celui fait par un automate qui lit la chaîne de caractères appelée mot, caractère par caractère, en un seul passage. L'automate dans sa généralité est alors un graphe fini étiqueté et orienté, où il y a un sommet n° `0` qui sert de début, où chaque sommet constitue un état de l'automate et possède une valeur `0` ou `1` qui indique si le mot dont la lecture se termine à cet état est accepté ou refusé, et où pour chaque sommet les arcs partant sont labellisés par un caractère. Au départ, l'automate est à l'état `0`. Chaque lecture d'un caractère correspond à un déplacement via un arc labellisé par le même caractère, partant de l'état en cours pour aller sur le nouvel état de l'automate. Le mot peut être refusé en cours de route si à une étape de lecture aucun arc n'est empruntable. Si pour chaque sommet, c'est-à-dire pour chaque état, les labels des arcs partants sont tous distincts alors l'automate est déterministe, sinon il est indéterministe et plusieurs changements d'état peuvent être possibles à la lecture d'un caractère.
Il reste à trouver la notation la plus pertinente pour définir cet automate : Une liste d'états, où chaque état comprend son numéro, un booléen et une liste d'arcs partants, où chaque arc partant comprend un caractère qui est son label et un état destinataire. Soit 3 sortes d'appel : Liste(...), État(.,.,.), Arc(.,.). On ne va pas chercher la meilleure solution, juste une solution pragmatique forcément très redondante en nommant les états et en suivant les conventions par défaut. L'expression de l'automate sera alors par exemple :
Liste(
État(0, 0, Liste(Arc("a", 1), Arc("b", 1))),
État(1, 0, Liste(Arc("c", 0), Arc("d", 2))),
État(2, 1, Liste())
)
Notez que le caractère de délimitation des chaînes étant le guillemet, celui-ci ne doit pas être utilisé dans les chaînes de caractères et donc dans le mot d'entrée.
L'automate est le b.a.-ba de la programmation, il représente un algorithme de complexité linéaire, sous forme d'organigramme. À chaque caractère lu du mot d'entrée, un arc est franchi et un changement d'état a lieu. À chaque arc franchi ou à chaque changement d'état, l'automate peut lancer une commande avec comme paramètres l'état avant et après et le caractère lu. Puis en cas de rejet en cours de lecture lorsqu'aucun arc ne peut satisfaire la lecture d'un caractère, il peut lancer une seconde commande, toujours avec comme paramètres le caractère, l'état avant et après et le caractère lu. Et à la fin de la lecture du mot d'entrée, l'automate peut lancer une commande avec comme paramètres le mot d'entrée et l'état final. Et cela toujours en respectant une complexité linéaire.
Reste à codifier ces appels de commande avec paramètres et à les intégrer dans l'expression de l'automate, puis reste à codifier l'appel de commande et la commande elle-même exécutant l'automate sur un mot d'entrée. La codification de ces opérations définit un langage de programmation minimal qui à son tour doit être capable de les définir en les programmant. Ainsi nous définissons notre interpréteur embryonnaire en définissant un langage embryonnaire capable de le programmer.
Un programme s'exécute toujours sur un ordinateur (le hardware) et sur un système d'exploitation (le software) comprenant le noyau complété par des programmes accessoires. C'est le noyau le plus important et qui constitue la couche logicielle sous-jacente sur laquelle s'appuit notre interpréteur. Le dialogue avec le noyau ce fait par l'intermédiaire de commandes shell. "Shell" est un mot anglais qui signifie "coque", et désigne en quelque sorte l'interface entre le noyau et le programme qui est à l'extérieur du noyau. Le shell est le langage générique permettant de lancer des commandes au noyau. Chaque système d'exploitation possède son shell. Sous linux, le langage shell sera généralement le Bash.
Mais nous n'allons pas développer notre interpréteur directement au dessus du noyau, nous le développons sur une couche logicielle intermédiaire contenue dans le navigateur Interrnet qui est le DOM et son moteur javascript.
Le javascript est donc utilisé ici comme un shell. Et nous allons définir par dessus, un langage de programmation minimaliste et un interpréteur minimaliste programmé dans ce langage de programmation minimamiste. On choisi d'abord un interface utilisateur minimaliste où l'utilisateur place son programme dans un textarea, clique sur le bouton Run pour l'exécuter et où le résultat texte sort ligne par ligne avec l'instruction javascript document.write(.) sur une nouvelle page web.
---- 22 avril 2024 ----