Интерпретатор Python уместился в 1024 байта кода на Си

Автор поставил себе задачу: уместить интерпретатор Python, написанный на Си, в как можно меньший размер кода, сперва цель была 512 байт, но по ходу работы ориентир сместился к 1024 байтам. Итог показан на примере программы FizzBuzz: она использует def, двоеточия, отступы вместо фигурных скобок и условия без скобок, то есть выглядит как настоящий Python, хотя язык внутри сильно урезан.

Первые попытки писать рекурсивный нисходящий парсер (recursive descent parser) быстро свелись к обычному калькулятору: сначала заработало выражение «1 + 2», потом «x = 1 + 2 * 3», затем условие «if x > y: z = 3», и бюджет по байтам уже был превышен, а получившееся ещё не было похоже на Python. После этого автор осознанно составил список конструкций, которые «выглядят по-питоновски», и заново подошёл к делу с целью в 1024 байта.

В отличие от настоящего CPython, который токенизирует исходник, строит дерево разбора (AST), оптимизирует и лишь потом выполняет байт-код, этот интерпретатор ничего не компилирует. Всё состояние, в глобальных переменных: массив на 999 байт хранит исходный код программы, массив на 256 элементов служит таблицей символов. Имена переменных ограничены одной строчной латинской буквой, это позволяет обращаться к таблице символов напрямую по коду символа, без хеширования или поиска по строке. Обработки ошибок нет вовсе: интерпретатор предполагает, что входной код синтаксически корректен, например, что ключевые слова набраны без опечаток. Циклы и функции не компилируются, а выполняются повторным разбором исходника: интерпретатор запоминает позицию начала условия или тела функции и при каждой итерации или вызове возвращается к ней и разбирает код заново; вложенная рекурсия при этом обслуживается стеком вызовов самого языка Си.

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

В результате читаемая, не сжатая гольфом версия интерпретатора занимает более 4800 байт исходного кода, а итоговая гольфнутая версия, ровно 1024 байта. По оценке автора, если бы единственной целью была работа FizzBuzz, код можно было бы ужать до менее чем 800 байт. Обе версии, читаемая и гольфнутая, выложены на GitHub. Автор отмечает, что процесс был утомительным (постоянно приходилось сверять гольфнутую версию с исходной, чтобы вспомнить, что именно было изменено пару минут назад) и в ближайшее время повторять подобные вызовы не планирует.

Ключевые факты

Интерпретатор написан на Си и после код-гольфа занимает ровно 1024 байта исходного кода.
Поддерживает урезанное подмножество Python: def, if/while/for, однобуквенные переменные нижнего регистра, print через скобки, без обработки ошибок.
Ничего не компилируется: циклы и функции выполняются повторным разбором исходника с сохранённых позиций, вложенная рекурсия, на стеке вызовов Си.
Читаемая (не гольфнутая) версия занимает более 4800 байт; по оценке автора, интерпретатор только под FizzBuzz уместился бы меньше чем в 800 байт.
Обе версии, читаемая и гольфнутая, опубликованы на GitHub.

Почему это важно

Это не продуктовая новость и не исследование, а инженерный курьёз: демонстрация того, насколько компактным может быть рабочий интерпретатор языка программирования при жёстком ограничении по размеру кода. Ценность, в самих приёмах: рекурсивный разбор без промежуточного представления (AST/байт-кода), повторное исполнение через возврат к сохранённой позиции вместо компиляции циклов, и набор трюков код-гольфа для Си (арифметика вместо ветвлений, экономия байт на вызовах функций).

Кому это важно

Программистам на Си и авторам компиляторов/интерпретаторов, которым интересна техника разбора без построения дерева; участникам код-гольф-сообществ; людям, изучающим минимальные учебные реализации языков программирования, например, для встраиваемых скриптовых движков с жёстким лимитом памяти.

Как это применить

Из истории можно взять сам подход: прежде чем гольфить код, сначала явно очертить синтаксическое подмножество, которое реально нужно поддержать, иначе легко получить лишь калькулятор выражений, как случилось в первой попытке автора. Читаемая и гольфнутая версии кода выложены на GitHub рядом друг с другом, что удобно для разбора конкретных приёмов сжатия построчно. Использовать такой интерпретатор для реального Python-кода не получится, он рассчитан только на демонстрацию урезанного подмножества и не проверяет корректность ввода.

Можно ли доверять

Источник, личный пост автора со ссылкой на опубликованный на GitHub исходный код в обеих версиях (читаемой и гольфнутой), а работоспособность подтверждена приведённым примером FizzBuzz. Итоговая цифра в 1024 байта повторяется в тексте несколько раз и явно подтверждена фразой «после всего гольфнутая версия, 1024 байта»; более ранняя формулировка цели («512 1024 байта») выглядит как технический артефакт текста (вероятно, потерянное зачёркивание более раннего ориентира в 512 байт) и не меняет итоговую цифру.

Риски и подводные камни

Интерпретатор прямо не обрабатывает ошибки и полагается на корректность входного кода, некорректный ввод приводит к неопределённому поведению, а не к внятной ошибке. Гольфнутый код опирается на расширения GNU C89, то есть не переносим на любой компилятор Си без изменений. Семантика предельно урезана (переменные, только однобуквенные, нижнего регистра), поэтому это учебная демонстрация и площадка для трюков, а не практический интерпретатор.

«Обработки ошибок нет вообще никакой! Интерпретатор исходит из того, что код синтаксически верен.»

— автор