Разрабатываем интерпретатор brainfuck на Arduino

Шла последняя неделя Августа, я неожиданно подумал. Пора бы сделать что, нибудь полезное для этого мира, так появился он - порт языка Brainfuck на ардуино. Каждый кто достаточно долгое время увлекается программированием слышал про такой миниатюрный язык программирования Brainfuck, который не зря получил такое название. Ну а если вы не знаете то вот вам краткий экскурс:

Brainfuck - экзотический тьюринг-полный язык программирования, содержащий в себе всего 8 операторов. У программы на brainfuck есть память , с которой она (программа) может взаимодействовать. Память представляет из себя массив чисел. Программа взаимодействует с ячейкой на которой в данный момент стоит курсор. 

Думаю что суть языка понятная и можно переходить к разработке.

Разработка

Для начала создадим функцию в которую мы будем передавать код и которая будет его выполнять.

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: жмак

Теги:

• Arduino