Интерпретатор BrainFuck

Все говорят, что с этим языком можно поломать мозг. И я решил попробовать, настолько ли страшен BrainFuck как его рисуют. Хороший способ разобраться с языком - написать интерпретатор.

Могу сказать, что BrainFuck - очень легкая версия ассемблера, поскольку в ассемблере купа регистров, память с адресами, разные команды, а в BrainFuck - память, один регистр, указывающий на ячейку памяти с которой работаем и пару простых операций:
> - увеличение регистра на 1 (перемещение по ленте-памяти вправо)
< - уменьшение регистра на 1 (перемещение по ленте-памяти вправо)
+ - увеличение значения ячейки памяти на 1
- - уменьшение значения ячейки памяти на 1
. - ввод данных в ячейку памяти
, - вывод данных из ячейки памяти
[ - начало цикла, если текущая ячейка памяти не 0 то заходим в цикл (следующая команда)
] - конец цикла, если текущая ячейка памяти равна 0 - то выходим из цикла, иначе идем к следующей команде после открывающей [

Я добавил в свой интерпретатор еще пару отладочных команд.
@ - остановить программу в этом месте
# - записать состояние памяти и указатель на память (потом можно будет вывести все)

Интерфейс у меня вышел таким.

public interface Interpreter {
    Interpreter compile(String program, String input);

    String getOutput();

    String printMemory();

    List<String> getTrace();

    Interpreter compile(String program);

    Interpreter run();

    Interpreter useBreakpoint();

    Interpreter withMemory(int... memory);
}

А использую я его как-то так (это тесты, которые мне помогли в разработке)

public class BrainFuckInterpreterTest {

    private static final String SYMBOL_Q = "+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++";

    protected Interpreter getInterpreter() {
        return new BrainFuckInterpreter();
    }

    @Test
    public void shouldPrintHelloWorld() {
        assertEquals("Hello World!\n",
                getInterpreter().compile(
                        "++++++++++[>+++++++>++++++++++>+++>+<<<<-]>" +
                                "++.>+.+++++++..+++.>++.<<++++++++++" +
                                "+++++.>.+++.------.--------.>+.>.").run().getOutput());
    }

    @Test
    public void shouldPrintHelloWorld2() {
        assertEquals("Hello World!",
                getInterpreter().compile(
                    ">+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.>>>++++++++[<++++>-]" +
                    "<.>>>++++++++++[<+++++++++>-]<---.<<<<.+++.------.--------.>>+.").run().getOutput());
    }

    @Test
    public void shouldOut() {
        assertEquals("Q",
                getInterpreter().compile(
                    SYMBOL_Q + ".").run().getOutput());
    }

    @Test
    public void shouldIncrease() {
        assertEquals("P",
                getInterpreter().compile(
                    SYMBOL_Q + "-.").run().getOutput());
    }

    @Test
    public void shouldIncreaseTwice() {
        assertEquals("O",
                getInterpreter().compile(
                        SYMBOL_Q + "--.").run().getOutput());
    }

    @Test
    public void shouldNextPreviousVar() {
        assertEquals("QP",
                getInterpreter().compile(
                        SYMBOL_Q + "->" + SYMBOL_Q + "><.<.").run().getOutput());
    }

    @Test
    public void shouldPrintFirst() {
        assertEquals("\u0000",
                getInterpreter().compile(
                        ".").run().getOutput());
    }

    @Test
    public void shouldIncreaseFromCurrentPosition() {
        assertEquals("QS",
                getInterpreter().compile(
                        SYMBOL_Q + "<<<<" + SYMBOL_Q + "++>>>>.<<<<.").run().getOutput());
    }

    @Test
    public void shouldLoop() {
        assertEquals("QQ",
                getInterpreter().compile(
                        SYMBOL_Q + ".[>+<-]>.").run().getOutput());
    }

    @Test
         public void shouldInput() {
        assertEquals("R",
                getInterpreter().compile(
                        ",+.", "Q").run().getOutput());
    }

    @Test
    public void shouldInputFromEmpty() {
        assertEquals("\u0000Q",
                getInterpreter().compile(
                        ",>,.<.", "Q").run().getOutput());
    }

    @Test
    public void shouldPrintMemory() {
        assertEquals("0 1 2 3 >4 ",
                getInterpreter().compile(
                        ">+>++>+++>++++").run().printMemory());
    }

    @Test
    public void shouldBreakpointAt() {
        assertEquals("0 1 2 >1 ",
                getInterpreter().compile(
                        ">+>++>+@++>++++").useBreakpoint().run().printMemory());
    }

    @Test
    public void shouldMoveRight() {
        assertEquals("\u0003",
                getInterpreter().compile(
                        "+++" + BrainFuckUtils.MOVE_RIGHT + ">.").run().getOutput());
    }

    @Test
    public void shouldCopyValue() {
        assertEquals("\u0003\u0003",
                getInterpreter().compile(
                        "+++" + BrainFuckUtils.COPY_RIGHT + ".>.").run().getOutput());

    }

    @Test
    public void shouldCopyInputToOutput() {
        assertEquals("sdgsjmfgl",
                getInterpreter().compile(
                        BrainFuckUtils.READ_ALL_INPUT +
                        BrainFuckUtils.GOTO_TO_MEMORY_START +
                        BrainFuckUtils.WRITE_ALL_OUTPUT, "sdgsjmfgl").run().getOutput());

    }

    @Test
    public void shouldWithMemory() {
        assertEquals(">14 ", getInterpreter()
                .withMemory(14).printMemory());
    }

    @Test
    public void shouldMultiple() {
        assertEquals(
               "[>2 0 3 , " +
                "2 0 >3 , " +
                "2 0 >3 3 0 , " +
                ">2 0 3 3 0 , " +
                "2 0 >3 3 0 , " +
                "2 3 >0 3 0 , " +
                "2 3 0 >3 0 , " +
                "2 3 3 >0 0 , " +
                "2 3 >3 0 0 , " +
                "2 3 >3 3 0 , " +
                ">1 3 3 3 0 , " +
                "1 3 >3 3 0 , " +
                "1 6 >0 3 0 , " +
                "1 6 0 >3 0 , " +
                "1 6 3 >0 0 , " +
                "1 6 >3 0 0 , " +
                "1 6 >3 3 0 , " +
                ">0 6 3 3 0 , " +
                "0 >6 3 3 0 ]"
        , getInterpreter()
        .withMemory(2, 0, 3)
        .useBreakpoint()
        .compile("#>>#" + COPY_RIGHT + "#<<#[>># [<+>-]# ># " +
                "[<+>-]# <# [>+>+<<-]>>[<<+>>-]<<# <<-#]>#")
        .run().getTrace().toString());
    }

    @Test
    public void shouldNotIgnoreNextCommandAfterCycle() {
        assertEquals("<0 0 1", getInterpreter()
                .withMemory(0, 0, 1)
                .compile("<[-]>")
                .run().printMemory());
    }
}

Что касается реализации, то ее можно найти тут.

В коде я специально оставил класс BrainFuckInterpreterNOOOP, который можно, по моему, использовать для проверки того как трейни разобрался в ООП - попросив его зарефакторить этот класс со множеством ответственностей. Взглянуть только на его список полей

public class BrainFuckInterpreterNOOOP implements Interpreter {
    public List<Integer> memory;
    public int index;
    private String program;
    private String input;
    private String output;
    private boolean useBreakpoint;
    private List<String> trace;

Но не интерпретатор был целью, а кодинг на самом языке. А потому я написал небольшую подборку простеньких алгоритмов, которые можно повторно использовать.

public class BrainFuckUtils {
    public static final String MOVE_RIGHT = "[>+<-]";
    public static final String MOVE_LEFT = "[<+>-]";
    public static final String COPY_RIGHT = "[>+>+<<-]>>[<<+>>-]<<";
    public static final String COPY_LEFT = "[<+<+>>-]<<[>>+<<-]>>";
    public static final String GOTO_TO_MEMORY_START = "<[<]>";
    public static final String READ_ALL_INPUT = ">,[>,]";
    public static final String WRITE_ALL_OUTPUT = "[.>]";
    public static final String CLEAN = "[-]";
    public static final String MULTIPLE =
            COPY_LEFT + ">>" + COPY_RIGHT + "<<[>>" + MOVE_LEFT + ">" +
            MOVE_LEFT + "<" +COPY_RIGHT + "<<-]>>" + ">" + CLEAN +
                    "<<<<" + MOVE_RIGHT + ">>";

Алгоритм перемножения очень неоптимальный, так как фактически суммирует от 0 до результата, при этом бегая по памяти влево вправо, но все же работает.