Interpréteur Brainfuck en C++

Dans cet article, je propose une implémentation pour un interpréteur du langage Brainfuck en utilisant les design patterns Interpreter, Composite et Factory method.

En soi, une n-ième implémentation de ce stupide langage est vraiment inutile 😉 . En revanche, il est intéressant d’avoir un cas concret de l’utilisation du pattern Interpreter car les exemples trouvés sur le net se ressemblent beaucoup et tournent autour de la numérotation romaine et de la notation polonaise inversée.

Le Brainfuck, c’est quoi ?

L’article Wikipedia sur le Brainfuck est assez complet. Pour faire court, il s’agit d’un langage de programmation très simpliste inventé par Urban Müller.

Il ne comporte que 8 instructions mais a la particularité d’être Turing-complet. Il est donc théoriquement possible d’écrire n’importe quel programme informatique en Brainfuck !

Dans ce langage, on dispose d’un tableau d’octets (initialisés à 0), d’un pointeur se déplaçant dans ce tableau (initialement positionné sur le premier octet du tableau) et de deux flux d’octets pour les entrées et les sorties.

Voici les huit instructions disponibles dans ce langage :

Caractère Signification
> déplace le pointeur d’un élément vers la droite.
< déplace le pointeur d’un élément vers la gauche.
+ incrémente l’octet du tableau sur lequel est positionné le pointeur.
décrémente l’octet pointé.
. sortie de l’octet pointé (valeur ASCII).
, entrée d’un octet dans le tableau à l’endroit où est positionné le pointeur (valeur ASCII).
[ saute à l’instruction après le ] correspondant si l’octet pointé est à 0.
] retourne à l’instruction après le [ si l’octet pointé est différent de 0.

Le programme « Hello World ! » peut s’écrire de la manière suivante :

++++++++++
[>+++++++>++++++++++>+++>+<<<<-]
>++.
>+.
+++++++.
.
+++.
>++.
<<+++++++++++++++.
>.
+++.
------.
--------.
>+.
>.

D’une lisibilité à toute épreuve… Allez faire un tour sur la page Wikipedia évoquée plus haut, le programme y est expliqué.

Le pattern Interpreter

Je n’ai pas encore écrit d’articles sur les design patterns mais ça me démange 🙂 ! Il faut juste que je trouve du temps pour le faire !

Le pattern Interpreter est le patron de conception utilisé lorsque le programme a besoin d’un langage pour décrire les instructions réalisables. Il définit la manière d’interpréter les différents éléments de ce langage.

interpreter

  • Client : utilisateur du patron de conception. Dans notre cas, ça sera simplement la fonction main.
  • AbstractExpression : classe abstraite qui fournit une interface pour toutes les expressions du langage interprété. La méthode interpret y est déclarée comme virtuelle pure.
  • TerminalExpression : classe associée à une expression interprétable avec un seul objet. Elle dérive de la classe AbstractExpression et propose une implementation de la méthode interpret. Dans le cas de notre interpréteur Brainfuck, une classe de ce type sera créée pour chacun des caractères >, <, +, -, . et ,.
  • NonTerminalExpression : classe associée à une expression qui est une composition d'expressions. Elle dérive de la classe AbstractExpression et agrègent des instances des classes TerminalExpression et NonTerminalExpression. L'appel de la méthode NonTerminalExpression::interpret lancera les méthodes interpret de toutes les instances agrégées. Dans le cas de l'interpréteur Brainfuck, il faut une classe de ce type qui sauvegarde l'ensemble du code interprété et une autre pour les boucles [ ].
  • Context : sauvegarde d'informations utilisées par les objets des classes TerminalExpression et NonTerminalExpression via la méthode interpret. Dans le cas de l'interpréteur Brainfuck, il s'agit d'une structure de données contenant le tableau et le pointeur associé.

Le pattern Composite

En fait, la structure précédente est très proche du pattern Composite qui consiste à manipuler un groupe d'objet de la même manière qu'un objet seul. Les objets regroupés possèdent des opérations communes.

composite

  • Component : classe abstraite pour déclarer l'interface de la composition d'objet. Elle fournit le comportement par défaut.
  • Leaf : classe représentant les objets manipulés ayant une interface commune.
  • Composite : classe pour définir le comportement des objets composés. C'est une agrégation d'instances des classes Leaf et Composite. Elle gère l'ajout add, la suppression remove et le traitement operation de ces instances.

Ce pattern permet de construire un arbre syntaxique associé au code Brainfuck interprété. Pour clarifier les choses, voici l'arbre syntaxique de ce code ,[.[-],]:

tree

Le pattern Factory method

Le pattern Factory method permet de créer des objets dans une hiérarchie de classe où la classe de base est abstraite.

factory_method

Ce pattern est utilisé pour instancier des objets du type NonTerminalExpression. On expliquera plus bas pourquoi.

Bon et le code maintenant !

Au final, l’interpréteur Brainfuck présenté est un mélange de ces trois design patterns.

Fichiers en-tête de la librairie standard

#include <iostream> // flux d'entrées et de sorties
#include <exception> // envoie d'une exception lorsque le pointeur sort du domaine

#include <list> // conteneur utilisé pour l'arbre syntaxique
#include <vector> // conteneur utilisé pour parcourir le tableau
#include <map> // dictionnaire associant les caractères aux expressions terminales

#include <string> // format utilisé pour parser le code Brainfuck
#include <memory> // utilisation du pointeur intelligent std::shared_ptr

Structure pour le tableau et le pointeur

On définit une structure qui contient le tableau sous la forme d'un std::vector et le pointeur associé de type int. L'accès à l'élément pointé se fera en utilisant l'opérateur operator[].

struct Data
{
    std::vector<int> array;
    int ptr;
};

Dans le pattern Interpreter, il s'agit de la classe Context.

Classe AbstractExpression

Cette classe abstraite fournit l'interface pour la composition d'objets et l’interprétation des différents caractères.

class AbstractExpression
{
    public:
        virtual void add(std::shared_ptr<AbstractExpression>) {}
        virtual void interpret(Data &) const = 0;

};

typedef std::shared_ptr<AbstractExpression> AbstractExpressionPtr;

Le type Data est passé par référence dans la méthode interpret car son contenu évolue durant le parcours de l'arbre syntaxique.

NB :

  • Les méthodes remove et isComposite du pattern Composite sont absentes de cette classe. Comme elle ne seront pas utilisées ici, il n'est pas nécessaire de les déclarer.
  • Un typedef a été introduit pour simplifier l'utilisation de std::shared_ptr<AbstractExpression>.

Classes des expressions terminales

Ces classes dérivent de la classe AbstractExpression et décrivent le comportement des caractères >, <, +, -, . et ,. Chaque classe fournit une implémentation spécifique de la méthode void interpret(Data &). Il s'agit des classes du type TerminalExpression évoquées dans la description du pattern Interpreter.

class IncrementByte: public AbstractExpression
{
    public:
        virtual void interpret(Data &data) const {
            data.array[data.ptr]++;
        }
};

class DecrementByte: public AbstractExpression
{
    public:
        virtual void interpret(Data &data) const {
            data.array[data.ptr]--;
        }
};

class IncrementPtr: public AbstractExpression
{
    public:
        virtual void interpret(Data &data) const {
            data.ptr++;
            if(data.array.size()==data.ptr) data.array.push_back(0);
        }
};

class DecrementPtr: public AbstractExpression
{
    public:
        virtual void interpret(Data &data) const {
            data.ptr--;
            if(data.ptr<0) throw std::out_of_range("Negative value of pointer");
        }
};

class Output: public AbstractExpression
{
    public:
        virtual void interpret(Data &data) const {
            std::cout<<char(data.array[data.ptr]);
        }
};

class Input: public AbstractExpression
{
    public:
        virtual void interpret(Data &data) const {
            char input;
            std::cin>>input;
            data.array[data.ptr] = static_cast<char>(input);
        }
};

Classes des expressions non terminales

Ces classes dérivent aussi de la classe AbstractExpression et sont une agrégation de classes dérivant de AbstractExpression. Il y a deux classes :

  • la première CompositeExpression permet de générer l'arbre syntaxique ;
  • la deuxième Loop dérive de la première et représente les boucles [ ].
class CompositeExpression: public AbstractExpression
{
    protected:
        std::list<AbstractExpressionPtr> expTree;
    public:
        virtual void add(AbstractExpressionPtr expr) {expTree.push_back(expr);}

        virtual void interpret(Data &data) const {
            for(const AbstractExpressionPtr & expPtr : expTree)
                expPtr->interpret(data);
        }
};

class Loop: public CompositeExpression
{
    public:
        virtual void interpret(Data &data) const {
            while(data.array[data.ptr]) {
                for(const AbstractExpressionPtr & expPtr : expTree)
                    expPtr->interpret(data);
            }
        }
};

Fabrique d'expressions

On y est presque ! Il ne reste plus qu'à mettre en oeuvre le pattern Factory method.

class AbstractFactory
{
    public:
        virtual AbstractExpressionPtr makeExpression() = 0;
        virtual char getClosure() {}
};

typedef std::shared_ptr<AbstractFactory> AbstractFactoryPtr;

template <class Expression>
class Factory: public AbstractFactory
{
    private:
        char closure;
    public:
        Factory(char c): closure(c) {}
        
        virtual AbstractExpressionPtr makeExpression() {
            return AbstractExpressionPtr(new Expression);
        }

        virtual char getClosure() {return closure;}
};

La classe Factory est capable d'instancier un objet de n'importe quelle classe dérivant de AbstractExpression. Néanmoins, on va voir qu'elle est uniquement utilisée pour la classe Loop.

NB :

  • L'attribut closure correspond au caractère de fermeture (par exemple ] pour les boucles).
  • Un typedef a été introduit pour simplifier l'utilisation de std::shared_ptr<AbstractFactory>.

Analyseur syntaxique

Pour l'analyseur syntaxique, je crée un paragraphe à part mais la classe associée est implémentée comme une fabrique.

class Parser: public AbstractFactory
{
    private:
        std::map<char, AbstractExpressionPtr> terminalMap;
        std::map<char, AbstractFactoryPtr> nonTerminalMap;
        std::string code;
    public:
        Parser(const std::string & c): code(c) {
            terminalMap['+'] = AbstractExpressionPtr(new IncrementByte);
            terminalMap['-'] = AbstractExpressionPtr(new DecrementByte);
            terminalMap['>'] = AbstractExpressionPtr(new IncrementPtr);
            terminalMap['<'] = AbstractExpressionPtr(new DecrementPtr);
            terminalMap['.'] = AbstractExpressionPtr(new Output);
            terminalMap[','] = AbstractExpressionPtr(new Input);
            nonTerminalMap['['] = AbstractFactoryPtr(new Factory<Loop>(']'));
        }
        
        virtual AbstractExpressionPtr makeExpression() {
            AbstractExpressionPtr syntaxTreePtr(new CompositeExpression);

            std::list<AbstractExpressionPtr> listNode(1, syntaxTreePtr);
            std::list<char> closure;
            
            for(char c : code) {
                if(terminalMap.find(c) != terminalMap.end()) {
                    listNode.back()->add(terminalMap);
                }
                else if(nonTerminalMap.find(c) != nonTerminalMap.end()) {
                    AbstractExpressionPtr current = nonTerminalMap->makeExpression();
                    listNode.back()->add(current);
                    listNode.push_back(current);
                    closure.push_back(nonTerminalMap->getClosure());
                }
                else if(c == closure.back()) {
                    listNode.pop_back();
                    closure.pop_back();
                }
            }
            return syntaxTreePtr;
        }
};

La chaîne de caractère code sauvegarde le code en Brainfuck.

Les dictionnaires terminalMap et nonTerminalMap permettent d'instancier les classes dérivant de AbstractFactory.

Avec terminalMap, les classes associés aux instructions >, <, +, -, . et , ne sont instanciés qu'une seule fois car les instancier à chaque fois qu'une de ces instructions est détectée occuperait inutilement la mémoire. En effet, comme ces classes n'ont pas d'attribut, les objets d'une même classe sont identiques.

Avec nonTerminalMap, la classe Loop est instanciée au moyen de la fabrique Factory. Ainsi, à chaque fois qu'une boucle est détectée, on crée une nouvelle instance.

La méthode makeExpression génère l'arbre syntaxique du type CompositeExpression. Une fois l'arbre généré, l'utilisation de la méthode CompositeExpression::interpret sur cet arbre exécutera le code Brainfuck.

Résultat final

Ça y est, on a tout ce qu'il nous faut pour interprêter notre code en Brainfuck.

int main()
{
    // Initialisation du tableau et du pointeur
    Data data;
    data.array.assign(1,0);
    data.ptr = 0;
    // Code HelloWorld
    string code("++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.");
    // Utilisation de l'analyseur syntaxique et de interpret
    Parser parser(code);
    AbstractExpressionPtr syntaxTreePtr = parser.makeExpression();
    syntaxTreePtr->interpret(data);
}

Avantages et limites de cette implémentation

On aurait très bien pu imaginer écrire l'interpréteur suivant une approche procédurale. Par exemple, on crée une fonction pour chacun des caractères >, <, +, -, . et , puis une fonction récursive pour interpréter le code en Brainfuck.

J'ai fait ça en python, on peut aussi le faire en C++. Évidemment, le code aurait été plus court et comporterait moins de classes, voire pas du tout.

Par ailleurs, l'utilisation du polymorphisme propre aux design patterns pénalisent les performances en terme d'exécution, de mémoire et de compilation : il faudrait faire un benchmark entre les deux approches pour en mesurer l'impact réel.

Néanmoins, la force d'une approche objet qui utilise les design patterns adaptés à la situation rencontrée est de produire un code très facile à faire évoluer. Dans le cas de cet interpréteur, rajouter l'interprétation d'une nouvelle instruction est un jeu d'enfant. En effet, il n'est pas nécessaire de toucher à l'algorithme qui génère l'arbre syntaxique comme on devrait le faire avec une approche procédurale.

Par exemple, je veux rajouter une instruction if matérialisée par les accolades { } et qui n'exécute son contenu que si l'élément pointé est non nul. Il suffit alors de rajouter une classe qui dérive de CompositeExpression avec une implémentation spécifique de interpret.

class If: public CompositeExpression
{
    public:
        virtual void interpret(Data &data) const {
            if(data.array[data.ptr]) {
                for(const AbstractExpressionPtr & expPtr : expTree)
                    expPtr->interpret(data);
            }
        }
};

Et de rajouter cette ligne dans le constructeur de la classe Parser :

nonTerminalMap['{'] = AbstractFactoryPtr(new Factory<If>('}'));

En conclusion, il est toujours préférable d'adopter une architecture logicielle évolutive quitte à optimiser par la suite. Cette approche augmentera significativement la durée de vie du projet !

N’hésitez pas à laisser un commentaire si vous souhaitez faire une remarque ou poser une question.

Partager :

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *