Шла последняя неделя Августа, я неожиданно подумал. Пора бы сделать что, нибудь полезное для этого мира, так появился он — порт языка 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: жмак