Exercices FORTH
Comment apprendre à programmer en langage Forth ? Il est plus facile d’assimiler en s’amusant par le biais d’exercices, de construire soi-même des bouts de programmes.
1. Le PGCD
Rappel de ce que c’est que le « PGCD » : Plus Grand Commun des Diviseurs entre 2 nombres.
Il existe plusieurs méthodes pour calculer le PGCD, celle qui est le plus répandue (et la plus rapide) est la méthode d’Euclide. Il s’agit d’effectuer des divisions successives.
Exemple de la méthode d’Euclide pas à pas :
Soit 2 nombres : 63 et 42 [ 63 est le plus grand et 42 le plus petit ]
Premiere division: 63
/ 42 = 1*42 + 21 [ 42 est
le plus petit, le reste est 21 ]
Seconde
division: 42 / 21 = 2*21 + 0 [ on
divise 42 par 21 ]
Le reste = 0 : le résultat est le dernier diviseur soit 21
Nous avons bien 63 divisible par 21 (résultat 3) et 42 divisible par 21 (résultat 2).
La méthode : Il faut diviser le plus grand nombre par le plus petit. Et on divise le plus petit des 2 nombres de la division précédente par le reste de la division. Il est intéressant de noter qu’il s’agit d’écrire un programme faisant appel à la récursivité.
Étudions pas à pas le bout de programme suivant (pour eforth du GA144) :
programme pgcd.e4
Le code Forth est édité avec un simple éditeur de son choix, j’ai une préférence pour la coloration syntaxique (ici l’éditeur est Win32ForthIDE et reconnait le langage Forth).
Pour bien comprendre le déroulement du programme, j’ai ajouté quelques informations utiles comme afficher les données sur la pile ( .s ).
?dup copie le sommet de la pile (TOS) s’il est diffèrent de 0.
Le mot TUCK permet de copier le sommet de la pile en dessous du second élément :
Pour effectuer une division entre 2 nombres et récupérer « le reste » il existe le mot MOD. Il faut veiller que le premier nombre soit supérieur au second.
La condition « if then »
est intéressante. En effet ici on effectuera ce qu’il y a entre la boucle si la
condition est vraie.
Sous eForth :
Effectuant une simple comparaison :
ok 1 2 = .
0
ok 0 0 = .
-1
On Remarque que une condition vraie est différent de « 0 » et qu’une condition fausse = 0
Définissons un mot TEST, celui-ci effectue ce qu’il y a entre le IF et le THEN si la condition est fausse.
On peut dire qu’il faut un nombre différent de 0. En remarque le sommet de la pile est détruit.
ok : TEST IF
." different de 0 " THEN ;
ok 8 TEST different de 0
ok 9 TEST different de 0
ok 0 TEST
ok
On charge notre
programme par le biais de l’éditeur terminal :
« ESC
P » PGCD
Testons le programme PGCD :
ok 63 42 PGCD .
?dup : 63 42 42
IF
swap over : 42 63 42
mod : 42 21
?dup : 42 21 21
IF
swap over : 21 42 21
mod : 21 0
?dup :
21 0
21
ok
Cool le resultat est bien 21. J’ai en plus la décomposition de tous les calculs. Au départ j’ai bien 63 et 42 sur la pile
Le IF va comparer le sommet de la pile avec 0 , 42 est différent de 0 donc on va exécuter ce qu’il y a entre le IF et THEN .
Le mot TUCK va permettre de copier le sommet de la pile en dessous du second.
On effectue la division est on récupère le reste :
Le mot « recurse » permet d’appeler de nouveau le mot PGCD avec les données sur la pile.
De nouveau ?dup :
Toujours différent de 0 , on exécute les instructions entre le IF et THEN:
On copie le sommet de la pile en dessous du second.
On divise 42 par 21 et on récupère le reste
On appel de nouveau le mot PGCD avec les données sur la pile.
Comme le sommet de la pile =0, on ne duplique pas le sommet.
Le IF THEN joue parfaitement son rôle, la comparaison avec 0 donne un résultat vrai, donc c’est la fin !
Le résultat est affiché : 21