Введение
История движется по спирали. Авторы Go, встав на плечи авторитетной корпорации Google, смогли воплотить свой идеальный язык программирования в жизнь, как когда-то Никлаус Вирт принес в этот мир язык Оберон, собственной непоколебимостью и авторитетом борясь с зарождавшимся трендом усложнения и экстенсивного развития мейнстрим-языков.
Сегодня язык Оберон забыт, но дело Вирта проявилось в языке Go совершенно неожиданно. В некоторых аспектах реализации сходство подходов не вызывает сомнений. Конечно, каждый язык по-своему уникален и нет нужды из одного языка делать другой. Время не повернуть назад. Но в разное время люди стремились сохранить технологии, ушедшие в прошлое. Чего стоят бережно хранимые эмуляторы Спектрума и MSX, музеи старых компьютеров в разных странах. Эмуляция, как один из способов остановить мгновение прочно зарекомендовал себя.
Общепринято считать, что язык Go нашел себя в нише сетевых сервисов. Но мы пойдем другим путем.
Задача
История языка Оберон насчитывает несколько вариантов языка. Каждую редакцию Н. Вирт создавал под какой-то конкретный проект, его языки всегда были созданы под задачу исходя из её целей. Оберон-2 создавался как вариант Оберона с развитым механизмом типов данных, реализуя концепцию ООП. Ученики Н. Вирта решили, что именно Оберон-2 подходит для промышленного программирования. Они дополнили язык фичами, нарастили систему типов до совместимой с набиравшей популярность Java, реализовали идею истинной модульности и выпустили продукт BlackBox с языком Компонентный Паскаль (КП) внутри.
Шло время, корпорации из-за океана более успешно вышли на рынок и BlackBox ушел в тень, оставаясь объектом исследования небольшой группы энтузиастов, в том числе из России и стран СНГ.
Один из принципов КП — модульность, возможность смены реализации компонента без смены его интерфейса (в применении к объектам это называется pimpl). И вот я подумал, а чем конкретный фреймворк отличается от реализации компонента. И описание языка — интерфейс Его… Проще говоря, мне пришло в голову реализовать интерпретатор с функциями фреймворка. То есть с поддержкой модульности, как она описана в сообщении о языке.
Расследование
Особенностью фреймворка BlackBox является динамическая линковка модулей в памяти процесса. Как известно, процесс создания программы из исходного кода состоит из нескольких этапов. В разных реализациях различных компиляторов эти этапы могут быть скрыты, пропущены, примитивизированы. Линковка это приведение машинного кода к виду, приемлимому для непосредственного исполнения процессором. Например в Go линковка статическая, на этапе компиляции. А в BlackBox динамическая, на этапе загрузки тела модуля в память. Интересной особенностью такого решения является независимость кода от операционной системы, когда один и тот же машинный код исполняется в разных ОС без перекомпиляции, при условии одинаковой архитектуры (x86, например).
Однако, в компиляторе BlackBox предусмотрена еще одна возможность — смена кодогенератора для конкретной архитектуры. Достигается такой результат применением внутри компилятора структуры AST — абстрактного синтаксического дерева для платформонезависимого сохранения структуры программ и данных. Удалось выяснить, что изначально BlackBox был написан для платформы Mac+PowerPC, и только затем переписан под Wintel. При этом компилятор остался практически неизменным. Сменный backend сегодня не является чем-то удивительным, но в 90-х это было необычно и вновинку.
Таким образом, эти две особенности позволили мне создать свой backend. Без особых усилий я перевел AST в формат XML, точнее, в graphml, с прицелом на красивую визуализацию процесса интерпретации. Планов было громадье.
Решение
Для реализации я выбрал язык Go, хотя мог выбрать Java, C#, Dart и прочие. Почему? Причин несколько, основная — информация о том, что Go по своей природе похож на Оберон, отсекает все лишнее из процесса выражения предметной области. Взять хотя бы исключения, эти легкие легализованные якобы безвредные аналоги оператора GOTO.
Отличный повод изучить Go.
Проект я назвал просто: Framework.
Краткий экскурс в описание языка — и в бой. Сериализация xml в структуры с помощью тэгов — отлично. Сокрытие данных в пакетах — отлично, применим наш любимый pimpl. Утиная типизация интерфейсами поначалу смутила, но после пары шишек пришло понимание. Основная ловушка здесь — сравнение разноименных интерфейсов с одинаковым набором методов. Этот набор может сформироваться исторически, и даже опытный разработчик может обнаружить, что тайпсвитч на тип А обрабатывает тип Б и закономерно падает.
Итак, AST загружен в память, основные узлы описаны, правила интерпретации известны. Как оказалось — типов узлов немало. Типов данных еще больше. Одним из основных принципов, который я взял на вооружение, стал принцип let it fall, при любой непонятной ситуации программа завершает работу. Конечно, домашний проект позволял такие вольности.
Интерпретировать алгоритмы это интересно. AST языка КП состоит из операторов, выражений и указателей на объекты (statement, expression, designator). Операторы следуют друг за другом, изменяют объекты, меняют ход программы в зависимости от подчиненных узлов (выражений или указателей). В данном случае подчиненных узлов два — left и right. Есть так же дополнительные узлы, такие как link и object.
Для начала выберем схему обхода данных — я предположил, что выдумывать ничего не надо, все уже придумано, поэтому применил стек для обработки узлов в глубину и нерекурсивный обход узлов от одного выражения к другому. Каждому узлу в стеке соответствует фрейм, в котором хранится результат обработки дочерних узлов и указания от родительских узлов. Специфичные действия для конкретного узла и есть основная часть интерпретации программы. Программа выполняется, пока операторы, управляющие потоком исполнения добавляют в стек один или больше следующих операторов для выполнения.
Как только стек пустеет или результат выполнения итерации возвращает код ошибки — программа останавливается. Ничего сложного.
Для хранения данных в высокоуровневой среде языка Go можно описать различные типы данных, в том числе примитивные. В этом я увидел еще одно преимущество языка Go для задачи реализации интерпретатора.
Полный перечень правил, по которым составлено дерево AST можно увидеть здесь.
Пример
Коротко опишу процесс интерпретации узлов простой программы.
MODULE XevDemo2;
VAR
i: INTEGER;
PROCEDURE Init;
BEGIN
i:=1;
END Init;
PROCEDURE Stop;
BEGIN
i:=0;
END Stop;
BEGIN
Init
CLOSE
Stop
END XevDemo2.
- Дерево программы загружается в память. Обнаруживается узел EnterNode входа в программу (BEGIN), на него нацеливается интерпретатор.
- Интерпретатор кладет текущий узел (EnterNode) на стек. EnterNode дает команду на размещение переменной i, затем кладет в стек узел CallNode, то есть вызов процедуры Init.
- Текущий узел CallNode кладет в стек узел EnterNode процедуры Init.
- Узел EnterNode не размещает данных, так как в процедуре нет локальных переменных. Следущим в стек выполнения отправляется узел присваивания AssignNode.
- Узел присваивания должен вычислить указатель на объект переменной и значение справа. Для этого он кладет в стек узел VariableNode.
- VariableNode возвращает в данных фрейма адрес своего объекта.
- Узел присваивания кладет в стек узел константы. Хотя для константы можно было бы выполнить оптимизацию, но для понимания процесса я сделал обработку всех узлов-выражений единообразной.
- Узел константы просто кладет на фрейм свое значение.
- Узел присваивания берет результаты выполнения левой и правой части и выполняет обновление данных в памяти переменной.
- Так как за узлом присваивания нет никакого оператора, фрейм убирается со стека, управление переходит к узлу EnterNode.
- Узел EnterNode при завершении работы очищает данных процедуры, так как они не нужны и возвращает управление. Его фрейм так же снимается со стека.
- Далее секция CLOSE работает аналогично секции BEGIN. В многомодульных системах секция CLOSE несет важную функцию завершения работы модуля в целом.
- Процесс интерпретации завершается.
Результаты и перспективы
В данный момент интерпретатор поддерживает полный набор операторов языка КП. Так же поддерживается система типов, наследование, расширение методов и так далее, о них я не упомянул, чтобы не загромождать статью.
Отдельные проблемы есть в управлении сложными структурами данных, типа массив массивов рекордов и так далее. Но это уже вопрос времени — внимательно проверить алгоритмы работы и исправить ошибки.
Изначальные планы по созданию из языка КП специализированных DSL для разных случаев жизни пришлось отложить. Оказалось, что даже простенькая задача интерпретации не самого сложного с точки зрения фич языка КП наталкивается на проблему сложности предметной области, когда куча нюансов реализации должны вместе существовать и работать. Тут стоит пожать руку авторам JVM, можно только представить, какие задачи они решали в процессе развития среды, особенно на ранних этапах.
В копилку знаний я добавил язык Go, кучу материалов про языки программирования, интерпретацию, модифицируемую семантику языка и так далее. В конце работы я понял, что абстрактное синтаксическое дерево в его текущем виде может быть применимо не только для КП, но и для схожих императивных языков. Уже после завершения основных работ я узнал, что выпущен интерпретатор языка Lua для Go.
В некотором смысле история опять совершила движение по спирали, оказалось, что язык КП уже в 90-е годы представлял собой экстракт основных идей императивного программирования, которые, при попутном ветре могли бы радикально изменить все то, с чем мы имеем дело сейчас.
Можно только размышлять о том, как подобно эффекту бабочки шутки о «паскале для обучения» и «смешном синтаксисе» изменили будущее индустрии на десятилетия вперед.
Автор: kpmy
