Шла последняя неделя Августа, я неожиданно подумал. Пора бы сделать что, нибудь полезное для этого мира, так появился он — порт языка Brainfuck на ардуино. Каждый кто достаточно долгое время увлекается программированием слышал про такой миниатюрный язык программирования Brainfuck, который не зря получил такое название. Ну а если вы не знаете то вот вам краткий экскурс:
Brainfuck — экзотический тьюринг-полный язык программирования, содержащий в себе всего 8 операторов. У программы на brainfuck есть память , с которой она (программа) может взаимодействовать. Память представляет из себя массив чисел. Программа взаимодействует с ячейкой на которой в данный момент стоит курсор.
Оператор
Значение
>
Сдвинуть курсор вправо
<
Сдвинуть курсор
+
увеличить значение в ячейке на единицу
—
уменьшить значение в ячейке на единицу
[
начало цикла, команды внутри цикла повторяются до тех пор пока значение в ячейке не равно нулю
]
конец цикла
.
вывести данные из ячейки на экран в виде ASCII символа
,
получить один символ от пользователя и преобразовать его в число по таблиц ASCII
Думаю что суть языка понятная и можно переходить к разработке.
Разработка
Для начала создадим функцию в которую мы будем передавать код и которая будет его выполнять.
void BrainFuck(const char code[]){}
Как мы видим на вход функция принимает константный массив символов — это и есть код программы на BrainFuck.
Теперь внутри функции создадим несколько переменных необходимых для нашего интерпретатора.
int codeCursor = 0;
byte memory[255] = {0};
byte memCursor;
Первая переменная — это указатель на текущий символ в коде который мы выполняем, второе — это память доступная нашей программе (в нашем случае это массив байт), ну и последнее это указатель (курсор) на область памяти в которой сейчас мы находимся.
Создадим цикл в котором мы будем выполнять программу.
while (code[codeCursor] != 0){
codeCursor++;
}
Как мы видим цикл у нас идет до тех пор пока ячейка в коде (на которую указывает codeCursor) не станет равной нулю. Что за магия здесь происходит? А дело все в том, что любая строка (массив символов) в ASCII заканчивается нулевым байтом т.е нулем. Это необходимо что бы мы понимали когда закачивается строка и не лезли в ту область памяти которая не относится к строке.
В теле цикла мы увеличиваем codeCursor каждый раз на единицу. Таким образом мы пройдемся по всем операторам в нашей строке. Теперь необходимо научить нашу программу как, то реагировать на эти операторы.
while (code[codeCursor] != 0){
switch(code[codeCursor]){
case ‘>’:
memCursor++;
break;
}
codeCursor++;
}
Для обработки операторов мы будем использовать конструкцию switch — case . Данная конструкция позволяет нам избавился от кучи Ifов. В начале мы указываем переменную с которой мы будем сравнивать в нашем случае это текущая ячейка в коде (code[codeCursor]) далее внутри тела swich мы прописываем сами сравнения. Сравнения выглядят следующим образом
case константа_с_которой_мы_сравниваем :
//код который выполняется в случае если переменная и константа равны
break
Разобравшись с тем как это работает, думаю не составит труда понять данный код
while (code[codeCursor] != 0){
switch(code[codeCursor]){
case ‘>’:
memCursor++;
break;
case ‘<‘:
memCursor—;
break;
case ‘+’:
memory[memCursor]++;
break;
case ‘-‘:
memory[memCursor]—;
break;
codeCursor++;
}
}
Думаю с первыми 4мя операторами все понятно. Перейдем к более сложным вещам, а именно ввод и вывод в нашем языке.
Он будет выглядеть следующим образом.
case ‘.’:
Serial.print(char(memory[memCursor]));
break;
case ‘,’:
while(true){
if(Serial.available() >0){
memory[memCursor] = Serial.read();
break;
}
}
break;
Кстати, поскольку мы используем Serial, незабываем в начале функции добавить
Serial.begin(9600);
Думаю что с выводом данных все понятно, мы просто берем число из ячейки, трансформируем его в символ и выводим на монитор. То с вводом все немного сложнее. Здесь мы запускаем бесконечный цикл и внутри с помощью команды Serial.available() проверяем пришли ли нам данные от пользователя (возвращает длину данных в serial буфере, если их нет то длина равна 0). Если в буфере появились данные мы записываем первый байт в текущую ячейку (Serial.read() возвращает первый байт из буфера) и выходим из цикла.
Вот мы уже почти доделали наш интерпретатор языка brainfuck осталось самое сложное, но и самое интересное, именно циклы.
Циклы мы реализуем с помощью стека поэтому добавим в начале нашей функции следующие переменные
int stack[255] = {0};
byte stackCursor = 0;
Думаю логику циклов лучше разобрать сразу на примере кода так, что приступим.
case ‘[‘:
if(memory[memCursor]){
stackCursor++;
stack[stackCursor] = codeCursor;
}
else{
while(code[codeCursor] != ‘]’){
codeCursor++;
}
}
break;
Разберем код обработки начала цикла. Если вы вдруг забыли, циклы исполняют команды внутри себя если значение в текущей ячейке не ноль. Так что вначале мы проверяем значение в текущей ячейке. Если оно не ноль, то сдвигаем указатель стека на одну клетку и записываем в шапку стека индекс текущей позиции в коде (на нее мы будем возвращаться когда дойдем до конца цикла). Кстати, если вы не знаете что такое стек, советую вам почитать. Теперь обработаем обратную ситуацию, если значение в ячейке — ноль, то просто пропускаем все операторы пока не дойдем до конца цикла.
Разберем код обработки конца цикла.
case ‘]’:
if(memory[memCursor])
codeCursor = stack[stackCursor];
else
stackCursor—;
break;
Тут код намного проще по сравнению с предыдущим. А именно, если значение в ячейке не ноль, то присваиваем текущую позицию в коде шапке объявления цикла, иначе просто убираем цикл из стека (передвигаем курсор на ячейку вниз).
Вот и весь код, а вы ожидали чего, то сложного ?)
void BrainFuck(const char code[]){
int codeCursor = 0;
byte memory[255] = {0};
byte memCursor;
int stack[255] = {0};
byte stackCursor = 0;
Serial.begin(9600);
while (code[codeCursor] != 0){
switch(code[codeCursor]){
case ‘>’:
memCursor++;
break;
case ‘<‘:
memCursor—;
break;
case ‘+’:
memory[memCursor]++;
break;
case ‘-‘:
memory[memCursor]—;
break;
case ‘.’:
Serial.print(char(memory[memCursor]));
break;
case ‘,’:
while(true){
if(Serial.available() >0){
memory[memCursor] = Serial.read();
break;
}
}
break;
case ‘[‘:
if(memory[memCursor]){
stackCursor++;
stack[stackCursor] = codeCursor;
}
else{
while(code[codeCursor] != ‘]’){
codeCursor++;
}
}
break;
case ‘]’:
if(memory[memCursor])
codeCursor = stack[stackCursor];
else
stackCursor—;
break;
}
codeCursor++;
}
}
void setup() {
}
void loop() {
}
Ну и напоследок Hello World
Hello World на Brainfuck будет выглядеть следующим образом
++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.——.———.>+.>.
Для того что бы наш код заработал, просто добавим в функцию setup следующую строчку.
BrainFuck(«++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.——.———.>+.>.»);
Таким образом мы исполним код и получим следующе сообщение в Serial-мониторе.
А зачем?
Ну во первых это очень интересный опыт который можно приобрести при разработке подобных проектов, а во вторых у меня есть проект программируемого калькулятора на ардуино и Brainfuck вполне подходит под эти задачи. Жду ваших комментариев по данному проекту
Чуть не забыл, исходный код:
Репозиторий проекта: тык
Онлайн интерпретатор Brainfuck: жмак