Voici une question théorique - une réponse qui ne permet pas une réponse facile dans tous les cas, même pas triviale.
Dans le jeu de la vie de Conway, il existe des constructions telles que le métapixel qui permettent au jeu de la vie de simuler tout autre système de règles Game-of-Life. De plus, il est connu que le jeu de la vie est complet.
Votre tâche est de construire un automate cellulaire en utilisant les règles du jeu de la vie de Conway qui permettra de jouer à un jeu de Tetris.
Votre programme recevra une entrée en modifiant manuellement l’état de l’automate lors d’une génération spécifique pour représenter une interruption (par exemple, déplacer une pièce, la laisser tomber, la faire pivoter ou générer de manière aléatoire une nouvelle pièce à placer sur la grille), en comptant un nombre spécifique de générations comme temps d’attente et affichage du résultat quelque part sur l’automate. Le résultat affiché doit visiblement ressembler à une grille de Tetris réelle.
Votre programme sera noté dans l'ordre suivant (les critères les plus bas jouant le rôle de bris d'égalité pour les critères les plus élevés):
Taille de la boîte englobante - la boîte rectangulaire avec la plus petite surface qui contient complètement la solution donnée l'emporte.
Changements mineurs en entrée - le moins de cellules (dans le cas le plus défavorable de votre automate) qui doivent être ajustées manuellement pour une interruption gagne.
L'exécution la plus rapide - le moins de générations à avancer d'un cran dans la simulation gagne.
Nombre initial de cellules vivantes - le plus petit nombre gagne.
Premier post - post précédent gagne.
Réponses:
Cela a commencé comme une quête mais s'est terminée par une odyssée.
Quest for Tetris Processor, 2 940 928 x 10 295 296
Le fichier de signatures, dans toute sa splendeur, peut être trouvé ici , visualisable dans le navigateur ici .
Ce projet est l'aboutissement des efforts de nombreux utilisateurs au cours des 1 et 1/2 dernières années. Bien que la composition de l'équipe ait varié au fil du temps, les participants au moment de l'écriture sont les suivants:
Nous souhaitons également remercier 7H3_H4CK3R, Conor O'Brien et les nombreux autres utilisateurs qui ont déployé des efforts considérables pour résoudre ce problème.
En raison de la portée sans précédent de cette collaboration, cette réponse est divisée en plusieurs réponses écrites par les membres de cette équipe. Chaque membre écrira sur des sous-thèmes spécifiques correspondant approximativement aux domaines du projet dans lesquels il a le plus participé.
S'il vous plaît, distribuez tous les votes positifs ou primes à tous les membres de l'équipe.
Table des matières
Pensez également à consulter notre organisation GitHub où nous avons inséré tout le code que nous avons écrit dans le cadre de notre solution. Les questions peuvent être adressées à notre salle de discussion sur le développement .
Partie 1: aperçu
L'idée sous-jacente de ce projet est l' abstraction . Plutôt que de développer directement un jeu de Tetris dans Life, nous avons lentement augmenté l'abstraction en une série d'étapes. À chaque couche, nous nous éloignons des difficultés de la vie et nous rapprochons de la construction d'un ordinateur aussi facile à programmer que n'importe quel autre.
Premièrement, nous avons utilisé les métapixels OTCA comme base de notre ordinateur. Ces métapixels sont capables d'émuler n'importe quelle règle "réaliste". Wireworld et l' ordinateur Wireworld ont été d'importantes sources d'inspiration pour ce projet. Nous avons donc cherché à créer une construction similaire avec des métapixels. Bien qu'il ne soit pas possible d'émuler Wireworld avec des métapixels OTCA, il est possible d'attribuer des règles différentes à différents métapixels et de créer des arrangements de métapixels qui fonctionnent de manière similaire aux fils.
L'étape suivante consistait à construire une variété de portes logiques fondamentales qui serviraient de base à l'ordinateur. Déjà à ce stade, nous avons affaire à des concepts similaires à la conception de processeurs dans le monde réel. Voici un exemple de porte OU, chaque cellule de cette image est en fait un métapixel OTCA complet. Vous pouvez voir des "électrons" (chacun représentant un seul bit de données) qui entrent et sortent de la porte. Vous pouvez également voir tous les types de métapixels que nous avons utilisés dans notre ordinateur: B / S comme fond noir, B1 / S en bleu, B2 / S en vert et B12 / S1 en rouge.
De là, nous avons développé une architecture pour notre processeur. Nous avons consacré beaucoup d’efforts à la conception d’une architecture non ésotérique et aussi simple à mettre en œuvre que possible. Alors que l'ordinateur de Wireworld utilisait une architecture rudimentaire déclenchée par le transport, ce projet utilise une architecture RISC beaucoup plus flexible, dotée de plusieurs opcodes et modes d'adressage. Nous avons créé un langage d'assemblage, appelé QFTASM (Quest for Tetris Assembly), qui a guidé la construction de notre processeur.
Notre ordinateur est également asynchrone, ce qui signifie qu’il n’ya pas d’horloge globale contrôlant l’ordinateur. Au lieu de cela, les données sont accompagnées d'un signal d'horloge pendant qu'elles circulent autour de l'ordinateur, ce qui signifie que nous devons uniquement nous concentrer sur les synchronisations locales mais pas globales de l'ordinateur.
Voici une illustration de notre architecture de processeur:
À partir de là, il suffit d'implémenter Tetris sur l'ordinateur. Pour ce faire, nous avons travaillé sur plusieurs méthodes de compilation de langage de niveau supérieur pour QFTASM. Nous avons un langage de base appelé Cogol, un deuxième langage plus avancé en cours de développement, et nous avons enfin un backend GCC en construction. Le programme Tetris actuel a été écrit / compilé à partir de Cogol.
Une fois que le code final Tetris QFTASM a été généré, les étapes finales consistaient à assembler ce code dans la ROM correspondante, puis à partir de métapixels vers le jeu de vie sous-jacent, complétant ainsi notre construction.
Courir Tetris
Pour ceux qui souhaitent jouer à Tetris sans jouer avec l'ordinateur, vous pouvez exécuter le code source de Tetris sur l' interpréteur QFTASM . Définissez les adresses d’affichage RAM sur 3-32 pour afficher le jeu entier. Voici un lien permanent pour plus de commodité: Tetris dans QFTASM .
Caractéristiques de jeu:
Afficher
Notre ordinateur représente le tableau Tetris sous forme de grille dans sa mémoire. Les adresses 10 à 31 affichent le tableau, les adresses 5 à 8 affichent la pièce d’aperçu et l’adresse 3 contient la partition.
Contribution
La saisie au jeu s'effectue en modifiant manuellement le contenu de l'adresse de la RAM 1. En utilisant l'interpréteur QFTASM, cela signifie d'effectuer des écritures directes sur l'adresse 1. Recherchez "Écriture directe dans la RAM" sur la page de l'interprète. Chaque mouvement nécessite uniquement l'édition d'un seul bit de RAM et ce registre d'entrée est automatiquement effacé après la lecture de l'événement d'entrée.
Système de notation
Vous obtenez un bonus pour effacer plusieurs lignes en un seul tour.
la source
Partie 2: OTCA Metapixel et VarLife
OTCA Metapixel
( Source )
Le OTCA metapixel est une construction dans le jeu de la vie de Conway qui peut être utilisé pour simuler les automates cellulaires tout comme la vie. Comme dit le LifeWiki (lien ci-dessus),
Ce que l’automate cellulaire ressemble à une vie signifie essentiellement ici que des cellules naissent et que des cellules survivent en fonction du nombre de cellules sur huit qui sont en vie. La syntaxe de ces règles est la suivante: un B suivi du nombre de voisins vivants qui vont provoquer une naissance, puis d'une barre oblique, puis d'un S suivi du nombre de voisins vivants qui maintiendront la cellule en vie. Un peu verbeux, alors je pense qu'un exemple aidera. Le jeu canonique de la vie peut être représenté par la règle B3 / S23, qui stipule que toute cellule morte avec trois voisins vivants deviendra vivante et toute cellule vivante avec deux ou trois voisins vivants restera en vie. Sinon, la cellule meurt.
En dépit d'être une cellule de 2048 x 2048, le métapixel OTCA a en fait un cadre de sélection de 2058 x 2058 cellules, la raison en étant qu'il chevauche cinq cellules dans toutes les directions avec ses voisines diagonales . Les cellules qui se chevauchent servent à intercepter les planeurs - qui sont émis pour signaler aux voisins de métacellules sur lesquels il se trouve - afin qu'ils ne se mêlent pas aux autres métapixels ni ne s'envolent indéfiniment. Les règles de naissance et de survie sont codées dans une section spéciale de cellules du côté gauche du métapixel, par la présence ou l'absence de consommateurs dans des positions spécifiques le long de deux colonnes (une pour la naissance, l'autre pour la survie). En ce qui concerne la détection de l'état des cellules voisines, voici comment cela se passe:
Un diagramme plus détaillé de chaque aspect du métapixel d'OTCA est disponible sur son site Web d'origine: Comment ça marche ? .
VarLife
J'ai construit un simulateur en ligne de règles réalistes dans lequel n'importe quelle cellule peut se comporter conformément à une règle réaliste, et je l'ai appelé "Variations de la vie". Ce nom a été abrégé en "VarLife" pour être plus concis. Voici une capture d'écran de celle-ci (lien vers celle-ci ici: http://play.starmaninnovations.com/varlife/BeeHkfCpNR ):
Caractéristiques notables:
La fonctionnalité de rendu au format gif est ma préférée, car elle a nécessité une tonne de travail à mettre en œuvre. Elle était donc vraiment satisfaisante lorsque je l'ai finalement craqué à 7 heures du matin, et parce qu'il est très facile de partager les constructions VarLife avec d'autres .
Circuit de base VarLife
Au total, l’ordinateur VarLife n’a besoin que de quatre types de cellules! Huit états dans tous comptant les états morts / vivants. Elles sont:
Utilisez cette courte URL pour ouvrir VarLife avec ces règles déjà codées: http://play.starmannovations.com/varlife/BeeHkfCpNR .
Fils
Il existe plusieurs types de câbles avec des caractéristiques variables.
C'est le fil le plus simple et le plus simple de VarLife, une bande de bleu entourée de bandes de vert.
URL courte: http://play.starmaninnovations.com/varlife/WcsGmjLiBF
Ce fil est unidirectionnel. C'est-à-dire que cela tuerait tout signal essayant de voyager dans la direction opposée. C'est aussi une cellule plus étroite que le fil de base.
URL courte: http://play.starmaninnovations.com/varlife/ARWgUgPTEJ
Les fils diagonaux existent aussi, mais ils ne sont pas très utilisés.
URL courte: http://play.starmaninnovations.com/varlife/kJotsdSXIj
portes
Il y a en fait beaucoup de façons de construire chaque porte individuelle, donc je ne montrerai qu'un exemple de chaque type. Cette première image montre respectivement les portes AND, XOR et OR. L'idée de base ici est qu'une cellule verte agit comme un AND, une cellule bleue comme un XOR et une cellule rouge comme un OR, et que toutes les autres cellules autour d'elles sont simplement là pour contrôler correctement le flux.
URL courte: http://play.starmaninnovations.com/varlife/EGTlKktmeI
La porte AND-NOT, en abrégé "ANT gate", s'est avérée être un élément essentiel. C'est une porte qui transmet un signal de A si et seulement s'il n'y a pas de signal de B. D'où "A AND NOT B".
URL courte: http://play.starmaninnovations.com/varlife/RsZBiNqIUy
Bien que n'étant pas exactement une porte , une tuile de croisement de fil est toujours très importante et utile à avoir.
URL courte: http://play.starmaninnovations.com/varlife/OXMsPyaNTC
Incidemment, il n'y a pas de porte NON ici. En effet, sans signal entrant, une sortie constante doit être produite, ce qui ne fonctionne pas bien avec la variété de minutages requise par le matériel informatique actuel. Nous nous entendions très bien sans cela de toute façon.
En outre, de nombreux composants ont été conçus à dessein pour s’inscrire dans une boîte englobante de 11 sur 11 (une tuile ) dans laquelle il faut 11 signaux de sortie pour entrer dans la tuile et la quitter. Cela rend les composants plus modulaires et plus faciles à assembler selon les besoins sans avoir à s'inquiéter du réglage des fils pour l'espacement ou la synchronisation.
Pour voir plus de portes découvertes / construites au cours de l'exploration de composants de circuits, consultez cet article de blog de PhiNotPi: Building Blocks: Logic Gates .
Composants de retard
Lors du processus de conception du matériel de l'ordinateur, KZhang a conçu plusieurs composants de délai, illustrés ci-dessous.
Délai de 4 ticks: URL courte: http://play.starmannovations.com/varlife/gebOMIXxdh
Délai de 5 ticks: URL courte: http://play.starmannovations.com/varlife/JItNjJvnUB
Délai de 8 ticks (trois points d’entrée différents): URL courte: http://play.starmaninnovations.com/varlife/nSTRaVEDvA
Délai de 11 ticks: URL courte: http://play.starmannovations.com/varlife/kfoADussXA
Délai de 12 ticks: URL courte: http://play.starmannovations.com/varlife/bkamAfUfud
Délai de 14 ticks: URL courte: http://play.starmannovations.com/varlife/TkwzYIBWln
Délai de 15 ticks (vérifié en comparant avec celui-ci ): URL courte: http://play.starmaninnovations.com/varlife/jmgpehYlpT
Eh bien, voilà pour les composants de circuit de base dans VarLife! Voir le poste matériel de KZhang pour connaître les principaux circuits de l'ordinateur!
la source
Partie 3: matériel
Grâce à notre connaissance des portes logiques et de la structure générale du processeur, nous pouvons commencer à concevoir tous les composants de l’ordinateur.
Démultiplexeur
Un démultiplexeur, ou démultiplexeur, est un composant essentiel de la ROM, de la RAM et de l’ALU. Il achemine un signal d'entrée vers l'un des nombreux signaux de sortie en fonction de données de sélecteur données. Il est composé de 3 parties principales: un convertisseur série-parallèle, un vérificateur de signal et un séparateur de signal d'horloge.
Nous commençons par convertir les données du sélecteur de série en "parallèle". Cela se fait en séparant et en retardant stratégiquement les données de sorte que le bit de données le plus à gauche intersecte le signal d'horloge au carré 11x11 le plus à gauche, le bit de données suivant intersecte le signal d'horloge au carré 11x11 suivant, etc. Bien que chaque bit de données soit émis dans chaque carré 11x11, chaque bit de données intersectera le signal d'horloge une seule fois.
Ensuite, nous vérifierons si les données parallèles correspondent à une adresse prédéfinie. Nous faisons cela en utilisant les portes AND et ANT sur l'horloge et les données parallèles. Cependant, nous devons nous assurer que les données parallèles sont également émises afin de pouvoir les comparer à nouveau. Ce sont les portes que je suis venu avec:
Enfin, nous venons de scinder le signal d'horloge, d'empiler une série de contrôleurs de signal (un pour chaque adresse / sortie) et nous avons un multiplexeur!
ROM
La ROM est supposée prendre une adresse en entrée et envoyer l'instruction à cette adresse en sortie. Nous commençons par utiliser un multiplexeur pour diriger le signal d'horloge vers l'une des instructions. Ensuite, nous devons générer un signal en utilisant des croisements de fils et des portes OU. Les croisements de fils permettent au signal d'horloge de parcourir les 58 bits de l'instruction et permettent également à un signal généré (actuellement en parallèle) de descendre dans la ROM à émettre.
Ensuite, nous devons simplement convertir le signal parallèle en données série et la ROM est terminée.
La ROM est actuellement générée en exécutant un script dans Golly qui convertit le code d'assembly de votre presse-papiers en ROM.
SRL, SL, SRA
Ces trois portes logiques sont utilisées pour les décalages de bits, et elles sont plus compliquées que vos AND, OR, XOR, etc. Pour que ces portes fonctionnent, nous allons tout d'abord retarder le signal d'horloge pendant un laps de temps approprié afin de provoquer un "décalage" dans les données. Le deuxième argument donné à ces portes détermine le nombre de bits à déplacer.
Pour le SL et le SRL, nous devons
C'est faisable avec un tas de portes AND / ANT et un multiplexeur.
Le SRA est légèrement différent, car nous devons copier le bit de signe pendant le décalage. Pour ce faire, nous appelons ET le signal d'horloge avec le bit de signe, puis copions cette sortie plusieurs fois avec des séparateurs de fils et des portes OU.
Loquet Set-Reset (SR)
De nombreuses parties des fonctionnalités du processeur reposent sur la possibilité de stocker des données. En utilisant 2 cellules rouges B12 / S1, nous pouvons le faire. Les deux cellules peuvent rester l'une sur l'autre et rester ensemble. En utilisant des circuits supplémentaires de réglage, de réinitialisation et de lecture, nous pouvons créer un verrouillage SR simple.
Synchroniseur
En convertissant des données série en données parallèles, puis en configurant un ensemble de verrous SR, nous pouvons stocker un mot entier de données. Ensuite, pour récupérer les données, nous pouvons simplement lire et réinitialiser tous les verrous et retarder les données en conséquence. Cela nous permet de stocker un (ou plusieurs) mot de données en attendant un autre, ce qui permet de synchroniser deux mots de données arrivant à des moments différents.
Compteur de lecture
Cet appareil enregistre combien de fois il doit s’adresser à partir de la RAM. Pour ce faire, il utilise un périphérique similaire au verrou SR: une bascule en T. Chaque fois que la bascule T reçoit une entrée, elle change d'état: si elle était activée, elle s'éteint et inversement. Lorsque la bascule T bascule de on à off, elle envoie une impulsion de sortie qui peut être transmise à une autre bascule T pour former un compteur à 2 bits.
Afin de créer le compteur de lecture, nous devons régler le compteur sur le mode d'adressage approprié avec deux portes ANT et utiliser le signal de sortie du compteur pour décider où diriger le signal d'horloge: vers l'ALU ou vers la RAM.
File d'attente de lecture
La file d'attente de lecture doit garder trace du compteur de lecture qui a envoyé une entrée dans la RAM afin de pouvoir envoyer la sortie de la RAM à l'emplacement correct. Pour ce faire, nous utilisons des bascules SR: un bascule pour chaque entrée. Lorsqu'un signal est envoyé à la RAM depuis un compteur de lecture, le signal d'horloge est scindé et définit le verrouillage SR du compteur. La sortie de la RAM est alors associée à AND avec le verrou SR et le signal d'horloge de la RAM réinitialise le verrou SR.
ALU
L'ALU fonctionne de manière similaire à la file d'attente de lecture, en ce sens qu'elle utilise un verrou SR pour garder une trace de l'endroit où envoyer un signal. Tout d'abord, le verrouillage SR du circuit logique correspondant au code opération de l'instruction est défini à l'aide d'un multiplexeur. Ensuite, les valeurs du premier et du second argument sont associées à AND avec le verrou SR, puis sont transmises aux circuits logiques. Le signal d'horloge réinitialise le verrou au passage afin que l'ALU puisse être utilisée à nouveau. (La plupart des circuits sont paralysés et une tonne de gestion des retards est intégrée, de sorte que cela ressemble à un désordre.)
RAM
La RAM était la partie la plus compliquée de ce projet. Cela nécessitait un contrôle très spécifique sur chaque verrou SR qui stockait des données. Pour la lecture, l'adresse est envoyée dans un multiplexeur et envoyée aux unités de RAM. Les unités de RAM produisent en sortie les données stockées en parallèle, qui sont converties en série et sorties. Pour l'écriture, l'adresse est envoyée dans un multiplexeur différent, les données à écrire sont converties de série en parallèle et les unités de RAM propagent le signal dans toute la RAM.
Chaque unité de RAM métapixel 22x22 a cette structure de base:
En assemblant toute la RAM, nous obtenons quelque chose qui ressemble à ceci:
Tout mettre ensemble
Utilisation de tous ces composants et de l’architecture informatique générale décrite dans Présentation , nous pouvons construire un ordinateur en état de marche!
Téléchargements: - Ordinateur Tetris fini - Script de création de ROM, ordinateur vide et ordinateur principal
la source
Partie 4: QFTASM et Cogol
Vue d'ensemble de l'architecture
En bref, notre ordinateur a une architecture RISC Harvard asynchrone 16 bits. Lors de la construction manuelle d’un processeur, un RISC ( ordinateur à jeu d’instructions réduit) ) est pratiquement indispensable. Dans notre cas, cela signifie que le nombre d'opcodes est petit et, ce qui est beaucoup plus important, que toutes les instructions sont traitées de manière très similaire.
Pour référence, l'ordinateur Wireworld utilisait une architecture déclenchée par le transport , dans laquelle la seule instruction était
MOV
et les calculs étaient effectués en écrivant / lisant des registres spéciaux. Bien que ce paradigme conduise à une architecture très facile à mettre en œuvre, le résultat est également inutilisable à la limite: toutes les opérations arithmétiques / logiques / conditionnelles nécessitent trois instructions. Il était clair pour nous que nous voulions créer une architecture beaucoup moins ésotérique.Afin de garder notre processeur simple tout en augmentant la convivialité, nous avons pris plusieurs décisions de conception importantes:
Une illustration de notre architecture est contenue dans le post général.
Fonctionnalité et opérations ALU
À partir de là, il s’agissait de déterminer les fonctionnalités que devrait avoir notre processeur. Une attention particulière a été accordée à la facilité de mise en œuvre ainsi qu'à la polyvalence de chaque commande.
Mouvements conditionnels
Les mouvements conditionnels sont très importants et servent à la fois de flux de contrôle à petite et à grande échelle. "Petite échelle" désigne sa capacité à contrôler l'exécution d'un mouvement de données particulier, tandis que "grande échelle" désigne son utilisation en tant qu'opération de saut conditionnel pour transférer le flux de contrôle vers un élément de code quelconque. Il n'y a pas d'opération de saut dédiée car, en raison du mappage de la mémoire, un déplacement conditionnel peut à la fois copier des données dans la RAM normale et copier une adresse de destination sur le PC. Nous avons également choisi de renoncer aux mouvements inconditionnels et aux sauts inconditionnels pour une raison similaire: les deux peuvent être implémentés en tant que mouvement conditionnel avec une condition codée en dur en VRAI.
Nous avons choisi deux types de mouvements conditionnels: "move si non nul" (
MNZ
) et "move si inférieur à zéro" (MLZ
). Fonctionnellement, celaMNZ
revient à vérifier si l'un des bits de la donnée est un 1, alors queMLZ
de vérifier si le bit de signe est à 1. Ils sont utiles pour les égalités et les comparaisons, respectivement. La raison pour laquelle nous avons choisi ces deux options, telles que "déplacer si zéro" (MEZ
) ou "déplacer si supérieur à zéro" (MGZ
) étaitMEZ
de créer un signal VRAI à partir d'un signal vide, alors qu'ilMGZ
s'agit d'une vérification plus complexe nécessitant la le bit de signe soit à 0 tandis qu'au moins un autre bit est à 1.Arithmétique
Les instructions suivantes les plus importantes pour guider la conception du processeur sont les opérations arithmétiques de base. Comme je l'ai mentionné précédemment, nous utilisons des données série little-endian, le choix de l'endianité étant déterminé par la facilité des opérations d'addition / soustraction. En faisant arriver le bit le moins significatif en premier, les unités arithmétiques peuvent facilement suivre le bit de retenue.
Nous avons choisi d'utiliser la représentation du complément à 2 pour les nombres négatifs, car cela rend l'addition et la soustraction plus cohérentes. Il est à noter que l'ordinateur Wireworld utilisait un complément à un.
L'addition et la soustraction sont l'étendue du support arithmétique natif de notre ordinateur (en plus des décalages de bits qui seront discutés plus tard). D'autres opérations, comme la multiplication, sont beaucoup trop complexes pour être gérées par notre architecture et doivent être implémentées dans un logiciel.
Opérations sur les bits
Notre processeur a
AND
,OR
et desXOR
instructions qui font ce que vous attendez. Plutôt que d'avoir uneNOT
instruction, nous avons choisi d'avoir une instruction "and-not" (ANT
). La difficulté avec l'NOT
instruction est encore une fois qu'elle doit créer un signal à partir d'un manque de signal, ce qui est difficile avec un automate cellulaire. L'ANT
instruction ne renvoie 1 que si le bit du premier argument est 1 et que le second bit de l'argument vaut 0. Ainsi,NOT x
équivaut àANT -1 x
(ainsi qu'àXOR -1 x
). De plus, ilANT
est polyvalent et présente le principal avantage de masquer: dans le cas du programme Tetris, nous l’utilisons pour effacer les tétrominos.Bit Shifting
Les opérations de transfert de bits sont les opérations les plus complexes gérées par l'ALU. Ils prennent deux entrées de données: une valeur à déplacer et une quantité à déplacer. Malgré leur complexité (en raison du nombre variable de changements), ces opérations sont cruciales pour de nombreuses tâches importantes, y compris les nombreuses opérations "graphiques" impliquées dans Tetris. Les décalages de bits serviraient également de fondement à des algorithmes efficaces de multiplication / division.
Notre processeur effectue trois opérations de décalage de bits, "décalage gauche" (
SL
), "décalage droit logique" (SRL
), et "décalage droit arithmétique" (SRA
). Les deux premiers bits décalés (SL
etSRL
) remplissent les nouveaux bits avec tous les zéros (ce qui signifie qu'un nombre négatif décalé à droite ne sera plus négatif). Si le deuxième argument du décalage est en dehors de la plage de 0 à 15, le résultat est tous les zéros, comme vous pouvez vous attendre. Pour le dernier changement de bit,SRA
, le décalage de bits préserve le signe de l'entrée et agit donc comme une véritable division par deux.Instruction Pipelining
Le moment est venu de parler de certains des détails les plus difficiles de l’architecture. Chaque cycle de la CPU comprend les cinq étapes suivantes:
1. Récupérer l’instruction en cours de la ROM
La valeur actuelle du PC est utilisée pour extraire l’instruction correspondante de la ROM. Chaque instruction a un opcode et trois opérandes. Chaque opérande comprend un mot de données et un mode d'adressage. Ces parties sont séparées les unes des autres lors de leur lecture à partir de la ROM.
Le code opération est de 4 bits pour prendre en charge 16 codes opération uniques, dont 11 sont attribués:
2. Ecrivez le résultat (si nécessaire) de l' instruction précédente dans la RAM
Selon la condition de l'instruction précédente (telle que la valeur du premier argument d'un déplacement conditionnel), une écriture est effectuée. L'adresse de l'écriture est déterminée par le troisième opérande de l'instruction précédente.
Il est important de noter que l'écriture a lieu après l'extraction des instructions. Cela conduit à la création d'un intervalle de temps de branche dans lequel l'instruction est immédiatement exécutée après une instruction de branche (toute opération écrite sur le PC) à la place de la première instruction sur la cible de la branche.
Dans certains cas (comme des sauts inconditionnels), l'intervalle de retard de branche peut être optimisé. Dans d'autres cas, cela ne peut pas et l'instruction après une branche doit être laissée vide. En outre, ce type d'intervalle de retard signifie que les branches doivent utiliser une cible de branche dont l'adresse est inférieure de 1 à l'instruction cible réelle, afin de prendre en compte l'incrément PC qui se produit.
En bref, étant donné que la sortie de l'instruction précédente est écrite dans la RAM après l'extraction de l'instruction suivante, les sauts conditionnels doivent avoir une instruction vide après eux, sinon le PC ne sera pas mis à jour correctement pour le saut.
3. Lisez les données des arguments de l'instruction en cours à partir de la RAM.
Comme mentionné précédemment, chacun des trois opérandes comprend à la fois un mot de données et un mode d'adressage. Le mot de données est 16 bits, la même largeur que RAM. Le mode d'adressage est 2 bits.
Les modes d'adressage peuvent être une source de complexité importante pour un processeur comme celui-ci, car de nombreux modes d'adressage dans le monde réel impliquent des calculs en plusieurs étapes (comme l'ajout de décalages). Dans le même temps, les modes d'adressage polyvalents jouent un rôle important dans la convivialité du processeur.
Nous avons cherché à unifier les concepts d'utilisation de nombres codés en dur en tant qu'opérandes et d'utilisation d'adresses de données en tant qu'opérandes. Cela a conduit à la création de modes d'adressage basés sur des compteurs: le mode d'adressage d'un opérande est simplement un nombre représentant le nombre de fois que les données doivent être envoyées autour d'une boucle de lecture RAM. Cela englobe l'adressage immédiat, direct, indirect et double-indirect.
Une fois ce déréférencement effectué, les trois opérandes de l'instruction ont des rôles différents. Le premier opérande est généralement le premier argument d'un opérateur binaire, mais sert également de condition lorsque l'instruction en cours est un déplacement conditionnel. Le deuxième opérande sert de deuxième argument pour un opérateur binaire. Le troisième opérande sert d'adresse de destination pour le résultat de l'instruction.
Comme les deux premières instructions servent de données, tandis que la troisième sert d’adresse, les modes d’adressage ont des interprétations légèrement différentes selon la position dans laquelle ils sont utilisés. Par exemple, le mode direct est utilisé pour lire des données à partir d’une adresse RAM fixe ( une lecture RAM est nécessaire), mais le mode immédiat est utilisé pour écrire des données sur une adresse RAM fixe (aucune lecture RAM n'étant nécessaire).
4. Calculer le résultat
Le code d'opération et les deux premiers opérandes sont envoyés à l'ALU pour effectuer une opération binaire. Pour les opérations arithmétiques, au niveau du bit et de décalage, cela signifie que vous effectuez l'opération appropriée. Pour les mouvements conditionnels, cela signifie simplement renvoyer le deuxième opérande.
L'opcode et le premier opérande sont utilisés pour calculer la condition, qui détermine si le résultat doit être écrit ou non en mémoire. Dans le cas de déplacements conditionnels, cela signifie soit de déterminer si un bit de l'opérande est égal à 1 (pour
MNZ
), soit de déterminer si le bit de signe est égal à 1 (pourMLZ
). Si l'opcode n'est pas un mouvement conditionnel, l'écriture est toujours effectuée (la condition est toujours vraie).5. Incrémenter le compteur de programme
Enfin, le compteur de programme est lu, incrémenté et écrit.
En raison de la position de l'incrément du PC entre l'instruction lue et l'écriture de l'instruction, cela signifie qu'une instruction qui incrémente le PC de 1 est un non-op. Une instruction qui copie le PC sur lui-même entraîne l'exécution de l'instruction suivante deux fois de suite. Mais, soyez averti, plusieurs instructions PC consécutives peuvent provoquer des effets complexes, y compris des boucles infinies, si vous ne faites pas attention au pipeline d'instructions.
Quest for Tetris Assembly
Nous avons créé un nouveau langage d'assemblage appelé QFTASM pour notre processeur. Ce langage d'assemblage correspond 1 pour 1 au code de la machine dans la ROM de l'ordinateur.
Tout programme QFTASM est écrit sous la forme d’une série d’instructions, une par ligne. Chaque ligne est formatée comme ceci:
Liste d'opcode
Comme indiqué plus haut, l’ordinateur prend en charge onze codes, chacun ayant trois opérandes:
Modes d'adressage
Chacun des opérandes contient à la fois une valeur de données et un déplacement d'adressage. La valeur de données est décrite par un nombre décimal compris entre -32768 et 32767. Le mode d'adressage est décrit par un préfixe d'une lettre à la valeur de donnée.
Exemple de code
Séquence de Fibonacci en cinq lignes:
Ce code calcule la séquence de Fibonacci, l’adresse RAM 1 contenant le terme actuel. Il déborde rapidement après 28657.
Code gris:
Ce programme calcule le code Gray et le stocke dans des adresses successives commençant à l'adresse 5. Ce programme utilise plusieurs fonctionnalités importantes telles que l'adressage indirect et un saut conditionnel. Il s'arrête une fois que le code gris résultant est
101010
, ce qui se produit pour l'entrée 51 à l'adresse 56.Interprète en ligne
El'endia Starman a créé un interprète en ligne très utile ici . Vous pouvez parcourir le code, définir des points d'arrêt, effectuer des écritures manuelles sur la RAM et visualiser la RAM sous forme d'affichage.
Cogol
Une fois que l'architecture et le langage d'assemblage ont été définis, l'étape suivante du côté "logiciel" du projet a été la création d'un langage de niveau supérieur, adapté à Tetris. C'est ainsi que j'ai créé Cogol . Le nom est à la fois un jeu de mots sur "COBOL" et un acronyme pour "C de Game of Life", bien qu'il soit intéressant de noter que Cogol est à C ce que notre ordinateur est à un ordinateur réel.
Cogol existe à un niveau juste au-dessus du langage d'assemblage. Généralement, la plupart des lignes d'un programme Cogol correspondent chacune à une seule ligne d'assemblage, mais le langage présente certaines caractéristiques importantes:
ADD A1 A2 3
devientz = x + y;
, avec le compilateur, mappant des variables sur des adresses.if(){}
,while(){}
etdo{}while();
ainsi, le compilateur gère les branches.Le compilateur (que j'ai écrit à partir de zéro) est très basique / naïf, mais j'ai essayé d'optimiser manuellement plusieurs constructions de langage pour obtenir une longueur de programme compilée courte.
Voici quelques aperçus du fonctionnement de diverses fonctionnalités linguistiques:
Tokenization
Le code source est segmenté linéairement (passe unique), à l'aide de règles simples permettant de déterminer quels caractères sont autorisés à être adjacents dans un jeton. Lorsqu'un caractère rencontré ne peut pas être adjacent au dernier caractère du jeton actuel, le jeton actuel est considéré comme terminé et le nouveau caractère commence un nouveau jeton. Certains caractères (tels que
{
ou,
) ne peuvent pas être adjacents à d'autres caractères et constituent donc leur propre jeton. D' autres (comme>
ou=
) ne sont autorisés à être adjacents à d' autres personnages dans leur classe, et peuvent ainsi former des jetons comme>>>
,==
ou>=
, mais pas comme=2
. Les caractères d'espacement imposent une limite entre les jetons mais ne sont pas eux-mêmes inclus dans le résultat. Le personnage le plus difficile à tokenize est-
car il peut à la fois représenter une soustraction et une négation unaire, et nécessite donc une casse spéciale.L'analyse
L'analyse est également effectuée en une seule passe. Le compilateur dispose de méthodes pour gérer chacune des différentes constructions de langage et les jetons sont extraits de la liste des jetons globaux au fur et à mesure de leur utilisation par les différentes méthodes du compilateur. Si le compilateur voit un jeton qu'il ne s'attend pas, il génère une erreur de syntaxe.
Allocation de mémoire globale
Le compilateur assigne à chaque variable globale (mot ou tableau) sa ou ses adresses RAM désignées. Il est nécessaire de déclarer toutes les variables à l'aide du mot clé
my
afin que le compilateur sache lui allouer de l'espace. La gestion de la mémoire d’adresses de travail est beaucoup plus intéressante que les variables globales nommées. De nombreuses instructions (notamment les conditions et de nombreux accès au tableau) nécessitent des adresses temporaires de travail pour stocker les calculs intermédiaires. Pendant le processus de compilation, le compilateur alloue et désalloue des adresses de travail si nécessaire. Si le compilateur a besoin d’adresses de travail supplémentaires, il consacrera plus de RAM en tant qu’adresses de travail. Je pense qu’il est typique pour un programme de n’exiger que quelques adresses de travail, bien que chaque adresse de travail soit utilisée à plusieurs reprises.IF-ELSE
Les déclarationsLa syntaxe des
if-else
instructions est la forme C standard:Une fois converti en QFTASM, le code est organisé comme suit:
Si le premier corps est exécuté, le second corps est ignoré. Si le premier corps est ignoré, le deuxième corps est exécuté.
Dans l'assemblage, un test de condition est généralement une simple soustraction, et le signe du résultat détermine s'il faut effectuer le saut ou exécuter le corps. Une
MLZ
instruction est utilisée pour gérer des inégalités telles que>
ou<=
. UneMNZ
instruction est utilisée pour gérer==
, car elle saute sur le corps lorsque la différence n'est pas nulle (et donc lorsque les arguments ne sont pas égaux). Les conditions de multi-expression ne sont actuellement pas prises en charge.Si l'
else
instruction est omise, le saut inconditionnel l'est aussi, et le code QFTASM ressemble à ceci:WHILE
Les déclarationsLa syntaxe des
while
instructions est également la forme C standard:Une fois converti en QFTASM, le code est organisé comme suit:
Le test de condition et le saut conditionnel sont à la fin du bloc, ce qui signifie qu'ils sont réexécutés après chaque exécution du bloc. Lorsque la condition est fausse, le corps n'est pas répété et la boucle se termine. Au début de l'exécution de la boucle, le flux de contrôle saute sur le corps de la boucle jusqu'au code de condition. Ainsi, le corps n'est jamais exécuté si la condition est fausse la première fois.
Une
MLZ
instruction est utilisée pour gérer des inégalités telles que>
ou<=
. Contrairement auxif
instructions, uneMNZ
instruction est utilisée pour manipuler!=
, car elle saute au corps lorsque la différence n'est pas égale à zéro (et donc lorsque les arguments ne sont pas égaux).DO-WHILE
Les déclarationsLa seule différence entre
while
etdo-while
est que ledo-while
corps d' une boucle n'est pas initialement ignoré, il est donc toujours exécuté au moins une fois. J'utilise généralement desdo-while
instructions pour enregistrer quelques lignes de code d'assemblage lorsque je sais que la boucle n'aura jamais besoin d'être ignorée.Tableaux
Les tableaux unidimensionnels sont implémentés sous forme de blocs de mémoire contigus. Tous les tableaux ont une longueur fixe en fonction de leur déclaration. Les tableaux sont déclarés comme suit:
Pour le tableau, il s'agit d'un mappage RAM possible, montrant comment les adresses 15-18 sont réservées pour le tableau:
L'adresse étiquetée
alpha
est remplie par un pointeur sur l'emplacement dealpha[0]
. Ainsi, dans ce cas, l'adresse 15 contient la valeur 16. Laalpha
variable peut être utilisée à l'intérieur du code Cogol, éventuellement en tant que pointeur de pile si vous souhaitez utiliser ce tableau comme une pile. .L'accès aux éléments d'un tableau se fait avec la
array[index]
notation standard . Si la valeur deindex
est une constante, cette référence est automatiquement renseignée avec l'adresse absolue de cet élément. Sinon, il effectue une arithmétique de pointeur (juste addition) pour trouver l'adresse absolue souhaitée. Il est également possible d'imbriquer une indexation, telle quealpha[beta[1]]
.Sous-routines et appels
Les sous-routines sont des blocs de code pouvant être appelés à partir de plusieurs contextes, empêchant la duplication de code et permettant la création de programmes récursifs. Voici un programme avec un sous-programme récursif pour générer des nombres de Fibonacci (essentiellement l'algorithme le plus lent):
Un sous-programme est déclaré avec le mot-clé
sub
et un sous-programme peut être placé n'importe où dans le programme. Chaque sous-routine peut avoir plusieurs variables locales, qui sont déclarées dans la liste des arguments. Ces arguments peuvent également recevoir des valeurs par défaut.Afin de gérer les appels récursifs, les variables locales d'un sous-programme sont stockées dans la pile. La dernière variable statique dans la RAM est le pointeur de la pile d'appels, et toute la mémoire qui suit sert de pile d'appels. Lorsqu’un sous-programme est appelé, il crée une nouvelle trame sur la pile d’appels, qui inclut toutes les variables locales ainsi que l’adresse de retour (ROM). Chaque sous-routine du programme reçoit une seule adresse RAM statique pour servir de pointeur. Ce pointeur indique l'emplacement de l'appel "en cours" du sous-programme dans la pile d'appels. Le référencement d'une variable locale s'effectue à l'aide de la valeur de ce pointeur statique et d'un décalage pour donner l'adresse de cette variable locale particulière. La pile d'appels contient également la valeur précédente du pointeur statique. Ici'
Une chose intéressante à propos des sous-programmes est qu’ils ne renvoient aucune valeur particulière. Au lieu de cela, toutes les variables locales du sous-programme peuvent être lues après l'exécution du sous-programme, de sorte qu'une variété de données peut être extraite d'un appel de sous-programme. Ceci est accompli en stockant le pointeur pour cet appel spécifique du sous-programme, qui peut ensuite être utilisé pour récupérer l'une des variables locales à partir du cadre de pile (récemment désalloué).
Il existe plusieurs façons d'appeler un sous-programme, toutes en utilisant le
call
mot - clé:N'importe quel nombre de valeurs peut être donné comme argument pour un appel de sous-routine. Tout argument non fourni sera renseigné avec sa valeur par défaut, le cas échéant. Un argument qui n'est pas fourni et qui n'a pas de valeur par défaut n'est pas effacé (pour enregistrer des instructions / du temps) et peut donc potentiellement prendre n'importe quelle valeur au début du sous-programme.
Les pointeurs sont un moyen d'accéder à plusieurs variables locales du sous-programme, bien qu'il soit important de noter que le pointeur n'est que temporaire: les données pointées sur le pointeur seront détruites lors d'un autre appel de sous-programme.
Débogage des étiquettes
Tout
{...}
bloc de code dans un programme Cogol peut être précédé d’une étiquette descriptive comportant plusieurs mots. Cette étiquette est jointe en tant que commentaire dans le code d'assembly compilé et peut s'avérer très utile pour le débogage, car elle facilite la localisation de fragments de code spécifiques.Optimisation d'emplacement de délai de branche
Afin d’accroître la rapidité du code compilé, le compilateur Cogol effectue une optimisation des créneaux de retard vraiment élémentaire lors du passage final sur le code QFTASM. Pour tout saut inconditionnel avec un intervalle de retard de branche vide, cet intervalle peut être rempli par la première instruction à la destination du saut, et la destination du saut est incrémentée de un à la prochaine instruction. Cela enregistre généralement un cycle à chaque fois qu'un saut inconditionnel est effectué.
Écrire le code Tetris dans Cogol
Le programme final de Tetris a été écrit en Cogol et le code source est disponible ici . Le code QFTASM compilé est disponible ici . Pour plus de commodité, un lien permanent est fourni ici: Tetris dans QFTASM . L'objectif étant de jouer au code d'assemblage (et non au code Cogol), le code Cogol résultant est difficile à manier. De nombreuses parties du programme se trouveraient normalement dans des sous-routines, mais ces sous-routines étaient en fait suffisamment courtes pour que les instructions enregistrées en code soient dupliquées par dessus.
call
déclarations. Le code final n'a qu'un seul sous-programme en plus du code principal. De plus, de nombreux tableaux ont été supprimés et remplacés soit par une liste de variables individuelles de longueur équivalente, soit par un grand nombre de nombres codés en dur dans le programme. Le code QFTASM final compilé contient moins de 300 instructions, bien qu’il soit légèrement plus long que la source Cogol elle-même.la source
=
cela ne peut être qu’à côté de lui-même, mais il y a un!=
.+=
Partie 5: Assemblée, traduction et avenir
Avec notre programme d'assemblage du compilateur, il est temps d'assembler une ROM pour l'ordinateur Varlife et de tout traduire en un grand modèle GoL!
Assemblée
L’assemblage du programme d’assemblage dans une ROM s’effectue sensiblement de la même manière que dans la programmation traditionnelle: chaque instruction est traduite en un équivalent binaire, et celles-ci sont ensuite concaténées en un gros blob binaire que nous appelons un exécutable. Pour nous, la seule différence est que ce blob binaire doit être traduit dans des circuits Varlife et connecté à l'ordinateur.
K Zhang a écrit CreateROM.py , un script Python pour Golly qui effectue l'assemblage et la traduction. C'est assez simple: il prend un programme d'assemblage dans le presse-papiers, l'assemble dans un binaire et le traduit en circuit. Voici un exemple avec un testeur de primalité simple inclus avec le script:
Cela produit le binaire suivant:
Traduit en circuits Varlife, il ressemble à ceci:
La ROM est ensuite connectée à l'ordinateur, qui forme un programme pleinement fonctionnel dans Varlife. Mais nous n'avons pas encore fini ...
Traduction au jeu de la vie
Pendant tout ce temps, nous avons travaillé sur différentes couches d’abstraction au-dessus de la base de Game of Life. Mais maintenant, il est temps de lever le rideau de l'abstraction et de traduire notre travail en un modèle de jeu de la vie. Comme mentionné précédemment, nous utilisons le métapixel OTCA comme base pour Varlife. La dernière étape consiste donc à convertir chaque cellule de Varlife en métapixel dans Game of Life.
Heureusement, Golly est livré avec un script ( metafier.py ) capable de convertir des patterns de différents jeux de règles en patterns de Game of Life via le métapixel OTCA. Malheureusement, il est uniquement conçu pour convertir des modèles avec un seul jeu de règles global. Par conséquent, cela ne fonctionne pas avec Varlife. J'ai écrit une version modifiée qui résout ce problème afin que la règle de chaque métapixel soit générée cellule par cellule pour Varlife.
Ainsi, notre ordinateur (avec la ROM Tetris) a une boîte englobante de 1 436 x 5 082. Parmi les 7 297 752 cellules de cette boîte, 6 075 811 sont des espaces vides, ce qui laisse un effectif de 1 221 941 personnes. Chacune de ces cellules doit être traduite en métapixel OTCA, qui a un cadre englobant de 2048 x 2048 et une population de 64 691 (pour un métapixel ON) ou de 23 920 (pour un métapixel OFF). Cela signifie que le produit final aura un cadre de sélection de 2 940 928 x 10 407 936 (plus quelques milliers de plus pour les limites des métapixels), avec une population comprise entre 29 228 828 720 et 79 048 585 231. Avec 1 bit par cellule vivante, il faut entre 27 et 74 Go pour représenter l’ensemble de l’ordinateur et de la ROM.
J'ai inclus ces calculs ici parce que j'avais négligé de les exécuter avant de lancer le script et que très rapidement, il n'y avait plus de mémoire sur mon ordinateur. Après une
kill
commande paniquée , j'ai apporté une modification au script metafier. Toutes les 10 lignes de métapixels, le motif est enregistré sur le disque (fichier RLE compressé) et la grille est vidée. Cela ajoute du temps d'exécution supplémentaire à la traduction et utilise plus d'espace disque, mais maintient l'utilisation de la mémoire dans des limites acceptables. Étant donné que Golly utilise un format RLE étendu qui inclut l'emplacement du motif, cela n'ajoute pas de complexité supplémentaire au chargement du motif - il suffit d'ouvrir tous les fichiers de motif du même calque.K Zhang s'est inspiré de ce travail et a créé un script métafier plus efficace utilisant le format de fichier MacroCell, qui est plus efficace que RLE pour les grands modèles. Ce script s'exécute beaucoup plus rapidement (quelques secondes, comparé à plusieurs heures pour le script metafier d'origine), crée une sortie beaucoup plus réduite (121 Ko contre 1,7 Go) et peut métaficher l'ordinateur entier et la ROM en une seule fois sans utiliser une quantité énorme. de mémoire. Il tire parti du fait que les fichiers MacroCell encodent des arborescences décrivant les modèles. En utilisant un fichier de modèle personnalisé, les métapixels sont préchargés dans l'arborescence, et après quelques calculs et modifications pour la détection de voisins, le modèle Varlife peut simplement être ajouté.
Le fichier de configuration de l’ensemble de l’ordinateur et de la ROM dans Game of Life est disponible ici .
L'avenir du projet
Maintenant que nous avons fabriqué Tetris, nous avons terminé, non? Pas même proche. Nous avons plusieurs autres objectifs pour ce projet sur lesquels nous travaillons:
la source
ADD PC offset PC
? Excusez ma naïveté si cela est inexact, la programmation d’assemblage n’a jamais été mon fort.Partie 6: Le compilateur plus récent à QFTASM
Bien que Cogol soit suffisant pour une implémentation rudimentaire de Tetris, il est trop simple et trop bas pour une programmation polyvalente à un niveau facilement lisible. Nous avons commencé à travailler sur une nouvelle langue en septembre 2016. Les progrès sur la langue ont été lents à cause de bugs difficiles à comprendre et de la vie réelle.
Nous avons construit un langage de bas niveau avec une syntaxe similaire à Python, comprenant un système de types simple, des sous-routines prenant en charge la récursivité et les opérateurs intégrés. Le compilateur de texte en QFTASM a été créé en 4 étapes: le tokeniser, l’arbre de grammaire, un compilateur de haut niveau et un compilateur de bas niveau.
Le jeton
Le développement a été lancé à l'aide de Python à l'aide de la bibliothèque tokeniser intégrée, ce qui signifie que cette étape était assez simple. Seules quelques modifications de la sortie par défaut étaient nécessaires, notamment les commentaires de suppression (mais pas les commentaires
#include
).L'arbre de grammaire
L'arbre de grammaire a été créé pour être facilement extensible sans avoir à modifier le code source.
L'arborescence est stockée dans un fichier XML qui inclut la structure des nœuds pouvant constituer l'arborescence et la manière dont ils sont constitués avec d'autres nœuds et jetons.
La grammaire devait prendre en charge des nœuds répétés ainsi que des nœuds facultatifs. Ceci a été réalisé en introduisant des balises méta pour décrire comment les jetons devaient être lus.
Les jetons générés sont ensuite analysés selon les règles de la grammaire, de sorte que la sortie forme un arbre d’éléments grammaticaux tels que
sub
s etgeneric_variables
, qui contiennent à leur tour d'autres éléments de grammaire et des jetons.Compilation en code de haut niveau
Chaque caractéristique du langage doit pouvoir être compilée en constructions de haut niveau. Ceux-ci incluent
assign(a, 12)
etcall_subroutine(is_prime, call_variable=12, return_variable=temp_var)
. Des fonctions telles que l’insertion d’éléments sont exécutées dans ce segment. Ceux-ci sont définis en tant queoperator
s et sont spéciaux en ce sens qu’ils sont en ligne chaque fois qu’un opérateur tel que+
ou%
est utilisé. Pour cette raison, ils sont plus restreints que le code habituel - ils ne peuvent utiliser ni leur propre opérateur, ni aucun opérateur qui s'appuie sur celui qui est défini.Pendant le processus en ligne, les variables internes sont remplacées par celles appelées. Cela tourne en effet
dans
Ce comportement peut toutefois être préjudiciable et sujet à des bogues si la variable d'entrée et les variables de sortie pointent vers le même emplacement en mémoire. Pour utiliser le comportement "plus sûr", le
unsafe
mot - clé ajuste le processus de compilation de sorte que des variables supplémentaires soient créées et copiées vers et à partir de l'inline, le cas échéant.Variables à gratter et opérations complexes
Des opérations mathématiques telles que
a += (b + c) * 4
ne peuvent pas être calculées sans utiliser des cellules de mémoire supplémentaires. Le compilateur de haut niveau résout ce problème en séparant les opérations en différentes sections:Ceci introduit le concept de variables de grattage qui sont utilisées pour stocker des informations intermédiaires de calculs. Ils sont alloués selon les besoins et désalloués dans le pool général une fois terminé. Cela réduit le nombre d'emplacements de mémoire de travail nécessaires à l'utilisation. Les variables de grattage sont considérées comme globales.
Chaque sous-routine a son propre VariableStore pour conserver une référence à toutes les variables utilisées par le sous-programme ainsi que leur type. À la fin de la compilation, ils sont traduits en décalages relatifs à partir du début du magasin, puis donnés aux adresses réelles dans la RAM.
Structure RAM
Compilation de bas niveau
Les seules choses que le compilateur de bas niveau doit faire face sont
sub
,call_sub
,return
,assign
,if
etwhile
. Il s'agit d'une liste très réduite de tâches pouvant être traduites plus facilement en instructions QFTASM.sub
Ceci localise le début et la fin d'un sous-programme nommé. Le compilateur de bas niveau ajoute des étiquettes et, dans le cas du
main
sous - programme, ajoute une instruction de sortie (saut à la fin de la ROM).if
etwhile
Les interprètes
while
etif
les interprètes de bas niveau sont assez simples: ils ont des indications sur leurs conditions et sautent en fonction d’eux.while
les boucles sont légèrement différentes en ce qu'elles sont compilées commecall_sub
etreturn
Contrairement à la plupart des architectures, l'ordinateur pour lequel nous compilons ne prend pas en charge le matériel pour pousser et extraire une pile. Cela signifie que pousser et sortir de la pile prend deux instructions. Dans le cas de popping, nous décrémentons le pointeur de pile et copions la valeur dans une adresse. Dans le cas de la transmission, nous copions une valeur d'une adresse vers l'adresse du pointeur de la pile actuel, puis nous incrémentons.
Toutes les sections locales d'un sous-programme sont stockées à un emplacement fixe dans la RAM, déterminé au moment de la compilation. Pour que la récursion fonctionne, toutes les sections locales d’une fonction sont placées dans la pile au début d’un appel. Ensuite, les arguments du sous-programme sont copiés dans leur emplacement dans le magasin local. La valeur de l'adresse de retour est mise sur la pile et le sous-programme est exécuté.
Lorsqu'une
return
instruction est rencontrée, le haut de la pile est extrait et le compteur du programme est défini sur cette valeur. Les valeurs pour les sections locales du sous-programme appelant sont les sorties de la pile et leur position précédente.assign
Les assignations de variables sont les choses les plus faciles à compiler: elles prennent une variable et une valeur et sont compilées sur une seule ligne:
MLZ -1 VALUE VARIABLE
Assigner des cibles de saut
Enfin, le compilateur élabore les cibles de saut pour les étiquettes attachées aux instructions. La position absolue des étiquettes est déterminée, puis les références à ces étiquettes sont remplacées par ces valeurs. Les étiquettes elles-mêmes sont supprimées du code et, finalement, les numéros d'instructions sont ajoutés au code compilé.
Exemple de compilation pas à pas
Maintenant que nous avons franchi toutes les étapes, passons en revue le processus de compilation d’un programme réel, étape par étape.
Ok, assez simple. Il devrait être évident que , à la fin du programme,
a = 8
,b = 12
,c = 96
. Tout d’abord, incluons les parties pertinentes destdint.txt
:Ok, un peu plus compliqué. Passons sur le tokeniser et voyons ce qui en sort. A ce stade, nous n'aurons qu'un flux linéaire de jetons sans aucune forme de structure
Désormais, tous les jetons sont soumis à l’analyseur de grammaire et produisent un arbre avec le nom de chacune des sections. Cela montre la structure de haut niveau telle que lue par le code.
Cet arbre de grammaire configure les informations à analyser par le compilateur de haut niveau. Il comprend des informations telles que les types de structure et les attributs d'une variable. L'arbre de grammaire prend ensuite ces informations et affecte les variables nécessaires aux sous-programmes. L'arbre insère également toutes les lignes.
Ensuite, le compilateur de bas niveau doit convertir cette représentation de haut niveau en code QFTASM. Les variables sont affectées à des emplacements dans la RAM comme suit:
Les instructions simples sont ensuite compilées. Enfin, les numéros d'instruction sont ajoutés, ce qui donne un code QFTASM exécutable.
La syntaxe
Maintenant que nous avons le langage simple, nous devons y écrire un petit programme. Nous utilisons l'indentation comme le fait Python, divisant les blocs logiques et le flux de contrôle. Cela signifie que les espaces sont importants pour nos programmes. Chaque programme complet a un
main
sous-programme qui agit comme lamain()
fonction des langages C-like. La fonction est exécutée au début du programme.Variables et types
Lorsque les variables sont définies pour la première fois, elles doivent être associées à un type. Les types actuellement définis sont
int
etbool
avec la syntaxe pour les tableaux définis mais pas le compilateur.Bibliothèques et opérateurs
Une bibliothèque appelée
stdint.txt
est disponible qui définit les opérateurs de base. Si ce n'est pas inclus, même les opérateurs simples ne seront pas définis. Nous pouvons utiliser cette bibliothèque avec#include stdint
.stdint
définit des opérateurs tels que+
,>>
et même*
et%
qui ne sont pas non plus des opcodes QFTASM directs.Le langage permet également aux codes d'opération QFTASM d'être appelés directement avec
__OPCODENAME__
.L'addition dans
stdint
est définie commeCe qui définit ce que l’
+
opérateur fait quand on lui donne deuxint
s.la source