Интерпретатор Brainfuck на BAT

Простота языка Brainfuck порождает множество реализаций его исполнения. На хабре уже были интерпретаторы и компиляторы на различных языках программирования, даже на Bash. Мне показалось, что несправедливо обойти еще один командный процессор. А именно командные файлы семейства WindowsNT, они же батники. При написании данного интерпретатора была поставлена цель реализовать всё только на встроенном «языке» консоли.

Спецификация диалекта Brainfuck

Командный процессор Windows имеет множество ограничений. Вот только некоторые из них:

1. Из-за того, что символы "<" и ">" используются для перенаправления ввода/вывода использовать их в качестве команд языка brainfuck приведет к неоправданному усложнению кода. Поэтому замененим их на схожие по написанию "(" и ")".
2. Ограничены возможности по выводу текста и вводу данных с клавиатуры.

В конечном итоге получаем спецификацию на язык:

1. Память представляет кольцевой буфер.
2. Вывод ограничен первыми 127 символами кодовой страницы с исключением непечатных символов и некоторых символов, которые вызывали ошибку при работе батника. Последние были заменены на символ ".". Пробел заменен на знак "_".
3. «Ключевые слова» языка:
   • «)» – перейти на следующую ячейку памяти
   • «(» – перейти на предыдущую ячейку памяти
   • «+» – увеличить значение ячейки на единицу
   • «-» – уменьшить значение ячейки на единицу
   • «,» – прочесть значение в ячейку со стандартного устройства ввода. В данный момент не реализовано
   • «.» – напечатать значение ячейки на стандартном устройстве вывода
   • «[» – начать цикл. если значение текущей ячейки не равно 0 и перейти к следующей команде. Иначе перейти к ] учитывая вложенность
   • «]» – конец цикла. Продолжить цикл, если значение текущей ячейки не равно 0

Хочется выразить огромное спасибо автору реализации массивов на батниках. Без его кода написание интерпретатора Brainfuck было бы затрудненно.
А также хабраюзеру Roy за подсказки в оптимизации кода.

Описание интерпретатора

Полный текст интерпретатора находится здесь: http://pastebin.com/KZXUuz48

В программе используются следующие глобальные переменные:

• mp (memory pointer) — указатель на текущую ячейку памяти
• cp (command pointer) — указатель текущей выполняемой команды

После инициализации переменных и заполнения «памяти» нулями читаем файл с программой. В процессе чтения происходит склейка многострочной программы в одну строку. В последствии, во время выполнения Brainfuck программы все не «словарные» символы будут проигнорированы. Все символы после * до конца строки будут проигнорированы. Это даст возможность писать «красиво» оформленные программы. Пример программы:

+++++++++[ * while mem[0]<=9 {
  )+++++   * mem[1]+=5
(-]        * }
).         * print chr(mem[1])

Все вышеописанные действия выполняются всего двумя строчками батника

set bf_prog=
FOR /F "eol=c delims=*" %%I IN (%work_file%) DO SET bf_prog=!bf_prog!%%I

Желающие могут дописать удаление из программы всех не словарных символов.

Далее начинается основной цикл работы интерпретатора. Здесь все достаточно прозрачно.
Происходит чтение кода операции по указателю cp. Далее классическим if… else попадаем на соответствующую подпрограмму. Если символ не из «языкового словаря», то он будет игнорирован. Далее увеличиваем счетчик cp и делаем переход на начало цикла.

:work
set cop=!bf_prog:~%cp%,1!

if "%cop%" == "+" (
  call :array get mem %mp% tmp
  set /a tmp += 1
  if "!tmp!" == "256" set tmp=0
  call :array set mem %mp% !tmp!
) else if "%cop%" == "-" (
  call :array get mem %mp% tmp
  set /a tmp -= 1
  if !tmp! LSS 0 set tmp=255
  call :array set mem %mp% !tmp!
) else if "%cop%" == ")" (
  set /a mp +=1
  if !mp! == %maxmem% set mp=0
) else if "%cop%" == "(" (
  set /a mp -=1
  if !mp! == -1 set /a mp=%maxmem% - 1
) else if "%cop%" == "," (
  call :comma
) else if "%cop%" == "." (
  call :array get mem %mp% tmp
  call :Echochr !tmp!
) else if "%cop%" == "[" (
  call :array get mem %mp% tmp
  if "!tmp!" == "0" (
    call :skip1
  )
) else if "%cop%" == "]" (
  call :array get mem %mp% tmp
  if "!tmp!" NEQ "0" (
    call :skip2
  )
)

set /a cp += 1
if %cp% == %bf_len% goto :exit
goto :work

Описание некоторых интересных решений

Для эмуляции функции chr() необходимо прочитать символ из переменной char из позиции, соответствующей коду этого символа.

:echochr
rem Набор выводимых символов. Символы, вывод которых вызывал ошибки исполнения cmd заменены символом "."
set char=".#$...'()*+,-./0123456789.....?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]._`abcdefghijklmnopqrstuvwxyz{.}~_"

if %1==10 echo.
if %1==13 echo.
if %1==32 <nul set /p strTemp="_"
if %1 GTR 32 (
  set /a code=%1 - 32
  for /f %%t in ('cmd /c "echo %%char:~!code!,1%%"') do <nul set /p strTemp="%%t"
)
exit /b 0

Напрямую символ вырезать не удастся. Т.е. конструкция

set t=%char:~%code%,1%

либо

set t=%char:~!code!,1%

выдаст ошибку. Проблема в том, что функции по обработке строк требуют указания в виде числа, но никак не в виде переменной. Например: set t=%char:~5,1% вырежет из строки 1 символ начиная с 5-й позиции. Но никаким способом нельзя напрямую передать содержимое переменой (в нашем случае — code) в команду set. Обойти это можно воспользовавшись связыванием времени исполнения. Которое работает только в командах if или for Поэтому приходится вызывать копию командного процессора с командой echo %%char:~!code!,1%% (где уже содержимое code передается в виде числа) и перехватывать вывод конструкцией «for /f».
Есть еще конструкция

set t=!char:~%code%,1!

, но она в данном случае отрабатывает неправильно. Т.к. операций вывода не так уж и много, было решено пожертвовать скоростью выполнения ради скорости разработки и отладки программы.

В данной функции (:echochr) используется еще одно интересное решение: вывод текста без перевода строки.

Команда echo при выводе всегда добавляет перевод строки. В данном случае это не подходит. К счастью, есть возможность обойти это ограничение:

<nul set /p strTemp="%~1"

То есть, мы используем ввод с устройства 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, на что требуется некоторое время.
Простой тест который делает одно и тоже. Но в первом случае напрямую, во втором через вызов подрограммы.

@echo off
setlocal ENABLEDELAYEDEXPANSION ENABLEEXTENSIONS

echo %time% - start test1
set a=0
for /l %%i in (1,1,1000) do set /a a=!a!+1
echo %a%
echo %time% - end test1
echo --------------
echo %time% - start test2
set a=0
for /l %%i in (1,1,1000) do call :m1
echo %a%
echo %time% - end test2
goto :eof

:m1
set /a a=%a%+1
exit /b /0

Как говорится, комментарии излишни.

Поэтому я отказался от использования реализации массивов через подпрограммы и переписал код интерпретатора. В результате скорость работы увеличилась больше, чем в 15 раз!
Собственно, сам оптимизированный интерпретатор http://pastebin.com/MDbVJXsE