7
\$\begingroup\$

Inspired by FizzBuzz by Brainfuck, I decided to write an interpreter for Brainfuck. It:

  1. Removes all non-command characters
  2. Optimizes commands (removing +- and <> pairs)
  3. Executes each command one-by-one

Speed:

  1. FizzBuzz by Brainfuck: about 10 milliseconds

Code:

BFInterpreter.java

import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class BFInterpreter {

    public static final int BF_MEMORY_SIZE = 30000;

    private static final InputStreamReader INPUT = new InputStreamReader(
            System.in);

    private static final int BYTE_SIZE = 256;
    private static final int HALF_BYTE = BYTE_SIZE / 2;

    public static void interpret(BFCode code) {
        // Check for errors
        if (hasErrors(code.getCode())) {
            throw new IllegalArgumentException(
                    "code has at least one error in it");
        }
        // -128 = 0, 0 = 128, 127 = 255 etc.
        byte[] bfMemory = new byte[BF_MEMORY_SIZE];
        Arrays.fill(bfMemory, Byte.MIN_VALUE);
        char[] commands = code.getOptimizedCode().toCharArray();
        for (int i = 0, pointer = 0, len = commands.length; i < len; i++) {
            switch (commands[i]) {
            case '+':
                bfMemory[pointer]++;
                break;
            case '-':
                bfMemory[pointer]--;
                break;
            case '<':
                if (--pointer == -1) {
                    pointer += BF_MEMORY_SIZE;
                }
                break;
            case '>':
                if (++pointer == BF_MEMORY_SIZE) {
                    pointer = 0;
                }
                break;
            case '.':
                System.out.print((char) (bfMemory[pointer] + HALF_BYTE));
                break;
            case ',':
                try {
                    bfMemory[pointer] = (byte) (INPUT.read() - HALF_BYTE);
                } catch (IOException e) {
                    // EOF? no change
                }
                break;
            case '[':
                if (bfMemory[pointer] == Byte.MIN_VALUE) { // == 0
                    i = indexOfMatchingCloseBracket(commands, i);
                }
                break;
            case ']':
                if (bfMemory[pointer] != Byte.MIN_VALUE) { // == 0
                    i = indexOfMatchingOpenBracket(commands, i);
                }
            }
        }
    }

    private static boolean hasErrors(String bfCode) {
        // each [ must have a ]
        char[] commands = bfCode.toCharArray();
        int diff = 0;
        for (char command : commands) {
            if (command == '[') {
                diff++;
            } else if (command == ']') {
                diff--;
            }
            if (diff < 0) {
                return false;
            }
        }
        return diff != 0;
    }

    private static int indexOfMatchingCloseBracket(char[] commands, int currentIndex) {
        int index = currentIndex;
        int numOfOpeningBrackets = 1;
        while (numOfOpeningBrackets != 0) {
            index++;
            if (commands[index] == ']') {
                numOfOpeningBrackets--;
            } else if (commands[index] == '[') {
                numOfOpeningBrackets++;
            }
        }
        return index;
    }

    private static int indexOfMatchingOpenBracket(char[] commands,
            int currentIndex) {
        int index = currentIndex;
        int numOfClosingBrackets = 1;
        while (numOfClosingBrackets != 0) {
            index--;
            if (commands[index] == ']') {
                numOfClosingBrackets++;
            } else if (commands[index] == '[') {
                numOfClosingBrackets--;
            }
        }
        return index;
    }

}

BFCode.java

public class BFCode {

    private final String code;

    public BFCode(String code) {
        this.code = code;
    }

    public String getCode() {
        return code;
    }

    public String getOptimizedCode() {
        return BFOptimizer.optimize(code);
    }

}

BFOptimizer.java

public class BFOptimizer {

    public static final String NOT_BF_REGEX = "[^\\Q><+-.,[]\\E]";
    public static final String EMPTY_STRING = "";

    public static String optimize(String bfCode) {
        bfCode = bfCode.replaceAll(NOT_BF_REGEX, EMPTY_STRING);
        while (true) {
            String result = bfCode.replaceAll("(\\+\\-)|(\\-\\+)|(<>)|(><)", EMPTY_STRING);
            if (result.equals(bfCode)) {
                return result;
            }
            bfCode = result;
        }
    }

}

Concerns:

  1. It's really slow executing each command one-by-one. I was thinking of grouping all same commands together, but that will have to wait until the next revision.
  2. Naming?
  3. Anything?
\$\endgroup\$
  • \$\begingroup\$ Does this support nested loops? \$\endgroup\$ – Ethan Bierlein Oct 24 '15 at 23:05
  • \$\begingroup\$ @EthanBierlein yes, at least I tested it to be yes: I actually used the code in the fizzbuzz question to test my code. \$\endgroup\$ – TheCoffeeCup Oct 24 '15 at 23:06
  • \$\begingroup\$ One of the most important bf optimizations is replacing small loops like [-] with their equivalents (that loop is used for zeroing a cell). There are several bf idioms that are commonly used, but very slow to interpret. \$\endgroup\$ – user3125280 Oct 25 '15 at 7:37
7
\$\begingroup\$

Performance

It looks like the biggest performance problem is in

        case '[':
            if (bfMemory[pointer] == Byte.MIN_VALUE) { // == 0
                i = indexOfMatchingCloseBracket(commands, i);
            }
            break;
        case ']':
            if (bfMemory[pointer] != Byte.MIN_VALUE) { // == 0
                i = indexOfMatchingOpenBracket(commands, i);
            }

Each time the interpreter hits the bracket, it performs a linear search over the source code. You may want to memoize a target address once the branch is taken.

Bug?

hasErrors returning false on diff < 0 sounds like a bug. The diff < 0 is an error, no?

Missing diagnostics

I'd want to know an exact position of a faulty bracket. In any case, checking for errors prior to execution is questionable. You may consider a interpretation-time exception.

\$\endgroup\$
  • \$\begingroup\$ Whoops, good catch on the bug! I actually meant true... \$\endgroup\$ – TheCoffeeCup Oct 25 '15 at 2:28

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.