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