# Практика. Интерпретатор Brainfuck ## Описание проекта Brainfuck — это [эзотерический](https://ru.wikipedia.org/wiki/%D0%AD%D0%B7%D0%BE%D1%82%D0%B5%D1%80%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D1%8F%D0%B7%D1%8B%D0%BA_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D1%8F) язык программирования, известный своим минимализмом. Это относится не только к синтаксису языка (всего 8 команд!), но и к размеру его интерпретатора. Интерпретатор Brainfuck занимает несколько десятков строк. И сегодня вы их напишете. ### Синтаксис Brainfuck за 5 минут Brainfuck — это [тьюринг-полный](https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%BB%D0%BD%D0%BE%D1%82%D0%B0_%D0%BF%D0%BE_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D1%83) язык. То есть всё, что написано на Python, Java или вашем любимом языке C++, можно переписать на Brainfuck. Цена тому — вынос мозга и бесконечные листинги кода. Brainfuck — эталонный пример [тьюринговской трясины.](https://ru.wikipedia.org/wiki/%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%BE%D0%B2%D1%81%D0%BA%D0%B0%D1%8F_%D1%82%D1%80%D1%8F%D1%81%D0%B8%D0%BD%D0%B0) Его синтаксис настолько примитивен, что программы на нем пишутся в качестве прикола или эксперимента, но не ради практического применения. По сути Brainfuck описывает абстрактную машину, у которой есть 8 команд и память из 30 000 ячеек. Размер каждой ячейки — 1 байт: в нее вмещаются числа от 0 до 255. При запуске программы все ячейки обнуляются. По ним перемещается указатель, изначально установленный на нулевую ячейку. Допустим, массив из 30 000 ячеек называется `mem`, а указатель установлен на его элемент с индексом `i`. Тогда набор команд описывается следующим образом: | Команда Brainfuck | Эквивалент на C++ | Описание | | ----------------- | -------------------------- | ---------------------------------- | | `>` | `++i` | Перейти к следующей ячейке | | `<` | `--i` | Перейти к предыдущей ячейке | | `+` | `++mem[i]` | Инкремент значения в текущей ячейке | | `-` | `--mem[i]` | Декремент значения в текущей ячейке | | `.` | [std::putchar](https://en.cppreference.com/w/cpp/io/c/putchar)`(mem[i])` | Вывести значение текущей ячейки в консоль | | `,` | `mem[i] =` [std::getchar()](https://en.cppreference.com/w/cpp/io/c/getchar) | Прочитать в текущую ячейку значение из консоли | | `[` | `while(mem[i]) {` | Если текущая ячейка равна нулю, сдвинуться вперед по коду программы до символа, следующего за парной `]` с учетом вложенности | | `]` | `}` | Если текущая ячейка не равна нулю, сдвинуться назад по коду программы до парного символа `[` с учетом вложенности | Поздравляем, теперь вы знаете Brainfuck. Закрепим на примерах. **Пример 1.** Напишем программу, которая выводит в консоль символ `B`. В [таблице ASCII-кодов](https://www.ascii-code.com/) ему соответствует число 66. Наивное решение заключается в том, чтобы 66 раз сделать инкремент ячейки с индексом 0, а затем вывести ее в консоль: ``` +++++++++++++++++++++++++++++++++ +++++++++++++++++++++++++++++++++. ``` ``` B ``` Этот код можно улучшить: в нулевую ячейку записать число 11. И пока ее значение не станет равным нулю, в цикле 6 раз делать инкремент ячейки 1 и 1 раз — декремент ячейки 0. Такой код выглядит короче: ``` +++++++++++[>++++++<-]>. ``` ``` B ``` **Пример 2.** Сложение двух чисел выглядит так: ``` +++++>+++[<+>-] ``` В нулевую ячейку записано число 5, а в первую — число 3. Мы хотим сохранить результат сложения в нулевой ячейке. Для этого в цикле, пока первая ячейка не станет нулем, мы делаем инкремент нулевой ячейки и декремент первой. **Пример 3.** Надеюсь, вы уловили принцип. Подкрепим его последним примером с умножением чисел: ``` +++[>+++++<-] ``` В ячейку 0 помещено число 3. Затем в цикле к ячейке 1 прибавляется число 5. Это происходит до тех пор, пока значение ячейки 0 не обнулится. Мы получили умножение 3 на 5. Результат умножения в виде числа 15 сохранился в ячейке 1. ### Реализация интерпретатора Реализуйте класс `BrainfuckInterpreter`. В конструкторе он принимает строку с кодом и исполняет его: ```c++ BrainfuckInterpreter run( " ++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++" ".>+.+++++++..+++.>++.<<+++++++++++++++.>.+++." "------.--------.>+.>." ); ``` ``` Hello World! ``` ### Обработка ошибок Если в коде встретится символ, не являющийся командой, он просто пропускается. Но в двух случаях конструктор должен бросать исключения. | Ошибка | Тип исключения | Начало текста ошибки | | ----------------- | -------------------------- | ---------------------------------- | | Выход индекса ячейки за пределы допустимой памяти | `std::out_of_range` | Memory pointer out of bound | | Несоответствие открывающих и закрывающих скобок | `std::runtime_error` | Brackets [] do not match | Формулировка «Начало текста ошибки» означает, что _по желанию_ вы можете дополнить сообщение полезной информацией. Например, индексом символа, на котором она обнаружена. ### Что может пригодиться В качестве типа для ячейки памяти подойдет `unsigned char`. Тип `char` не годится, так как в зависимости от реализации он может хранить значения в диапазоне от 0 до 255 либо от -128 до 127. А `unsigned char` предназначен именно для беззнаковых целых. Для вывода символа в консоль и для чтения символа из консоли есть функции [std::putchar()](https://en.cppreference.com/w/cpp/io/c/putchar) и [std::getchar()](https://en.cppreference.com/w/cpp/io/c/getchar). Для получения форматированной строки воспользуйтесь [std::format()](https://en.cppreference.com/w/cpp/utility/format/format.html). Отличие этой функции от `std::print()` в том, что вместо вывода форматированного текста в консоль она возвращает его в качестве значения. Это может пригодиться для составления текста исключений. ## Теория **Пропустите** этот раздел, если хотите самостоятельно придумать решение. Интерпретацию Brainfuck лучше всего выполнять в два прохода по строке с кодом. **За первый проход** строится словарь с индексами скобок. Ключи — это индексы открывающих и закрывающих скобок, а значения — индексы их пар. ``` +++[-] ``` Например, для этого кода словарь будет содержать два элемента: | Ключ | Значение | | ---- |--------- | | 3 | 5 | | 5 | 3 | Построение словаря позволяет заранее проверить правильность расстановки скобок и не запускать некорректный код. А при выполнении программы словарь потребуется для быстрого перемещения в начало цикла и на следующую за циклом инструкцию. Для составления словаря нужно завести вспомогательную переменную типа `std::stack` и в цикле пройти по индексам строки с кодом: — Если текущий символ — открывающая скобка `[`, то его индекс помещается в стек. — Если текущий символ — закрывающая скобка `]`, то с вершины стека извлекается элемент. Он и содержит парную открывающую скобку. Если стек пуст, то в коде несоответствие скобок. После цикла стек должен оказаться пустым. Иначе в коде есть несоответствие скобок. **За второй проход** по строке с кодом поштучно выполняются команды Brainfuck. Это тоже цикл по индексам строки. Выполняемое действие зависит от конкретной команды: — Управляющая команда выполняется. — Открывающая скобка: если значение текущей ячейки равно нулю, счетчик цикла перемещается на индекс после соответствующей закрывающей скобки. — Закрывающая скобка: если значение текущей ячейки больше нуля, счетчик цикла перемещается на индекс после парной открывающей скобки. ## Тестирование По кнопке **«Запустить»** компилируется и запускается `main.cpp`. Внутри `main()` вы можете менять строку с кодом на Brainfuck, чтобы отлаживаться. Имейте ввиду, что в online IDE отсутствует возможность консольного ввода. Возле кнопки «Запустить» есть поле для ввода аргументов. В нем вы можете указать путь к файлу с кодом на Brainfuck, который лежит в директории `examples`. Например, `examples/squares.b`. Тогда выполнится он. Как это работает, вы можете посмотреть в коде `main.cpp`. По кнопке **«Отправить на проверку»** выполняются юнит-тесты из файла `tests.cpp`. Запустите их, когда класс `BrainfuckInterpreter` будет готов к тестированию. В `tests.cpp` можно посмотреть ожидаемое поведение класса. Проект будет засчитан как выполненный после успешного прохождения юнит-тестов. Если у вас возникнут проблемы при выполнении практики, воспользуйтесь подсказкой. Она доступна по кнопке со знаком вопроса.