Інтерпретатор Python, що вміщується у 1024 байти C

Більшість вихідних проєктів Остіна Генлі — це привід писати код вручну, і останній мав жорсткий бюджет: інтерпретатор Python на C, що вміщується у 512 байтів коду. Ця мета виявилася недосяжною — за його словами, навичок у code golf забракло — тож він зупинився на 1024 байтах, без макросів-трюків і без бібліотек, які робили б роботу за нього.

Тестовою програмою став fizzbuzz, який виглядає цілком по-пітонівськи: є def, двокрапки, відступи й жодних дужок навколо умови if. Вміщується лише підмножина мови, і правила суворі.

Що інтерпретатор робить, а чого — ні

Обробки помилок немає жодної: інтерпретатор припускає, що ключові слова написані правильно, а межі токенів точні. Під час читання він прибирає майже всі пробіли, залишаючи лише відступи та пробіли всередині рядкових літералів. Імена змінних і функцій обмежені однією малою літерою, завдяки чому пошук у таблиці символів — це прямий індекс масиву, а не перебір. Стан зберігається в кількох глобальних змінних: буфер джерела на 999 байтів, таблиця символів на 256 слотів і кілька покажчиків позиції.

Виконання без абстрактного синтаксичного дерева

Дизайн майже не має спільного з CPython, який токенізує код, будує дерево, аналізує його, компілює в байткод і лише потім інтерпретує. Версія Генлі розбирає код рекурсивним спуском і виконує вирази одразу; блок повертає керування, коли відступ зменшується, тож вкладеність обробляє стек викликів C. Нічого не компілюється, тому цикли працюють стрибками назад і повторним розбором джерела на кожній ітерації, запам'ятовуючи початок умови. Виклик функції зберігає позицію того, хто викликав, стрибає в тіло й відновлює позицію в кінці.

Як дійшло до 1024 байтів

Щоб перейти від читабельної версії, яка сягає понад 4800 байтів, до 1024, знадобився звичайний гольф: коротші імена, відкинуті необов'язкові дужки та прийоми зі старої теми Stack Overflow про гольф у C, разом із особливостями GNU C89. Функція парсера з чотирма аргументами стала однорядковим виразом, який ASCII-арифметикою визначає, який оператор читається; рекурсивний помічник для переходу до кінця рядка стиснувся до Y(){c&&c-10&&Y(G());}. Оператори порівняння були наступними на черзі — завдяки truthiness if n%15: усе одно працює — і, за оцінкою автора, версія лише під fizzbuzz могла б вкластися в 800 байтів. Обидві версії є на GitHub.