You are here: Tutoriels » L'Ada » Exercice : SimpleForth

Pour mettre en œuvre un peu d'Ada, rien ne vaut un bon exercice. Pour entrer dans l'esprit du club tout de suite, on se propose de réaliser un petit interpréteur Forth (cf. le tutorial qui va bien).

Squelette de base

Pour commencer, il faut récupérer le squelette de base du programme. Pour cela, on va cloner un depot mercurial qui contient mes réponses aux questions : 
hg clone http://bitbucket.org/telrob/simpleforth/">http://bitbucket.org/telrob/simpleforth/ -r 0
Pour obtenir mon exemple de programme répondant à la question "n", il suffit d'executer la même commande en changeant le 0 par "n" (cf tuto Mercurial pour plus d'info)
Pour que notre interpréteur soit plus user friendly, il va utiliser la librairie bien connu readline. Il n'existe malheureusement pas de package standard pour utiliser cette librairie. Il faut donc importer "à la main" les fonctions qui nous intéressent. Heureusement, je l'ai déjà fait wink (Merci Sam) il suffit de récupérer mon package ici:
La configuration par défaut demande que "areadline" soit dans le répertoire parent par rapport à notre interpréteur Forth.
Ensuite, un rapide parcourt du code s'impose. On trouve 3 fichiers : forth.ads, forth.adb et test_forth.adb.
·         forth.ads : L'ads de notre package. On y déclare 2 fonctions :
o    Register_Ada_Word: Pour jouer avec notre robot, on aura besoin de fonction qui n'existe pas en Forth de base. Pour pouvoir les utiliser, on va écrire une petite procédure Ada et on dira ensuite à notre interpréteur (via Register_Ada_Word) que lorsque l'utilisateur tape un "mot" particulier, il faut exécuter cette fonction.
o    Interpret_Line: Cette fonction est chargé d'interpréter une ligne de Forth
·         forth.adb: un fichier un peu vide pour l'instant, à compléter...
·         test_forth.adb: Pour pouvoir tester notre interpréteur, il faut un programme de test. Ce programme se réduit à une boucle qui lit une ligne au clavier, l'interprète puis recommence.

1ère partie

Notre interpréteur va travailler avec des "mots". Une ligne sera une suite de mots qui seront interprétés les uns après les autres. Pour l'instant, on va définir 2 types de mots : les nombres et les mots Ada. Les nombres seront des flottants pour plus de généralité et les mots ada sont ceux qui vont appeler une fonction Ada.
Question 1: définir le type Word_Type
Maintenant, on va s'occuper de la liste des mots connus.
Question 2: écrire la procédure Register_Ada_Word
Indication: Pour simplifier, on va se donner un nombre de mot maximal et on définira un tableau de mot de cette taille.
Note: Par convention on choisit de remplacer l'ancienne valeur d'un mot s'il est défini plusieurs fois
Ensuite, on va commencer à traiter notre ligne
Question 3: Ecrire une fonction qui découpe la ligne en mot.
Indication: On pourra utiliser une variable qui enregistre où on en est dans la ligne.
Question 4: Compléter la fonction Interpret_Line pour qu'elle exécute les mots ou empile les nombres.
Note: De même que pour la liste des mots, on prendre une pile de taille finie.
Question 5: Ecrire quelques mots de base, comme par exemple +, -, .s
Et voilà ! On dispose maintenant d'une belle calculatrice !

2ème partie

Une calculatrice, c'est bien, mais bon, en polonais inversé c'est un peu limité...
Pour aller plus loin, il va falloir complexifier un peu les choses. Une bête interprétation des mots au fur et à mesure pose de gros problème pour faire des choses comme la définition de nouveaux mots ou des boucles imbriquées complexes. On va donc introduire un nouveau mode : le mode compilation. 
Au lieu d'interpréter les mots, on va "compiler" l'ensemble de la ligne pour l'exécuter. Pour les wariors, on peut compiler la ligne en assembleur x86 directement (ou en assembleur PIC, cf. rfoth1). Sinon, on peut se définir notre propre langage et écrire une machine virtuelle pour exécuter ce langage. Ca a l'air compliqué mais c'est très simple en fait. Pour notre langage virtuelle, on va prendre nos mot de type Word_Type (ça tombe bien, on les a déjà sous la main) et pour exécuter notre byte-code, on va reprendre notre fonction qui exécute les mots.
Finalement, au niveau des changements, nous faut un endroit où stocker les mots compilé, une mémoire contenant notre "programme" (un simple tableau fini suffira). Il faut aussi créer un nouveau type de mot, les mots de type "Number" dont l'exécution consiste à empiler la valeur correspondante. Et voilà.
Question 6 : Modifier notre interpréteur pour qu'il compile la ligne avec de l'exécuter.
Ajoutons maintenant les structures de type "IF THEN". Avec notre interpréteur de la 1ere partie, il n'est pas simple d'ajouter ces structures. Avec notre compiler, ça va se passer beaucoup mieux.
L'idée est la suivante : on va transformer
toto if tata then titi
en
toto "jump_if_false titi" tata titi
On remplace le "if" par un "goto" après le "then" si la condition est fausse. Le problème consiste à connaître l'adresse de ce qui suit le "then". Au moment de la compilation du "if", cette adresse est inconnue (ce qui pose de gros problème pour l'interpréteur de la partie 1). Ce qu'on va faire, c'est laisser l'adresse vide et la remplir au moment de la compilation du "then".
La compilation du "if" est plus compliqué que celle des autres mots vu jusqu'ici : il ne suffit pas d'écrire le "if" dans notre mémoire, il faut enregistrer l'adresse mémoire du "if" pour pouvoir le mettre à jour lors de la compilation du "then". On pourrait faire un test pour chaque mot à compiler et faire quelque chose de différent lorsque c'est un "if", un "then", etc. mais il est plus simple de définir un nouvel attribut des mots : on dit qu'un mot est "immédiat" s'il demande une action spécifique, sinon, il se compile comme précédemment. Pour compiler un mot, on regarde s'il est immédiat. S'il l'est, on l'exécute immédiatement :), sinon on l'ajoute dans notre mémoire des mots compilés.
Question 7 : Ajouter l'attribut "immediat" aux mots
Question 8 : Ajout les mots "if" et "then"
Indication : On ajoutera un mot "Jump_If_False" qui sautera ou ne sautera pas à l'adresse sur le sommet de la pile en fonction du 2ème élément de la pile.
Indication 2: Lors de la compilation, la pile ne sert à rien, on peut donc s'en servir pour enregistrer les endroits où mettre les adresses à compléter par le "then". L'avantage, c'est que ça permet de gérer les "if" imbriqué sans réfléchir.
Question 9: Juste pour la forme, rajouter un "else"
Indication : On va compiler
toto if tata else titi then tutu
en
toto Adresse(titi) Jump_If_False tata Adresse(tutu) Jump titi tutu
Il "suffit" maintenant d'écrire le mot immédiat "else"
Pour finir, attaquons nous à la définition de mot en Forth. Il va nous falloir définir 2 nouveaux mots ":" et ";". L'idée de base est assez simple : on défini un nouveau type de mots, les mots Forth, par analogie aux mots ada. A la place d'un pointeur vers une procédure Ada, ces mots contiendront une position dans notre mémoire, l'endroit où le mot en question à été compilé (on peut aussi compiler un mot en l'adresse de destination, suivi d'un nouveau mot "Call")
Pour la compilation du mot ":", prenons un exemple :
toto : titi tata ; tutu titi
Lors de l'exécution, il ne faut pas exécuter "tata" après toto. Ce qu'on va faire, c'est de rajouter un "Jump" après le toto pour sauter directement à "tutu" et passer la définition de "titi".
Pour la compilation du mot ":", il faudra compléter l'adresse du "Jump" introduit par le ":" et ajouter un mot spécial "Exit" qui, lors de l'exécution indique qu'il faut sortir du mot en cours.
Finalement, on obtiendra
toto Adresse(tutu) Jump tata Exit tutu titi
Question 10: Ajouter la création de nouveau mot.
Note: Au lieu de mettre un "jump" après la définition du mot, on peut employer une autre stratégie : on interprète les mots, comme dans la 1ere partie, jusqu'à ce que trouve un ":". La on change de monde, on passe en mode compilation jusqu'au ";". Ensuite, on reprend notre interprétation. Cette technique a l'avantage d'économiser de la mémoire : seuls les mots sont compilés et prennent de la place dans notre mémoire.
Question 11: Rajouter tous les mots qui vous font plaisir !