Вызов выходного дня: интерпретатор Python в 1024 байта
По выходным написано давно: писать код от руки — это ощущение человечности.
Последний вызов: создать интерпретатор Python в 512 1024 байта хорошего старого C-кода. Никаких макросов и трюков с библиотеками.
def buzz():
for n in range(101):
if n % 15 == 0:
print("FizzBuzz")
else:
if n % 3 == 0:
print("Fizz")
else:
if n % 5 == 0:
print("Buzz")
else:
print(n)
buzz()
Вместить весь Python в интерпретатор размером 1024 байта не получится. Но можно сделать так, чтобы это выглядело как Python?
Эта программа FizzBuzz выглядит как настоящий Python: есть def, двоеточия, отступы, нет скобок в условиях. Похоже на Python! Конечно, придётся наложить и другие ограничения сверх ограничения синтаксиса.
Первая попытка: 512 байт недостаточно
Написано много рекурсивных парсеров нисходящего анализа. Насколько это может отличаться? Подмножество Python должно быть похоже на другие языки, которые реализованы (например, Teeny Tiny компилер).
Начал с самого простого: 1 + 2
Потом усложнил: x = 1 + 2 * 3
И даже добавил операторы: if x > y: z = 3
В итоге получился калькулятор. Не совсем то! И уже превышен лимит. Тогда отошли на шаг назад и составили список элементов, которые выглядят как Python, и одновременно осознали, что навыков code golf недостаточно, чтобы уместить в 512 байт.
Может быть, 1024 байта? Сначала сделать так, чтобы работало, потом — сжимать.
Парсер
Настоящая реализация CPython токенизирует исходный код Python, парсит его в абстрактное синтаксическое дерево, выполняет анализ и оптимизации, генерирует bytecode и интерпретирует bytecode.
Здесь ничего этого не будет.
Состояние хранится в нескольких глобальных переменных. Используется массив фиксированной длины (999 символов), который хранит сырой код Python. Переменные и имена функций укладываются в один массив.
char src[999]; /* Весь исходный код без большинства пробелов. */ int vars[256]; /* Таблица символов. */ int pos; /* Следующий символ в src. */ int ch; /* Текущий символ в src. */ int line_start; /* Где начинается текущая строка. */
Выражения обрабатываются как обычный рекурсивный парсер, и они выполняются во время анализа. Например:
int parse_sum(void) {
int value = parse_term();
while (ch == '+' || ch == '-') {
if (ch == '+')
value = value + parse_term();
else
value = value - parse_term();
}
return value;
}
Пока всё просто.
Обработки ошибок вообще нет! Парсер делает множество предположений о корректности кода. Например, предполагается, что ключевые слова написаны правильно.
if (ch == 'w' || ch == 'i' || ch == 'f') {
int keyword = ch;
int loop_var = 0;
if (keyword == 'f') { /* "for K in range(N):" */
pos += 2; /* Пропустить "or". */
loop_var = next();
pos += 8; /* Пропустить "inrange(". */
vars[loop_var] = 0;
} else if (keyword == 'w')
pos += 4; /* Пропустить "hile". */
else
pos += 1; /* Пропустить "f" из "if". */
Также предполагается правильность границ токенов, и большинство пробелов удаляются. Сохраняются отступы и пробелы в строковых литералах.
Ограничено одиночными строчными буквами как имена переменных, что позволяет прямо обращаться к таблице символов:
if (ch > 96) {
value = vars[ch];
next();
}
Магия управления потоком
Функция для выполнения блоков кода продолжает работу, пока отступ не уменьшится. Когда это происходит, функция возвращает управление вызывающему коду, который обрабатывает следующую строку. Таким образом, используется стек вызовов программы C для обработки рекурсии.
void run_block(int min_indent) {
for (;;) {
int indent = read_indent();
if (ch == '\n')
continue;
if (indent < min_indent || ch == 0) {
pos = line_start;
return;
}
А как с циклами?
Так как ничего не компилируется, циклы работают прыгая назад и перепарсивая исходный код на каждой итерации. Оба цикла while и for сохраняют позицию выражения условия. После выполнения тела цикла возвращаемся на эту позицию и продолжаем парсинг.
Функции работают аналогично. При парсинге определения функции таблица символов запоминает позицию функции в исходном коде. При вызове функции сохраняется позиция вызывающего кода, парсер прыгает на тело функции, выполняет его, и восстанавливает позицию вызывающего кода при достижении конца.
Это красиво — что можно делать даже без промежуточного представления! Интерпретатор хранит минимум состояния.
Минификация
Code golf раньше не практиковалось. Обрезание имён переменных и пробелов — это очевидно, но как сэкономить основной объём?
Существует древний, забытый сайт под названием Stack Overflow, где маги кода прошлого поколения делились знаниями. Из поста Tips for golfing in C взяли множество идей.
Так как правила существуют только в воображении, пришлось быть креативным. Некоторые из этих подсказок полагаются на "возможности" GNU C89. Это не трюки! Это обычный способ. Вот что было сделано, чтобы сэкономить байты в читаемой версии:
- Однобуквенные имена переменных и функций
- Предположить, что компилятор свяжет libc
- Использовать глобальные переменные для временных значений
- Глобальные переменные инициализируются нулями
- C89 позволяет объявлениям переменных быть неявно int, функции предполагаются возвращающими int
- Использовать параметры функций как временные переменные, сохранённые в стеке вызовов
- ASCII-значения вместо литералов символов
- Тернарный оператор и оператор запятой
- Побитовые операции вместо логических
Например, функция parse_sum(void), показанная ранее, была сжата до e(){for(z=t();c-43u<3;)y=44-c,z+=y*t();return z;}. Используются ASCII-значения для экономии байт.
Ещё пример — вспомогательная функция, которая прыгает в конец строки:
void skip_to_eol(void) {
if (ch != 0 && ch != '\n') {
next();
skip_to_eol();
}
}
Сжато до: Y(){c&&c-10&&Y(G());}. Проверяется 0, вычитается 10 для проверки на перевод строки, используется && вместо if. Потом экономится байт, делая Y(G()); вместо G();Y();. Умно! Спасибо ещё раз посту Stack Overflow.
В конце сжатая версия занимает 1024 байта!
Читаемая версия занимает свыше 4800 байт. Изначально было ещё несколько возможностей, но пришлось обрезать, чтобы уместить. Выражения сравнения были на очереди на удаление, так как они занимают много байт, а truthiness всё ещё работает без них: if n%15:.
Если бы цель была только заставить работать fizzbuzz, можно было бы получить менее 800 байт! Вероятно, есть и другие трюки code golf.
Вот сжатый исходный код во всей своей красе:
char s[999];v[256],p,c,x,y,z,w,u;G(){return c=s[p++];}I(){for(u=p;G()==32;);return p-u;}Y(){c&&c-10&&Y(G());}f(){x=0;if(G()>96)x=v[c],G();for(;c-48u<10;G())x=x*10+c-48;return x;}t(g,h){for(g=f();c==42|c==37;)h=c,g=h-42?g%f():g*f();return g;}e(){for(z=t();c-43u<3;)y=44-c,z+=y*t();return z;}E(a,q){a=e();if(c-60u>2)return a;w=c-61;q=G()==61;p-=!q;x=e();return w?(a-x)*w>-q:a==x;}S(i){for(;I()>i|c==10;)Y();p=u;}Q(){for(G();G()-34;)putchar(c);G();}B(i,q,j,k,a,m,n){for(;;){j=I();if(c==10)continue;if(j<i|!c){p=u;return;}if(c==119|c==105|c==102){k=c;k-102?p+=k/4-25:(p+=2,m=G(),p+=8,v[m]=0);q=p;for(;;){a=k-102?E():v[m]<E();p+=k==102;G();if(!a){S(j);break;}B(j+1);if(k==105)break;k-102||v[m]++;p=q;}I()-j|c-101?p=u:(p+=4,G(),a?S(j):B(j+1));}else if(c==100){p+=2;k=G();Y();v[k]=p;S(j);}else{if(c>96){k=c;while(G()>96);c==40?k-112?(G(),n=p,p=v[k],B(2),p=n,G()):(s[p]-34?printf("%d",E()):Q(),puts(""),G()):(v[k]=E());}Y();}}}main(q,m,h){for(h=m=q=0;~(c=getchar());){c=c-9?c:32;h^=c==34;s[q]=c;q+=c-32?1:!m|h;m=c>32|m&&c-10;}B(0);}
В результате удалось реализовать эти возможности:
- Целочисленные переменные (одиночная буква) и литералы
- Присваивание переменных
- Арифметика с +, -, *, % с учётом приоритета (унарные +, - работают только в начале выражения)
- Сравнения с <, >, <=, >=, == (только одно за выражение)
- Целочисленная truthiness
- if и else
- Циклы while, включая блоки else
- Циклы for x in range(y), включая блоки else
- Определения функций без аргументов
- Вызовы функций, включая рекурсию
- Блоки на основе отступов (без области видимости)
- print с одиночным строковым литералом или целочисленным выражением
- Комментарии
Code golf больше не планируется. Процесс был утомительным — туда-сюда между минифицируемой версией и оригиналом, пытаясь понять, что было изменено 2 минуты назад. Обе версии находятся на GitHub.
Теперь твой ход. Как выглядит твой Python в 1024 байта?