Читать книгу: «Интерпретатор. Паттерн GoF на Python, C++23, Rust и Java»
Введение
Эта книга посвящена одному паттерну проектирования — Интерпретатор (Interpreter). Он относится к каталогу «Банды четырёх» (Gang of Four, GoF). Здесь паттерн разобран сразу в четырёх реализациях: на Python, C++23, Rust и Java. Каждая реализация — отдельная часть книги: сначала задача и общая схема, затем код, модификации, гибридные варианты и самостоятельные работы.
Как читать
Основы каждого языка здесь не повторяются: они собраны в книгах серий по соответствующему языку. Разделы каждой части нумеруются заново, поэтому ссылка «раздел 1.2» указывает на раздел той же части, где она сделана.
Глава 15. Реализация на Python
15.1. Зачем нужен интерпретатор
Маркетологи хотят сами задавать правила скидок: «сумма больше 5000 и клиент постоянный или промокод SALE». Аналитики пишут фильтры для отчётов, администраторы — правила маршрутизации писем. Каждый раз переписывать код под новое правило нельзя, а давать людям писать Python — опасно.
Интерпретатор задаёт грамматику небольшого языка и представляет каждое предложение языка деревом объектов. Каждый вид узла знает, как вычислить себя. Конечные узлы (числа, переменные) — терминальные выражения, составные (и, или, +) — нетерминальные. Дерево вычисляется рекурсивно в заданном контексте.
Паттерн хорошо подходит для простых языков: правил, фильтров, формул, команд. Для сложных языков нужны генераторы парсеров и компиляторы, но идея дерева выражений остаётся той же — модуль ast самого Python представляет программы именно так.
15.2. Участники и схема

Abstract Expression — общий интерфейс eval(context).
Terminal Expression — листья грамматики.
Nonterminal Expression — правила, содержащие другие выражения.
Context — глобальная информация для вычисления (значения переменных).
Client — строит дерево (обычно парсером) и запускает вычисление.
15.3. Классический пример: калькулятор с переменными
Файл 01_calculator.py :

Листинг 15.1 — Классический пример: калькулятор с переменными

Листинг 15.1 (продолжение) — Классический пример: калькулятор с переменными

Листинг 15.1 (продолжение) — Классический пример: калькулятор с переменными

Листинг 15.1 (продолжение) — Классический пример: калькулятор с переменными
Разбор. Работа разделена на две части. Парсер — рекурсивный спуск — превращает текст в дерево: каждому правилу грамматики соответствует метод, и приоритет операций задаётся тем, что term (умножение) вызывается из expr (сложения). Само вычисление — дело узлов: BinOp.eval вычисляет детей и применяет операцию. Одно дерево можно вычислить в разных контекстах, не разбирая текст повторно.
Последняя строка показывает само дерево: умножение b * 2 стало правым поддеревом сложения, потому что связывает сильнее.
15.4. Язык правил
Файл 02_rules.py :

Листинг 15.2 — Язык правил

Листинг 15.2 (продолжение) — Язык правил

Листинг 15.2 (продолжение) — Язык правил
Разбор. Правило — дерево из пяти видов узлов. Его можно построить в коде, загрузить из JSON или разобрать из текста, а затем применить к тысячам заказов. all и any вычисляют части лениво: если первое условие И ложно, второе не проверяется. Метод __str__ превращает дерево обратно в понятный человеку текст, удобный для интерфейса администратора.
15.5. Модификации паттерна
Интерпретатор на модуле ast
Чтобы не писать парсер, можно разобрать выражение стандартным модулем ast и интерпретировать только разрешённые узлы. Это безопасная альтернатива eval.
Файл 03_safe_ast.py :

Листинг 15.3 — Модификации паттерна

Листинг 15.3 (продолжение) — Модификации паттерна
Разбор. ast.parse даёт готовое дерево выражения, а наш интерпретатор обходит его оператором match и выполняет только явно разрешённые узлы: числа, известные имена, арифметику и функции из белого списка. Всё остальное — вызовы атрибутов, импорт, доступ к __class__ — отклоняется. Отдельная проверка запрещает огромные степени, которые могли бы надолго занять процессор.
Компиляция дерева в функцию
Обходить дерево при каждом вычислении медленно. Дерево можно один раз «скомпилировать» в замыкание.
Файл 04_compile.py :

Листинг 15.4 — Модификации паттерна

Листинг 15.4 (продолжение) — Модификации паттерна
Разбор. interpret при каждом вызове заново проверяет типы узлов и ищет операции. compile_tree делает эту работу один раз и возвращает вложенные замыкания, где всё уже решено. Аргументы по умолчанию (name=t, v=t) фиксируют значения в момент создания лямбды. Такой приём — промежуточный шаг между интерпретатором и настоящим компилятором.
15.6. Самостоятельные работы
Работа 1. Мини-язык команд для робота
Задание. Робот понимает программу вида ВПЕРЁД 3; НАЛЕВО; ПОВТОР 2 [ ВПЕРЁД 1; НАПРАВО ]. Разберите её в дерево и выполните, выводя итоговую позицию.
Полное решение — файл 05_robot.py :

Листинг 15.5 — Самостоятельные работы

Листинг 15.5 (продолжение) — Самостоятельные работы
Разбор. ПОВТОР — нетерминальное выражение, содержащее вложенную программу; парсер рекурсивно вызывает себя для тела в скобках. Квадрат из ПОВТОР 4 возвращает робота в ту же точку и направление.
Работа 2. Поиск по тегам
Задание. Фильтр вида python & (web |!legacy) применяется к статьям с наборами тегов.
Полное решение — файл 06_tags.py :

Листинг 15.6 — Самостоятельные работы

Листинг 15.6 (продолжение) — Самостоятельные работы
Разбор. Здесь парсер сразу строит не узлы-объекты, а функции — совмещая интерпретатор с приёмом компиляции из раздела 15.5. Приоритет! > & > | задаётся порядком вложенных функций.
15.7. Типичные ошибки
eval вместо интерпретатора. eval выполняет любой код Python — для пользовательского ввода это дыра в безопасности.
Неявный приоритет операций. Без отдельного правила для умножения 2 + 3 * 4 вычислится как 20.
Нет проверки конца ввода. Парсер, разобравший начало строки, может молча проигнорировать хвост 2 + 3).
Разросшаяся грамматика. Если язык становится сложным, интерпретатор из классов превращается в сотни узлов. Пора брать генератор парсеров.
15.8. Вопросы для самопроверки
Из каких частей состоит интерпретатор?
Чем терминальное выражение отличается от нетерминального?
Как в рекурсивном спуске задаётся приоритет операций?
Почему нельзя вычислять пользовательские выражения через eval?
Как модуль ast помогает построить безопасный интерпретатор?
Что даёт компиляция дерева в замыкания?
Зачем аргументы по умолчанию в lambda env, v=t: v?
Когда паттерн «Интерпретатор» перестаёт подходить?
15.9. Ответы
Грамматика, классы узлов с методом вычисления, контекст и парсер, строящий дерево.
Терминальное — лист (число, переменная), нетерминальное содержит другие выражения.
Правило для операций с меньшим приоритетом вызывает правило для операций с большим.
eval выполнит любой код, включая доступ к файлам и системе.
Он даёт готовое дерево, а интерпретатор выполняет только разрешённые узлы.
Скорость: проверки типов и выбор операций делаются один раз, а не при каждом вычислении.
Чтобы зафиксировать значение в момент создания лямбды, а не при вызове.
Когда грамматика становится большой и сложной; тогда нужны генераторы парсеров.
Глава 15. Реализация на C++23
15.1. Зачем отделять обход от коллекции
Итератор предоставляет последовательный доступ к элементам составного объекта и хранит собственное положение обхода. Отправителю не требуется знать расположение узлов дерева, а несколько итераторов могут независимо находиться на разных позициях. В каталоге GoF это поведенческий паттерн. В C++ идеи итераторов стали частью стандартной библиотеки и обобщённых алгоритмов: один алгоритм может работать с разными контейнерами при соблюдении нужной категории итератора.

Внешний итератор позволяет клиенту управлять шагами, внутренний передаёт коллекции операцию для полного обхода. Отделение обхода упрощает повторное использование алгоритмов, но добавляет состояние и правила жизни. Изменение контейнера может сделать итераторы недействительными; правила зависят от конкретного контейнера. Независимость позиций не означает автоматическую потокобезопасность.
15.2. Классический пример: STL-совместимый обход дерева
Итератор хранит стек узлов и выполняет симметричный обход бинарного дерева поиска. Копия итератора получает собственную копию стека, поэтому её продвижение не меняет другую копию. static_assert проверяет концепт std::forward_iterator, а std::ranges::distance использует интерфейс диапазона.
Каждый листинг — отдельная программа на C++23. Обычная сборка в Ubuntu / WSL:

Полный код — 00_tree_iterator.cpp :

Листинг 15.1 — Классический пример: STL-совместимый обход дерева

Листинг 15.1 (продолжение) — Классический пример: STL-совместимый обход дерева
begin помещает в стек путь к самому левому узлу; operator++ удаляет текущий узел из стека и добавляет левую ветвь его правого поддерева. Конечный итератор имеет пустой стек. Разыменовывать end или продвигать его нельзя. Дерево должно жить дольше итераторов, а во время обхода его не следует изменять. Сравнение положения корректно для данного дерева, где каждый узел имеет единственного родителя; копирование итератора копирует стек, что стоит времени и памяти пропорционально высоте.
Пример вывода:

15.3. Девять вариантов и практика
1. External / Active Iterator
Клиент сам выбирает, когда получить следующий элемент. Задание: синхронно обходить два контейнера.
Полный код — 01_zip_iterator.cpp :

Листинг 15.2 — Девять вариантов и практика
Разбор и ограничения. next возвращает пару по текущему индексу и завершает обход при окончании более короткого контейнера. Оба контейнера должны жить дольше итератора и не должны изменяться во время обхода. Это учебный интерфейс next, а не STL-итератор.
Пример вывода:

2. Internal / Passive Iterator
Коллекция сама выполняет проход и вызывает переданную функцию. Задание: применить действие только к элементам, прошедшим предикат.
Полный код — 02_internal.cpp :

Листинг 15.3 — Девять вариантов и практика
Разбор и ограничения. for_each_if вызывает предикат для каждого элемента и действие для совпавших. Исключение предиката или действия прекращает проход и передаётся вызывающему. Порядок соответствует порядку хранения.
Пример вывода:

3. Cursor / Memento Iterator
Курсор может представлять позицию между запросами к таблице без ссылки на её внутренние узлы. Задание: постраничное чтение строк.
Полный код — 03_cursor.cpp :

Листинг 15.4 — Девять вариантов и практика

Листинг 15.4 (продолжение) — Девять вариантов и практика
Разбор и ограничения. Курсор содержит смещение и номер поколения коллекции. После добавления строки старый курсор отвергается; размер страницы не может быть нулевым. Данные находятся в памяти, а не во внешней БД. Для настоящей большой изменяемой таблицы обычно нужен устойчивый порядок и продуманный курсор по ключу, а не только смещение.
Пример вывода:

Бесплатный фрагмент закончился.
