Преобразование деревьев выражений

Статья
03/02/2024

В этой статье вы узнаете, как посетить каждый узел в дереве выражений при создании измененной копии этого дерева выражений. Вы переводите деревья выражений, чтобы понять алгоритмы, чтобы его можно было преобразовать в другую среду. Вы изменяете созданный алгоритм. Вы можете добавлять журналы, перехватывать вызовы методов и отслеживать их или другие цели.

Код, создаваемый для преобразования дерева выражения, является расширением кода, который используется для обхода всех узлов в дереве. Во время преобразования дерева выражения вы выполняете обход всех узлов и, таким образом, построение нового дерева. Новое дерево может содержать ссылки на исходные узлы или новые узлы, помещенные в дерево.

Давайте посетите дерево выражений и создадим новое дерево с некоторыми узлами замены. В этом примере давайте заменим любую константу константой, которая составляет 10 раз больше. В противном случае дерево выражений остается нетронутым. Вместо того, чтобы считывать значение константы и заменять его новой константой, замените этот узел константой новым узлом, выполняющим умножение.

После поиска постоянного узла создается новый узел умножения, дочерние элементы которого являются исходной константой и константой 10:

private static Expression ReplaceNodes(Expression original)
{
    if (original.NodeType == ExpressionType.Constant)
    {
        return Expression.Multiply(original, Expression.Constant(10));
    }
    else if (original.NodeType == ExpressionType.Add)
    {
        var binaryExpression = (BinaryExpression)original;
        return Expression.Add(
            ReplaceNodes(binaryExpression.Left),
            ReplaceNodes(binaryExpression.Right));
    }
    return original;
}

Создайте новое дерево, заменив исходный узел заменой. Вы проверяете изменения путем компиляции и выполнения замененного дерева.

var one = Expression.Constant(1, typeof(int));
var two = Expression.Constant(2, typeof(int));
var addition = Expression.Add(one, two);
var sum = ReplaceNodes(addition);
var executableFunc = Expression.Lambda(sum);

var func = (Func<int>)executableFunc.Compile();
var answer = func();
Console.WriteLine(answer);

Создание нового дерева представляет собой сочетание обхода узлов в существующем дереве и создания новых узлов и вставки их в дерево. В предыдущем примере показано важность неизменяемых деревьев выражений. Обратите внимание, что новое дерево, созданное в предыдущем коде, содержит смесь только что созданных узлов и узлов из существующего дерева. Узлы можно использовать в обоих деревьях, так как узлы в существующем дереве не могут быть изменены. Повторное использование узлов приводит к значительной эффективности памяти. Одни и те же узлы можно использовать в одном дереве или в нескольких деревьях выражений. Поскольку узлы нельзя изменить, один узел можно при необходимости использовать повторно.

Обход и выполнение добавления

Давайте проверим новое дерево, создав второй посетитель, который проходит дерево узлов сложения и вычисляет результат. Сделайте пару изменений для посетителя, который вы видели до сих пор. В этой новой версии посетитель возвращает частичную сумму операции добавления до этой точки. Для константного выражения это просто значение константного выражения. Для выражения добавления результатом будет сумма левого и правого операндов, поскольку выполняется обход этих деревьев.

var one = Expression.Constant(1, typeof(int));
var two = Expression.Constant(2, typeof(int));
var three = Expression.Constant(3, typeof(int));
var four = Expression.Constant(4, typeof(int));
var addition = Expression.Add(one, two);
var add2 = Expression.Add(three, four);
var sum = Expression.Add(addition, add2);

// Declare the delegate, so you can call it
// from itself recursively:
Func<Expression, int> aggregate = null!;
// Aggregate, return constants, or the sum of the left and right operand.
// Major simplification: Assume every binary expression is an addition.
aggregate = (exp) =>
    exp.NodeType == ExpressionType.Constant ?
    (int)((ConstantExpression)exp).Value :
    aggregate(((BinaryExpression)exp).Left) + aggregate(((BinaryExpression)exp).Right);

var theSum = aggregate(sum);
Console.WriteLine(theSum);

Здесь есть довольно немного кода, но основные понятия подходят. Этот код обходит дочерние элементы при поиске в глубину. При обнаружении узла константы посетитель возвращает значение этой константы. После того, как посетитель посетил обоих детей, эти дети вычислили сумму, вычисленную для этой поддеревки. Теперь добавленный узел может вычислить свою сумму. После посещения всех узлов в дереве выражений сумма вычисляется. Вы можете отслеживать выполнение, запустив пример в отладчике с трассировкой выполнения.

Мы можем упростить трассировку анализа узлов и вычисления суммы путем обхода дерева. Вот обновленная версия метода агрегирования, который включает совсем немного данных трассировки:

private static int Aggregate(Expression exp)
{
    if (exp.NodeType == ExpressionType.Constant)
    {
        var constantExp = (ConstantExpression)exp;
        Console.Error.WriteLine($"Found Constant: {constantExp.Value}");
        if (constantExp.Value is int value)
        {
            return value;
        }
        else
        {
            return 0;
        }
    }
    else if (exp.NodeType == ExpressionType.Add)
    {
        var addExp = (BinaryExpression)exp;
        Console.Error.WriteLine("Found Addition Expression");
        Console.Error.WriteLine("Computing Left node");
        var leftOperand = Aggregate(addExp.Left);
        Console.Error.WriteLine($"Left is: {leftOperand}");
        Console.Error.WriteLine("Computing Right node");
        var rightOperand = Aggregate(addExp.Right);
        Console.Error.WriteLine($"Right is: {rightOperand}");
        var sum = leftOperand + rightOperand;
        Console.Error.WriteLine($"Computed sum: {sum}");
        return sum;
    }
    else throw new NotSupportedException("Haven't written this yet");
}

Выполнение выражения sum дает следующие выходные данные:

10
Found Addition Expression
Computing Left node
Found Addition Expression
Computing Left node
Found Constant: 1
Left is: 1
Computing Right node
Found Constant: 2
Right is: 2
Computed sum: 3
Left is: 3
Computing Right node
Found Addition Expression
Computing Left node
Found Constant: 3
Left is: 3
Computing Right node
Found Constant: 4
Right is: 4
Computed sum: 7
Right is: 7
Computed sum: 10
10

Трассировка выходных данных и следуйте инструкциям в приведенном выше коде. Вы наверняка поймете, каким образом код обходит каждый узел и вычисляет сумму по мере обхода дерева и нахождения суммы.

Теперь рассмотрим другое выполнение, где выражение задается объектом sum1:

Expression<Func<int>> sum1 = () => 1 + (2 + (3 + 4));

Ниже вы видите выходные данные проверки этого выражения:

Found Addition Expression
Computing Left node
Found Constant: 1
Left is: 1
Computing Right node
Found Addition Expression
Computing Left node
Found Constant: 2
Left is: 2
Computing Right node
Found Addition Expression
Computing Left node
Found Constant: 3
Left is: 3
Computing Right node
Found Constant: 4
Right is: 4
Computed sum: 7
Right is: 7
Computed sum: 9
Right is: 9
Computed sum: 10
10

Хотя окончательный ответ один и тот же, древовидная обход отличается. Узлы обходятся в другом порядке, так как дерево было создано с помощью других начальных операций.

Создание измененной копии

Создайте новый проект консольного приложения. Добавьте в файл директиву using для пространства имен System.Linq.Expressions. Добавьте в проект класс AndAlsoModifier.

public class AndAlsoModifier : ExpressionVisitor
{
    public Expression Modify(Expression expression)
    {
        return Visit(expression);
    }

    protected override Expression VisitBinary(BinaryExpression b)
    {
        if (b.NodeType == ExpressionType.AndAlso)
        {
            Expression left = this.Visit(b.Left);
            Expression right = this.Visit(b.Right);

            // Make this binary expression an OrElse operation instead of an AndAlso operation.
            return Expression.MakeBinary(ExpressionType.OrElse, left, right, b.IsLiftedToNull, b.Method);
        }

        return base.VisitBinary(b);
    }
}

Этот класс наследует класс ExpressionVisitor и специально предназначен для изменения выражений, которые представляют условные операции AND. Он изменяет эти операции с условного AND на условное OR. Класс переопределяет VisitBinary метод базового типа, так как условные AND выражения представлены как двоичные выражения. Если выражение, переданное в метод VisitBinary, представляет условную операцию AND, код создает новое выражение, которое содержит условный оператор OR вместо условного оператора AND. Если переданное выражение VisitBinary не представляет условную AND операцию, метод отложит реализацию базового класса. Методы базового класса создают узлы, такие как деревья выражений, которые передаются, но узлы заменяют их вложенными деревьями, замененными деревьями выражений, созданными рекурсивно посетителем.

Добавьте в файл директиву using для пространства имен System.Linq.Expressions. Добавьте код в Main метод в файле Program.cs, чтобы создать дерево выражений и передать его в метод, который изменяет его.

Expression<Func<string, bool>> expr = name => name.Length > 10 && name.StartsWith("G");
Console.WriteLine(expr);

AndAlsoModifier treeModifier = new AndAlsoModifier();
Expression modifiedExpr = treeModifier.Modify((Expression)expr);

Console.WriteLine(modifiedExpr);

/*  This code produces the following output:

    name => ((name.Length > 10) && name.StartsWith("G"))
    name => ((name.Length > 10) || name.StartsWith("G"))
*/

В приведенном ниже коде создается выражение, которое содержит условную операцию AND. Затем в нем создается экземпляр класса AndAlsoModifier, и в метод Modify этого класса передается выражение. Как исходные, так и измененные деревья выражений выводятся для отображения изменения. Скомпилируйте и запустите приложение.

Подробнее

В этом примере показана малая часть кода, который необходимо создать для обхода и интерпретации алгоритмов, представляемых деревом выражения. Сведения о создании библиотеки общего назначения, которая преобразует деревья выражений на другой язык, см . в этой серии Мэтт Уоррен. Здесь преобразование кода, который можно найти в дереве выражения, рассматривается гораздо подробнее.

Теперь вы видели истинную силу деревьев выражений. Вы проверяете набор кода, вносите изменения в этот код и выполняете измененную версию. Так как деревья выражений неизменяемы, вы создаете новые деревья с помощью компонентов существующих деревьев. Повторное использование узлов сводит к минимуму объем памяти, необходимой для создания измененных деревьев выражений.

Поделиться через

Преобразование деревьев выражений

Обход и выполнение добавления

Создание измененной копии

Подробнее

Дополнительные ресурсы