Чтобы всё ещё ощущать себя человеком, по выходным я пишу код вручную.
Недавно я поставил перед собой задачу создания интерпретатора в 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 в интерпретатор такого размера. Так что же можно уместить в этот код?
Эта программа fizzbuzz явно выглядит, как Python. В ней есть def, двоеточия, отступы и отсутствуют скобки в операторах if. Мне кажется, это вполне походит на Python! Разумеется, наряду с использованием только подмножества синтаксиса придётся добавить и другие ограничения.
Но моя первая попытка оказалась неудачной.
Первая попытка: 512 байт недостаточно!
Раньше я уже писал парсеры, работающие по принципу рекурсивного спуска, поэтому мне показалось, что в данном случае задача будет не сильно сложнее. Подмножество Python вроде как похоже на другие реализованные мной языки (например, в моём компиляторе Teeny Tiny).
Я начал с самого простого кода: 1 + 2
Затем немного усложнил его: x = 1 + 2 * 3
А потом даже добавил конструкции: if x > y: z = 3
Отлично, у меня получился калькулятор... А это не совсем то, к чему я стремился! И код уже вышел за установленные мной рамки. Я решил посмотреть на картину в целом и составил список элементов, которые выглядят, как Python; при этом я осознал, что моих навыков код‑гольфинга будет недостаточно, чтобы уместить всё это в 512 байт.
Возможно, удастся решить задачу в 1024 байта? Сначала заставим систему работать, а потом постараемся её уменьшить.
Парсер
Реализация CPython токенизирует исходный код на Python, парсит его в абстрактное синтаксическое дерево, выполняет анализ и оптимизации, генерирует байт‑код, а затем интерпретирует этот байт‑код.
Мой парсер ничего такого делать не будет.
Состояние хранится в нескольких глобальных переменных. Для него используется массив фиксированного размера (пока он имеет длину 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 отслеживают позицию выражения условия. После исполнения тела происходит переход в эту позицию и парсинг продолжается.
Функции работают аналогично. При парсинге определения таблица символов запоминает позицию функции в исходному коде. Затем при парсинге вызова функции местоположение вызывающей стороны сохраняется, парсер переходит к телу функции, исполняет его, после чего восстанавливает местоположение вызывающей стороны.
Удивительно, что это возможно даже без промежуточного представления! Интерпретатор тоже почти не хранит никакого состояния.
Минифицируем код!
Я не особо силён в код‑гольфинге. Очевидно, что можно сократить имена переменных и удалить пробелы, но как добиться реальной экономии?
В Интернете есть древний забытый веб‑сайт под названием 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());}. Она выполняет проверку на ноль, вычитает 10 для проверки наличия символа новой строки и использует && вместо if. Также она экономит байт благодаря использованию Y(G()); вместо G();Y();. Умное решение! Снова спасибо посту со Stack Overflow.
После всех этих операций сокращённая версия уместилась ровно в 1024 байта!
Окончательная читаемая версия занимает больше 4800 байт. Изначально в коде было намного больше фич, но от них пришлось избавиться. Следующими кандидатами на удаление были выражения сравнения, потому что они занимают много байт, а проверка на истинность работает и без них: if n%15:.
Если бы я хотел ограничиться только работающим fizzbuzz, то, наверно, уместился бы и в 800 байт! Скорее всего, есть и другие трюки код‑гольфинга.
Вот подвергнутые код‑гольфингу исходники во всём их великолепии:
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);}
В конечном итоге, мне удалось реализовать следующие фичи:
Целочисленные переменные (однобуквенные) и литералы.
Присвоение значений переменным.
Арифметика с
+ - * %и приоритетом (унарные+ -работают только в начале выражения).Сравнения при помощи < > <= >= == (только один из операторов на выражение).
Логическая интерпретация целых чисел.
ifиelse.Циклы
while, в том числе и блокиelse.Циклы
for x in range(y), в том числе и блокиelse.Определения функций без аргументов.
Вызовы функций, в том числе рекурсивные.
Блоки, определяемые отступами (без областей видимости).
printс одним строковым литералом или целочисленным выражением.Комментарии.
Не думаю, что в ближайшем будущем снова буду браться за задачки по код‑гольфингу. Этот процесс показался мне довольно монотонным, приходилось много раз переключаться между сокращённой и исходной версиями, чтобы разобраться, что же я поменял всего две минуты назад. Обе версии выложены на GitHub.
Теперь ваша очередь. Как будет выглядеть ваш Python в 1024 байтах?