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


quine



Для оптимизации нужно выполнить 3 правила:


  1. Обратные инструкции (+ и -, > и <) взаимоуничтожаются, когда идут одна за другой. Код >++>><<- превращается в >+. Это, скорее, защита от дурака, чем оптимизация, т.к. такой код бессмысленен.


  2. Повторяющиеся инструкции заменяются на команды, в аргументах которых сказано сколько раз конкретную инструкцию выполнить. Например, код +++ заменяется на команду ADD с аргументом 3, а код <<< на MOVE:-3.


  3. Добавляется новая команда, у которой в bf нет соответствующий инструкции. Команда присвоения значения. Код [+] и [-] обнуляет текущую ячейку, а команда ADD за этим кодом присваивает текущей ячейке значение своего аргументы. Код --[-]+++ заменяется на команду ASSIGN:3.

Список команд с описанием


Каждая команда имеет свой аргумент (далее просто arg). Значение аргумента ограничено только у команды ADD, т.к. размер одной ячейки 256.


Имя команды Инструкции Описание
ADD + и - Изменяет значение текущей ячейки на arg
MOVE > и < Изменяет индекс текущей ячейки на arg
READ , Пропускает из потока ввода arg символов и читает следующий за ними символ
PRINT . Печатает символ соответствующий значению текущей ячейки arg раз
GOTO [ и ] Переходит к выполнению arg по счёту команды относительно текущей
ASSIGN [+] и [-] Присваивает текущей ячейке arg

Пример кода интерпретатора


Интерпретация разделена на 3 этапа. Чтение исходного кода, его преобразование в оптимизированные команды и выполнение этих команд. Это всё происходит в функциях main и parse.


Первый и последний этап происходят сразу в функции main. Её код с комментариями:


int main(int argc, char* argv[]){
    /* имя файла с исходниками передаётся первым аргументом */
    if(argc == 1){
        fprintf(stderr, "%s: Wrong argument count\n", argv[0]);
        return 1;
    };
    /* файл открывается для чтения */
    FILE* f = fopen(argv[1], "r");
    if(f == NULL){
        fprintf(stderr, "%s: Can't open %s\n", argv[0], argv[1]);
        return 2;
    };
    /* исходный код читается из файла */
    int n = fread(str, sizeof(char), SIZE - 1, f);
    if(n == 0){
        fprintf(stderr, "%s: Can't read data from %s\n", argv[0], argv[1]);
        return 3;
    };
    str[n] = '\0';
    /* проверяется правильность расстановки скобок */
    fclose(f);
    if(brackets()){
        fprintf(stderr, "%s: Wrong brackets sequence\n", argv[0]);
        return 4;
    };
    /* парсинг исходного кода */
    parse();
    /* выполнение команд */
    ptr = mem;
    int (*exe[])(int) = {exe_a, exe_b, exe_c, exe_d, exe_e, exe_f};
    struct code* p = src + 1;
    for(; p->cmd; ++p){
        p += (*exe[p->cmd - 1])(p->arg);
    };
    return 0;
};

Оптимизация с помощью преобразования инструкций bf в команды для интерпретатора происходит в функции parse. Её код с комментариями:


void parse(){
    /* инициализируется массив команд */
    struct code *p = src;
    p->cmd = 0;
    p->arg = 0;
    /* указатель на текущую инструкцию */
    char* ch = str;
    /* указатель на вершину стека необходимый для обработки скобок */
    top = stk;
    /* массив из указателей на функции обрабатывающих 8 возможных команд и комментарии */
    int (*prs[])(struct code*) = {prs_0, prs_1, prs_2, prs_3, prs_4, prs_5, prs_6, prs_7, nothing};
    /* парсинг */
    for(; *ch != '\0'; ++ch){
        p += (*prs[find(*ch)])(p);
    };
    /* нуль-терминальная команда в конце массива */
    (p + 1)->cmd = 0;
};

Проверка эффективности


Для сравнения взял интерпретатор из официального репозитория ubuntu и несколько тестов из этого репозитория. В таблице записано среднее время работы теста в секундах.


Имя теста Официальный Из статьи
Long 34 20
Mandelbrot 21 26
EasyOpt 24 27
Counter 34 37

На всех тестах, кроме первого, официальный интерпретатор работает примерно на 12 процентов быстрее интерпретатора из статьи. В первом тесте, в отличии от остальных, в большинстве циклов количество инструкций > не совпадает с количеством инструкций <. Это делает циклы несбалансированными и не поддающимися оптимизации (другому виду оптимизации, не описанному в статье). Похоже, официальный интерпретатор оптимизирует сбалансированные циклы и получает от этого 12-процентный прирост к скорости, в то время как интерпретатор из статьи этого не делает и побеждает только на первом тесте. Хотя это неплохой результат для такого простого алгоритма оптимизации.


Исходники на Github

Поделиться с друзьями
-->

Комментарии (11)


  1. FDA
    11.02.2017 22:53
    -1

    Класс!


  1. ruslanys
    11.02.2017 23:09

    Помнится статья, где johnfound написал форум на Assembler.

    Кто напишет форум на BrainFuck?)


    1. Avrong
      12.02.2017 22:11
      +1

      Для того, чтобы запускать форум на BrainFuck интерпретатором на Assembler?)


  1. mwizard
    11.02.2017 23:26

    А почему для [+] и [-] были выбраны триграфы, а не пара вида { и }?


    1. srbgd
      12.02.2017 00:03
      +1

      Это 3 разные инструкции языка, которые приводят к обнулению ячейки, а не одна инструкция. Это означает, что инструкция + или - будет выполняться до тех пор, пока значение текущей ячейки не равно нулю. Поскольку bf использует минимальное количество инструкций, то добавлять новую инструкцию для операции обнуления нет смысла.


  1. Temtaime
    12.02.2017 00:27

    Напишите бекенд к LLVM.


    1. VladimirKochetkov
      12.02.2017 03:05

      1. Temtaime
        12.02.2017 21:20

        Не, не компилятор брейнфака в x86, а бекенд, который будет генерировать брейнфак :)


  1. Carzil
    12.02.2017 03:10
    +1

    Лет 5-6 назад на Хабре была целая неделя Brainfuck'a — народ писал интерпретаторы/компиляторы для различных платформ/языков/виртуальных машин. Эх, были времена...


  1. Sirikid
    12.02.2017 03:20
    +1

    Я буду обновлять комментарии, аминь.


  1. bolk
    12.02.2017 14:35

    Я как-то писал вроде самый пока сильно оптимизирующий интерпретатор/компилятор —https://github.com/bolknote/brainfuck. По ссылке его порт с JS. Основной приход с развёртки циклов в конструкции без циклов. Правда я его подзабросил, надоело, в нём так и остались неисправленные баги.