EFORTH pour MK-161: Structures de données

Cet article est la fin d'une série d'articles eForth sur une calculatrice programmable. Commencez ici .

Les commandes du langage de saisie "Electronics MK-161" n'occupent que la moitié du fichier eForth0.mkl. La seconde moitié est occupée par des tableaux dont le développement n'a pas été moins difficile que l'écriture de la partie algorithmique du traducteur. Essayons de comprendre comment ces tables sont utilisées.


Le professeur Wirth enseigne que la «programmation dans le petit» consiste à développer deux composants tout aussi importants - les algorithmes et les structures de données.

Nous avons déjà rencontré une structure de données eForth. Il s'agit du corps de VCA (mots de haut niveau) situé dans la mémoire d'octets. Quatre gestionnaires interprètent les champs de paramètres de «leur propre» VCA de différentes manières:

.DB DOVAR ;      .DB … ;      .DB DOCON ;    .DW _ ;   .DB DOCONM ;     .DW _ ;   .DB DOLST ;     .DW 1, 2,… EXITT ;   

La structure de données relativement simple suivante est associée aux TYPE "messages standard". Tous les messages eForth sont numérotés et transférés dans la mémoire du programme bon marché. Si le mot TYPE imprime une seule lettre, son code peut être le numéro d'un tel message, de 0 à 7.

 ;   TYPE .BASE tblTYPE: .DBB str7,str6, str5, str4, str3, str2, str1, str0 

Dans le langage MK étendu, la pseudo-commande .BASE définit la "base" de la commande .DBB, qui place séquentiellement les décalages de ligne de str7, str6, etc., en octets. par rapport à l'étiquette de base tblTYPE. En ajoutant des nombres de 0 à 7 à l'adresse de la table, ce décalage peut être lu à partir de celle-ci. En ajoutant le décalage trouvé à tblTYPE, nous obtenons l'adresse de la ligne souhaitée.

Le premier octet de la chaîne contient sa longueur. eForth utilise largement ces lignes de comptage .

Nous sommes également tombés sur la table tblTokens, qui répertorie les adresses de code des 208 mots intégrés. Si le mot n'est pas primitif, le tableau contient 0. Aller à l'adresse 0 provoquera le redémarrage d'eForth, avec un grincement.

La table tblNames a également été mentionnée, se référant aux noms des mêmes 208 mots. Ces noms sous forme de lignes de comptage sont stockés dans la même mémoire de programme «caoutchouc». La table tblNames elle-même ne sera pas disponible pendant l'exécution d'eForth, mais les informations qu'elle contient ne seront pas perdues. Au moment de la compilation, eForth.f transférera l'adresse des noms vers une structure de données plus pratique stockée dans la mémoire décimale (voir 2).

J'ai également parlé de tblCHPUT, un tableau associatif de codes de contrôle lors de l'affichage d'une lettre sur l'écran d'une calculatrice. Sept autres tableaux, de tblKeyNum à tblKeyRusF, traduisent le code d'un bouton pressé dans différents modes de clavier en un code de lettre de 8 bits. L'adresse du sous-programme responsable du mode clavier actif est dans le registre décimal ptrKbdInt.

Au total, une seule structure de données n'est pas encore assemblée dans le fichier eForth0.mkl, ce sont des tables de reconnaissance de nom. Laissons-les en dessert (voir 5) après le plat principal - deux tableaux de titres stockés dans la mémoire décimale. Premièrement, nous nous armerons d'outils pour «bourrer» ces rubriques.

1. Travaillez avec les titres: HEAD! et HEAD @

 HEAD! ( xt nfa r -- )     r,  xt  nfa. HEAD@ ( r -- xt nfa lex )     r,  xt, nfa  . 

Un registre décimal MK-161 peut mémoriser 12 décimales. eForth utilise ce registre pour stocker trois petits nombres, chacun de 0 à 9999. Les trois «champs» pour stocker ces nombres sont I appelés A, B et C: AAAABBBBCCCC. Le signe décimal fait uniquement référence au champ A.

La primitive HEAD @ obtient le numéro de registre et en divise le nombre en champs, et HEAD! recueille des champs dans un nombre long et écrit le "monstre" résultant dans le registre spécifié. Mais il y a des nuances.

La «rubrique décimale» du mot contient dans le champ A l'adresse de son nom (nfa). Si cette adresse est négative, le nom est enregistré dans la mémoire du programme. Le champ B contient le mot jeton (xt). Le champ C est appelé un lexique. Il stocke le bit IMMEDIATE et un signe que le mot est destiné uniquement à la compilation.

HEAD @ divise l'en-tête en plusieurs parties. En haut de la pile se trouve le champ de lexique C, en dessous se trouve le champ de nom A. Le champ B, dans lequel le jeton est généralement stocké, est tout en bas.

HEAD! réinitialise le champ C.

2. Rubriques intégrées

Les en-têtes de chacun des 208 mots intégrés (0 à 207) vont dans l'ordre, en commençant par R44. Le champ A contient toujours un nombre négatif, car les noms de ces mots sont codés en dur dans la mémoire du programme.

Les champs B et C sont modifiables. Par conséquent, l'utilisateur peut redéfinir les mots intégrés et en faire IMMÉDIATEMENT le besoin (voir 4).

3. Rubriques utilisateur

Travailler avec seulement 208 noms prédéfinis économise de la mémoire d'octets, mais est exceptionnellement ennuyeux. Par conséquent, j'ai développé une autre structure de données où le fantasme dans le choix d'un nom est limité à seulement 32 lettres. Cette structure se compose de 32 listes , dont chacune est responsable des mots utilisateurs d'une certaine longueur. Chacune de ces 32 listes a un titre personnel. Les listes elles-mêmes sautent sur la mémoire décimale, mais leurs en-têtes sont toujours stockés dans R301 ... R332.

Le tri des mots par longueur de nom est un point fort important de 161eForth. Le tri réduit considérablement le nombre de comparaisons lorsque vous recherchez un mot par son nom, ce qui accélère la compilation. Qui a besoin de fonctions de hachage si chaque nom a une longueur connue?

Par souci de simplicité, l'en- tête de la liste a la même structure avec les champs A, B et C que l'en-tête du mot. Le but de ces champs est différent. Le champ A contient le numéro du premier registre de la liste. Le champ B contient le nombre de registres fournis dans la liste. Le champ C stocke le nombre de mots dont les en-têtes sont déjà sur la liste.

Au début du travail, les champs C sont égaux à zéro; les mots sont absents dans toutes les listes. Les champs B sont 2, chaque liste reçoit deux registres pour commencer. Les champs A indiquent des blocs de 2 registres commençant par R333.

Chaque liste contient des titres de mots. Nous les avons déjà démontés (voir. 1). Ici, peut-être, l'adresse du nom (nfa) sera positive et pointera vers la ligne de comptage, traditionnellement stockée devant le corps du VCA. En outre, le jeton dans le champ B est l'adresse du champ de code (cfa) qui va dans la mémoire binaire immédiatement après ce nom. Il y a une exception - si le mot a déjà été déterminé, le champ A pointera vers l'ancien nom. Pourquoi stocker à nouveau la chaîne? La mémoire binaire coûte cher.

Lorsque tous les registres de la liste sont pleins (B = C), le mot PUBLISH fournit 5 autres emplacements libres, poussant cette structure de données au bon endroit et ajustant les liens (A) dans les en-têtes de liste.

4. Publication d'un nouveau mot: TRAVAIL et PUBLICATION

 LAST ( -- a )      . WORK ( -- a )     . PUBLISH ( -- )     . $,n ( nfa -- )     ,    nfa. ?UNIQUE ( a -- a )  ,    . 

La structure de données développée pour le MK-161 pour le stockage des titres de mots s'est avérée pratique et facilement intégrable dans eForth. Lorsque CREATE, CONSTANT ou: crée un nouveau mot, ils accèdent au mot système $, n pour créer un titre pour le mot avec le nom donné. $, n fait référence à? UNIQUE pour vérification - créons-nous un nouveau mot ou redéfinissons-nous l'ancien?

Si un mot du même nom existe déjà ,? UNIQUE avertit l'utilisateur à ce sujet. Dans le même temps, l'adresse de l'en-tête redéfini est entrée dans la dernière variable système. Pour un nouveau mot, LAST est remis à zéro.

Dans tous les cas, $, n crée un nouvel en-tête dans la variable WORK - c'est un registre décimal qui peut stocker 12 bits de l'en-tête. Si le nom n'a pas été trouvé, il est inclus dans le dictionnaire avant le champ de code, comme cela se produit dans 86eForth et dans de nombreux autres Forts. Le MK-161 a réussi à se passer d'un «champ de communication» , ce qui économise également de la mémoire binaire.

La primitive PUBLISH complète la définition d'un mot. Lors de la compilation des mots deux-points, PUBLISH est appelé à partir de ;; en conséquence, le bit SMUDGE n'était pas requis. L'endroit où l'en-tête de WORK est copié est déterminé par la dernière variable. Si LAST est nul, un nouvel en-tête est créé dans la liste correspondante (voir 3). La liste est-elle complète? Ensuite, PUBLISH y ajoutera 5 registres supplémentaires, dont quatre pour l'avenir.

Après avoir exécuté PUBLISH, la dernière variable pointe toujours vers le titre du dernier mot. Cela aide IMMEDIATE à faire son travail en changeant le champ du lexique.

5. (FIND) et tableaux de reconnaissance des noms

 (FIND) ( a -- r T | a F )    r,        a. FIND ( a -- a F | xt 1 | xt -1)    .  1,  IMMEDIATE. 

Une primitive (FIND) gère la recherche d'un mot par son nom. Tout d'abord, il recherche un nom parmi les mots intégrés avec des noms précédemment connus, puis vérifie la liste des mots utilisateur avec la longueur de nom souhaitée (voir 3). Les tables de reconnaissance de noms accélèrent considérablement cette «première». Voici comment ils fonctionnent.

Au début (FIND), il trouve dans le tableau tblLen l'adresse de la table associative principale, dans laquelle des noms bien connus de la longueur requise sont "préparés". Dans ce tableau (FIND) recherche le premier caractère du nom. Dans la plupart des cas, cela vous permet immédiatement de trouver le numéro de registre de titre du mot recherché - par la première lettre et la longueur.

Il arrive que plusieurs mots de même longueur aient les mêmes premières lettres. Ensuite, au lieu du numéro de registre (FIND), il tombe sur l'adresse de la table associative suivante (le nombre lu est de 300 ou plus) et la recherche se poursuit sur la deuxième lettre. Et ainsi de suite, jusqu'à ce que le mot soit trouvé ou qu'il soit établi qu'il n'y a pas un tel mot.

Bien sûr, après une correspondance pour les premières lettres (FIND), le nom entier est vérifié. Mais les tables de reconnaissance ont rendu eForth rapide . Ce printemps, j'ai investi beaucoup de temps en eux, et maintenant ils économisent du temps de recherche. Les "clés" y sont même triées par ordre alphabétique. Désolé, le firmware MK-161 a craché dessus.

Dans un souci de compatibilité, j'ai implémenté le mot FIND de Fort ANS [4], qui fait confiance à la primitive «black work» (FIND). Le mot déjà considéré? UNIQUE recherche également son argumentation via (FIND).

6. Interprète externe

Le livre [1] contient une description exhaustive d'eForth, y compris un interprète «texte» externe. C'est lui qui exécute ou compile le texte source en langue Fort. Des différences par rapport aux interprètes textuels d'autres dialectes du fort ([2], [3]) sont apparues au cours des dernières décennies, mais il y en a peu.

Ci-dessous est un schéma de principe d'un interpréteur de texte tiré de [1]. Attention, cet "interprète" a un mode de compilation! Le mot $ COMPILE est responsable de la compilation du texte Forte en «code cousu», dont nous avons examiné l'exécution en détail dans le premier article. Lorsque $ INTERPRET est exécuté à la place, les mots saisis sont exécutés immédiatement - mode d'interprétation. EVAL "calcule" la chaîne entière entrée, en invoquant un de ces deux mots pour chaque mot entré.



Après le diagramme, l'auteur décrypte celui des blocs. Voici sa traduction. Les noms de bloc correspondent généralement aux noms de mot eForth. Le mot NOM? est absent de mon implémentation, il est remplacé avec succès par fast (FIND) (voir. 5).



Le livre fournit également le code source de chaque mot eForth dans la version Windows, avec de brèves explications. Quelle est la version différente pour MK-161, je vous l'ai déjà dit. Le code source de mon implémentation est dans l'archive: the-hacker.ru/2019/161eforth0.5b.zip

Enfin, je mentionnerai l'implémentation du mot (PARSE) dans le langage MK-161 - sous Windows c'est VCA. Le débogage a pris une semaine, mais il a accéléré la compilation de moitié . Le mot (PARSE) fait tout le «sale boulot» pour PARSE pour isoler les mots individuels du flux de texte d'entrée.

Mes ajouts à l'interpréteur externe sont deux mots, en plus du cycle QUIT habituel: le TLOAD déjà mentionné et tiré des anciennes versions de FILE. Le mot FILE traduit les E / S sur la console, mais lit les lignes d'interprétation à partir du port RS-232. Une fois le traitement de chaque ligne réussi, une lettre avec le code 11 est envoyée au port. Le fichier téléchargé depuis l'ordinateur doit se terminer par le mot QUIT.

Je n'ai pas encore débogué le mot FILE. Si quelqu'un en a besoin, partagez vos impressions.

La révision 161eForth des points faibles est terminée, mais le Fort est un outil incroyablement flexible que chaque propriétaire peut personnaliser. Même lorsque vous avez tout compris, quelqu'un quelque part sur la planète trouvera un autre truc qui peut vous surprendre.

Voici les derniers mots de l'auteur eForth de [1]:

Depuis 26 ans, j'ai réécrit eForth plusieurs fois. Dans chaque doublage, j'ai essayé de le rendre plus simple et plus clair. Maintenant, dans 86eForth v5.2, je pense avoir atteint l'exactitude et je suis donc très heureux.

Comme l'a dit Einstein:
Tout doit être fait aussi simple que possible, mais pas plus simple.

Rendre 86eForth v5.2 encore plus facile, peut-être le casser ou ne pas être utile comme outil de programmation.

Littérature

1. Dr. Chen-Hanson Ting. eForth et Zen - 3e édition, 2017. Disponible sur Amazon Kindle.
2. Baranov S.N., Nozdrunov N.R. Langage fort et sa mise en œuvre. - L.: Génie mécanique. Leningrad Département, 1988.
3. Semenov Yu.A. Programmation en langage FORT. - M.: Radio et communications, 1991.
4. Norme ANS Forth. X3.215-1994. La traduction
5. Documentation SP-Forth .
6. Offete Enterprises (Dr Chen-Hanson Ting) , auteur de 86eForth v5.2, est en anglais.
7. L'histoire de Mikhail Pukhov "True Truth" avec le programme "Moonwalker-1", où j'ai obtenu KDPV et l'amour pour les calculatrices soviétiques.