Computer Science Canada

Brainfuck Interpreter

Author:  Insectoid [ Sat Jul 09, 2011 4:16 am ]
Post subject:  Brainfuck Interpreter

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;
}

Author:  Insectoid [ Sat Jul 09, 2011 7:24 am ]
Post subject:  RE:Brainfuck Interpreter

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.

Author:  Insectoid [ Sat Jul 09, 2011 11:10 pm ]
Post subject:  Re: Brainfuck Interpreter

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.

Author:  mirhagk [ Tue Jul 12, 2011 6:51 pm ]
Post subject:  RE:Brainfuck Interpreter

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?

Author:  DemonWasp [ Wed Jul 13, 2011 10:38 am ]
Post subject:  RE:Brainfuck Interpreter

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.

Author:  Insectoid [ Wed Jul 13, 2011 12:43 pm ]
Post subject:  RE:Brainfuck Interpreter

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.

Author:  DemonWasp [ Wed Jul 13, 2011 1:43 pm ]
Post subject:  RE:Brainfuck Interpreter

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

Author:  btiffin [ Sun Jul 17, 2011 12:12 am ]
Post subject:  Re: Brainfuck Interpreter

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


: