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() на сформированный код.
<br /> 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
