Интерпретатор Lisp в типовой системе Rust

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

• Весь Lisp-интерпретатор работает в типовой системе Rust, код вычисляется на этапе компиляции
• Поддерживает определение функций, рекурсию, лямбды, глобальные и локальные переменные, вызовы через apply
• Реализован call/ec для управления потоком выполнения с помощью escape-continuations
• Ограничения: числа только от 0 до 8192, нет макросов и eval, нет поддержки отрицательных чисел
• Результаты вычислений проверяются типовой системой - например, assert_same проверяет, что факториал 5 равен 120

Ред. Lisp, который считается на этапе компиляции и не умеет отрицательных чисел, зато умеет call/ec. Числа до 8192, дальше упирается в стек: язык, у которого потолок натуральных чисел задаётся настройками компилятора.

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

Проект показывает, что типовые системы современных языков программирования намного более выразительны, чем казалось раньше. Используя механизм associated types и трейтов Rust, можно реализовать полноценный интерпретатор Lisp, выполняя логику во время компиляции. Это не просто забавная демонстрация - это открывает возможности для мета-программирования и проверки инвариантов кода на этапе компиляции.

Ред. Тезис «типовые системы выразительнее, чем казалось» проверен ценой превращения компилятора Rust в медленную виртуальную машину. Выразительность доказана, практичность опровергнута тем же экспериментом.

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

Разработчикам на Rust, которые интересуются расширенными возможностями типовой системы и генеративным программированием. Исследователям, работающим над языковыми расширениями и компиляторами. Авторам библиотек, которые ищут способы переместить вычисления на этап компиляции для производительности или безопасности.

Ред. Любителям заглянуть, куда типовая система гнётся до того, как сломается. Для всех, кому нужен Lisp, по-прежнему есть Lisp.

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

На практике этот подход полезен для встроенных DSL (domain-specific languages) в Rust, которые вычисляются на этапе компиляции. Можно использовать типовую систему для описания конфигураций, которые должны быть полностью известны на этапе компиляции, или для символических вычислений. Однако для чего-либо серьёзнее образовательной цели стоит рассмотреть proc-macros как более практичную альтернативу.

Ред. Авторская же рекомендация в конце («для чего угодно серьёзнее берите proc-macros») фактически отменяет раздел: применить это можно ровно один раз, чтобы убедиться, что применять это не надо.

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

Это любительский проект, автор честно указывает ограничения и не претендует на полноту реализации. Код работает для демонстрационных примеров вроде факториала и call/ec, но не тестировался на более сложных программах. Проект интересен как proof-of-concept, но использовать его как основу для продакшена не стоит.

Ред. Доверять можно: факториал пятёрки честно даёт 120, и автор сам перечисляет, чего нет (макросов, eval, отрицательных чисел). Редкий случай, когда proof-of-concept не притворяется ничем большим.

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

Времена компиляции Rust резко возрастут при использовании этого подхода для нетривиального кода - типовая система не оптимизирована для итеративных вычислений. Ограничение на 8192 числа и отсутствие отрицательных чисел делают его непригодным даже для средних программ. Сообщения об ошибках компилятора Rust в таком контексте будут нечитаемы.

Ред. Главный риск не в рантайме, а в компиляции: время сборки взлетает, а сообщение об ошибке от типовой системы Rust на рекурсивном Lisp читается как крик о помощи. Отлаживать факториал по выхлопу борроу-чекера это отдельный жанр.