README.md

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

    Описание

    Гибкий интерпретатор brainfuck кода

    Конвейеры
    0 успешных
    0 с ошибкой