brainfuck: java-компилятор

branfuck – это такой простейший язык программирования который реализует некую “полную машину Тьюринга”, подробнее в википедии, там же и подробное описание команд. Кому лень – пример, выводящий традиционное Hello world:

 ++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++
 .>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.
 ------.--------.>+.>.

Для тех, кто видит в первый раз это кажется диким. Ну разе lisp не страшнее?)

Зачем??!

Это – язык-головоломка. Благодаря такому маленькому набору команд компилятор/интерпретатор становится очень простым, а разработка на нём – поистине напряг для мозга, особенно для программистов которые привыкли к роскоши :)

И всё-таки зачем?

В рамках #SumIT был конкурс javathon от Sun Oracle на написание приложения используя последние java-технологии. Напомню, что за 2 недели назад вышла Java 7. Один из вариантов был написать компилятор какого-либо языка в джава-байткод за 23 часа. Подробнее о конкурсе и результатах

Вместе с приятелем, Максимом Колчиным мы взялись за написания такого компилятора, который попутно получился ещё и оптимизирующий. Соответственно цепочка логики: брейнфак компилятор на джаве генерит байткод программы, которая потом запускается и выдаёт то, что должна делать программа на брей,нфаке в исходном виде. Запутал :) Картинка иллюстрирует

Попутно добавили ещё одну команду, которая является расширением языка. “~”, “тильда” – создаёт задержку на 300мсек. Вводя тильду у нас удалось достичь эмуляции “набора текста” из за-за задержки при выводе на экран.

Макс предложил название jFuck – клёвое! :)

Поскольку писать на брейфаке большой текст геморой одно удовольствие пришлось на скорую руку написать конвертор(jfuck-gen) любого текста в брейфак код, рандомно добавляя тильды, т.е. задержки в тексте.

jFuck

Для разработки использовали maven, чтоб его… Тормознутая хрень, да. Точно не для нетбука – это был первый опыт работы с ним.

Разумеется, мы использовали библиотеки для генерации байткода – Apache BCEL (org.apache.bcel). Писать руками достаточно сложно, тем более в такое ограниченное время (фактически у нас вышло 4+10=14 часов, не спать было бы глупо – больше протупили бы)

Так же нам очень пригодилась публично выложенный код самого интерпретатора брейнфака, очень грамотно написанный (например есть “минусовая” память). Автор vampirus (vampirus.ru/code/brainfuck)

Как работает компилятор?

Мы имеем некую заготовку, класс Tmpl, который умеет выполнять инструкции брейнфака, вызывая соотвествующий метод. Например “+” должен вызвать метод incValue(). Дальше в этот класс нужно внедрить сами инструкции, т.е. код который будет вызывать методы у заготовки.

Кто внимательно читает сразу увидит что есть большое количество повторений одинаковых инструкций, и вызывать 200 раз метод incValue() – глупо. Есть где опимизировать :) А ещё если посмотреть на брейнфак можно заметить наличие циклов “[]“, которые достаточно сложно реализовать (нужно уметь корректно отмечать добавлять закладки и проверять условия, в случае чего нужно вернуться к этим закладкам. В контексте генерации байткода выглядит устрашающе :)) Поэтому мы добавили оптимизатор – во время компиляции мы эмулируем работу брейнфака, соответственно раскрывая циклы. В этом же месте и считаем количество повторений инструкций.

Например

Кусок кода, который добавляет в instructionList(читать как набор инструкций метода) вызов метода с одним аргументом

il.append(InstructionConstants.THIS);
il.append(new PUSH(factory.getConstantPool(), count));
il.append(factory.createInvoke("Tmpl", getMethod(last),
           Type.VOID, new Type[]{Type.INT},
           Constants.INVOKEVIRTUAL));

Сам Tmpl класс:

public class Tmpl {
    private int pointerzero = 0;
    private char[] memory;
    private int pointer = 0;
    private String in = "";
    private int pin;
   
    public Tmpl() {
        memory = new char[1];
    }

    private void nextCeil(int amount) {
        pointer += amount;
    }

    private void prevCeil(int amount) {
        pointer -= amount;
    }

    private void incValue(int value) {
        char cur = getValue(pointer);
        setValue(pointer, (char) ((cur + value) % 256));
    }

    private void decValue(int value) {
        char cur = getValue(pointer);
        setValue(pointer, (char) ((cur -= value) < 0 ? 255 - cur : cur % 256));
    }


    private void print(int amount) {
        char cur = getValue(pointer);
        while (--amount >= 0) System.out.print(cur);
        System.out.flush();
    }
   
    private void read(int amount) {
        setValue(pointer, in.charAt(pin+amount));
        pin+=amount;
    }
   
    private void sleep(int amount) {
        try {
            Thread.sleep(300 * amount);
        } catch (InterruptedException ex) {}
    }
   
    public char getValue(int pointer) {
        int newpointer = pointerzero + pointer;
        if (memory.length > newpointer && newpointer >= 0) {
            return memory[newpointer];
        } else {
            char[] tmp = new char[(newpointer > 0) ? newpointer + 1 : memory.length + Math.abs(newpointer)];
            for (int i = 0; i < tmp.length; i++) {
                tmp[i] = 0;
            }
            for (int i = 0, k = (newpointer > 0 ? 0 : Math.abs(newpointer)); i < memory.length; i++) {
                tmp[k++] = memory[i];
            }
            memory = tmp;
            if (newpointer < 0) {
                pointerzero += Math.abs(newpointer);
            }
            return 0;
        }
    }
   
    public void setValue(int pointer, char value) {
        int newpointer = pointerzero + pointer;
        if (memory.length > newpointer && newpointer >= 0) {
            memory[newpointer] = value;
        } else {
            char[] tmp = new char[(newpointer > 0) ? newpointer + 1 : memory.length + Math.abs(newpointer)];
            for (int i = 0; i < tmp.length; i++) {
                tmp[i] = 0;
            }
            for (int i = 0, k = (newpointer > 0 ? 0 : Math.abs(newpointer)); i < memory.length; i++) {
                tmp[k++] = memory[i];
            }
            memory = tmp;
            if (newpointer > 0) {
                memory[newpointer] = value;
            } else {
                memory[0] = value;
                pointerzero += Math.abs(newpointer);
            }
        }
    }
   
   
    public static void main(String[] args) {
        String code =  "";
        Tmpl tmpl = new Tmpl();
        tmpl.run();
        System.out.println();
    }
   
    private void run() {
        // stub
    }
   
    public void error(int somevar) {
        System.err.println("unknown command");
    }

}

Фактически этот класс – изменённый BFInt смерженный с Memory, взятый у вышеупомянутого автора vampirus. Как видно все вызываемые методы имеют один единственный аргумент – целое число повторений.

В Tmpl есть пустой метод run() – именно он заполняется инструкциями на этапе компиляции.

В самом же компиляторе jFuck основной метод, который загружает шаблонный класс Tmpl, и заменяет пустую заглушку (stub) run() на сформированный код.

    private void compile(char[] code) {
        ClassGen cg = null;
        try {
            cg = new ClassGen(Repository.lookupClass("Tmpl"));
        } catch (ClassNotFoundException ex) {
            Logger.getLogger(Jfuck.class.getName()).log(Level.SEVERE, null, ex);
        }
        cg.replaceMethod(lookupMethod(cg, "run"), generateRun(cg, code));
        try {
            cg.getJavaClass().dump("Tmpl.class");
        } catch (IOException ex) {
            Logger.getLogger(Jfuck.class.getName()).log(Level.SEVERE, null, ex);
        }
    }

Весь компилятор

Получился не большой:

package ru.ifmo.jfuck;

public class Jfuck {
    /**
     * Program start point
     * @param args
     */

    public static void main(String[] args) throws IOException{
        if (args.length > 0){
            BufferedReader input = null;
            try {
                StringBuilder sb = new StringBuilder();
                try {
                    input = new BufferedReader(new FileReader(new File(args[0])));
                } catch (FileNotFoundException ex) {
                    ex.printStackTrace();
                }
                String line = null;
                while (( line = input.readLine()) != null){
                  sb.append(line);
                  sb.append(System.getProperty("line.separator"));
                }
                Jfuck jfuck = new Jfuck();
                jfuck.compile(jfuck.interpret(sb.toString().toCharArray()));
            } catch (IOException ex) {
                ex.printStackTrace();
            } finally{
                input.close();
            }
        }else{
            System.out.println("Second argument should be path to program on Jfuck language.");
        }
    }

    private Method lookupMethod(ClassGen tmpl, String methodName) {
        for (Method m : tmpl.getMethods()) {
            if (m.getName().equals(methodName)) {
                return m;
            }
        }
        return null;
    }

    private Method generateRun(ClassGen jc, char[] cmds) {
        ConstantPoolGen cp = jc.getConstantPool();
        InstructionList il = new InstructionList();
        MethodGen m = new MethodGen(Constants.ACC_PRIVATE,
                Type.VOID, new Type[]{}, new String[]{}, "run", "Tmpl", il, cp);
        InstructionFactory factory = new InstructionFactory(jc);

        translate(il, factory, cmds);

        il.append(InstructionConstants.RETURN);
        m.setMaxStack(5);
        return m.getMethod();
    }


    /**
     * Find for corresponding method
     * @param ch brainfuck command
     * @return method name in Tmpl instance
     */

    private final String getMethod(char ch) {
        switch (ch) {
            case '>':
                return "nextCeil";
            case '<':
                return "prevCeil";
            case '+':
                return "incValue";
            case '-':
                return "decValue";
            case '.':
                return "print";
            case ',':
                return "read";
            case '~':
                return "sleep";
            default:
                return "error";
        }
    }

    /**
     * Interprets brainfuck
     * @param src source program
     * @return brainfuck w/o loops
     */

    private char[] interpret(char[] src) {
        return new BFInt(src).emulate();
    }

    private void compile(char[] code) {
        ClassGen cg = null;
        try {
            cg = new ClassGen(Repository.lookupClass("Tmpl"));
        } catch (ClassNotFoundException ex) {
            Logger.getLogger(Jfuck.class.getName()).log(Level.SEVERE, null, ex);
        }
        cg.replaceMethod(lookupMethod(cg, "run"), generateRun(cg, code));
        try {
            cg.getJavaClass().dump("Tmpl.class");
        } catch (IOException ex) {
            Logger.getLogger(Jfuck.class.getName()).log(Level.SEVERE, null, ex);
        }
    }

    private void translate(InstructionList il, InstructionFactory factory,
            char[] code) {
        char last = code[0];
        int count = 1;
        for (int i = 1; i < code.length; i++) {
            if (last == code[i]) {
                count++;
            } else {
                //Invoke with arg last
                il.append(InstructionConstants.THIS);
                il.append(new PUSH(factory.getConstantPool(), count));
                il.append(factory.createInvoke("Tmpl", getMethod(last),
                        Type.VOID, new Type[]{Type.INT},
                        Constants.INVOKEVIRTUAL));
                count = 1;
            }
            last = code[i];
        }
    }
}

Ах да, так как Макс и я студенты СПбГУ ИТМО, поэтому назвали соотвественно package: ru.ifmo.jfuck

Скачать jFuck

Все в архиве jFuck.tar.gz(компилятор + генератор)

Вообще достаточно хорошо провели время, весьма интересный формат мероприятия. Узнали то, с чем вряд ли бы когда-нибудь столкнулись. Не часто приходится писать компиляторы в повседневной жизни :D