Braintractor

Не быстрый и не маленький, но гибкий интерпретатор для brainfuck. В виде модуля Lua и утилиты командной строки на основе модуля.

• braintractor.lua - модуль

• braintractor - утилита коммандной строки на основе модуля

• Прямая интерпретация

• Трансплиттерация brainfuck кода в lua код
• Оптимизация повторяющихся команд
• Оптимизация прыжков через код в теле циклов
• Оптимизация запуления ячейки [-] и [+]
• Оптимизация поиска ближайшей нулевой ячейки [>] и [<]
• Потококое исполнение кода по мере загрузки кода
• Отладка через чимвол #
• Трассировка исполнения кода
• Может чего ещё…

Зависимости

Любой интерпретатор Lua на выбор apt install lua

• 5.1;
• 5.2;
• 5.3;
• 5.4;
• luajit;

Выбрать интерпретатор можно во время исполнения через ключ -l

Установка и удаление

По умолчанию устанавливается только модуль, если нужно установить утилиту то требуется передать параметр install-cli.

Глобально

#Только модуль
sudo make install
sudo make uninstall

#Модуль и утилита
sudo make install install-cli
sudo make uninstall uninstall-cli

Локально

#Только модуль
make PREFIX=$HOME/.local install
make PREFIX=$HOME/.local uninstall

#Модуль и утилита
make PREFIX=$HOME/.local install install-cli
make PREFIX=$HOME/.local uninstall uninstall-cli

Независимо

#Только модуль
make DESTDIR=$HOME/some_you_dir install
make DESTDIR=$HOME/some_you_dir uninstall

#Модуль и утилита
make DESTDIR=$HOME/some_you_dir install install-cli
make DESTDIR=$HOME/some_you_dir uninstall uninstall-cli

Информацию для установки и удаления можно получить через make help

Использование

Утилита

Описание использования находится в справке

Usage:  braintractor -i [FILE] -o [FILE]
        braintractor -e ',+.+.+.+.+.+.+'
        cat mandelbrot.bf | braintractor

 Execute input brainfuck code with or without
 different optimisations like transplitter to
 lua code and execute him, repeated operations
 optimisation and cycles jump optimisation.
 Cheking brainfuck syntax is correct.
 Handle debug symbol `#` and allow trace all code
 in execution time with trace lua function.
 This brainfuck language interpretor not very faster but flexibly.

Arguments:
   -h --help      This help information
   -              Execute brainfuck source code from stdin
   -i [FILE]      Execute filename with brainfuck source code
   -e [TEXT]      Execute brainfuck source code from string
   -o [FILE]      Output filename for write execution output
                  if output not set out writed to stdout

   -fi [FILE]     Send data to brainfuck programm from file
   -si [TEXT]     Send data to brainfuck programm from string


   -dj            Disable cycles jump optimisation
   -dr            Disable repeated operations optimisation
   -dt            Disable transplitter to lua optimisation
   -dz            Disable zero cell [+] [-] [<] [>] optimisations
   -da            Disable all optimisations

   -ds            Disable stream execution

   -dl            Disable set newline after terminal ouput
   -dd            Disable '#' symbol in brainfuck source code
   -do            Disable (force) any output (tracer worked)

   -sb [NUMBER]   Source buffer size for stream execution
                  minimum=1, maximum=2^31. (Default:100)
                  If posible braintractor execute this
                  chunks size or load more source code

   -tr [TEXT]     Lua function for trace brainfuck execution

   -dn            Disable check newline in input reader.
                  By default enabled checking '\n' if
                  input data ended but no have '\n' force
                  add this EOL LF symbol as last input symbol
                  this useful for varian set input as string
                  like -s 'someinput' -> 'someinput\n' you
                  can set other variant for EOL not '\n'

   -l [TEXT]      Select lua implementation for execute
                  lua5.1, lua5.2, lua5.3, lua5.4, luajit
                  By default used system '#!/usr/bin/env lua'

   Some brainfuck programs expect different behavior for
   end of line. Setting bottom transparent fix input for
   different behavior end of line. LF , CR, CRLF. You can
   enable only one variant. If set more last disable other
   By default enabled -eof_lf if input no have '\n' in line end
   force added '\n' in last input data. Use -dn for disable it

   -eol_lf        Enable check end of line and force set LF == '\n'
                  if input have '\r' or '\r\n' this option
                  change it to single '\n'. (*nix way)

   -eol_cr        Enable check end of line and force set CR == '\r'
                  if input have '\n' or '\r\n' this option
                  change it to single '\r'. (old osx way)

   -eol_crlf      Enable check end of line and force set CRLF == '\r\n'
                  if input have '\n' or '\r' this option change
                  it to two end of line symbols '\r\n'. (windows way)

   Some brainfuck programs expect different behavior for end of file
   some expect write '0' in memory cell, some need save cell value
   and skip write other value in cell and some needed write -1 in cell
   Options bottom can enable one of varians. By default enabled -eol_zero
   You can enable only one varian. If set more last disable other.

    -eof_zero      If no have data to read, write 0 in memory cell m[i]=0

    -eof_eof       If no have data to read, write -1 in memory cell m[i]=-1

    -eof_skip      if no have data save cell value m[i]=m[i] (it like clamp)

    -eof_same      same as -eof_skip, just alias, it's easier to remember :)


   Notice about default execution mode and configuration:

   By default execute source maked in strem mode, brainfuck
   source load in small chunck, chunck optimised and executed
   this makes it possible to execute code as it is received,
   without waiting for it to be fully loaded. Also, this is
   only possible if it is possible to isolate independent parts
   from the flow that are not included in the body of any loop
   You can set minimal buffer for load or disable stream mode

   By default debug symbol '#' executed, you can disable it
   No cell memory limit, you can use over 30000 cells
   No memory position limit, brainfuck code can use
   negative cell indexes. If you need check memory limit
   or check index allowed ranges you can use tracer -tr

   Notice about optimisations:

                  By default all optimisations is enabled.
                  You can disable some one or all. The more
                  you disable, the slower the code will run

   Notice about input data variants:

                  If input data taked from PIPE and brainfuck
                  have read ',' command need use -f or -s options
                  for send data in brainfuck reader ',' command.

                  If input data from file -i or string -e
                  brainfuck read from stdin. Imposible
                  use PIPE for load source code and for
                  take input for brainfuck code. Or or.

   braintractor -e ',..'                   # ok - you take interactive input
   braintractor -i code.b                  # ok - you take interactive input
   echo ',..' | braintractor -fi /dev/tty  # ok - you take interactive input
   echo ',..' | braintractor -fi input.txt # ok - input from file
   echo ',..' | braintractor -si 'a'       # ok - input from string

   echo ',..' | braintractor              # error, stdin empty after PIPE
                                          # need direct send input data
                                          # need directly use -f or -s

   About trace function:

   If you set trace function, this function be executed
   in brainfuck execution loop for any operations. But
   if you no disable repeater optimisation -dr, tracer miss
   some repeated operations, for example this code
   '+++.+++' in tracer show 3 trace becouse +++ combine
   to single '+' next one '.' and again single '+'
   if you set -dr tracer show full 7 operations per symbol.

   Example tracer:

   c - brainfuck code symbol
   i - brainfuck cell memory index
   v - brainfuck cell memory value
   r - repeated counter after operations or 1
   p - source code position, depend of optimisations, set -da -ds for correct

   -tr 'function(c,i,v,r,p) print(c,i,v,r,p) end'

   For example you can disable output -do and all optimisations
   and just use custom tracer debugger for you brainfuck code

   For example check memory usage no more 10 cells, and check negative index

   -tr 'function(_,i) if i > 10 then error('MEM OVERFLOW!')   end end'
   -tr 'function(_,i) if i <  0 then error('NEGATIVE INDEX!') end end'

   Warning: tracer execute any lua code, ANY LUA CODE! This mean
   you need set correct code, no use copypaste code from internet.
   If tracer function incorrect this application crashed.

Все аргументы являются опциональными. Можно просто передать имя файла или направить ввод через пайп. По умолчанию код исполняется в потоковом режиме считывая по блок по 100 байт (чистого кода), затем применяются немного простейших оптимизаций и код исполняется, но если в блоке находится тело незавершённого цикла то код будет загружаться до того момента пока тело цикла не будет загружено полностью.

Результаты некоторых тестов с подавлением вывода

dron@gnu:~/BFBench-1.4$ time braintractor -l luajit -i beer.b -do -dl
real	0m0,041s
user	0m0,029s
sys	0m0,008s
dron@gnu:~/BFBench-1.4$ time braintractor -l luajit -i bench.b -do -dl
real	0m0,045s
user	0m0,028s
sys	0m0,013s
dron@gnu:~/BFBench-1.4$ time braintractor -l luajit -i long.b -do -dl
real	0m12,477s
user	0m12,457s
sys	0m0,016s
dron@gnu:~/BFBench-1.4$ time braintractor -l luajit -i factor.b -do -dl -si "123456789123456789"
real	0m4,689s
user	0m4,654s
sys	0m0,031s
dron@gnu:~/BFBench-1.4$ time braintractor -l luajit -i hanoi.b -do -dl
real	0m1,556s
user	0m1,508s
sys	0m0,043s
dron@gnu:~/BFBench-1.4$ time braintractor -l luajit -i mandelbrot.b -do -dl
real	0m10,374s
user	0m11,043s
sys	0m0,029s

Модуль

Минимальный пример с параметрами исполнения по умолчанию

local btr = require('braintractor')
local src = '+++++++++++[>+++++++<-]>-----.>+++++[<++++++>-]<-.+++++++..+++.>++++[>+++<-]>--.'
local out = btr:execute(src)

Сначала можно оптиционально задать параметры исполнения

braintractor:configure(config_table)

Конфигурация в config_table может иметь следующий вид, ниже пример с настройками исполнения кода по умолчанию

local config_table =
{
    debug = true;             -- enable/disable debug symbol '#' handler
    jumper = true;            -- enable/disable cycles jump optimisation
    unrepeater = true;        -- enable/disable code repeater excluder
    transplitter = true;      -- enable/disable tranpliter to lua code
    source_stream = true;     -- enable/disable execute in read source time
    stream_buffer =  100;     -- chunks size read for execute
    check_end_line = true;    -- enable/disable check input has new line
    end_of_line_lf = true;    -- replace end of line to \n permanently   osx
    end_of_line_cr = false;   -- replace end of line to \r permanently   nix
    end_of_line_crlf = false; -- replace end of line to \r\n permanently win
    end_of_file_zero = true;  -- write 0  in cell if no have data to write
    end_of_file_eof  = false; -- write -1 in cell if no have data to write
    end_of_file_skip = false; -- skip write in cell if no have data to write
}

    braintractor:configure(config_table)

Если нужно конфигурацию сбросить на значения по умолчанию можно просто вызвать configure с пустой таблицей в качестве параметра, любой не заданный в таблице парамерт будет устанавливаться на значение по умолчанию. В случае успешного выполнения вернёт true иначе false

braintractor:configure({})

После конфигурации, можно вызывать исполнение кода через braintractor:execute

Эта функция принимает три аргумента

• Первый источник исходного кода brainfuck это может быть
  • файл;
  • строка;
  • таблица;
  • функция;
• Второй аргумент это то куда программа на brainfuck будет печатать вывод
  • файл;
  • таблица;
  • функция;
  • false; (исключить какой либо вывод)
  • nil; (возвращать троку возвратом из функции вместо статуса завершения true если стату завершения с ошибкой будет возвращено false)
• Третий аргумент это то откуда программа на brainfuck будет получать ввод
  • файл;
  • таблица;
  • строка;

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

Заданная конфигурация через braintractor:configure сохраняется между вызовами braintractor:execute но не сохраняется состояние выполнения. Если нужно непрерывно гегерировать brainfuck код и исполнять его сохраняя состояние памяти то можно использовать в пачестве первого аргумента для execute функцию, пока та не вернёт nil каждый полученный после её вызова код будет исполняться, а состояние памяти программы будет сохранено. При условии что source_stream не задан как false иначе исполнение по мере получения не будет выполнено.

Исполнение программы можно трассировать используя braintractor:strace(func) Можно установить функцию которая после исполнения каждого шага программы отправляет состояние текущей ячейкм памяти, её содержимого, последней “инструкиции” счётчика повторения и позиции кода в аргументы пользовательской функции трассировки через неё можно отлавливать превышение лимита на память (явных ограничений нет) отрицательные значения индекса ячеек памяти или что-то ещё

Например трассировка программы с лимитами на размер памяти и индекс ячейки

braintractor:strace(function(a,b,c,d,e)
    print("--------------")
    print("Инструкция:"..a)
    print("Номер ячейки:"..b)
    print("Значение ячейки:"..c)
    print("Количество повторений инструкиции:"..d)
    print("Позиция инструкиции в исходном коде:"..e)
    assert(b > 100,"Превышен лимит памяти")
    assert(b < 0,  "Отрицательный индекс памяти")
end)

• Повторение инструкициий 1 и более означает что был код ‘++++’ а стал ‘+4’ и 4 инструкции были выполнены как одна
• Позиция кода верна только в том случае если выключены все оптимизации и сам исходный код не содержал ничего кроме кода.
• Инструкция A означает что [+] или [-] были заменены первый цикл переполняет ячейку до нуля второй уменьшает до нуля смысл обоих дать значение 0 текущей ячейке.
• Инструкция B ведёт поиск ближайшей справа нулевой ячейке [>]
• Инструкция C ведёт поиск ближайшей слева нулевой ячейки [<] Всё это может быть в выводе трассировщика, всё это внутренние представления после оптимизаций, если нужна трассировка кода как есть, то нужно явно отключать все оптимизаци.

Все функции

• braintractor:configure()
• braintractor:execute()
• brainfuck:strace()

В случае успеха возвращают true иначе false. В случае не успеха они генерируют внутри себя строку с ошибкой получить которую можно через error_message (возвращают true за исключением execute с переданным вторым аргументом nil возвращающей, результат вывода программы в случае успеха вместо статуса true)

 local msg = "Внутреняя ошибка"            -- будет добавлено в начало вывода
 if not braintractor:execute(123)          -- 123 это число, будет ошибка
    print(braintractor:error_message(msg)) -- вывести сообщение об ошибке
 end

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

Некое подобие описания API

-----------------------------------------
-- Optional configuration
-----------------------------------------
-- input as table : can contain optional
                    keys or can be empty
-----------------------------------------
-- Empty input {} reset config to default
-----------------------------------------
local input = -- example with default values
{
    debug = true;             -- enable/disable debug symbol '#' handler
    jumper = true;            -- enable/disable cycles jump optimisation
    unrepeater = true;        -- enable/disable code repeater excluder
    transplitter = true;      -- enable/disable tranpliter to lua code
    source_stream = true;     -- enable/disable execute in read source time
    stream_buffer =  100;     -- chunks size read for execute min=1, max=2^31
    check_end_line = true;    -- enable/disable check input has new line
    end_of_line_lf = true;    -- replace end of line to \n permanently   osx
    end_of_line_cr = false;   -- replace end of line to \r permanently   nix
    end_of_line_crlf = false; -- replace end of line to \r\n permanently win
    end_of_file_zero = true;  -- write 0  in cell if no have data to write
    end_of_file_eof  = false; -- write -1 in cell if no have data to write
    end_of_file_skip = false; -- skip write in cell if no have data to write
}

braintractor:configure(input)

------------------------------------------
-- Optional trace function callback
------------------------------------------
-- input as function : with 5 arguments
------------------------------------------

local function input(source_instruction
                     memory_position,
                     memory_value,
                     repeat_counter,
                     source_position)
...some code...

end
braintractor:strace(input)

------------------------------------------
-- Execution brainfuck code
------------------------------------------
-- source as file      : text source code
-- source as string    : text source code
-- source as table     : text source code
-- source as function  : text source code
------------------------------------------
-- output as file      : write to file
-- output as table     : increment add to table
-- output as function  : send to function arg
-- output as false     : eixclude output
-- output as nil       : out from function return
------------------------------------------
-- input as file       : sended data to brainfuck program
-- input as string     : sended data to brainfuck program
------------------------------------------

brainfuck:execute(source,output,input)

------------------------------------------
-- Handle errors
------------------------------------------
-- input as string : optional additional message
------------------------------------------

braintractor:error_message(input)


-------------------------------------------
-- Extended example
-------------------------------------------

local braintractor = require('braintractor')
local conf = {debug=false}
if not braintractor:configure(conf) then
   print(braintractor:error_message("Internal error:"))
end
---
if not brainfuck:strace(function(ch) print(ch) end) then
   print(braintractor:error_message("Callback func error:"))
end
---
local status = braintractor:execute(io.stdin,io.stdout,"123")
if not status then
    print(braintractor:error_message())
end
---
local result = braintractor:execute(io.stdin,nil,"123")
if not refult then
    print(braintractor:error_message())
else
   print(result)
end
---
local src = '++++++++++[>+++++++<-]>-----.>++++++++++[<------>-]<+++++.'
local out = { }
local status = braintractor:execute(src,out)
if not status then
    print(braintractor:error_message())
else
    print(table.concat(out))
end

На заметку

В случае установки в $HOME/.local/ утилита автоматически найдёт модуль. В случае установки в /usr/local или /usr сработают стандартные пути. Но в ином варианте потребудется явное указание package.path как для использования модуля самого по себе так и для сопровождающей утилиты