Интерпретатор Python в 1024 байтах на чистом C

Остин Хенли по выходным пишет код от руки — «чтобы чувствовать себя человеком». Его очередной вызов самому себе: уместить интерпретатор Python в 512 байт кода на добром старом C, без макросов и библиотечных фокусов. Планка в 512 байт оказалась недостижимой, поэтому автор поднял её до 1024.

Цель — не поддержать весь язык, а сделать нечто, что убедительно выглядит как Python. Эталоном служит FizzBuzz: в нём есть def, двоеточия, отступы и if без скобок. Похоже на Python — и достаточно.

Как это устроено

Настоящий CPython токенизирует исходник, строит синтаксическое дерево, оптимизирует, генерирует байт-код и исполняет его. Здесь нет ничего из этого. Состояние держится в горстке глобальных переменных, весь текст программы лежит в массиве фиксированной длины, а имена переменных ограничены одной строчной буквой — это позволяет обращаться к таблице символов напрямую.

Выражения разбираются обычным рекурсивным спуском и вычисляются прямо по ходу разбора. Обработки ошибок нет вовсе: интерпретатор слепо доверяет корректности кода, не проверяет даже правильность написания ключевых слов и просто «перескакивает» нужное число символов. Циклы, поскольку ничего не компилируется, работают повторным разбором исходника: после тела парсер прыгает назад к условию. Функции устроены так же — позиция тела запоминается, вызывающий адрес сохраняется и восстанавливается по возвращении. Автор не без гордости замечает, как много удаётся сделать вообще без промежуточного представления.

Гольф по байтам

Обрезать имена и пробелы — очевидный шаг, но крупную экономию дали приёмы из «древнего, забытого сайта Stack Overflow», где, по выражению автора, «маги кода прошлого делились знаниями». В ход пошли особенности GNU C89: неявный тип int, нулевая инициализация глобальных, параметры функций как временные переменные на стеке, ASCII-коды вместо символьных литералов, тернарный оператор и запятая, битовые операции вместо логических. Так, функция разбора суммы ужалась до e(){for(z=t();c-43u<3;)y=44-c,z+=y*t();return z;}.

Читаемая версия занимает свыше 4800 байт; ради заветной цифры пришлось выкинуть немало возможностей — например, сравнения, ведь истинность и без них работает через if n%15:. Итоговый результат — ровно 1024 байта.

При всём аскетизме в интерпретатор влезли целочисленные переменные и арифметика с приоритетом операций, сравнения, ветвления if/else, циклы while и for x in range(y) (даже с блоком else), определения и рекурсивные вызовы функций без аргументов, блоки по отступам, print и комментарии.

Повторять подобное в ближайшее время автор зарекается: процесс, по его словам, изматывающий — приходится метаться между «в процессе гольфа» и исходной версией, чтобы вспомнить, что ты менял пару минут назад. Обе версии выложены на GitHub, а завершается заметка вопросом к читателю: а как выглядел бы ваш Python в 1024 байтах?

Источник: Lobsters