В этой статье я расскажу о двухлетнем эксперименте, проводимом над моим пет-проектом, интерпретатором ЯП HydraScript. Почему к разработке из области системного программирования были применены промышленные практики, и зачем конструированию компиляторов нужен Domain Driver Design с чистой архитектурой?
Исходники проекта доступны на GitHub.
Что такое HydraScript?
Краткое описание репозитория на GitHub гласит:
TypeScript & Go inspired open-source public research project written in C#
Но это описание состояния проекта на момент написания статьи, поэтому сейчас откачусь немного в прошлое.
Шёл 2022-й год, и мой 4-й курс бакалавриата МГТУ им. Н.Э. Баумана. Я заканчивал кафедру ИУ-9. Её направленность — «Анализ, порождение и преобразование программного кода», то есть в специализации входит, например, «создание новых языков программирования». Кстати, у кафедры есть GitHub, на мой взгляд, выглядит очень достойно!
Так вот, по окончании университета, естественно, надо было писать ВКР, в рамках которой было бы реализовано некое ПО. Конструирование компиляторов, как дисциплина, очень заинтересовала меня ещё в процессе обучения. Лично мне нравится, как в этой прикладной деятельности сходится почти вся фундаментальная теоретика компьютерных наук.
И тогда мне была назначена тема разработки интерпретатора подмножества JavaScript согласно ECMA-262. Советую ознакомиться со стандартом, если у вас возникает вопрос к JavaScript в духе: «ну почему он такой??!?!!?»
Получившаяся программа работает следующим образом.
- На вход подаётся некий фрагмент исходного кода:
function abs(x: number) { if (x < 0) return -x return x } print(abs(-10) as string) - Лексер нарезает этот фрагмент на поток токенов:
Keyword (1, 1)-(1, 9): function Ident (1, 10)-(1, 13): abs LeftParen (1, 13)-(1, 14): ( Ident (1, 14)-(1, 15): x Colon (1, 15)-(1, 16): : Ident (1, 17)-(1, 23): number RightParen (1, 23)-(1, 24): ) LeftCurl (1, 25)-(1, 26): { Keyword (2, 5)-(2, 7): if LeftParen (2, 8)-(2, 9): ( Ident (2, 9)-(2, 10): x Operator (2, 11)-(2, 12): < IntegerLiteral (2, 13)-(2, 14): 0 RightParen (2, 14)-(2, 15): ) Keyword (3, 9)-(3, 15): return Operator (3, 16)-(3, 17): - Ident (3, 17)-(3, 18): x Keyword (4, 5)-(4, 11): return Ident (4, 12)-(4, 13): x RightCurl (5, 1)-(5, 2): } Ident (7, 1)-(7, 6): print LeftParen (7, 6)-(7, 7): ( Ident (7, 7)-(7, 10): abs LeftParen (7, 10)-(7, 11): ( Operator (7, 11)-(7, 12): - IntegerLiteral (7, 12)-(7, 14): 10 RightParen (7, 14)-(7, 15): ) Keyword (7, 16)-(7, 18): as Ident (7, 19)-(7, 25): string RightParen (7, 25)-(7, 26): ) EOP - Парсер преобразует список этих токенов в абстрактное синтаксическое дерево согласно правилам грамматики:
- Далее, зависит от желания и возможностей: можно либо сразу исполнять AST, либо рассматривать его как первую форму IR (intermediate representation) и совершать статический анализ с последующей кодогенерацией:
Goto End_abs Start_abs: BeginFunction abs PopParameter x _t1648079328 = x < 0 IfNot _t1648079328 Goto End_if_else_53517805 _t1783762424 = -x Return _t1783762424 Goto End_if_else_53517805 Start_if_else_53517805: BeginCondition if_else_53517805 End_if_else_53517805: EndCondition if_else_53517805 Return x End_abs: EndFunction abs _t196877937 = -10 PushParameter _t196877937 _t3435491484 = Call abs _t4127716996 = _t3435491484 as string Print _t4127716996 End - Если есть этап кодогенерации, то, опять же, можно или сначала оптимизировать код, или сразу прогнать набор инструкций на некой встроенной виртуальной машине:
Однако вернёмся к процессу и хронологии разработки интерпретатора HydraScipt.
Цель определяет проект
Как уже было сказано, первая итерация проекта появилась в рамках написания дипломной работы.
Все мы знаем по каким двум правилам работает программист в условиях ограниченного времени:
- Работает? Не трожь!
И мой случай — не исключение...
Как нетрудно было догадаться, всё писалось на скорую руку, баги поверх багов, костыли и велосипеды, чтобы хоть как-то залатать и всё прочее подобное.
Изначально архитектуры не было вообще — сразу интерпретировалось AST, но это не позволяло добавить функции в язык, поэтому пришлось всё переписывать на минимальный кодген сценарий.
И в процессе у меня стали появляться амбиции, мол: «сейчас как напишу open-source убийцу JS, и все быстро перейдут на мой язык!»
И стал накидывать туда типизацию, базовые блоки, CFG, оптимизации — с некоторыми ограничениями оно работало!
Потом я успешно защитился и можно было немного причесать проект…
Однако стало тяжело совмещать это с работой, да и без реалити-чеков мне стало понятно, что JS не одолеть, и тогда проект снова пришлось двигать в другом направлении.
Я безусловно заинтересован в его поддержке и развитии, но сквозь время.
То есть, у меня должна быть возможность не заниматься им долго, потом прийти и не офигеть от того, насколько мне не понятно, что там написано.
И раз это уже в паблике, то было бы неплохо, чтобы другие люди тоже смогли прийти и разобраться, не обладая такими глубокими знаниями в сложной предметке компиляторов.
Поскольку планируется чистый код и всё такое, то конечно про перфоманс и реальную прикладную применимость такого интерпретируемого языка можно забыть)
Но учебная миссия, и задача публичного, понятного и доступного реверс-инжиниринга тоже важны!
Вот здесь я пришёл к DDD
Тогда он был в ходу на работе, и как-то затянуло. Начал копаться, какие там синие книжки, какие красные, доклад Мерсона и прочее.
Мне показалось: это то, что нужно: выстроив единый язык между указанной ранее предметной области и моим кодом задача по улучшению «усваиваемости» решится.
Тогда я начал описывать домен интерпретатора, и пришёл к выводу, что в моём случае он делится на три поддомена:
- FrontEnd — все сущности, которые относятся к стадии синтаксического анализа
- IR — конструкты для работы с промежуточным представлением, которые в моём случае используются в рамках статического анализа
- BackEnd — все сущности, которые рождаются в рамках кодогенерации и относятся к непосредственному исполнению кода
Забегая вперёд, такое деление прошло проверку временем, достаточно логичное со смысловой точки зрения, и наталкивало меня на правильные мысли в процессе доработки архитектуры.
Тогда я знал про неё очень мало и проект был обычным двухслойным приложением, где всё деление было исключительно по папкам…
Эту версию можно найти в ветке before.
Оставил специально в виде напоминания как делать не надо.
И на данном этапе важно поделится одним из усвоенных архитектурных уроков, который я вынес из опыта ведения этого пет-проекта:
Правильность архитектуры проверяется при внедрении нового функционала. При правильно заданной траектории архитектурной эволюции реализация сложных фич и задач будет напрашиваться сама. При этом таким образом, что это будет не повторение существующего, а нечто новое, но укладывающееся в общую канву.
Это обусловлено предыдущим спичем про DDD в контексте интерпретатора, потому что это правильное решение в начале задало всю траекторию на последующие месяцы разработки и рефакторинга.
А потом перешёл на Clean Architecture
Казалось бы, вот сказано: «в проекте DDD».
Что может пойти не так? Да, в общем-то, всё…
▍ Конечно же, были фатальные ошибки
Первой из них является выбор интрузивного подхода для работы c AST. То есть, реализация различных операций кладётся внутрь дерева виртуальным методом, который потом переопределяется вглубь иерархии. Нет, от виртуальных методов не стоит отказываться, но они подходят не для всех операций.
В данном случае идёт речь об операциях, реализация которых требует некоторого внешнего контекста. Тогда действительно стоит задуматься о функциональном подходе отделения операции от данных, потому что сущность не в состоянии инкапсулировать всё необходимое.
Попытка упаковать всё на свете внутрь иерархии привела в первую очередь к нескольким последствиям.
Ограниченность возможностей развития системы — сложность реализации новых фич росла экспоненциально.
Появились трудно исправляемые баги: статический анализ сваливался с ошибкой на корректных программах, и его пришлось отключить.
Кодогенерация присваивала инструкциям некорректный адрес, из-за чего виртуальная машина либо попадала в бесконечный цикл, либо создавался runtime exception.
Здесь очень помог паттерн Visitor, который создан для обработки структур, глобально попадающих в класс производных паттерна Composite.
Вот метод, генерирующий инструкции для унарного выражения до «Посетителя»:
public override List<Instruction> ToInstructions(int start, string temp)
{
var instructions = new List<Instruction>();
(IValue left, IValue right) right = (null, null);
if (_expression.Primary())
{
right.right = ((PrimaryExpression) _expression).ToValue();
}
else
{
instructions.AddRange(_expression.ToInstructions(start, temp));
if (_expression is MemberExpression member && member.Any())
{
var i = start + instructions.Count;
var dest = "_t" + i;
var src = instructions.Any()
? instructions.OfType<Simple>().Last().Left
: member.Id;
var instruction = member.AccessChain.Tail switch
{
DotAccess dot => new Simple(dest, (new Name(src), new Constant(dot.Id, dot.Id)), ".", i),
IndexAccess index => new Simple(dest, (new Name(src), index.Expression.ToValue()), "[]", i),
_ => throw new NotImplementedException()
};
instructions.Add(instruction);
}
right.right = new Name(instructions.OfType<Simple>().Last().Left);
}
var number = instructions.Any() ? instructions.Last().Number + 1 : start;
instructions.Add(new Simple(
temp + number, right, _operator, number
));
return instructions;
}
А вот после применения шаблона:
public AddressedInstructions Visit(UnaryExpression visitable)
{
if (visitable.Expression is PrimaryExpression primary)
return [new Simple(visitable.Operator, _valueDtoConverter.Convert(primary.ToValueDto()))];
var result = visitable.Expression.Accept(This);
var last = new Name(result.OfType<Simple>().Last().Left!);
result.Add(new Simple(visitable.Operator, last));
return result;
}
Честно сказать, сейчас не смогу рассказать, как работает первый вариант метода…
Но трудно не согласиться с тем, что второй выглядит вполне самоописываемым, практически набор предложений на английском языке.
Этого удалось добиться в том числе решением нестандартных и интересных, на мой взгляд, инженерных задач.
▍ AddressedInstructions
Главной проблемой перехода на паттерн Visitor и отделения операции от данных был переезд кодгена. Дело в том, что у старой версии метода был параметр int start, который хранил смещение в списке инструкции и позволял посчитать её целочисленный адрес.
Эта система дала сбой, в конце концов, да ещё и теперь параметр не передашь.
Хранить глобальный счётчик небезопасно, да и с точки зрения проектирования, написать класс визитора в функциональном стиле, более удачное решение с точки зрения читаемости кода.
В дебаге можно будет провалиться по цепочке вызовов и отследить, откуда пришёл невалидный результат.
В общем, систему адресации инструкций пришлось разрабатывать с нуля, и получилось интересно и неплохо.
Получилось изобрести велосипед структуру данных для адресации, которая при изменении набора элементов пересчитывает адреса за O(1).
Что это значит?
Раньше был список инструкций, где у каждой инструкции есть адрес, то есть, некоторое число:
0: a = 0
1: x = 2
2: y = a
3: print x
Мы видим, что инструкции с адресом 0 и 2 можно выкинуть, они являются мёртвым кодом. Тогда останется:
1: x = 2
3: print x
Но теперь виртуальная машина свалится с ошибкой, потому что старт у неё ноль, а правило вычисления следующего адреса по умолчанию это шаг плюс 1.
Она просто не сможет пройтись по оставшемуся набору, поэтому нужно пересчитать адреса:
0: x = 2
1: print x
И смысл в том, чтобы не бегать по массиву за линию или больше, переставляя индексы, а получать сразу корректные адреса при любом удалении/вставке/перестановке.
Для этого пришлось создать абстракцию понятия «адрес» и реализовать структуру данных, удовлетворяющую требованиям.
▍ Visitor.NET
В процессе переезда на паттерн «Посетитель» нужно было определиться с подходом к его реализации. Их на самом деле несколько. Если вы не понимаете о чём я, то посмотрите доклад Дмитрия Нестерука:
Мне был интересен ациклический вариант, он позволяет декларативно описать, какие элементы посещаются:
public class TypeSystemLoader : IVisitor,
IVisitor<ScriptBody>,
IVisitor<AbstractSyntaxTreeNode>,
IVisitor<TypeDeclaration>
{
// ...
}
Однако меня категорически не устраивает необходимость явного приведения типов при использовании:
public class ScriptBody : AbstractSyntaxTreeNode
{
public override void Accept(IVisitor visitor)
{
if (visitor is IVisitor<ScriptBody> typed)
typed.Visit(this);
}
}
Поэтому, я отказался от этой идеи и остался с классикой. Но такой компромисс тоже оказался неудачным.
Во-первых, на тот момент я не совсем правильно распределил сущности по поддоменам: узлы AST оказались в IR, хотя должны были быть во FrontEnd.
Во-вторых, классическая реализация принесла вместе с собой циклическую зависимость.
В-третьих, поддомены не были изолированы: например, FrontEnd знал про BackEnd, хотя бы потому, что этого требовала реализация паттерна.
Несмотря на все мои намерения писать чистый код, получилась какая-то спагетифицированная high-coupling-low-cohesion каша.
Пришлось переизобрести паттерн, чтобы создать типобезопасную ациклическую реализацию, которая удовлетворяет SOLID и не требует приведения типов вовсе.
www.nuget.org/packages/Visitor.NET
Получилась библиотека Visitor.NET, о которой я расскажу на Стачке в Питере 27 сентября.
А чуть позже напишу отдельную статью на Хабр, для тех, кто не смог посетить конференцию.
Если вкратце, то с помощью контравариантности удалось добиться желаемого поведения:
public interface IVisitor<in TVisitable, out TReturn>
where TVisitable : IVisitable<TVisitable>
{
TReturn Visit(TVisitable visitable);
}
public interface IVisitable<out TVisitable>
where TVisitable : IVisitable<TVisitable>
{
TReturn Accept<TReturn>(IVisitor<TVisitable, TReturn> visitor);
}
public record Operation(
char Symbol,
BinaryTreeNode Left,
BinaryTreeNode Right) : BinaryTreeNode, IVisitable<Operation>
{
public override TReturn Accept<TReturn>(
IVisitor<BinaryTreeNode, TReturn> visitor) =>
Accept(visitor);
public TReturn Accept<TReturn>(
IVisitor<Operation, TReturn> visitor) =>
visitor.Visit(this);
}
А бойлерплейт реализации потом отшлифовал инкрементальными сурс генераторами, и потом вообще хорошо стало.
www.nuget.org/packages/Visitor.NET.AutoVisitableGen
[AutoVisitable<BinaryTreeNode>]
public partial record Operation(
char Symbol,
BinaryTreeNode Left,
BinaryTreeNode Right) : BinaryTreeNode;
▍ Продвинутый статический анализ
Как уже писалось ранее, в дорефаченной версии проекта статический анализ приходилось отключать, потому что интрузивный подход породил странные и сложные баги.
Вдобавок к этому, в языке был недоступен forward reference, во многом из-за попытки заполнить таблицу символов во время работы парсера.
Снова пришлось изобретать и впервые заниматься реверс-инжинирингом, чтобы адекватно проверять семантику и получить расширяемый, устойчивый к изменениям код.
Это происходило в параллель с переосмыслением «Посетителя» и в момент, когда я понял, что мне понадобится несколько раз обходить дерево в рамках анализа, то осознал необходимость мини-фреймворка для того, чтобы клепать визиторы, как сервисы.
Получился многоступенчатый алгоритм с отдельными тонкостями реализации на каждом этапе.
Вот перечень проходов на момент написания статьи:
- Инициализация областей видимости: некоторые узлы имеют один скоуп, некоторые его углубляют. Например: функции, объекты, блоки и т. д.
- Загрузка системы типов: стандартные и пользовательские типы загружаются в таблицы символов, а потом резолвятся ссылки между ними.
- Резервирование имён: фиксация всех остальных символов. Вынесено в отдельный проход, потому что если не указан тип, то его надо явно выводить. А для вывода нужно проверять зарезервированные идентификаторы.
- Основная проверка программы: анализ выражений, вызовов функций, присваиваний и прочего.
Благодаря такому глубокому подходу код, который в TypeScript падает в рантайме, мой интерпретатор бракует в момент проверки семантики:
let x = f()
function f() {
print(x as string)
return 5
}
▍ Деление на проекты
Решения указанных выше задач и принятые архитектурные решения такие, как внедрение DDD, паттерна Visitor, проектирование сервисов с каждым коммитом всё яснее обрисовывали следующий шаг, надлежащий к исполнению. Окончательный переход на Clean Arhitecture.
Ядро предметной области, которым я оперировал: лексер, парсер, инструкция и так далее, нужно было превратить в набор строго изолированных друг от друга компонентов.
Статический анализ и кодогенерация — это фичи аппликационного слоя, реализованные с помощью визиторов в качестве сервисов.
Всякое дамп-логгирование, работа с конфигом и другая служебная история укладывалось в инфраструктурный слой, а обработчик CLI — хост, который всё это добро подключал.
Однако в процессе я неоднократно не смог проконтролировать ограничения слоёв и связей, и решил заставить компилятор контроливать ситуацию вместо тестов на ArchUnitNet.
Проекты вместо папок — это настоящая настоящая архитектурная статическая типизация
Если мы хотим, чтобы компоненты из одной папки были не зависимы от компонентов из другой, то можно заставить компилятор ругать за нарушение этого правила, путём размещения кода в разных проектах.
Кто-то может сказать, что разбив слишком мелкий, да и вообще: «в маленьком проекте как будто бы совсем не нужно, а в большом это превращается в мешанину»
Если вы так думаете, значит неправильно мыслите. Размер проекта — неправильный критерий применимости, надо смотреть на ясность предметной области. Если такой приём помогает очертить её структуру и улучшить «понимабельность», то вперёд и с песней.
Подведём итоги
После большого пройденного пути миллиона рефакторингов получился сильный проект с ООП, DDD, Clean Architecture, изолированными поддоменами, независимыми контрактами, слабосвязанными компонентами и сильносвязными модулями.
За время его ведения моя архитектурная компетенция несомненно выросла, и вот какими выводами я хочу с вами поделиться:
- Отталкивайтесь от предметной области при написании кода. Это поможет повысить ясность и читаемость кода, корректно распределить ответственность между компонентами и прийти к гибкой архитектуре, которая устойчива к изменениям.
- Избавьтесь от ощущения изобретения велосипеда. Вместо того, чтобы думать, что всё уже написано и сделано, задайте себе вопрос: «а что если нет?»
- Умейте играть в долгую. Если задача сейчас не решается, не нужно её бросать и латать костыли. Лучше признать, что вам чего-то не хватает, и двигаться маленькими шажками вширь и вглубь
- Не бойтесь изменений, принимайте их. Решения, принятые изначально, не высечены на камне. Какие-то из них могут вовсе оказаться непредсказуемо ошибочными и дорогими — нужно быть готовым работать с такими вводными
- Не бойтесь создавать сложные алгоритмы и системы. Не все задачи решаются в две строчки.
- Принимайте во внимание стоимость решений. Чем больше строк кода, тем внимательнее стоит относиться к последствиям того или иного выбора.
Приглашаю всех неравнодушных и желающих получить опыт contribution в open source внутрь issues репозитория hydrascript — там всегда есть задачи для вас.
Ещё я веду Telegram-канал StepOne, куда выкладываю много интересного контента про коммерческую разработку на C#, даю карьерные советы, рассказываю истории из личного опыта и раскрываю все тайны IT-индустрии.
© 2024 ООО «МТ ФИНАНС»
Автор: Stefanio
