Ще один Brainfuck інтерпретатор

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
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.