Brainfuck Interpreter in Java

Question

Description

To increase the awareness of my previous brainfuck question here's also a brainfuck interpreter.

This is written with Java 8

Class Summary (298 lines in 4 files, making a total of 7409 bytes)

• BrainF.java: Represents a Brainfuck program/execution
• BrainFCommand.java: Enum for the various Brainfuck commands

Code

This code can also be found on github

BrainF.java: (198 lines, 4575 bytes)

public class BrainF {
    public static final int DEFAULT_MEMORY_SIZE = 0x1000;

    public BrainF(int memorySize, String code, Stream<Byte> in) {
        this(memorySize, in);
        addCommands(code);
    }

    public BrainF(int memorySize, Stream<Byte> in) {
         memory = new byte[memorySize];
         input = in.iterator();
    }

    private final List<BrainFCommand> commands = new ArrayList<>();
    private final Iterator<Byte> input;
    private int commandIndex;
    private final byte[] memory;
    private final StringBuilder output = new StringBuilder();

    private int memoryIndex;

    public void addCommands(String string) {
        string.chars().mapToObj(i -> BrainFCommand.getCommand((char) i)).filter(obj -> obj != null).forEachOrdered(commands::add);
    }

    private void changeMemory(int i) {
        checkMemoryIndex();
        memory[memoryIndex] += i;
    }

    private void findMatching(BrainFCommand decrease, BrainFCommand increase, int direction) {
        int matching = 1;
        while (true) {
            commandIndex += direction;
            BrainFCommand current = commands.get(commandIndex);

            if (current == decrease) {
                matching--;
                if (matching == 0) {
                    break;
                }
            }
            else if (current == increase) {
                matching++;
            }
        }
    }

    public byte getMemory() {
        return memory[memoryIndex];
    }

    public void runToEnd() {
        while (commandIndex < commands.size()) {
            step();
        }
    }

    public BrainFCommand step() {
        if (commandIndex >= commands.size()) {
            return null;
        }
        BrainFCommand command = commands.get(commandIndex);
        perform(command);
        commandIndex++;
        return command;
    }

    public void setMemory(byte value) {
        memory[memoryIndex] = value;
    }

    public String getOutput() {
        return output.toString();
    }

    public int getMemoryIndex() {
        return memoryIndex;
    }

    public int getCommandIndex() {
        return commandIndex;
    }

    public void perform(BrainFCommand command) {
        switch (command) {
            case ADD:
                changeMemory(1);
                break;
            case END_WHILE:
                if (getMemory() != 0) {
                    findMatching(BrainFCommand.WHILE, BrainFCommand.END_WHILE, -1);
                }
                break;
            case NEXT:
                memoryIndex++;
                checkMemoryIndex();
                break;
            case PREVIOUS:
                memoryIndex--;
                checkMemoryIndex();
                break;
            case READ:
                byte value = input.next();
                setMemory(value);
                break;
            case SUBSTRACT:
                changeMemory(-1);
                break;
            case WHILE:
                if (getMemory() == 0) {
                    findMatching(BrainFCommand.END_WHILE, BrainFCommand.WHILE, 1);
                }
                break;
            case WRITE:
                char write = (char) getMemory();
                output.append(write);
                break;
            case NONE:
            default:
                break;
        }
    }

    private void checkMemoryIndex() {
        if (memoryIndex < 0) {
            memoryIndex += memory.length;
        }
        if (memoryIndex >= memory.length) {
            memoryIndex -= memory.length;
        }
    }

    public byte[] getMemoryArray(int fromIndex, int length) {
        return Arrays.copyOfRange(memory, fromIndex, fromIndex + length);
    }

    public void setCommands(String text) {
        commands.clear();
        addCommands(text);
    }

    public void reset() {
        Arrays.fill(memory, (byte) 0);
        commandIndex = 0;
        memoryIndex = 0;
        output.setLength(0);
    }

    public int getMemorySize() {
        return memory.length;
    }

    public byte getMemory(int index) {
        return memory[index];
    }

    public static BrainF createFromCodeAndInput(int memorySize, String code, String input) {
        return createFromCodeAndInput(memorySize, code, input.chars().mapToObj(i -> (byte) i ));
    }

    public static BrainF createFromCodeAndInput(int memorySize, String code, Stream<Byte> inputStream) {
        return new BrainF(DEFAULT_MEMORY_SIZE, code, inputStream);
    }

    public static BrainF createFromCode(String code) {
        return createFromCodeAndInput(DEFAULT_MEMORY_SIZE, code, "");
    }

    public static BrainF createFromCode(int memorySize, String code) {
        return createFromCodeAndInput(memorySize, code, "");
    }

    public static BrainF createWithDefaultSize() {
        return createUsingSystemInputWithMemorySize(DEFAULT_MEMORY_SIZE);
    }

    public static BrainF createUsingSystemInputWithMemorySize(int memorySize) {
        Stream<Byte> in = Stream.generate(() -> {
            try {
                return (byte) System.in.read();
            }
            catch (Exception e) {
                throw new RuntimeException(e);
            }
        });
        return new BrainF(memorySize, in);
    }

}

BrainFCommand.java: (27 lines, 619 bytes)

public enum BrainFCommand {

    NONE((char) 0), NEXT('>'), PREVIOUS('<'), WRITE('.'), READ(','), ADD('+'), SUBSTRACT('-'), WHILE('['), END_WHILE(']');

    private final char ch;
    private static final Map<Character, BrainFCommand> commands = new HashMap<>();

    static {
        for (BrainFCommand comm : BrainFCommand.values()) {
            commands.put(comm.ch, comm);
        }
    }

    private BrainFCommand(char ch) {
        this.ch = ch;
    }

    public static BrainFCommand getCommand(char ch) {
        return commands.getOrDefault(ch, NONE);
    }

}

Usage / Test

Just a simple test to prove it works. A simple GUI can be found on Github (be sure to click the 'Save Code' button if you use it)

BrainTest.java: (67 lines, 1992 bytes)

public class BrainTest {

    @Test
    public void gotoCorrectEndWhile() {
        BrainF brain = BrainF.createWithDefaultSize();
        brain.addCommands(">+>[-]+   ");
        brain.addCommands("++[-->++]-->   Find next 254 and go one step beyond it");
        brain.addCommands("            Loop through all 254s");
        brain.addCommands("+++[---         Make sure that we are not at 253 (end)");
        brain.addCommands("++[--<++]--  ");

        assertEquals(BrainFCommand.NEXT, brain.step());
        assertEquals(BrainFCommand.ADD, brain.step());
        assertEquals(BrainFCommand.NEXT, brain.step());
        assertEquals(BrainFCommand.WHILE, brain.step());

        assertEquals(6, brain.getCommandIndex());
        assertEquals(BrainFCommand.ADD, brain.step());
    }

    @Test
    public void simpleLoopMultiplication() {
        BrainF brain = BrainF.createWithDefaultSize();
        brain.addCommands("++[>+++<-]>>>");
        brain.runToEnd();
        assertArrayEquals(new byte[] { 0, 6, 0, 0, 0, 0, 0, 0, 0, 0 },
                brain.getMemoryArray(0, 10));
    }

    @Test
    public void printAlphabet() {
        BrainF brain = BrainF.createWithDefaultSize();
        brain.addCommands("++++++[>++++++++++>++++<<-]>+++++>++[-<.+>]");
        brain.runToEnd();
        assertEquals("ABCDEFGHIJKLMNOPQRSTUVWXYZ", brain.getOutput());
    }

    @Test
    public void input() {
        BrainF brain = BrainF.createFromCodeAndInput(BrainF.DEFAULT_MEMORY_SIZE, "+++,.", "a");
        brain.runToEnd();
        assertEquals("a", brain.getOutput());
    }

    @Test
    public void simpleCommands() {
        BrainF abc = BrainF.createWithDefaultSize();
        abc.addCommands("+>++>+++<");
        abc.runToEnd();
        assertEquals(9, abc.getCommandIndex());
        assertEquals(1, abc.getMemoryIndex());
        assertEquals(2, abc.getMemory());
        abc.perform(BrainFCommand.PREVIOUS);
        assertEquals(1, abc.getMemory());
        abc.perform(BrainFCommand.NEXT);
        abc.perform(BrainFCommand.NEXT);
        assertEquals(3, abc.getMemory());

    }

}

Questions

• Is the Stream<Byte> a good choice for the input? I was considering several but this seemed to me like the best option
• Any other comments welcome, but I would prefer more 'higher-level' comments than stylistic and naming details. I don't think I made any style or naming mistakes, but if you really think I have then feel free to comment on those as well.

Answer 1

Move the memory into it's own class. The concept of the tape which the BF program is operating can be cleanly made its own class with a limited interface.

Make private or eliminate interface cruft: perform, getMemoryIndex, reset, addCommands, setCommands, step. For a BF interpreter, it really only make sense to set a particular program and then run it. Manipulating or inspecting the state beyond that really isn't something makes sense for an interpreter. As it stands, you've got a interface with way too many options.

Don't pass input to the constructor. If this were at all a serious interpreter, you'd probably want to be able to run the same program against different input. So it really makes more sense to have input be a parameter to a run function.

checkMemoryIndex and findMatching have poor names. Both changes the state of the BF interpreter but neither names makes me think it will. I expect check* to assert if the state went bad and find* to return the result.

Answer 2

Usability

How the f.[< do I use this interpreter when it doesn't come with a main() function? Here's the simplest implementation I came up with, using java.nio.file.*:

public static void main(String[] args) throws IOException {
    String code = new String(Files.readAllBytes(Paths.get(args[0])));
    // TODO: Implement InputStreamToByteIteratorAdaptor
    BrainF interp = createFromCodeAndInput(DEFAULT_MEMORY_SIZE, code, new InputStreamToByteIteratorAdaptor());
    interp.runToEnd();
    System.out.println(interp.getOutput());
}

Even that shows some internal usability problems. I would have expected

public static void main(String[] args) throws IOException {
    (new BrainF(new File(args[0]))).run();
}

to work. Notably,

• The factory method name doesn't need to mention "default" — BrainF.create() or new BrainF() would work just as well. Let me worry about the size when I want to worry about the size. The interpreter can also auto-expand the memory as needed.
• Specifying the input via an Iterator<Byte> and buffering the output to a StringBuilder is extremely cumbersome. It should be easy to hook up the input and output to System.in and System.out, respectively — in fact, that is how it should be unless the I/O is deliberately redirected. I shouldn't have to write an InputStreamToByteIteratorAdaptor to run an interactive program.
• runToEnd() could just be run().

Additionally, this factory method is problematic:

public static BrainF createFromCodeAndInput(int memorySize, String code, Stream<Byte> inputStream) {
    return new BrainF(DEFAULT_MEMORY_SIZE, code, inputStream);
}

It is buggy in that it discards its memorySize paramater. Also, it serves the same purpose as the BrainF(memorySize, code, in) constructor. If you offer factory methods, then make the constructor private to avoid cluttering the interface offerings. Alternatively, just offer multiple constructors.

Commands

The giant switch in BrainF.perform() is a code smell. Why bother creating an enum at all, when you could just switch on character literals directly? Alternatively, if you do have an enum, then the behaviour of each command should be implemented in the command itself.

SUBSTRACT should be renamed SUBTRACT. (Personally, I would have chosen "increment"/"decrement".)