Tłumaczenie drzew wyrażeń

Z tego artykułu dowiesz się, jak odwiedzić każdy węzeł w drzewie wyrażeń podczas tworzenia zmodyfikowanej kopii tego drzewa wyrażeń. Przetłumacz drzewa wyrażeń, aby zrozumieć algorytmy, aby można je było przetłumaczyć na inne środowisko. Zmieniasz utworzony algorytm. Możesz dodać rejestrowanie, przechwytywać wywołania metod i śledzić je, lub robić to w innych celach.

Kod, który tworzysz w celu tłumaczenia drzewa wyrażeń, jest rozszerzeniem tego, co już widzieliśmy, aby odwiedzić wszystkie węzły w drzewie. Podczas tłumaczenia drzewa wyrażeń należy odwiedzić wszystkie węzły i podczas ich odwiedzania skompilować nowe drzewo. Nowe drzewo może zawierać odwołania do oryginalnych węzłów lub nowych węzłów umieszczonych w drzewie.

Odwiedźmy drzewo wyrażeń i utwórzmy nowe drzewo z niektórymi zamiennymi węzłami. W tym przykładzie zastąpmy dowolną stałą stałą, która jest 10 razy większa. W przeciwnym razie pozostaw drzewo wyrażeń bez zmian. Zamiast odczytywać wartość stałej i zastępować ją nową stałą, należy zastąpić ten węzeł stałej nowym węzłem, który wykonuje mnożenie.

W tym miejscu, gdy znajdziesz węzeł stały, tworzysz nowy węzeł mnożenia, którego dziećmi są oryginalna stała oraz stała 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;
}

Utwórz nowe drzewo, zastępując oryginalny węzeł zastępcą. Zmiany można zweryfikować, kompilując i wykonując zastąpione drzewo.

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);

Tworzenie nowego drzewa to połączenie odwiedzania węzłów w istniejącym drzewie oraz tworzenia nowych węzłów i wstawiania ich do drzewa. W poprzednim przykładzie pokazano znaczenie drzew wyrażeń, które są niezmienne. Zwróć uwagę, że nowe drzewo utworzone w poprzednim kodzie zawiera kombinację nowo utworzonych węzłów i węzłów z istniejącego drzewa. Węzły mogą być używane w obu drzewach, ponieważ nie można modyfikować węzłów w istniejącym drzewie. Ponowne użycie węzłów powoduje znaczne zwiększenie wydajności pamięci. Te same węzły mogą być używane w drzewie lub w wielu drzewach wyrażeń. Ponieważ nie można modyfikować węzłów, ten sam węzeł można ponownie użyć zawsze, gdy jest to konieczne.

Przemieszczanie się i dokonanie dodawania

Zweryfikujmy nowe drzewo, tworząc drugiego wizytatora, który przejdzie przez węzły dodawania i obliczy wynik. Wprowadź kilka modyfikacji dla gościa, które widzieliście do tej pory. W tej nowej wersji odwiedzający zwraca częściową sumę operacji dodawania do tego momentu. W przypadku wyrażenia stałego jest to po prostu wartość wyrażenia stałego. W przypadku wyrażenia dodawania, wynik jest sumą lewego i prawego operandu, po przemierzeniu tych drzew.

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);

Tutaj jest dużo kodu, ale koncepcje są łatwe do zrozumienia. Ten kod odwiedza dzieci w szczegółowym wyszukiwaniu. Gdy napotka węzeł stały, odwiedzający zwraca wartość stałej. Po odwiedzeniu obu dzieci te dzieci obliczyły sumę obliczoną dla tego poddrzewa. Węzeł dodawania może teraz obliczyć sumę. Po odwiedzeniu wszystkich węzłów w drzewie wyrażeń obliczana jest suma. Możesz śledzić wykonanie, uruchamiając przykład w debugerze i śledząc wykonanie.

Ułatwimy śledzenie sposobu analizowania węzłów i sposobu obliczania sumy przez przechodzenie drzewa. Oto zaktualizowana wersja metody Aggregate, która zawiera sporo informacji diagnostycznych:

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");
}

Uruchomienie go w wyrażeniu sum daje następujące dane wyjściowe:

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

Śledź dane wyjściowe i postępuj zgodnie z przebiegiem poprzedniego kodu. Należy sprawdzić, jak kod odwiedza każdy węzeł i oblicza sumę, przechodząc przez drzewo i wyszukując sumę.

Teraz przyjrzyjmy się innemu przebiegowi, z wyrażeniem podanym przez sum1.

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

Oto dane wyjściowe z badania tego wyrażenia:

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

Mimo że ostateczna odpowiedź jest taka sama, przeszukiwanie drzewa różni się. Węzły są odwiedzane w innej kolejności, ponieważ podczas konstruowania drzewa najpierw wykonano różne operacje.

Tworzenie zmodyfikowanej kopii

Utwórz nowy projekt aplikacja konsolowa . Dodaj do pliku dyrektywę using dla przestrzeni nazw System.Linq.Expressions. Dodaj klasę AndAlsoModifier do projektu.

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);
    }
}

Ta klasa dziedziczy klasę ExpressionVisitor i jest wyspecjalizowana do modyfikowania wyrażeń reprezentujących operacje warunkowe AND . Zmienia te operacje z warunkowego AND na warunkowy OR. Klasa zastępuje metodę VisitBinary typu podstawowego, ponieważ wyrażenia warunkowe AND są reprezentowane jako wyrażenia binarne. W metodzie VisitBinary , jeśli wyrażenie przekazane do niego reprezentuje operację warunkową AND , kod tworzy nowe wyrażenie, które zawiera operator warunkowy OR zamiast operatora warunkowego AND . Jeśli przekazane do VisitBinary wyrażenie nie reprezentuje operacji warunkowej AND, metoda przechodzi do implementacji klasy bazowej. Metody klasy bazowej konstruują węzły, które są podobne do przekazywanych drzew wyrażeń, ale ich drzewa podrzędne są zastępowane przez drzewa wyrażeń tworzone rekursywnie przez odwiedzającego.

Dodaj do pliku dyrektywę using dla przestrzeni nazw System.Linq.Expressions. Dodaj kod do Main metody w pliku Program.cs, aby utworzyć drzewo wyrażeń i przekazać go do metody, która ją modyfikuje.

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"))
*/

Kod tworzy wyrażenie zawierające operację warunkową AND . Następnie tworzy wystąpienie AndAlsoModifier klasy i przekazuje wyrażenie do Modify metody tej klasy. Zarówno oryginalne, jak i zmodyfikowane drzewa wyrażeń są zwracane w celu wyświetlenia zmiany. Skompiluj i uruchom aplikację.

Dowiedz się więcej

W tym przykładzie przedstawiono mały podzbiór kodu, który można utworzyć w celu przechodzenia i interpretowania algorytmów reprezentowanych przez drzewo wyrażeń. Aby uzyskać informacje na temat tworzenia biblioteki ogólnego przeznaczenia, która tłumaczy drzewa wyrażeń na inny język, przeczytaj tę serię Matt Warren. Zawiera on szczegółowe informacje na temat sposobu tłumaczenia dowolnego kodu, który można znaleźć w drzewie wyrażeń.

Znasz już prawdziwą moc drzew wyrażeń. Sprawdzasz zestaw kodu, wprowadzasz wszelkie zmiany, które chcesz wprowadzić w tym kodzie, i wykonujesz zmienioną wersję. Ponieważ drzewa wyrażeń są niezmienne, można tworzyć nowe drzewa przy użyciu składników istniejących drzew. Ponowne użycie węzłów minimalizuje ilość pamięci potrzebnej do utworzenia zmodyfikowanych drzew wyrażeń.