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