Immutable Brainfuck/C++ Interpreter

← Back to Immutable Brainfuck

The following is an interpreter for Immutable Brainfuck in C++ by User:None1.

crope version

It requires C++11 or newer and can only be compiled using GCC.

It uses the non-standard __gnu_cxx::crope (or __gnu_cxx::rope<char>), allowing it to execute every instruction in logarithm time.

Input code like dbfi (program!input) or use a file.

#include<bits/stdc++.h>
#include<ext/rope>
using namespace __gnu_cxx;
#define endl '\n'
using namespace std;
crope tape; // crope (or rope<char>) is just string but supports arbitrary insertion and deletion in O(logn) time
stack<int>s;
map<int,int>match;
int p,ip;
string program;
bool readtape(int x){
	if(x<tape.size())return tape[x];
	return 0;
}
void error(string msg){
	cerr<<"Error: "<<msg<<endl;
	exit(1);
}
int main(int argc,char *argv[]){
	tape.push_back(0);
	if(argc>1){
		if(argc>2){
			error("expected 0/1 arguments");
		}
		ifstream f(argv[1]);
		char c;
		while(f.get(c)){
			program.push_back(c);
		}
	}else{
		// dbfi-like format: program!input
		char c;
		while((c=cin.get())!='!'){
			program.push_back(c);
		}
	}
	for(int i=0;i<program.size();i++){
		char c=program[i];
		if(c=='['){
			s.push(i);
		}else if(c==']'){
			if(s.empty()){
				error("Unmatched ].");
			}
			match[i]=s.top();
			match[s.top()]=i;
			s.pop();
		}
	}
	if(s.size())error("Unmatched [.");
	while(ip<program.size()){
		char c=program[ip];
		switch(c){
			case '0':tape.insert(p+1,'\x00');break;
			case '1':tape.insert(p+1,'\x01');break;
			case '>':{
				++p;
				if(p>=tape.size())tape.push_back(0);
				break;
			}
			case '<':{
				if(!p)error("Pointer out of bounds");
				--p;
				break;
			}
			case '.':{
				char z=0;
				for(int i=0;i<p+8;i++)z=(z<<1)|readtape(i);
				cout<<z;
				break;
			}
			case ',':{
				char z=cin.get();
				if(cin.eof())z=0;
				for(int i=0;i<8;i++)tape.insert(p+1,z&1),z>>=1;
				break;
			}
			case '[':
			case ']':{
				if(readtape(p))ip=match[ip]; // Yep, the code for [ and ] are the same.
				break;
			}
			case '#':{
				cerr<<"IP: "<<ip<<"\tP: "<<p<<"\tTape: ";
				for(auto i:tape)cout<<(int)i;
				cout<<endl;
				break;
			}
		}
		++ip;
	}
	return 0;
}

list version

This version uses std::list. It executes every instruction in constant time and can be compiled with most compilers. However, it uses more memory than the crope version.

#include<iostream>
#include<fstream>
#include<string>
#include<stack>
#include<map>
#include<list>
#define endl '\n'
using namespace std;
list<bool>tape;
stack<int>s;
map<int,int>match;
int p,ip;
list<bool>::iterator ptr;
string program;
void error(string msg){
	cerr<<"Error: "<<msg<<endl;
	exit(1);
}
int main(int argc,char *argv[]){
	tape.push_back(0);
	ptr=tape.begin();
	if(argc>1){
		if(argc>2){
			error("expected 0/1 arguments");
		}
		ifstream f(argv[1]);
		char c;
		while(f.get(c)){
			program.push_back(c);
		}
	}else{
		// dbfi-like format: program!input
		char c;
		while((c=cin.get())!='!'){
			program.push_back(c);
		}
	}
	for(int i=0;i<program.size();i++){
		char c=program[i];
		if(c=='['){
			s.push(i);
		}else if(c==']'){
			if(s.empty()){
				error("Unmatched ].");
			}
			match[i]=s.top();
			match[s.top()]=i;
			s.pop();
		}
	}
	if(s.size())error("Unmatched [.");
	while(ip<program.size()){
		char c=program[ip];
		switch(c){
			case '0':tape.insert(next(ptr),0);break;
			case '1':tape.insert(next(ptr),1);break;
			case '>':{
				++p;
				if(p>=tape.size())tape.push_back(0);
				++ptr;
				break;
			}
			case '<':{
				if(!p)error("Pointer out of bounds");
				--p;
				--ptr;
				break;
			}
			case '.':{
				char z=0;
				list<bool>::iterator it=ptr;
				for(int i=0;i<8;i++){
					if(it==tape.end())z<<=1;
					else z=((z<<1)|(*it)),++it;
				}
				cout<<z;
				break;
			}
			case ',':{
				char z=cin.get();
				if(cin.eof())z=0;
				for(int i=0;i<8;i++)tape.insert(next(ptr),z&1),z>>=1;
				break;
			}
			case '[':
			case ']':{
				if(*ptr)ip=match[ip]; // Yep, the code for [ and ] are the same.
				break;
			}
			case '#':{
				cerr<<"IP: "<<ip<<"\tP: "<<p<<"\tTape: ";
				for(auto i:tape)cout<<(int)i;
				cout<<endl;
				break;
			}
		}
		++ip;
	}
	return 0;
}