Triceraprog
La programmation depuis le Crétacé

Forth et les nombres

À sa création, Forth ne manipule que les nombres entiers. C'est suffisant pour son usage. Et un nombre se stocke dans une cellule de données, généralement (et dans le choix d'implémentation de ce Forth sur 6502) une cellule de 16 bits pour un Forth sur processeur 8 bits.

Par la suite, les nombres « double » seront ajoutés, des nombres stockés sur deux cellules donc. Mais là où la plupart des langages de haut niveau utilisent les mêmes symboles arithmétiques quel que soit le type de donnée numérique, voire même font de la coercition (adapte les types de données pour pouvoir les manipuler ensemble), Forth n'a rien de tout cela : une addition de deux nombres « double » n'utilise pas le même symbole que l'addition de deux nombres simples.

Par exemple

4 6 + .      \ fait la somme de deux nombres simples (et l'affiche)
4. 6. D+ D.  \ fait la somme de deux nombres doubles (et l'affiche)

Le point dans un nombre indique un nombre double. Ce point peut d'ailleurs être n'importe où, ce qui est une bizarrerie pour des habitués de langages plus modernes. Ainsi 40.00, 4.000 ou 4000. représentent tous le nombre double 4000... Troublant.

De même pour les implémentations de nombres flottants, qui sont d'ailleurs souvent dans les implémentations historiques soit inexistants, soit sous forme d'ajout optionnel.

Pour cette implémentation sur 6502 pour Famicom, je vais me contenter, au moins dans un premier temps, de traiter les nombres simples. Il sera toujours possible d'ajouter les nombres doubles si besoin, mais... le besoin ne me semble pas évident pour le moment.

Une question de bases

Dans le monde des ordinateurs, depuis un bon moment, c'est la base 2 qui fait référence. Un nombre stocké dans une machine est fait de 0 et de 1, si vous êtes en train de lire cet article, je ne dois certainement rien vous apprendre.

Je ne vous apprends pas grand chose de plus en vous disant que de manière habituelle, les humains contemporains dans leur grande majorité comptent en base 10, avec des chiffres allant de 0 à 9.

Forth est capable d'analyser un nombre sous forme de chaîne de caractères en n'importe quelle base allant de 0 à 16. Et même d'écrire ces nombres à l'écran. En interne, ces nombres sont bien entendu en binaire et, on l'a vu plus haut, sont stockés naturellement dans une cellule de données, 16 bits pour cette implémentation.

Il est donc nécessaire d'avoir un mot Forth qui prend une chaîne de caractères représentant un nombre et qui la transforme en ce même nombre en base 2. Ainsi que l'inverse, prendre un nombre interne en base 2 et le transformer en suite de caractères représentant ce même nombre dans une base donnée.

Le premier mot est NUMBER, le second est . (point). Techniquement, point fait trop de choses : il affiche un nombre sur l'écran, il ne fait pas que la conversion, mais on va le garder en tête pour le moment. Et uniquement en tête car l'objectif courant est toujours le même, interpréter la ligne HEX 7FF FF C! afin de valider l'interpréteur grâce à un point d'arrêt dans le harnais de test. Et . n'est pas nécessaire pour cela.

HEX est l'équivalent de 16 BASE !, en supposant que la base actuelle est décimale. De manière similaire DECIMAL est l'équivalent de A BASE !, en supposant que la base actuelle est hexadécimale. La raison première de l'existence de ces deux mots est d'ailleurs, à mon avis, de ne pas se soucier de la base actuelle pour alterner entre les deux bases les plus usuelles.

Il nous faudra donc une variable BASE, ce qui est trivial.

D'une chaîne vers du binaire

Reste donc le vrai gros morceau. En Fig-Forth, NUMBER a pour signature ( addr - d ), c'est-à-dire qu'à partir d'un pointeur vers une chaîne précédée de sa longueur, sa représentation en nombre « double » est poussée sur la pile. Cependant, comme cette implémentation n'a pas de nombre double, je choisis pour signature ( addr - n ).

C'est un choix assez fort : une implémentation des nombres doubles dans le futur nécessitera une adaptation de tous les appels à NUMBER. Mais vraiment, je ne vois pas ce futur dans ce Forth pour Famicom que j'imagine (famous last words ?).

NUMBER est généralement un mot en Forth qui utilise (NUMBER) mais aussi plein de mots que je n'ai pas encore implémentés, comme DIGIT. C'est un mot qui ne sert qu'à la conversion des nombres dans un code source, donc sans besoin critique de performance. Voilà un source adapté aux seuls nombres simples :

: NUMBER      \ ( addr - n )
  0           \ accumulateur pour le résultat
  SWAP        \ pointeur de chaîne (addr) au-dessus de la pile
  DUP 1+ C@   \ prend le premier caractère de la chaîne
  2D = DUP >R \ regarde s'il est égal au signe - (moins) et duplique le résultat sur la pile de retour
  +           \ s'il y avait un signe moins, le pointeur de chaîne est avancé d'un (1)

  (NUMBER)    \ appel de (NUMBER) avec la chaîne ajustée
  DROP        \ ignore l'adresse de retour de (NUMBER) (2)

  R>          \ récupère l'existence d'un signe moins depuis la pile de retour
  IF
    MINUS     \ oppose le signe du nombre s'il y avait un signe moins en début de chaîne
  ENDIF
  ;

(1) Ce recalage peut sembler étrange, car il place le pointeur de la chaîne à analyser non pas sur le premier caractère mais une adresse avant. Puis (NUMBER), juste après, commence avant toute chose à avancer le pointeur d'une position. Pourquoi ne pas l'y positionner tout de suite ?

Cela permet à (NUMBER) de fonctionner avec des chaînes préfixées par la taille. (NUMBER), contrairement à NUMBER, ne fait pas de traitement de signe négatif, ni, dans le cas où cela est implémenté, de traitement de nombre double... ou presque.

(2) Dans l'implémentation avec les nombres doubles, l'adresse permet de vérifier si un . (point) est présent, et si c'est le cas, boucler pour traiter la deuxième partie du nombre. Ici, l'adresse ne nous intéresse pas.

Toute cette partie a été simplifiée ici, mais par curiosité, allez voir une implémentation complète, c'est étonnant.

: (NUMBER)  \ ( n1 addr1 - n2 addr2 )
  BEGIN
    1+      \ avance de 1 le pointeur de chaîne
    DUP >R  \ copie cette adresse sur la pile de retour (1)

    C@      \ met le caractère pointé sur la pile
    BASE @  \ récupère la base courante
    DIGIT   \ transforme ce chiffre alphanumérique en représentation numérique
    \ ici, la pile contient 1 (VRAI) ou 0 (FAUX) suivi 
    \ du le chiffre en représentation machine dans le cas VRAI
    \ DIGIT a consommé le caractère et la BASE

  WHILE      \ si DIGIT a renvoyé VRAI (sinon, va au REPEAT)
    SWAP     \ récupère l'accumulateur
    BASE @   \ ainsi que la base
    U* DROP  \ pour les multiplier (2)
    +        \ ajoute le résultat à l'accumulateur
    R>       \ récupération de l'adresse de chaîne avant nouvelle boucle
  REPEAT
  R>         \ remise sur la pile de l'adresse de chaîne
             \ après son analyse (pointe donc après le nombre)
  ;

(1) la pile de retour sert parfois, dans certains mots, comme pile temporaire supplémentaire à la pile des paramètres. Cela arrive lorsqu'il y a trop de paramètres à gérer sur la pile des paramètres. Il est bien entendu indispensable que le mot remette tout en place avant de se terminer, puisque les informations pour revenir au mot appelant sont présentes dans la pile de retour.

(2) U* renvoie un nombre double à partir de la multiplication de deux nombres simples ( n1 n2 - d ). Il faut donc oublier la partie haute avec un DROP. U* fait spécifiquement une multiplication non signée, contrairement à *. Je garde la signature et la sortie avec un nombre double même si l'implémentation ne le supporte pas plus, car la routine de multiplication fait de toute façon le calcul, et pour éviter de surprendre avec une signature non usuelle.

Les mots manquants

Pour implémenter NUMBER et (NUMBER), je vais avoir besoin des mots suivants :

Des mots de manipulation simples :

• SWAP ( n1 n2 - n2 n1 ) : inverse les positions des deux éléments les plus en haut de la pile.
• DUP ( n - n n ) : duplique le mot au sommet de la pile.
• C@ ( addr - n ) : met sur le sommet de la pile l'octet présent à l'adresse donnée (pour rappel, @ (fetch) met sur le sommet de la pile la cellule présente à l'adresse donnée, donc deux octets).

Un peu d'arithmétique et de logique :

• 1+ ( - ) : ajoute 1 à la valeur présente au sommet de la pile.
• U* ( n1 n2 - d ) : voir plus haut, effectue une multiplication non signée, avec en résultat un nombre double.
• MINUS ( n1 - n2 ) : place sur la pile l'opposé du nombre qui y était présent.
• + ( n1 n2 - n3 ) : effectue l'addition de deux nombres.
• = ( n1 n2 - b ) : compare deux nombres et place 1 (vrai) sur la pile s'ils sont égaux, 0 sinon.

De la manipulation de pile de retour :

• >R ( n - ) : envoie le nombre au sommet de la pile vers la pile des retours.
• R> ( - n ): récupère depuis la pile des retours la valeur au sommet et la pousse sur la pile des paramètres.

Pour le besoin des tests, j'ajoute R, qui copie le haut de la pile des retours sur la pile des paramètres. Cela permet de vérifier avec >R R R> que la valeur sur la pile des paramètres a été dupliquée. C'est un DUP en plus complexe. Mais comme >R et R> touchent à la pile des retours, et donc au noyau de l'interpréteur, j'ai trouvé ça moins risqué pour les tests.

Une variable :

• BASE : variable qui contient la base numérique actuelle.

Et enfin DIGIT ( c n1 - n2 b ) : qui convertit le caractère c selon la base n1 en nombre n2 si cela est possible. Dans ce cas, b est égal à 1, dans le cas contraire, b est égal à 0 et il n'y a rien d'autre de mis sur la pile. Et puisque ça ne coûte pas plus cher, la base supportée ira jusqu'à la base 36 (avec toutes les lettres de l'alphabet).

Tous ces mots seront implémentés en assembleur, puis NUMBER et (NUMBER) seront implémentés en mots Forth.

Pour passer le temps

Il n'y a pas beaucoup de choses à montrer dans ces deux derniers articles. C'est beaucoup d'implémentation de fond. Alors en attendant, voici ce à quoi ressemble la sortie du framework de tests après implémentation des tests mais avant l'implémentation des mots du bloc arithmétique et logique :

Failed tests:
  - 1+ increments TOS: Cannot resolve CFA for word: 1+
  - = returns 0 on inequality: Cannot resolve CFA for word: =
  - + adds two numbers: Cannot resolve CFA for word: +
  - MINUS opposes the TOS: Cannot resolve CFA for word: MINUS
  - U* unsigned-multiplies: Cannot resolve CFA for word: U*
  - = returns 1 on equality: Cannot resolve CFA for word: =

Quelle aventure...

Tout est implémenté et prêt pour NUMBER, cela sera pour la prochaine fois. Qui sait ? Si tout s'aligne parfaitement, peut-être que INTERPRET suivra dans la foulée !