BrainFuck est un langage de programmation
ésotérique constitué d'une mémoire linéaire traditionnellement de 30 000 cases d'un octet, et de 8 instructions
permettant de manipuler cette mémoire:
• + : Incrémente de 1 la case courante
• - : Décrémente de 1 la case courante
• > : Déplace le pointeur indiquant la case courante vers la droite
• < : Déplace le pointeur indiquant la case courante vers la gauche
• . : Imprime sur la sortie standard le contenu de la case courante comme un caractère ASCII
• , : Lit un caractère sur l'entrée standard et le stocke dans la case courante
• [ : Si la case pointée actuellement contient la valeur zéro, le programme saute directement jusqu'au
] correspondant
• ] : Retourne au [ correspondant
Comme vous le voyez, ce langage est extrêmement minimaliste, et pourtant Turing-complet
(si on fait omission de la mémoire finie), ce qui veut dire que théoriquement, tout programme peut être
écrit dans le langage Brainfuck. Néanmoins comme vous vous en doutez sûrement (et comme le nom du langage le suggère),
programmer en Brainfuck devient très vite mission impossible si on projette de faire des programmes un tant
soit peu avancé.
RASMO permet d'écrire des programmes dans un langage proche d'une sorte d'assembleur, et ensuite de transformer ce
code directement en un code Brainfuck.
Mais avant d'être un assembleur à destination de Brainfuck, RASMO était une simple machine virtuelle créée
dans le but humoristique de programmer directement avec des 0 et des 1 dans un fichier texte, programme qui
était nativement compris par la machine virtuelle RASMO.
J'ai ensuite décidé pour une raison inconnue et probablement dangereuse pour ma santé mentale, de démarrer un projet
visant à créer automatiquement un programme Brainfuck à partir d'un programme RASMO.
Téléchargement des outils finaux :
• Outils Windows
• Outils Linux
Un programme binaire RASMO est organisé en instructions. Il est une suite d'instructions. Une instruction est elle-même composée de 3 nombres : l'opcode (indiquant quelle instruction il faut exécuter), le premier argument et le second argument.
L'opcode est un nombre entre 0 et 31 et est donc codé sur 5 bits. Chacun des deux arguments est un nombre entre 0 et 255 et est donc codé sur 8 bits. Une instruction est donc finalement codée sur 5 + 8 + 8 = 21 bits.
Le langage RASMO :
Comme il n'est pas aisé de programmer en binaire, j'ai défini un "langage" se substituant au binaire brut et permettant de programmer plus facilement, mais nécessitant donc transformation avant de l'exécuter.
Ainsi, au lieu d'écrire :
00111 00000000 01100001
00101 00000000 00000000
on écrit :
set 0 97 printnum 0 0
Comme les arguments des instructions sont des nombres entre 0 et 255, tous les nombres que vous manipulerez en RASMO seront des entiers positifs entre 0 et 255.
Voici l'entièreté des instructions RASMO :
00000 ADD : met la case x à x + y
00001 SUB : met la case x à x - y
00010 MUL : met la case x à x * y
00011 DIV : met la case x à x // y
00100 MOD : met la case x à x % y
00101 PRINTNUM : affiche x comme un nombre
00110 PRINT : affiche x comme un caractère (selon la table ASCII)
00111 SET : met y dans la case x
01000 COP : copie le contenu de la case pointée par case d'adresse x dans la case pointée par la case d'adresse y
01001 INPUT : copie le caractère entré par l'utilisateur dans la case d'adresse x
01010 INPUTNUM : copie le nombre entré par l'utilisateur dans la case d'adresse x
01011 PUSH : met la case pointée par x dans la pile
01100 POP : met le premier élément de la pile dans la case pointée par x et l'enlève de la pile
01101 LABEL : enregistre le label du nom de x,y
01110 GOTO : Va à l'instruction suivant le label du nom de x,y
01111 GT : met la case x à (nombre à la case pointée par x) < (nombre à la case pointée par y)
10000 LT : met la case x à (nombre à la case pointée par x) > (nombre à la case pointée par y)
10001 GTE : met la case x à (nombre à la case pointée par x) >= (nombre à la case pointée par y)
10010 LTE : met la case x à (nombre à la case pointée par x) <= (nombre à la case pointée par y)
10011 EQ : met la case x à (nombre à la case pointée par x) == (nombre à la case pointée par y)
10100 NOTEQ : met la case x à (nombre à la case pointée par x) != (nombre à la case pointée par y)
10101 AND : met la case x à (nombre à la case pointée par x) and (nombre à la case pointée par y)
10110 OR : met la case x à (nombre à la case pointée par x) or (nombre à la case pointée par y)
10111 XOR : met la case x à (nombre à la case pointée par x) xor (nombre à la case pointée par y)
11000 NOT : met la case x à not (nombre à la case pointée par x)
11001 JUMP : jumps to label y if number at adress x is zero
11010 CALL : goto label x,y and returns here if a RETURN instrction was encountered
11011 RETURN : returns to label if call was used
11100 INCR : ajoute y à la case pointée par x
11101 DECR : soustrait y à la case pointée par x
11110 RAND : met la case pointée par x à nombre aléatoire entre MEMOIRE[256*CHUNK + x] et MEMOIRE[256*CHUNK + y]. Remarque : Ne fonctionne pas lors de la transformation Brainfuck
11111 SETCHUNK : met le chunk actuel au chunk indiqué par la valeur dans la case x
x et y désignent respectivement le premier et le deuxième argument donnés après l'instruction. Comme vous l'avez remarqué, certaines instructions (comme pop par exemple) ne demandent qu'un seul argument. Or, en réalité, ils doivent quand même recevoir un deuxième argument, mais qu'ils n'utiliseront pas. Prenez donc par habitude de mettre 0, ou encore -. La syntaxe '-' est strictement équivalente à '0' mais indique clairement que c'est un argument non utilisé.
Les instructions réalisant des opérations prennent en argument deux adresses, réalisent l'opération avec les nombres situés à ces adresses, et mettent le résultat dans l'adresse indiquée par le premier argument.
Ainsi, le programme suivant affiche 7 :
set 0 2 set 1 5 add 0 1 printnum 0 -
La pile :
La pile est une structure de données intégrée à RASMO et permettant de stocker des plusieurs valeurs. Pour ajouter un élément à la pile, il faut utiliser l'instruction push. Une pile est une structure de données spéciale, et lorsque l'on utilise un pile, on ne peut que récupérer le dernier élément empilé. Mettre des nombres dans une pile consiste littéralement à les empiler, et pour accéder à un nombre en plein milieu de la pile, il n'y a pas d'autre choix que de dépiler tous les éléments au dessus.
Les label et les goto permettent de sauter n'importe où dans un programme. Lorsque vous mettez un label, c'est comme si vous plantiez un drapeau dans le programme à l'endroit où figure le label. L'instruction goto, elle, permet de sauter directement au numéro de label indiqué en paramètre. Un complément sur les labels viendra après.
D'abord, parlons du jump. Le jump est le saut conditionnel. C'est l'une des instructions les plus importantes, sans laquelle les IF, boucle WHILE, FOR n'existeraient pas. Cependant l'instrution jump n'est pas compliquée. Elle s'utilise comme suit : jump adresse label. Voici le comportement du jump : si la condition représentée par le nombre à l'adresse indiquée au jump est fausse (c'est-à-dire l'adresse pointe vers zéro), alors le programme saute directement au label indiqué. Sinon, rien ne se passe.
Exemple d'un IF simple à l'aide d'un JUMP :
set 12 condition ; jump 12 5 PRINTSTRING \La condition est vraie !\ 1 goto 1 1 label 5 - PRINTSTRING \La condition est fausse !\ 1 label 1 1
Si la condition est vraie, jump 12 5 ne va rien faire, et le programme va afficher La condition est vraie. Puis il va sauter à la fin pour éviter le deuxième bloc. Si au contraire, la condition était fausse, le programme va directement sauter au label 5 et afficher La condition est fausse.
Voici un petit complément sur les labels et les jump :
L'instruction label prenant en argument 2 nombres, est important de comprendre que les labels sont représentés par ces deux nombres (entre 0 et 255), et qu'il y a donc théoriquement 256*256 = 65536 labels utilisables.
Certaines instructions comme goto ou label permettent d'entrer un nom de label complet/large (deux arguments), mais certaines comme WHILE n'acceptent que des noms de label entre 0 et 255 (représentés par un seul argument). Pour ces instructions particulières, les labels que vous entrerez seront de la forme x (un seul nombre entre 0 et 256), mais les labels réels que vous utiliserez seront des labels sous la forme x 0 ou x - au lieu de x y. Ainsi, pour utiliser ces labels sur des instructions prenant des labels larges (à deux arguments), remplacez simplement le deuxième argument par 0 ou -
L'instruction call et l'instruction return vont par paire. call label_partie1 label_partie2 est quasiment comme goto label_partie1 label_partie2, à cela près que si une fois le saut effectué, le programme rencontre à un moment où à un autre un return - - (les return ne prennent pas d'arguments), il va revenir à l'endroit où le call avait été effectué. Cela ouvre la porte à la création de fonctions.
Les instructions incr et decr prennent en argument une adresse et un nombre et incrémentent ou décrémentent la valeur située à l'adresse indiquée de <deuxième argument>.
L'instruction cop est particulièrement pénible à utiliser, mais je vais vous l'expliquer un peu plus en détail car elle est indispensable et tout de même très puissante.
Pour vous l'expliquer, je vais prendre un nombre : 48. Ce nombre, je le mets dans la case 1. Enfin, dans la case 0, je mets 1. Concrètement :
| Adresse | Valeur |
|---|---|
| 0 | 1 |
| 1 | 48 |
De plus, dans la case 11, je mets 10. Au total, on a :
| Adresse | Valeur |
|---|---|
| 0 | 1 |
| 1 | 48 |
| 11 | 10 |
| 10 | ? |
ce que l'on peut aussi représenter par :
0 -> 1 -> 48
11 -> 10 -> ?
Maintenant, si j'exécute cop 0 11, la case 10 contiendra 48.
Retenez ceci :
Si x pointe vers a et que a contient b et que y pointe vers c, cop x y copiera le nombre b dans la case c
Si on traduit l'exemple du haut en code :
set 0 1 set 1 48 set 11 10 cop 0 11 printnum 10 -
Ceci affiche 48.
Les macros :
Les macros définies ci-dessous permettent de simplifier la vie au programmeur et sont transformées en code pendant l'assemblage/compilation. C'est pour cela que vous m'avez vu écrire PRINTSTRING alors que ce n'est pas une instruction. En réalité, PRINTSTRING et toutes les autres macros sont transformées en plusieur instructions lors de la compilation.
Cependant pour un souci de simplicité du parser, tout le programme doit être divisé en blocs de 3 "mots" à la suite. C'est pourquoi on retrouve deux types de macros :
- Les macros à 2 arguments
- Les macros à 5 arguments
De sorte que ces macros (arguments + mot-clé) sont des blocs de taille un multiple de 3.
Cependant il est important de noter que certaines instructions ne demandent pas toujours 2 paramètres, mais parfois 1 seul. C'est pourquoi on complète les paramètres avec des zéros ou '-', de telle manière a toujours avoir des blocs de 3 "mots" et ainsi les mots-clé sont toujours au début d'un bloc de 3.
Syntaxe des macros :
PRINTSTRING string mem : string est une suite de caractères collés et mem doit être une case de mémoire libre qui va être utilisée pour copier les caractères avant de les afficher
PRINTSTRING peut être utilisé avec deux syntaxes différentes, dans deux cas différents :
Ou alors vous voulez afficher une chaine de caractères sans espaces, auquel cas vous pouvez par exemple écrire PRINTSTRING coucou 0
Ou alors votre chaine de caractères a des espaces, et vous devez l'entourer de caractères \. Exemple : PRINTSTRING \La condition est vraie !\ 1
FOR label1 label2 variant nombre_max mem
ENDFOR label1 label2 variant pas - <- instruction à cinq arguments
Ces deux macros permettent d'érire simplement des boucles for.
Vous mettez la macro FOR, ensuite vous définissez le corps de votre boucle for, et enfin vous mettez le ENDFOR.
label1 et label2 doivent être des numéros de label libres et qui seront utilisés exclusivement pour cette boucle FOR. Comme vous l'avez remarqué, ce sont des labels de type [0-255] 0 et non pas [0-255] [0-255] comme je l'ai expliqué dans le paragraphe sur les label et les jump.
variant est la case mémoire qui sera utilisée pour le compteur de la boucle FOR
Les boucles FOR utilisent également une case en plus, la case mem.
Le nombre `pas` est de combien va être incrémenté le variant de boucle à chaque tour.
nombre_max est la borne supérieure pour le variant de boucle.
WHILE label1 label2 condition - -
ENDWHILE label1 label2
Le principe est à peu près le même, à cela près que vous devez vous occuper vous-même de calculer la condition de la boucle while (à coups d'instructions logiques).
FUNCTIONDEF id label : définit une routine appelable par call id -. label est un label utilisé par la macro FUNCTIONDEF car elle définit des goto
FUNCTIONEND label -
Entre les deux, vous pouvez écrire le corps de votre fonction. Notez qu'il n'y a pas besoin de mettre de return, car celui-ci est intégré dans le FUNCTIONEND.
Fonctionnement des chunks :
Nous arrivons à la fin et il ne reste qu'une seule instruction un peu mystérieuse : setchunk.
Comme vous l'avez vu, les instructions ne prennent que des arguments entre 0 et 255. Or, à ce stade, j'ai également dit deux autres choses qui peuvent paraître contradictoires : RASMO supporte l'adressage direct et la plage de mémoire accessible a une taille de 65 536 octets. Comment est-ce alors possible d'accéder à la case mémoire n°35 451 par exemple ?
La réponse est : les chunks. Cela ne vous aura pas échappé, 65 536 = 256 * 256. Et ce n'est pas pour rien. En réalité, la plage de mémoire de 65 536 octets est découpée en 256 chunks de 256 octets. A l'intérieur d'un chunk, vous pouvez adresser directement n'importe quel octet du chunk dans lequel vous vous trouvez, par des nombres entre 0 et 255. L'instruction setchunk vous permet de changer de chunk parmi les 256 chunks possibles.
Codes ASCII remarquables :
Espace : 32
Retour à la ligne : 10
Retour en arrière : 8
Le chiffre zéro : 48
Le 'A' majuscule : 65
Le 'a' minuscule : 97
Les define :
Comme vous l'avez remarqué, en RASMO, on ne manipule que des nombres pour les adresses mémoire et les labels. Les define permettent d'utiliser des mots au lieu des nombres. Par exemple, si j'écris :
define maVariable 56
je peux écrire maVariable partout où il y a un 56 normalement. Cela rend le code plus lisible. Je vous encourage à utiliser massivement les define.
Les commentaires :
Le seul type de commentaires existant est le commentaire sur une ligne, qui commence avec ; et finit à la fin de la ligne
Remarque :
Grâce aux call et à la pile, il est parfaitement possible de créer des fonctions prenant des arguments, et même de programmer de la récursivité. Vous trouverez des exemples de ces concepts avancés dans les fichiers fact.rsm (où j'ai implémenté une fonction factorielle récursive) et print.rsm (où j'ai implémenté une fonction prenant en argument une chaine de caractères et l'affichant).
Pour envoyer des arguments à une fonction, la meilleure idée est de les empiler sur la pile, et ensuite d'appeler la fonction avec call. La première chose que fait la fonction est alors de dépiler les arguments pour les utiliser et de faire ses calculs. Pour renvoyer une (ou plusieurs valeur), la fonction peut empiler elle aussi des nombres sur la pile avant de quitter. Après l'appel de la fonction, vous dépilez les valeurs de retour.
Pour implémenter des fonctiones récursives, il y a une petite subtilité. Avant de lancer l'appel récursif, vous devez empiler toutes les variables dont vous aurez besoin après l'appel récursif, et ensuite empiler les arguments de l'appel récursif. En effet, sinon, les appels récursifs vont écraser la valeur des cases que vous avez utilisées (toutes les variables sont globales).
Grâce au fait que vous avez empilé vos valeurs importantes, après la fin de l'appel récursif, vous pouvez dépiler le résultat renvoyé par l'appel récursif, et ensuite récupérer les valeurs que vous aviez empilées, et continuer vos calculs. Ce petit tour de passe-passe a permis à vos valeurs importantes de ne pas être écrasées par les mêmes valeurs lors des appels récursifs.
Voyons maintenant comment fonctionnent les outils de transformation en BrainFuck.
Comme vous vous en doutez peut-être, il n'est pas possible de créer un compilateur pur de RASMO vers Brainfuck. En effet, la différence fondamentale entre ces deux langages est qu'en RASMO, vous avez la possibilité de contrôler le pointeur d'exécution du programme (via des goto, des call). Vous pouvez sauter d'un endroit à un autre du programme comme bon vous semble, ce qui est impossible en Brainfuck. Les seuls sauts possibles sont les sauts de boucle, qui ne peuvent pas être combinés comme on le souhaite.
Pour cette raison, plutôt que de faire un simple compilateur, j'ai écrit en Brainfuck un interpréteur RASMO, qui lit un programme RASMO écrit dans la mémoire et l'exécute. Pour cette raison, la mémoire (la bande brainfuck) est découpée en trois grandes parties :
Chacune de ces parties de la mémoire est elle-même subdivisée en parties plus petites et répétitives nommées chunks (ce qui n'est pas un mot bien choisi car il y a beaucoup de types de chunks).
La zone mémoire réservée au programme est subdivisée en 256 gros chunks de 256 petits chunks. Chacun de ces petits chunks est organisé comme suit :
| OP | ARG1 | ARG2 | AD | DEST | CAR |
OP, ARG1 et ARG2 est l'instruction du programme, AD est l'adresse du petit chunk au sein du grand chunk, et DEST et CAR sont des cases permettant d'effectuer des copies quand on déplace des valeurs.
De plus, chaque début de grand chunk est organisé de cette manière :
| OP | ARG1 | ARG2 | AD | CHUNKNO | CHUNKAD |
où CHUNKAD est le numéro de gros chunk dans la mémoire. CHUNKNO sert à déplacer des valeurs.
Ensuite, l'UALC est simplement composée d'une vingtaine de cases, dont les 7 premières sont réservées à calculer le elif sur les opcodes, et les autres à réaliser les opérations telles que la division, la multiplication, etc.
Enfin, pour ce qu'on pourrait appeler la RAM (le tas et les deux piles), la mémoire est elle aussi divisée en 256 gros chunks de 256 petits chunks. Voici comment est organisé un petit chunk :
| CAR | DEST | AD | PILE I | PILE LS | TAS |
CAR et DEST servent à déplacer des valeurs, AD correspond à la place du petit chunk dans le grand chunk, et les trois dernières cases sont des cases mémoire, respectivement réservées à la Pile Intégrée, la Pile Libre Service, et le Tas.
Enfin, chacun des grands chunks commence par un petit chunk spécial organisé de la manière suivante :
| AD | CAR0 | DEST0 | PILE LS | PILE I |
où AD est le numéro de gros chunk, CAR0 et DEST0 permettent de stocker des valeurs temporaires en déplacement de gros chunk en gros chunk, et les deux dernières cases contiennent la taille de la division de la PILE I et de la PILE LS au sein du gros chunk.
Enfin, toute la RAM commence par les trois cases suivantes :
| NBCHUNK | PILE I | PILE LS |
qui permettent respectivement de stocker le numéro de chunk actuel, le chunk actif de la pile I et le chunk actif de la pile LS.
Comme vous le remarquez, la construction de cet interpréteur capable d'exécuter du code RASMO se rapproche de la construction d'une architecture de processeur. On dispose de places réservées (une UALC, une RAM, et une ROM), et on passe notre temps à déplacer des valeurs de l'une à l'autre et inversement pour exécuter le code.
Si on imagine que le programme RASMO est déjà chargé en mémoire, le schéma d'exécution sera toujours le même :
Cette grosse boucle while se termine au moment où l'opcode actuel est 41.
Comme vous le voyez, une fois le programme chargé en mémoire, il ne reste plus qu'à exécuter l'interpréteur (la grosse boucle while).
Ce qui précède étant dit, il devient extrêmement simple de créer le compilateur (une fois bien sûr que l'on a fini l'interpréteur RASMO, ce qui est plus de 99% du travail). En effet, il suffit de concaténer dans un même fichier trois programmes Brainfuck qui vont s'emboîter :
Le rôle du compilateur est donc uniquement de calculer le programme n°1 en fonction du binaire RASMO, puis de le concaténer avec les deux autres programmes qui eux, ne changent jamais.