Библиотека сайта rus-linux.net
Среда времени выполнения динамических языков и языки Iron
Глава 8 из книги "Архитектура приложений с открытым исходным кодом", том 2.
Оригинал: The Dynamic Language Runtime and the Iron Languages
Автор: Jeff Hardy
Перевод: Н.Ромоданов
8.5. Деревья выражений
Дерево выражений (expression tree) также является представлением программы, с которым можно манипулировать во время выполнения, но в более низкогоуровневом представлении, независимым от языка. На платформе .NET, типы узлов находятся в пространстве имен System.Linq.Expressions, и все типы узлов являются производными от абстрактного класса Expression. Пространство имен является историческим артефактом; первоначально в .NET 3.5 для реализации языка интегрированных запросов LINQ - Language-Integrated Query были добавлены деревья выражений, а затем они были расширены деревьями выражений DLR. Эти деревья выражений используются не только в выражениях, хотя также есть типы узлов для инструкций if, блоков try и циклов; в некоторых языках (в Ruby, например) есть выражения и нет инструкций.
Есть узлы, которые покрывают практически все функции, которые могут потребоваться в языке программирования. Впрочем, есть тенденция определять их на достаточно низком уровне; вместо того, чтобы иметь узлы ForExpression, WhileExpression и т.д., существует один узел LoopExpression, которые в сочетании с узлом GotoExpression может описывать циклы любого типа. Для того, чтобы описывать язык на более высоком уровне, в языках можно определять свои собственные типы узлов с помощью их наследования из Expression и переопределения метода Reduce(), который возвращает другое дерево выражений. В IronPython, дерево разбора также является деревом выражений DLR, но в нем есть множество специальных узлов, которые обычно непонятны для DLR (например, ForStatement). Эти специальные узлы могут быть приведены к деревьям выражений, которые хорошо понятны в DLR (например, сочетание LoopExpressions и GotoExpressions). Эти специальные узлы выражений могут приводиться к другим специальным узлам выражений, поэтому приведение продолжается рекурсивно до тех пор, пока не останутся только узлы DLR. Одно из ключевых различий между IronPython и IronRuby состоит в том, что абстрактное синтаксическое дерево (AST) языка IronPython также является деревом выражения, а в языке IronRuby - не является. Вместо этого, прежде, чем произойдет переход на следующий этап, дерево AST языка IronRuby преобразуется в дерево выражений. На самом деле неясно, насколько полезно то, что дерево AST также может быть деревом выражений, поэтому оно не было реализовано таким образом в языке IronRuby.
Для каждого типа узла известно, как его можно сократить, причем обычно сокращение можно выполнить единственным образом. Для преобразований, которые выполняются над кодом, не находящимся в дереве — например, сворачивание констант или реализация генераторов Python в IronPython — используется подкласс класса Expression. В классе ExpressionVisitor есть метод Visit(), который вызывает метод Accept() класса Expression, а в подклассе Expression метод Accept() переопределяется таким образом, чтобы вызвать конкретный метод Visit() класса ExpressionVisitor, например, VisitBinary(). Это классическая реализация паттерна Visitor, предложенного Gamma и другими - есть фиксированный набор типов узлов, которые можно посетить, и есть бесконечное количество операций, которые над ними могут быть выполнены. Когда при разборе выражения посещается узел, то, как правило, рекурсивно посещаются его потомки, а также потомки его потомков и так далее вниз по дереву. Однако метод ExpressionVisitor не может в действительности изменить дерево при его просмотре, поскольку деревья выражений являются немутируемыми (неизменямыми). Если необходимо изменить узел (например, удалить потомков), то вместо этого следует создать новый узел, который заменит старый узел, а также всех его предков.
После того, как дерево выражений будет создано, сокращено и преобразовано к паттерну Visitor, его, в конце концов, нужно будет выполнить. Хотя деревья выражений могут быть откомпилированы непосредственно в код IL, в IronPython и IronRuby происходит их первоначальное перенаправление в интерпретатор, т. к. компиляция непосредственно в IL является слишком дорогой для кода, который, возможно, будет выполнен всего-лишь несколько раз.
Продолжение статьи: Интерпретация и компиляция