22
\$\begingroup\$

I was bored yesterday morning, so I wrote a brainfuck interpreter.

I know there are a lot, but this one is different. Why? Because it evaluates brainfuck code on the fly, reading from the input file, and eliminates code once it's not reachable anymore, instead of reading the whole program, analyzing it, and evaluating it.

I wrote it in C++ because that way I didn't have to re-write a vector, a stack...

I'm aware of a few bad program design practices:

  • It's monolithic, even though I find it readable... It's just a brainfuck interpreter though, so instead of using a context struct whith all the program data and split it, I found it easier to continue the main function.
  • Use of C functions (getchar/putchar) in evaluation instead of using C++'s streams. I think this way is more readable though.

I've compiled it with g++ in c++11 mode:

$ g++ -std=c++11 -Wall bf.cc -o bf

To run a program:

$ ./bf program.bf

I've tested successfully with all the files in here.

I'm concerned about:

  • Performance: I made it to be faster than most of interpreters out there. Any performance implication to make it run faster?
  • Readability: I think even though is monolithic, it's readable enough. Is it true?
  • Any bug/memory leak I could have missed.

The code

#include <iostream>
#include <vector>
#include <stack>
#include <fstream>

#define STACK_INITIAL_SIZE 300
#define DEAD_CODE_LIMIT 100
typedef unsigned char byte;

enum class State {
    READING,
    WHILE_IGNORING
};

int main(int argc, char** argv) {

    if ( argc < 2 ) {
        std::cerr << "Usage: " << argv[0] << " <file_name>" << std::endl;
        exit(1);
    }

    /** Get the source stream. */
    std::ifstream source(argv[1]);

    if ( ! source ) {
        std::cerr << "Invalid file: " << argv[1] << std::endl;
        exit(1);
    }

    /** Allocate the program stack. */
    size_t stack_size = STACK_INITIAL_SIZE;
    byte* stack = new byte[stack_size];

    /** Ensure it's initialized to zero */
    std::fill(stack, stack + stack_size, 0);

    /** Initial offset: pointing to the beginning of the stack */
    size_t offset = 0;

    /** Store the tokens, to allow looping */
    std::vector<char> tokens;
    size_t current_token_index = 0;

    /** Store the loop entry points */
    std::stack<size_t> entry_points;

    /** Store the states, to allow multiple looping */
    std::stack<State> states;

    /** Start reading */
    states.push(State::READING);

    while ( true ) {
        /** Declare the token */
        char token;

        /** Get the current state */
        State state = states.top();

        /** Realloc if we have not enough space, allocate 2 * stack_size */
        if ( offset == stack_size ) {
            size_t new_size = 2 * stack_size;

            /** Allocate space */
            byte* tmp = new byte[new_size];

            /** Copy old data */
            std::copy(stack, stack + stack_size, tmp);

            /** Set to 0 new data */
            std::fill(tmp + stack_size, tmp + new_size, 0);

            /** Delete old space */
            delete[] stack;

            /** Set the new stack data */
            stack = tmp;

            /** Keep track of the new stack size */
            stack_size = new_size;
        }

        /** If we are reading from `tokens` and reached the end, read next token from the file and push it into `tokens` */
        if ( current_token_index == tokens.size() ) {
            if ( (source >> token) )
                tokens.push_back(token);
            else
                break; /** Exit if the program ended */
        } else {
            token = tokens[current_token_index];
        }

        /** If we are ignoring chars... Just process '[' (add to the state stack) and ']' (remove from the state stack) */
        if ( state == State::WHILE_IGNORING && ! (token == ']' || token == '[') ) {
            current_token_index++;
            continue;
        }

        /** Main processing */
        switch ( token ) {
            case '>':
                offset++;
                break;
            case '<':
                offset--;
                break;
            case '+':
                stack[offset]++;
                break;
            case '-':
                stack[offset]--;
                break;
            /**
             * I know these could be written as
             * std::cout << static_cast<char>(stack[offset]);
             * and
             * std::cin >> static_cast<char>(stack[offset]);
             * but i find this way more readable
             */
            case '.':
                putchar(stack[offset]);
                fflush(stdout);
                break;
            case ',':
                stack[offset] = getchar();
                fflush(stdin);
                break;
            case '[':
                /** Add the current token to the stack, to come back later */
                entry_points.push(current_token_index);

                /** If the condition is false, or we're already ignoring, just ignore */
                if ( state == State::WHILE_IGNORING || ! stack[offset] )
                    states.push(State::WHILE_IGNORING);
                break;
            case ']':
                /** If we're ignoring just remove the last state */
                if ( state == State::WHILE_IGNORING )
                    states.pop();
                /** Else go back to the loop */
                else
                    current_token_index = entry_points.top() - 1;

                /** Remove the last entry_point */
                entry_points.pop();
                break;
            default:
                break; // ignore comments
        }

        /** Go to the next token */
        current_token_index++;

        /** Dead code elimination */
        if ( current_token_index > DEAD_CODE_LIMIT && entry_points.empty() ) {
            tokens.clear();
            current_token_index = 0;
        }
    }

    /** Program terminated, delete the stack data */
    delete[] stack;

    return 0;
}
\$\endgroup\$
12
\$\begingroup\$

Looks great! Just a few (small) suggestions:

Style

  • It really is quite readable and straightforward, but breaking out a few functions certainly wouldn't hurt.
  • Even though you're not using using namespace std; (woo!), the variable name stack still makes me a bit uncomfortable (then again, I can't think of a name for it that wouldn't end up being gross).
  • If you do end up pulling things into functions, you could orient the program reading around templated iterators (using an istream_iterator to accomplish what you're doing now). That would allow you to stream the program or to store it up front. That doesn't really accomplish much on its own, I suppose, but just figured it was worth noting since breaking it into smaller functions without doing it that way would quickly get quite messy.
  • STACK_INITIAL_SIZE and DEAD_CODE_LIMIT should be const int constants instead of macros.
  • Super subjective thing, but alphabetized includes can be a bit easier to mentally scan through.

Technicalities

  • size_t should technically be std::size_t, though it doesn't realistically matter.
  • You missed the include for cstdio.
  • getchar and putchar should be std::getchar and std::putchar.

Design

This is perhaps the most glaring thing I see in your code: stack should be a std::vector. In fact, it pretty much already is a manually managed vector. Performance will be the same as long as you're careful, and as a bonus, quite a bit of code should fall away (resizing, zeroing out, etc).


Preaching time: Manual memory (and resource) management should be incredibly rare (it should be limited pretty much to library-like containers, if even there).

For resources, there's always the RAII approach, and for memory, there's std::shared_ptr and std::unique_ptr (you code could have used std::unique_ptr for example).

To way oversimplify it, memory management (or more abstractly resource management) is incredibly difficult to get right in all but the smallest and simplest snippets of code. Luckily classes provide a nice, isolated place to tuck the complications away and more easily reason about behavior.

\$\endgroup\$
  • \$\begingroup\$ Asking because I don't know. How did you assume it was C++11 without the tag ? (You mentioned shared_ptr,..) \$\endgroup\$ – bhathiya-perera Mar 18 '15 at 3:24
  • \$\begingroup\$ @JaDogg The scoped enum was a dead give away :) \$\endgroup\$ – Corbin Mar 18 '15 at 3:45
  • \$\begingroup\$ Hi! Thanks for your detailed answer, really. The std::size_t really caught me off guard... ;) You're absolutely right about the std::vector instead of manual memory management. I chose manual because I wasn't aware of std::vector::resize(n, val);. Really good answer, I'll wait a day and if there's no better answer by then (I don't really think so) I'll mark it as accepted. \$\endgroup\$ – Emilio Cobos Mar 18 '15 at 8:09
  • \$\begingroup\$ stack should be a (gasp) std::stack. Hey presto, unlimited stack size! \$\endgroup\$ – Bulletmagnet Mar 18 '15 at 14:36
  • 2
    \$\begingroup\$ @Bulletmagnet Then you couldn't persist state when offset decreases \$\endgroup\$ – Emilio Cobos Mar 18 '15 at 14:43
6
\$\begingroup\$
  • DEAD_CODE_LIMIT is unnecessary. Once you've interpreted a command, you can definitely forget that command, unless there is an active [. (For example, if the program is +++++[<->], you don't need to store any of the first +++++. And as soon as you interpret a top-level ] and skip past it, it's safe to forget all of the preceding tokens.

  • You should special-case at least [-] as a well-known idiom for "set the current cell to zero". Otherwise you're wasting cycles that could be used for real work.

  • For memory management, consider using either realloc or a higher-level construct such as std::string::erase, rather than constantly using new+std::copy to copy data around.

  • When skipping to the next ], it's good that you don't pay attention to +-<> characters; but you still check offset == stack_size on every iteration. Write some special-case code to skip to the next ]. In general, use more small functions in order to simplify your main function. (You can declare your helper functions inline to get the same level of efficiency as inline code.)

  • I may not fully understand your code, but doesn't it crash when given <<<<<<+? The Brainfuck tape is not a "stack"; it's a two-way tape, and needs to "grow" in both directions[1]. You can fix this by checking for offset < 0 and reallocating (and increasing offset) if that's the case.


([1] Or else wrap around with a fixed length, in which case it doesn't need to grow in either direction and you can just use a plain old array.)

\$\endgroup\$
  • \$\begingroup\$ I understand the point you make about DEAD_CODE_LIMIT. Should have commented that that's a way of preventing a huge amount of deallocations (that may occur when you call std::vector::clear();). About the special instruction optimizations... They might be easy to do when you analyze the code statically, but not when you're dynamically evaluating it. \$\endgroup\$ – Emilio Cobos Mar 18 '15 at 8:11
  • 1
    \$\begingroup\$ When it skips to the next ], it's true that check is made. I didn't give it too much importance, good point there. Can you provide a source about the tape? At least according to Esolangs: "There is a pointer, initially pointing to the first memory cell. " \$\endgroup\$ – Emilio Cobos Mar 18 '15 at 8:20
  • \$\begingroup\$ Hmm, I'd always thought that the tape should be either infinite or looping, but muppetlabs.com/~breadbox/bf/standards.html says "If a program attempts to move the pointer below the first array cell, or beyond the last array cell, then that program's behavior is undefined. (A few implementations cause the pointer to wrap around, but many, perhaps most, implementations behave in a manner consistent with a C pointer wandering off into arbitrary memory.)" Still, if your C++ program has undefined behavior on any input (even maliciously crafted input), it's not a good C++ program. \$\endgroup\$ – Quuxplusone Mar 19 '15 at 6:42
  • \$\begingroup\$ What do you mean with any input? I mean... Is undefined if you move to the left, but... \$\endgroup\$ – Emilio Cobos Mar 19 '15 at 10:11
  • \$\begingroup\$ Right; you have undefined behavior on the input <+. So the answer to the question "Does there exist any input for which the behavior is undefined?" is "Yes." If there is any input for which your behavior is undefined, it's a bad thing. Equivalently (in this context): If your behavior is undefined for any input, it's a bad thing. Yes, the English language is less precise than mathematical notation. Unfortunately, it's what we've got to work with. \$\endgroup\$ – Quuxplusone Mar 19 '15 at 19:31
4
\$\begingroup\$

Hate your comments:

    /** Declare the token */
    char token;

    /** Get the current state */
    State state = states.top();

90% of them are useless.

Useless comment are bad. If they fall out of sync with the code then they cause a maintenance burden. Which is costly.

Don't write comments that explain the code (I can read the code and see what it means). Write comments that explain WHY you are doing something or at a high level the algorithm. If you use good variable and function names comments become nearly unnecessary (self documenting code).

You should not need to do manual memory management:

byte* stack = new byte[stack_size];

Either use something from the standard library std::vector or create your own class. But your business logic and your resource management code should be completely separate. See: Separation of Concerns.

Also doing it this way is not exception safe (which would matter a lot more in a larger program).

Encapsulation is your friend.

I would put the BF interpreter into its own class. Then it is much easier to think about (you can put initialization in one place (constructor)). Destructor can hold the tidy up etc.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.