Интерпретатор Scheme (Lisp), написанный на Python.
- Ядро Scheme: Поддержка лямбда-исчисления, лексических областей видимости (closures),
define,set!,if,quote. - Типы данных: Числа (int, float, complex), строки, символы, списки, булевы значения (
#t,#f). - Синтаксический сахар: Комментарии (
;), цитирование ('), квазицитирование (`,,,,@). - Макросы: Макросы через
define-macro. Встроенные макросы:let,and,orиdo. - Оптимизация: Оптимизация хвостовой рекурсии (TCO) позволяет выполнять циклы без переполнения стека.
- Продолжения: Поддержка
call/cc(call-with-current-continuation). - Ленивые вычисления: Поддержка
delayиforceдля создания отложенных вычислений и бесконечных потоков. - Система типов: Опциональная статическая типизация. Поддержка аннотаций типов (
::) для переменных и аргументов функций. Проверка типов во время выполнения. - Каррирование: Функция
curryдля частичного применения аргументов к функциям. - Обработка ошибок: Сообщения об ошибках с использованием кастомных классов исключений. Поддержка
tryиraise. - Динамическое связывание: Поддержка
dynamic-letдля временного изменения значений переменных. - Модульность: Код разделен на логические модули для удобства поддержки и расширения.
- Доступ к вызовам Python: Возможность импортировать модули Python и использовать их функции и объекты.
lispy/
__init__.py # Инициализация пакета, определение встроенных макросов
__main__.py # Точка входа (python -m lispy)
types.py # Типы данных (Symbol, Exp, Atom)
constants.py # Константы и настрцойки
errors.py # Классы исключений
messages.py # Тексты сообщений об ошибках
parser.py # Токенизатор и парсер (read)
env.py # Окружение (Environment)
evaluator.py # Вычислитель (eval), поддержка TCO, try, dynamic-let
macros.py # Система макросов (expand)
primitives.py # Стандартная библиотека функций
repl.py # Read-Eval-Print Loop
tests/
test_math.py # Тесты математических функций
test_lists.py # Тесты работы со списками
test_control_flow.py # Тесты управляющих конструкций
test_definitions.py # Тесты определений и функций
test_do.py # Тесты do
test_syntax.py # Тесты синтаксиса
test_parser.py # Юнит-тесты парсера
test_env.py # Юнит-тесты окружения
test_try_catch.py # Тесты обработки исключений
test_dynamic_binding.py # Тесты динамического связывания
test_laziness.py # Тесты ленивых вычислений
test_currying.py # Тесты каррирования
test_types.py # Тесты системы типов
test_platform.py # Тесты взаимодействия с Python
test_types.py # Тесты системы типов
Интерпретатор построен по модульному принципу, где каждая часть отвечает за свой этап обработки кода. Основной цикл работы — это REPL (Read-Eval-Print Loop), который реализован в repl.py.
Модуль parser.py отвечает за преобразование исходного текста программы в структуру данных, понятную интерпретатору (Abstract Syntax Tree, AST).
- Токенизация: Сначала строка разбивается на токены (скобки, символы, числа, строки).
- Построение AST: Токены преобразуются в вложенные списки Python. Например,
(define x 10)превращается в['define', 'x', 10]. Атомы (числа, строки) конвертируются в соответствующие типы Python.
Модуль env.py реализует класс Env, который представляет собой область видимости переменных.
- Структура: Это словарь (
dict), хранящий пары "имя переменной" — "значение". - Вложенность: Каждое окружение имеет ссылку на родительское (
outer). При поиске переменной интерпретатор сначала смотрит в текущем окружении, и если не находит — идет вверх по цепочке родителей до глобального окружения. - Замыкания (Closures): Когда создается лямбда-функция, она "запоминает" окружение, в котором была создана. Это позволяет функциям иметь доступ к переменным, которые были видны в момент их определения, даже если вызов происходит в другом месте.
Перед вычислением код проходит этап раскрытия макросов, реализованный в macros.py.
- Expand: Функция
expandрекурсивно обходит AST. Если она встречает вызов макроса (определенного черезdefine-macro), она вызывает функцию-трансформер макроса, которая возвращает новый код. - Встроенные макросы: Конструкции вроде
let,and,or,doреализованы как макросы, которые раскрываются в базовые формы (lambda,if). Это упрощает ядро языка.
Сердце интерпретатора — модуль evaluator.py.
- Диспетчеризация: Вместо длинной цепочки
if/elifдля обработки специальных форм (if,define,lambdaи т.д.) используется таблица диспетчеризацииSPECIAL_FORMS. Это словарь, где ключи — символы форм, а значения — функции-обработчики. Это делает код чище и расширяемым. - Стандартные функции: Если первый элемент списка не является спецформой, он считается вызовом функции. Аргументы вычисляются, и вызывается соответствующая процедура (из
primitives.pyили пользовательская).
Python имеет лимит на глубину рекурсии, что мешает писать в функциональном стиле. В этом проекте реализована полная поддержка TCO.
- Механизм: Когда функция вызывает другую функцию в "хвостовой позиции", вместо создания нового фрейма стека Python, мы возвращаем объект
TailCall, содержащий новую функцию и аргументы. - Цикл: В
evaluator.pyесть бесконечный циклwhile True. Он ловит объектыTailCallи просто обновляет текущее выражение и окружение, продолжая вычисление на том же уровне стека. Это позволяет выполнять рекурсии без переполнения памяти.
Реализована система исключений, похожая на Python, но внутри Lisp.
- Классы ошибок: В
errors.pyопределены типы ошибок (LispyError,UserError,ArgumentErrorи т.д.). - Try/Raise: Спецформа
tryпозволяет перехватывать ошибки. Если внутри блокаtryпроисходитraise, управление передается в обработчик (catch), который получает объект ошибки.
В дополнение к лексическому (статическому) связыванию, реализовано динамическое через dynamic-let.
- Это позволяет временно переопределить значение глобальной переменной только на время выполнения определенного блока кода. После выхода из блока старое значение восстанавливается.
Реализованы примитивы для отложенных вычислений.
- Promise: Специальный тип данных, хранящий невычисленное выражение и (после первого вычисления) его результат.
- Delay: Макрос
(delay exp), который оборачивает выражение вPromise. - Force: Функция
(force promise), которая вычисляет значениеPromiseпри первом обращении и возвращает кэшированный результат при последующих (мемоизация). Функция рекурсивно раскрывает вложенные промисы (например,(delay (delay x))), пока не будет получено конкретное значение.
Функция curry позволяет преобразовать функцию от N аргументов в цепочку из N функций от одного аргумента.
- Это полезно для частичного применения функций и создания новых функций на основе существующих.
- Поддерживается только для пользовательских процедур (не для встроенных примитивов с переменным числом аргументов).
- Поддержка промисов:
curryподдерживает передачу промисов. Вычисление промиса происходит лениво — только в момент вызова результирующей функции.
Реализована базовая система проверки типов во время выполнения.
- Синтаксис: Типы указываются через
::.- Определения:
(define x :: int 10) - Аргументы:
(lambda (x :: int) ...)
- Определения:
- Поддерживаемые типы:
int,float,str,bool,list. - Проверка: Если переданное значение не соответствует указанному типу, выбрасывается исключение
TypeMismatchError.
Lispy позволяет использовать мощь экосистемы Python напрямую.
- py-import: Импортирует модуль Python.
(define math (py-import "math"))
- py-getattr: Получает атрибут объекта (функцию, переменную, класс).
(define pi (py-getattr math "pi")) (define cos (py-getattr math "cos")) (cos pi) ; -> -1.0
- py-eval: Выполняет строку кода Python и возвращает результат.
(py-eval "1 + 2") ; -> 3
- py-exec: Выполняет строку кода Python (для побочных эффектов).
(py-exec "print('Hello from Python')")
- Python 3.8+
Чтобы запустить интерактивную оболочку:
python3 -m lispyПример сессии:
lispy> (define r 10)
None
lispy> (* 3.141592653 (* r r))
314.1592653
lispy> (define (fact n) (if (<= n 1) 1 (* n (fact (- n 1)))))
None
lispy> (fact 10)
3628800
lispy> (try (/ 1 0) (lambda (e) "caught error"))
"caught error"
lispy> (define *x* 10)
None
lispy> (dynamic-let ((*x* 20)) *x*)
20
lispy> *x*
10python3 -m lispy my_script.scmДля установки зависимостей разработки (тесты, линтеры):
pip install -r requirements/dev.txtЗапуск всех тестов:
pytestПроект использует flake8 для проверки стиля и isort для сортировки импортов.
# Проверка стиля
flake8 .
# Автоматическая сортировка импортов
isort .Настроена автоматическая проверка кода (Linting) и запуск тестов (Testing) через GitHub Actions. Тесты запускаются только после успешного прохождения линтеров.
Проект содержит подробную документацию, сгенерированную с помощью Sphinx.
Актуальная версия документации доступна на GitHub Pages: https://fuodorov.github.io/lispy/
Для сборки документации локально выполните:
# Установка зависимостей для документации
pip install -r requirements/docs.txt
# Сборка HTML версии
sphinx-build -b html docs docs/_build/htmlПосле сборки откройте файл docs/_build/html/index.html в браузере.
- Базовый синтаксис и семантика Scheme
- REPL
- Арифметика и математические функции
- Строки и комментарии
- Макросы (
define-macro) -
let,and,or,do(через макросы) - Хвостовая рекурсия (TCO)
-
call/cc - Обработка ошибок (Custom Exceptions,
try,raise) - Динамическое связывание (
dynamic-let) - Ленивые вычисления (
delay,force) - Каррирование (
curry) - Система типов (аннотации типов, проверка во время выполнения)
- Модульная архитектура
- Покрытие тестами
- CI/CD (GitHub Actions)
- Документация (Sphinx)
Данный проект основан на книге "Structure and Interpretation of Computer Programs" и реализации lispy, представленной в ней, а также на статье Питера Норвига "How to Write a (Lisp) Interpreter (in Python)".