Brainfuck interpreter using interpreter and composite patterns

Question

I wrote this brainfuck interpreter in C++ using interpreter and composite patterns. I would like to make this code more scalable.

Indeed, if we need to add a extra command, we'll have to add a new class derived from AbstractExpression but we may also need to modify some initialization in the constructor CompositeExpression(string code).

Is it possible to get something more polymorphic without adding a lot of classes?

Besides, is it a good practice to use a recursive call in the constructor CompositeExpression(string code)?

Includes and using namespace

#include <exception>
#include <iostream>
#include <list>
#include <deque>
#include <map>
#include <string>
#include <algorithm>
using namespace std;

Structure handled by Brainfuck commands

struct Data
{
 deque<int> array;
 int ptr;
};

Abstract class of an expression

class AbstractExpression
{
 public:
 virtual void interpret(Data &data) = 0;
 virtual void add(AbstractExpression * exp) {}
 virtual bool isComposite() {return false;}
 virtual ~AbstractExpression() {}
};

Classes of terminal expression

class IncrementByte: public AbstractExpression
{
 public:
 virtual void interpret(Data &data) {
 data.array[data.ptr]++;
 }
};
class DecrementByte: public AbstractExpression
{
 public:
 virtual void interpret(Data &data) {
 data.array[data.ptr]--;
 }
};
class IncrementPtr: public AbstractExpression
{
 public:
 virtual void interpret(Data &data) {
 data.ptr++;
 if(data.array.size()==data.ptr) data.array.push_back(0);
 }
};
class DecrementPtr: public AbstractExpression
{
 public:
 virtual void interpret(Data &data) {
 data.ptr--;
 if(data.ptr<0) throw out_of_range("Negative value of pointer");
 }
};
class Output: public AbstractExpression
{
 public:
 virtual void interpret(Data &data) {
 cout<<char(data.array[data.ptr]);
 }
};
class Input: public AbstractExpression
{
 public:
 virtual void interpret(Data &data) {
 char input;
 cin>>input;
 data.array[data.ptr] = static_cast<char>(input);
 }
};

Class of non terminal expression (loop)

class CompositeExpression: AbstractExpression
{
 private:
 CompositeExpression() {}
 protected:
 map<char,AbstractExpression*> expMap;
 list<AbstractExpression*> expTree;
 public:
 // To change if we add an extra command
 CompositeExpression(string code): expTree() {
 expMap['+'] = new IncrementByte;
 expMap['-'] = new DecrementByte;
 expMap['>'] = new IncrementPtr;
 expMap['<'] = new DecrementPtr;
 expMap['.'] = new Output;
 expMap[','] = new Input;
 char chars[6] = {'+','-','>','<','.',','};
 int skip(0);
 for(int i=0; i<code.size(); i++) {
 if(skip) {
 if(code[i] == '[') skip++;
 if(code[i] == ']') skip--;
 continue;
 }
 if(find(chars, chars+6, code[i]) != chars+6) {
 this->add(expMap[code[i]]);
 }
 else if (code[i] == '[') {
 this->add(new CompositeExpression(code.substr(i+1)));
 skip = 1;
 }
 else if(code[i]==']') break;
 }
 }
 virtual ~CompositeExpression() {
 for(list<AbstractExpression*> ::iterator it=expTree.begin(); it!=expTree.end(); it++) {
 if((*it)->isComposite()) delete (*it);
 }
 for(map<char,AbstractExpression*>::iterator it=expMap.begin(); it!=expMap.end(); it++)
 delete (*it).second;
 }
 virtual bool isComposite() {return true;}
 virtual void add(AbstractExpression * exp) {expTree.push_back(exp);}
 virtual void interpret(Data &data)
 {
 for(list<AbstractExpression*>::iterator it=expTree.begin(); it!=expTree.end(); it++) {
 if((*it)->isComposite()) {
 while(data.array[data.ptr])
 (*it)->interpret(data);
 }
 else {
 (*it)->interpret(data);
 }
 }
 }
};

Hello world !

int main()
{
 Data data; data.array.assign(1,0); data.ptr = 0;
 string code("++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.");
 CompositeExpression parser(code);
 parser.interpret(data);
}

Answer 1

As anybody is inspired by my code, I propose the following improvements.

First, it's not a good practice to call the virtual method virtual void add(AbstractExpression * exp) in the constructor CompositeExpression(string code).

Indeed, if we want to add a new class derived from CompositionExpression and with a new implementation of this method add, we need to overwrite the constructor otherwise it calls CompositionExpression::add instead of the new implementation. So it's more scalable to use a separate method rather than the constructor to parse brainfuck code.

Second, we can use shared_ptr from the c++11 standard library in order to simplify the destructor of CompositionExpression.

Last but not least, we can put the table chars in attributes to improve readability. Besides, I prefer to use a standard contener (list for example) otherwise find(chars, chars+6, code[i]) needs to be updated if we add a new terminal expression.

New include + a typedef

#include <memory>
typedef shared_ptr<AbstractExpression> AbstractExpressionPtr;

Updated AbstractExpression class

class AbstractExpression
{
 public:
 AbstractExpression() {}
 virtual ~AbstractExpression() {}
 virtual void add(shared_ptr<AbstractExpression>) {}
 virtual bool isComposite() {return false;}
 virtual void interpret(Data &) = 0;
 virtual void parse(const string &) {}
};

Updated CompositeExpression class

class CompositeExpression: public AbstractExpression
{
 protected:
 map<char, AbstractExpressionPtr> expMap;
 list<char> chars;
 list<AbstractExpressionPtr> expTree;
 public:
 CompositeExpression(): expTree() {
 chars.push_back('+'); expMap[chars.back()] = AbstractExpressionPtr(new IncrementByte);
 chars.push_back('-'); expMap[chars.back()] = AbstractExpressionPtr(new DecrementByte);
 chars.push_back('>'); expMap[chars.back()] = AbstractExpressionPtr(new IncrementPtr);
 chars.push_back('<'); expMap[chars.back()] = AbstractExpressionPtr(new DecrementPtr);
 chars.push_back('.'); expMap[chars.back()] = AbstractExpressionPtr(new Output);
 chars.push_back(','); expMap[chars.back()] = AbstractExpressionPtr(new Input);
 }
 virtual ~CompositeExpression() {}
 virtual bool isComposite() {return true;}
 virtual void add(AbstractExpressionPtr exp) {expTree.push_back(exp);}
 void parse(const string & code) {
 int skip(0);
 for(int i=0; i<code.size(); i++) {
 if(skip) {
 if(code[i] == '[') skip++;
 if(code[i] == ']') skip--;
 continue;
 }
 if(find(chars.begin(), chars.end(), code[i]) != chars.end()) {
 this->add(expMap[code[i]]);
 }
 else if (code[i] == '[') {
 AbstractExpressionPtr expr(new CompositeExpression());
 expr->parse(code.substr(i+1));
 this->add(expr);
 skip = 1;
 }
 else if(code[i]==']') break;
 }
 }
 virtual void interpret(Data &data)
 {
 for(list<AbstractExpressionPtr>::iterator it=expTree.begin(); it!=expTree.end(); it++) {
 if((*it)->isComposite()) {
 while(data.array[data.ptr])
 (*it)->interpret(data);
 }
 else {
 (*it)->interpret(data);
 }
 }
 }
};

Updated main

int main()
{
 Data data; data.array.assign(1,0); data.ptr = 0;
 string code("++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.");
 CompositeExpression parser;
 parser.parse(code);
 parser.interpret(data);
}

• kyrill: Talk about overkill. Here's some food for thought: how many classes would have to be added / extended to make this an interpreter of Brainlove?
• cromod: I must update my answer because I improved this code especially for looping. See my github repo. I wrote an article on my blog but in French...
• cromod: With this new code, we must add four classes + 4 lines in a constructor to interpret brainlove and we don't need to understand how the parser works. So it's easily scalable. I'm aware it's stupid to use this kind of code for this small project but my goal was to experiment scalability.
• kyrill: Nice. I have a few questions: Adding four classes + "registering" these classes in parser is one thing, but you also have to extensively modify Data, don't you? Extensively, because to make it really "scalable", you have to make Data abstract, then make expressions take the right subclass of Data. Eg. + needs only the memory vector and pointer, but $ also needs the accumulator; > only needs the pointer, etc. Thus at least one abstract class for Data, one subclass of Data for "memory", one for "pointer", one for "accumulator" and then combinations of these. That would be fun :D
• kyrill: Second question: how would you deal with ~? Unless I'm missing something, you would have to change the signature of AbstractExpression::interpret to return a value*. All instructions except ~ would return one value and ~ would return another value. Then in the loops, you have to check the returned value and break if it's the return value of ~. Of course loops would have to return a value as well... | * or somehow indicate to break from the loop, probably requiring to change Data