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 inne cele.
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.
Przejdźmy do drzewa wyrażeń i utwórzmy nowe drzewo z niektórymi węzłami zastępczymi. 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 po znalezieniu węzła stałego utworzysz nowy węzeł mnożenia, którego elementy podrzędne są oryginalną stałą i stałą 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.
Przechodzenie i wykonywanie dodawania
Zweryfikujmy nowe drzewo, tworząc drugiego gościa, który przeprowadzi drzewo węzłów 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ą lewych i prawych operandów, gdy te drzewa zostały przechylione.
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);
W tym miejscu istnieje sporo kodu, ale koncepcje są dostępne. 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 śledzenia:
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
Prześledź dane wyjściowe i postępuj zgodnie z instrukcjami w poprzednim kodzie. Należy sprawdzić, jak kod odwiedza każdy węzeł i oblicza sumę, przechodząc przez drzewo i wyszukując sumę.
Teraz przyjrzyjmy się innego przebiegu z wyrażeniem podanym przez sum1polecenie :
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
Chociaż ostateczna odpowiedź jest taka sama, przechodzenie drzewa różni się. Węzły są przesyłane w innej kolejności, ponieważ drzewo zostało skonstruowane z różnymi operacjami występującymi najpierw.
Tworzenie zmodyfikowanej kopii
Utwórz nowy projekt aplikacja konsolowa. Dodaj dyrektywę using do pliku dla System.Linq.Expressions przestrzeni nazw. 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 na warunkowy ANDOR. 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 wyrażenie przekazane do VisitBinary elementu nie reprezentuje operacji warunkowej AND , metoda odchyli implementację klasy bazowej. Metody klasy bazowej konstruują węzły, które są podobne do drzew wyrażeń, które są przekazywane, ale węzły mają swoje drzewa podrzędne zastąpione drzewami wyrażeń tworzonymi rekursywnie przez gościa.
Dodaj dyrektywę using do pliku dla System.Linq.Expressions przestrzeni nazw. 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ń.
