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

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

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

   
   

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

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

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

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

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

Интерпретация разделена на 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 и несколько тестов из этого репозитория. В таблице записано среднее время работы теста в секундах.

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

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