Brainfuck Interpreter

Insectoid · **Posted:** Sat Jul 09, 2011 4:16 am

Version 0.1 of my brainfuck interpreter, written in C. It is partially functional at the moment, but it will run the Hello World, addition, and multiplication programs as shown on the brainfuck wiki.

Bugs:
I/O: Currently reads from stdin. Need to rewrite it to read individual keystrokes. I'll probably end up using SDL, because I know how to use it, even though it's serious overkill (hunting rabbits with a rocket launcher-scale overkill). If someone has a better multi-platform solution, lemme know.

Loops: If the value at the data pointer is zero when entering a loop (for example, if your program is nothing more than []), the interpreter will 'forget' about the opening of the loop, execute the loop once, reach the close and return 'expected '[' before ']'. I know why this is happening, and I know how to fix it (rewriting most of the loop function, to be less messy and to consolidate errors). I'm gonna fix it tomorrow (well, later today. I haven't slept yet). Note that this will allow programs like '[+[-]' to run, even though it is incorrect syntax.

Goals for Version 1.0:
-Fix bugs (duh).
-Add a loop validator, to confirm that all loops are properly closed (and that there are no stray closing brackets). This may be integrated into a new sub-function for handling loops (searching for closing brackets as soon as an opening bracket is found). This should be easy to code, though it may run (negligibly) slower.
-Add overflow checks (currently, it is possible to go to byte -1 or lower and 30,000 and higher).

Goals for Version 2.0:
-Add support for as-you-go interpreting (like IRB for Ruby). Currently, the interpreter will only run prewritten files.
-Add 'optimization'- if you have 10 +'s in a row, it execute it as +10 instead of 10 +1's. This will only really be noticeable in verbose, but it might run (negligibly) faster and will be more fun to code. This will greatly reduce Verbose spam (see below).

Instructions:
Compile the program normally with your favorite compiler. Run with the filename as a parameter, for example './a.out hello_world.bf' (I have claimed .bf as my brainfuck extension, but the interpreter doesn't care).

There are 2 modes: Verbose, and non-verbose. As uploaded, I have non-verbose enabled. Verbos will tell you what it's doing, if it's moving the pointer, incrementing a value, entering a loop, etc (there are approximately as many lines of output in verbose as there are commands in your input file). To enable verbose, simply uncomment the line that defines it (#define VERBOSE, line 7). If I feel like it, I'll add verbose as a parameter instead of a compile-time definition.

Anyway, code!

c:

/*
* C Brainfuck interpreter
*Author: Jordan Dykstra
* ~FroopWare~
*/

//#define VERBOSE //if VERBOSE is defined, output will describe every command in the brainfuck source while executing.

#include <stdio.h>

int processChar(char);
int loop();

char data[30000];//dataz
char *dp; //data pointer, as per brainfuck specs
char cp; //command 'pointer' (not really, but it does the job of it as described in brainfuck)
FILE *file;//the file pointer, of course.

#ifdef VERBOSE
int index = 0; //integer representation of the location of the pointer, relative to 'data'.
#endif

int main (int argc, char* args[]){

for (int x = 0; x < 30000; x++){ //zero the array
data[x]=0;
}

//file stuff. Making sure the file opened and whatnot.
if (argc > 1) {
if ((file = fopen (args[1], "r")) == NULL){
fprintf (stderr, "Input file failed to load.\n");
return 1;
}

}
else {
fprintf (stderr, "No input file specified.\n");
return 1;
}

dp = data;
//main loop
while (!feof (file)){
cp = fgetc (file);
if (processChar (cp) == 2) {
fprintf (stderr, "Expected '[' before ']'.\n");
return 1;
}
}
printf ("\n");
return 0;
}

//returns 0 for success, 1 for eof, and 2 if it finds a ']'
int processChar(char in){
switch (in) {
case '>' :
dp++;

#ifdef VERBOSE
printf ("Incrementing Pointer to %d\n", ++index);
#endif
break;
case '<' :
#ifdef VERBOSE
printf ("Decrementing Pointer to %d\n", --index);
#endif
dp--;
break;
case '+' :
(*dp)++;
#ifdef VERBOSE
printf ("Incrementing Current Byte to %d\n", *dp);
#endif
break;
case '-':
(*dp)--;
#ifdef VERBOSE
printf ("Decrementing Current Byte to %d\n", *dp);
#endif
break;
case '.' :
printf ("%c", *dp);
break;
case ',' :
#ifdef VERBOSE
printf ("Inputting to Current Byte...");
#endif
*dp = getchar();
#ifdef VERBOSE
printf ("Stored %d in current byte.\n", *dp);
#endif
break;
case '[' :
#ifdef VERBOSE
printf ("Checking loop condition...");
#endif
return loop();
break; //This is just here, because I said it should be.
case ']' :
return 2;
break;
case EOF :
return 1;
break;
default :
break;
}
return 0;
}

int loop() {//returns 0 if successful; 1 otherwise
fpos_t start_of_loop; //stream pointer position at beginning of loop ('[')
int a; //stores return value of processChar();
fgetpos (file, &start_of_loop);

while (*dp > 0) {

fsetpos (file, &start_of_loop);
#ifdef VERBOSE
printf ("Loop entered; value at data pointer: %d\n", *dp);
#endif
while (true) {
cp = fgetc (file);
a = processChar(cp);
if (a == 2) {

#ifdef VERBOSE
printf ("Bottom of loop reached.\n");
#endif
break;
}
if (a == 1){
fprintf (stderr, "Expected ']' before end of file.\n");
return 1;
}
else if (a == 2) fprintf (stderr, "Expected '[' before ']'.\n");
}

}
#ifdef VERBOSE
printf ("Exiting loop.\n");
#endif
return 0;
}

Insectoid · **Posted:** Sat Jul 09, 2011 7:24 am

So, instead of going to bed and sleeping 'till 2, I kept slogging away at this. I managed to kinda fix the loop issue (it still won't complete the division program- gets about 75% of the way there). Now, it seems to 'forget' that it's in a loop. It gets 3 loops deep into the division program (I think), exits 2 of them properly, and then at the bottom of the 3rd it thinks that it isn't in a loop (same error as before).

I'm trying to fix it, but I keep distracting myself with throwing in more #ifdefs (verbose mode is so much fun!). However, being so tired (from coding all night), it's probably doing more harm than good. Anyway, if anyone thinks they can help out, that would be awesome.

Code for V0.2

c:

/*
* C Brainfuck interpreter
*Author: Jordan Dykstra
* ~FroopWare~
*/

#define VERBOSE //if VERBOSE is defined, output will describe every command in the brainfuck source while executing.

#include <stdio.h>

int processChar(char);
int loop();
int skipLoop();

char data[30000];//dataz
char *dp; //data pointer, as per brainfuck specs
char cp; //command 'pointer' (not really, but it does the job of it as described in brainfuck)
FILE *file;//the file pointer, of course.

#ifdef VERBOSE
int depth = 0; //Depth of loops. More for debugging the interpreter, than the code it will run.
int index = 0; //integer representation of the location of the pointer, relative to 'data'.
#endif

int main (int argc, char* args[]){
for (int x = 0; x < 30000; x++){ //zero the array
data[x]=0;
}

//file stuff. Making sure the file opened and whatnot.
if (argc > 1) {
if ((file = fopen (args[1], "r")) == NULL){
fprintf (stderr, "Input file failed to load.\n");
return 1;
}

}
else {
fprintf (stderr, "No input file specified.\n");
return 1;
}

dp = data;
//main loop
while (!feof (file)){
cp = fgetc (file);
if (processChar (cp) == 2) {
fprintf (stderr, "Expected '[' before ']'\n");
return 1;
}
}
printf ("\n");
return 0;
}

//returns 0 for success, 1 for eof, and 2 if it finds a ']'
int processChar(char in){
switch (in) {
case '>' :
#ifdef VERBOSE
printf ("Shifting pointer right to byte %d\n", ++index);
#endif
dp++;
break;
case '<' :
#ifdef VERBOSE
printf ("Shifting pointer left to byte %d\n", --index);
#endif
dp--;
break;
case '+' :
(*dp)++;
#ifdef VERBOSE
printf ("Incrementing byte %d to %d\n",index, *dp);
#endif
break;
case '-':
(*dp)--;
#ifdef VERBOSE
printf ("Decrementing byte %d to %d\n",index, *dp);
#endif
break;
case '.' :
printf ("%c", *dp);
break;
case ',' :
#ifdef VERBOSE
printf ("Inputting to byte %d: ", index); //Rewrite to record keystrokes instead of stdin
#endif
*dp = getchar();
#ifdef VERBOSE
printf ("Stored %d in byte %d\n", *dp, index);
#endif
break;
case '[' :
#ifdef VERBOSE
printf ("Checking loop condition...");
#endif
return loop();
break; //This is just here, because I said it should be.
case ']' :
return 2;
break;
case EOF :
return 1;
break;
default :
break;
}
return 0;
}
int loop() {//returns 0 if successful; 1 otherwise
if (*dp <= 0) return skipLoop();//hackish, but worky?
fpos_t start_of_loop; //stream pointer position at beginning of loop ('[')
int a; //stores return value of processChar();
fgetpos (file, &start_of_loop);

while (*dp > 0) {
fsetpos (file, &start_of_loop);
#ifdef VERBOSE
depth++;
printf ("Loop entered (%d); value at data pointer: %d\n", depth, *dp);
#endif
while (true) {
cp = fgetc (file);
a = processChar(cp);
if (a == 2) {
#ifdef VERBOSE
printf ("Bottom of loop %d reached...", depth);
depth--;
#endif
break;
}
if (a == 1){
fprintf (stderr, "Expected ']' before end of file.\n");
return 1;
}
else if (a == 2) fprintf (stderr, "Expected '[' before ']'.\n");
}

}
#ifdef VERBOSE
printf ("Exiting loop.\n", depth);
#endif

return 0;
}

int skipLoop (){ //called by loop() whenever there's a loop that initially fails the condition (*dp = 0)
#ifdef VERBOSE
depth++;
printf ("Bypassing loop %d\n", depth);
#endif
char bleh; //I'm tired, shuddup.
while (bleh = fgetc(file)){
if (bleh == ']') {
#ifdef VERBOSE
printf ("Bottom of loop %d reached\n", depth);
depth--;
#endif
return 0;
}
else if (bleh == '[') return skipLoop();
}
return 1;
}

If you try to interpret the division program (I'll paste a copy), you'll see that toward the end of the program, it bypasses a loop of depth 3 (depth being the number of 'nestings'). It then automatically bypasses loops 4 and 5 (because they are nested inside loop 3), exits the loop 5 bypass correctly, and then...loops 3 and 4 'complete' inside the loop function (which is odd, since it returns as soon as skipLoop() returns) and then I get that damn 'expected [ before ]' error, which I assume happens because the stream pointer isn't bumped forward enough because it's not running the rest of the skipLoop() function?

I dunno. It's completely baffling me. Anyway, here's the division program.

code:

,>,>++++++[-<--------<-------->>] Store 2 numbers from keyboard in (0) and (1);
and subtract 48 from each
<<[ This is the main loop which continues until
the dividend in (0) is zero
>[->+>+<<] Destructively copy the divisor from (1) to (2)
and (3); setting (1) to zero
>[-<<- Subtract the divisor in (2) from the dividend
in (0); the difference is stored in (0) and
(2) is cleared
[>]>>>[<[>>>-<<<[-]]>>]<<] If the dividend in (0) is zero; exit the loop
>>>+ Add one to the quotient in (5)
<<[-<<+>>] Destructively copy the divisor in (3) to (1)
<<<] Move the stack pointer to (0) and go back to
the start of the main loop
>[-]>>>>[-<<<<<+>>>>>] Destructively copy the quotient in (5) to (0)
(not necessary; but cleaner)
<<<<++++++[-<++++++++>]<. Add 48 and print result

You can just copy&paste this into a text file; the interpreter ignores all characters that don't actually do something.

Insectoid · **Posted:** Sat Jul 09, 2011 11:10 pm

All right, up to version 0.9!

I managed to fix that damn error (That'll teach me to code all night), and I've re-written I/O to use the ncurses library. Since this is a dynamic library, you'll need to have the runtime environment installed to run the program, but odds are it came pre-installed with your OS.

I still need to tweak I/O to be less of a pain in the ass for V1 (verbose is a nightmare atm, due to no wraparound). I think I'm going to write a class(yeah, I know this has so far been written in C and mixing is bad, but whatever) to manage the output window, 'cause this would very quickly become more of a mess than it already is is I wrote it inline with the rest of the program.

Little fun fact: a brainfuck interpreter, written in brainfuck, has fewer characters than this interpreter (though you need a brainfuck interpreter or compiler, to execute/compile them, so they can execute your code).

Until I get the window management figured out, I suggest you guys leave verbose off.

Other changes: You must compile with the -lncurses flag (to 'link ncurses' to the dynamic library). You'll need to have the library installed (not the runtime environment) to compile, which you're less likely to have installed by default (though 'nix and osx should come with it).

Anyway, code! This is fully functional (unlike the crippled wrecks above ^^) and should run any brainfuck program.

c:

/*
* C Brainfuck interpreter
*Author: Jordan Dykstra
* ~FroopWare~
*/

//#define VERBOSE //if VERBOSE is defined, output will describe every command in the brainfuck source while executing.

#include <stdio.h>
#include <ncurses.h>

int processChar(char);
int loop();
int skipLoop();
#define EXIT(a, b) \
printw ((b)); \
refresh(); \
getch(); \
endwin(); \
return 0;

char data[30000];//dataz
char *dp; //data pointer, as per brainfuck specs
char cp; //command 'pointer' (not really, but it does the job of it as described in brainfuck)
FILE *file;//the file pointer, of course.

#ifdef VERBOSE
int depth = 0; //Depth of loops. More for debugging the interpreter, than the code it will run.
int index = 0; //integer representation of the location of the pointer, relative to 'data'.
#endif

int main (int argc, char* args[]){

initscr();
raw();
noecho();
printw ("FroopWare Brainfuck Interpreter Version 1.0\nCopyright(c) Jordan Dykstra\n");
refresh();
for (int x = 0; x < 30000; x++){ //zero the array
data[x]=0;
}

//file stuff. Making sure the file opened and whatnot.
if (argc > 1) {
if ((file = fopen (args[1], "r")) == NULL){
EXIT (1, "Input file failed to load");
}

}
else {
EXIT (1, "No input file specified");
}

dp = data;
//main loop
while (!feof (file)){
cp = fgetc (file);
if (processChar (cp) == 2) {
EXIT (1, "Expected '[' before ']'\n");
}
}
printf ("\n");
getch();
endwin();
return 0;
}

//returns 0 for success, 1 for eof, and 2 if it finds a ']'
int processChar(char in){
switch (in) {
case '>' :
#ifdef VERBOSE
printw ("Shifting pointer right to byte %d\n", ++index);
refresh();
#endif
dp++;
break;
case '<' :
#ifdef VERBOSE
printw ("Shifting pointer left to byte %d\n", --index);
refresh();
#endif
dp--;
break;
case '+' :
(*dp)++;
#ifdef VERBOSE
printw ("Incrementing byte %d to %d\n",index, *dp);
refresh();
#endif
break;
case '-':
(*dp)--;
#ifdef VERBOSE
printw ("Decrementing byte %d to %d\n",index, *dp);
refresh();
#endif
break;
case '.' :
addch(*dp);
refresh();
break;
case ',' :
#ifdef VERBOSE
printw ("Inputting to byte %d: ", index);
refresh();
#endif
*dp = getchar();
#ifdef VERBOSE
printw ("%c (ASCII value: %d)\n", *dp, *dp);
#else
printw ("%c", *dp);
#endif
refresh();
break;
case '[' :
#ifdef VERBOSE
printw ("Checking loop condition...");
refresh();
#endif
return loop();
break; //This is just here, because I said it should be.
case ']' :
return 2;
break;
case EOF :
return 1;
break;
default :
break;
}
return 0;
}
int loop() {//returns 0 if successful; 1 otherwise
if (*dp <= 0) return skipLoop();//hackish, but worky?
fpos_t start_of_loop; //stream pointer position at beginning of loop ('[')
int a; //stores return value of processChar();
fgetpos (file, &start_of_loop);

while (*dp > 0) {
fsetpos (file, &start_of_loop);
#ifdef VERBOSE
depth++;
printw ("Loop entered (%d); value at data pointer: %d\n", depth, *dp); refresh();
#endif
while (true) {
cp = fgetc (file);
a = processChar(cp);
if (a == 2) {
#ifdef VERBOSE
depth--;
printw ("Bottom of loop %d reached from loop()", depth); refresh();
#endif
break;
}
if (a == 1){
printw ("Expected ']' before end of file.\n");refresh();
return 1;
}
else if (a == 2) printw ("Expected '[' before ']'.\n");refresh();
}

}
#ifdef VERBOSE
printw ("Exiting loop().\n", depth);refresh();
#endif

return 0;
}

int skipLoop (){ //called by loop() whenever there's a loop that initially fails the condition (*dp = 0)
#ifdef VERBOSE
depth++;
printw ("Bypassing loop %d\n", depth); refresh();
#endif
int return_value;
char bleh; //I'm tired, shuddup.
while (bleh = fgetc(file)){
if (bleh == ']') {
#ifdef VERBOSE
printw ("Bottom of loop %d reached from skipLoop()\n", depth);refresh();
depth--;
#endif
return 0;
}
else if (bleh == '[') {
if (skipLoop() == 1) return 1;
}
}
return 1;
}

And as a bonus, here's DBFI, a brainfuck interpreter, written in brainfuck!

brainfuck:

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

Save that as a file and pass it as an arg to my interpreter (henceforth "FroopWare Brainfuck Interpreter" or FWBI), then paste in any brainfuck program, followed by an exclamation point, and the input to that program (lol, I know). I warn you; nested interpreters are slow!

And a final word for this post; if anyone knows of a free, cross-platform console I/O library easier to use than ncurses (I really just need a getch() function) lemme know, 'cause it's gonna be a fair bit of work to make this pretty.

mirhagk · **Posted:** Tue Jul 12, 2011 6:51 pm

Developing cross-platform in C seems to be insanely difficult lol, might have been easier to use Brainfuck.

Brainfuck is a very interesting language, and attempting to code in it is very fun. Brainfuck was probably the first interpreter I ever wrote, as it is pretty easy to do.

I wanna do a project where I build a brainfuck machine out of logic gates, or perhaps even cooler, a brainfuck interpreter in minecraft lol, would you be interested in this?

DemonWasp · **Posted:** Wed Jul 13, 2011 10:38 am

Out of curiosity, why did you use #ifdefs for verbosity? Isn't that something most people would want to specify at run-time, not compile-time? Did you maybe mean "debug"?

Also, yes, cross-platform C is a royal pain in the ass.

Insectoid · **Posted:** Wed Jul 13, 2011 12:43 pm

yeah, I meant debug. Much of this was written early in the morning following a sleepless night, so mistakes like this (and worse) are expected.

DemonWasp · **Posted:** Wed Jul 13, 2011 1:43 pm

Ah well, quickly solved via :%s/VERBOSE/DEBUG/g

btiffin · **Posted:** Sun Jul 17, 2011 12:12 am

Insectoid: "And a final word for this post; if anyone knows of a free, cross-platform console I/O library easier to use than ncurses (I really just need a getch() function) lemme know, 'cause it's gonna be a fair bit of work to make this pretty."

Check out S-Lang http://en.wikipedia.org/wiki/S-Lang_(programming_library)
I tried making a sample for OpenCOBOL and posted the experiments to http://www.opencobol.org/modules/newbb/viewtopic.php?topic_id=589&forum=1#forumpost2983
Works well, and won't virtually erase the screen as ncurses is fond off when you just need a keyboard keycode.

And if you'd like to see OpenCOBOL to Guile to Scheme to bf in action, see http://www.opencobol.org/modules/newbb/viewtopic.php?topic_id=1167&forum=1

Well done Insectoid. The CompFu is strong in this one. Wink

Insectoid; Try this one. +++++ +++++ [ > +++++ ++ > +++++ +++ > + <<< - ] > -- . + . > ++ . -- . > . > , [ <<<< > - . + . > ++ . -- . > . > - ]

Cheers

	Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB Username: Password: Register
Wiki Blog Search Turing Chat Room Members