Programmation Brainfuck/Compilateurs et interpréteurs

Programmation Brainfuck

• Introduction
• Les 8 instructions du langage
• Compilateurs et interpréteurs
• Comment effectuer les opérations courantes
• Variantes
• Conclusion

Compilation en C

Les programmes Brainfuck peuvent être traduits en C en utilisant les substitutions suivantes, en considérant que ptr est du type char*:

Brainfuck	C
>	++ptr;
<	--ptr;
+	++*ptr;
-	--*ptr;
.	putchar(*ptr);
,	*ptr = getchar();
[	while (*ptr) {
]	}

Le programme en C ci-dessous génère un code source en C à partir d'un programme source en Brainfuck. Cependant, le programme généré a une limite de taille mémoire, et le débordement de pointeur n'est pas vérifié.

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>

#define DEFAULT_DATA_SIZE 1024

void printHeader(unsigned int data_size)
{
	printf("#include <stdio.h>\n");
	printf("#include <stdlib.h>\n\n");
	printf("unsigned char octets[%d];\n", data_size);
	printf("unsigned char *ptr;\n\n");
	printf("int main()\n");
	printf("{\n");
	printf("\tptr = octets + %d;\n", data_size/2); /* Pointeur au milieu */
	return;
}

void printFooter()
{
	printf("\n\treturn 0;\n}\n");
	return;
}

int main()
{
	unsigned int data_size = DEFAULT_DATA_SIZE;
	int c;
	printHeader(data_size);
	while ((c = getchar()) != EOF)
	{
		switch(c)
		{
			case '>': printf("\tptr++;\n"); break;
			case '<': printf("\tptr--;\n"); break;
			case '+': printf("\t(*ptr)++;\n"); break;
			case '-': printf("\t(*ptr)--;\n"); break;
			case '.': printf("\tputchar(*ptr);\n"); break;
			case ',': printf("\t*ptr = getchar();\n"); break;
			case '[': printf("\twhile (*ptr)\n{\n"); break;
			case ']': printf("\t}\n"); break;
		}
	}
	printFooter();
	return 0;
}

Interpréteur en Javascript

Le code source ci-dessous est un interpréteur du langage Brainfuck. Il effectue une précompilation facilitant l'interprétation du code, en particulier pour les sauts d'instruction pour éviter de rechercher le caractère crochet correspondant. Il a la particularité d'autoriser tous les mouvements de pointeur de données, en allouant et décalant le buffer de données quand nécessaire. La seule limite étant la capacité mémoire du système.

function SyntaxErrorException(message, index)
{
   this.message = message;
   this.index = index;
}

class Brainfuck
{
	// Runtime data and input
	bf_data = []; // Data area
	bf_index = 0; // Data pointer
	ip = 0;       // Instruction Pointer (IP)
	input=[];     // Input data
	o_in = 0;     // Offset in input buffer

	// Compilation
	target_ip = []; // Target IP for [ and ]
	prog = '';      // Current program

	constructor(prog, input)
	{
		if (input!==undefined) this.input = input;
		this.compile(prog);
	}
	resetinput()
	{
		this.input = []
		this.o_in = 0
	}
	addinput(input)
	{
		if (input!==undefined && input!==null)
		{
			if (Array.isArray(input))
				this.input = this.input.concat(input)
			else if (typeof(input)==='number')
				this.input = this.input.concat([input])
			else if (typeof(input)==='string')
				this.input = this.input.concat(Object.assign([], input).map(v=>v.charCodeAt(0)))
		}
	}
	compile(prog)
	{
		this.ip = 0;
		this.prog = prog;
		var stack = [];
		var target_ip = [];
		for(var i=0;i<prog.length;i++)
		{
			var c = prog.charAt(i);
			switch(c)
			{
				case '[': stack.push(i); break;
				case ']':
					if (stack.length<=0) throw new SyntaxErrorException("ERROR ]", i);
					var n = stack.pop();
					target_ip[i] = n+1;
					target_ip[n] = i+1;
					break;
				default: target_ip[i] = 0;
			}
		}
		if (stack.length>0) throw new SyntaxErrorException("ERROR [", i);
		this.target_ip = target_ip;
	}
	reset()
	{
		this.bf_data=[];
		this.bf_index=0;
		this.ip = 0;
	}
	make()
	{
		if (this.bf_index<0)
		{
			let ar = [];
			while (this.bf_index<0) { ar.push(0); this.bf_index++; }
			this.bf_data = ar.concat(this.bf_data);
		}
		else if (this.bf_index>=this.bf_data.length)
		{
			while (this.bf_index>=this.bf_data.length) this.bf_data.push(0);
		}
	}
	get current()
	{
		this.make();
		return this.bf_data[this.bf_index];
	}
	set current(value)
	{
		this.make();
		this.bf_data[this.bf_index] = value;
	}
	execute(maxsteps)
	{
		if (maxsteps===undefined) maxsteps = 10000;
		var output = [];
		var ip = this.ip;
		var target_ip = this.target_ip;
		var prog = this.prog
		while (ip<prog.length)
		{
			if (--maxsteps<0) break;
			var c = prog.charAt(ip++);
			switch(c)
			{
			case '[': if (this.current==0) ip=target_ip[ip-1]; break;
			case ']': if (this.current!=0) ip=target_ip[ip-1]; break;
			case '+': this.current = this.current + 1; break;
			case '-': this.current = this.current - 1; break;
			case '>': this.bf_index++; break;
			case '<': this.bf_index--; break;
			case ',': this.current = (this.o_in>=this.input.length) ? 0 : this.input[this.o_in++]; break;
			case '.': output.push(this.current); break;
			default: // ignore comment
			}
		}
		this.ip = ip;
		return output;
	}
	// Retourne la sortie sous forme d'une chaîne de caractères.
	run(maxsteps)
	{
		return this.execute(maxsteps).map(v => String.fromCharCode(v)).join('')
	}
	// Retourne la sortie sous forme d'un tableau de nombres.
	runnum(maxsteps)
	{
		return this.execute(maxsteps)
	}
}

L'exemple ci-dessous montre comment utiliser la classe :

new Brainfuck('++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.').run()
// Retourne "Hello World!\n"

L'interpréteur permet de spécifier les données à lire, soit au constructeur, soit au fur et à mesure par exécution pas à pas :

// Boucle de 4 itérations (7 instructions par itération + 5 initiales)
var prog = new Brainfuck('++++[>,+.<-]');

prog.addinput([10,40]);
res = prog.runnum(19); // les 2 premières itérations
// Tableau de résultat : [11,41]

prog.addinput(20);
res = res.concat(prog.runnum(7)); // itération suivante
// Tableau de résultat : [11,41,21]

prog.addinput(50);
res = res.concat(prog.runnum(7)); // itération suivante
// Tableau de résultat : [11,41,21,51]

prog.addinput(90);
res = res.concat(prog.runnum(7)); // itération suivante ?
// Tableau de résultat : [11,41,21,51] inchangé car les 4 itérations sont passées.

prog.reset();      // Remise à zéro de l'exécution
res = res.concat(prog.runnum(12)); // initialisation et première itération
// Tableau de résultat : [11,41,21,51,91]

Optimisations

Certaines optimisations sont possibles :

• Regrouper plusieurs instructions d'incrémentation ou décrémentation + - en une instruction de synthèse ajoutant directement la valeur voulue,
• Même principe pour les instructions de déplacement du pointeur de données < >,
• Supprimer certaines séquences d'instructions qui s'annulent :
  • +-
  • <>
  • ...
• Supprimer les séquences entre crochets (boucle) quand il est certain que l'octet pointé vaut zéro (aucune itération) :
  • Une boucle en début de programme, car l'octet pointé vaut initialement zéro ;
  • Une boucle suivant immédiatement une autre paire de crochets, car à la sortie de la première boucle, l'octet pointé vaut zéro ;

    [ __A__ ][ __B__ ] → [ __A__ ]

  • Une boucle incluse dans une autre paire de crochets sans opérations entre les crochets des deux boucles, car après que toutes les itérations ont été effectuées par la boucle interne, l'octet pointé vaut zéro ;

    [[ __A__ ]] → [ __A__ ]

• Pré-calculer la position du crochet correspondant de chaque paire de la boucle (comme dans l'interpréteur en Javascript de la section précédente),
• Pour un interpréteur : retirer tous les caractères ignorés (commentaire),
• Optimiser les séquences de déplacement et incrémentation/décrémentation en calculant les opérations effectuées sur chaque case au cours du déplacement.

Exemple : <+<+<+>-<- simplifié : <+<<

• ...