Интерпретатор Brainfuck на BAT
Простота языка Brainfuck порождает множество реализаций его исполнения. На хабре уже были интерпретаторы и компиляторы на различных языках программирования, даже на Bash. Мне показалось, что несправедливо обойти еще один командный процессор. А именно командные файлы семейства WindowsNT, они же батники. При написании данного интерпретатора была поставлена цель реализовать всё только на встроенном «языке» консоли.
Спецификация диалекта Brainfuck
- Из-за того, что символы "<" и ">" используются для перенаправления ввода/вывода использовать их в качестве команд языка brainfuck приведет к неоправданному усложнению кода. Поэтому замененим их на схожие по написанию "(" и ")".
- Ограничены возможности по выводу текста и вводу данных с клавиатуры.
- Память представляет кольцевой буфер.
- Вывод ограничен первыми 127 символами кодовой страницы с исключением непечатных символов и некоторых символов, которые вызывали ошибку при работе батника. Последние были заменены на символ ".". Пробел заменен на знак "_".
- «Ключевые слова» языка:
- «)» – перейти на следующую ячейку памяти
- «(» – перейти на предыдущую ячейку памяти
- «+» – увеличить значение ячейки на единицу
- «-» – уменьшить значение ячейки на единицу
- «,» – прочесть значение в ячейку со стандартного устройства ввода. В данный момент не реализовано
- «.» – напечатать значение ячейки на стандартном устройстве вывода
- «[» – начать цикл. если значение текущей ячейки не равно 0 и перейти к следующей команде. Иначе перейти к ] учитывая вложенность
- «]» – конец цикла. Продолжить цикл, если значение текущей ячейки не равно 0
Описание интерпретатора
Полный текст интерпретатора находится здесь: http://pastebin.com/KZXUuz48
- mp (memory pointer) — указатель на текущую ячейку памяти
- cp (command pointer) — указатель текущей выполняемой команды
Все вышеописанные действия выполняются всего двумя строчками батника
Желающие могут дописать удаление из программы всех не словарных символов.
Далее начинается основной цикл работы интерпретатора. Здесь все достаточно прозрачно. Происходит чтение кода операции по указателю cp. Далее классическим if… else попадаем на соответствующую подпрограмму. Если символ не из «языкового словаря», то он будет игнорирован. Далее увеличиваем счетчик cp и делаем переход на начало цикла.
Описание некоторых интересных решений
Для эмуляции функции chr() необходимо прочитать символ из переменной char из позиции, соответствующей коду этого символа.
Напрямую символ вырезать не удастся. Т.е. конструкция либо выдаст ошибку. Проблема в том, что функции по обработке строк требуют указания в виде числа, но никак не в виде переменной. Например: set t=%char:
5,1% вырежет из строки 1 символ начиная с 5-й позиции. Но никаким способом нельзя напрямую передать содержимое переменой (в нашем случае — code) в команду set. Обойти это можно воспользовавшись связыванием времени исполнения. Которое работает только в командах if или for Поэтому приходится вызывать копию командного процессора с командой echo %%char:
!code!,1%% (где уже содержимое code передается в виде числа) и перехватывать вывод конструкцией «for /f». Есть еще конструкция , но она в данном случае отрабатывает неправильно. Т.к. операций вывода не так уж и много, было решено пожертвовать скоростью выполнения ради скорости разработки и отладки программы.
В данной функции (:echochr) используется еще одно интересное решение: вывод текста без перевода строки.
Команда echo при выводе всегда добавляет перевод строки. В данном случае это не подходит. К счастью, есть возможность обойти это ограничение:
То есть, мы используем ввод с устройства nul в команде set /p для эмуляции команды echo.
Данное решение может предоставить еще несколько интересных фишек которые можно увидеть на форуме, ссылка на который приведена ниже.
Заключение
Предупреждение:
Работает все очень медленно независимо от производительности компьютера. Microsoft позаботилась, чтобы владельцы медленных компьютеров не завидовали владельцам быстрых.
Код тестировался на Windows XP, Windows Vista, Windows 7.
Ссылки
- Пост автора реализации массивов: http://habrahabr.ru/blogs/crazydev/75951/
- Форум где было подсмотрено несколько идей: http://forum.script-coding.com/viewforum.php?id=12
- Здесь разъяснены особенности примененных в батнике решений: http://rsdn.ru/article/winshell/NTCommandProcessor.xml
Об оптимизации скорости работы bat-файлов
На отдельную статью, по моему мнению не хватает материала, поэтому размещу здесь. Ибо непосредственно касается увеличению скорости работы представленного здесь интерпретатора. В ходе работы над интерпретатором было замечено постоянное порождение дочерних процессов командного процессора cmd. Да и общая скорость работы небольшая. Все дело в вызове функции call. Читаем хелп: Команда CALL допускает использование меток в качестве адресата вызова. Применяется следующий синтаксис:
CALL :метка аргументы
При вызове создается новый контекст текущего пакетного файла с заданными аргументами, и управление передается на инструкцию, расположенную сразу после метки. Для выхода из такого пакетного файла необходимо дважды достичь его конца. Первый выход возвращает управление на инструкцию, расположенную сразу после строки CALL, а второй выход завершает выполнение пакетного файла. Команда GOTO /? выводит описание расширения GOTO :EOF, позволяющее выполнить быстрый возврат из пакетного файла. Поэтому стоит помнить что на каждый вызов подпрограммы через call будет запускаться cmd, на что требуется некоторое время. Простой тест который делает одно и тоже. Но в первом случае напрямую, во втором через вызов подрограммы.