Übersetzen von Ausdrucksbaumstrukturen
In diesem Artikel erfahren Sie, wie Sie auf jeden Knoten in einer Ausdrucksbaumstruktur zugreifen, während eine geänderte Kopie dieser Ausdrucksbaumstruktur erstellt wird. Sie übersetzen Ausdrucksbaumstrukturen, um die Algorithmen zu verstehen, sodass sie in eine andere Umgebung übersetzt werden können. Sie ändern den Algorithmus, der erstellt wurde. Sie könnten zum Beispiel Protokollierung hinzufügen, Methodenaufrufe abfangen und verfolgen oder Sonstiges tun.
Der Code, den Sie erstellen, um eine Ausdrucksbaumstruktur zu übersetzen, ist eine Erweiterung von dem, was Sie bereits gesehen haben, um auf alle Knoten in einer Struktur zuzugreifen. Wenn Sie eine Ausdrucksbaumstruktur übersetzen, greifen Sie auf alle Knoten zu, und erstellen während des Zugriffs auf diese die neue Struktur. Die neue Struktur kann Verweise auf den ursprünglichen Knoten enthalten, oder auf neue Knoten, die Sie in der Struktur platziert haben.
Wir betrachten eine Ausdrucksbaumstruktur und erstellen eine neue Struktur mit einigen Ersetzungsknoten. In diesem Beispiel ersetzen wir jede Konstante durch eine Konstante, die zehnmal so groß ist. Ansonsten lassen Sie die Ausdrucksbaumstruktur intakt. Anstatt den Wert der Konstante zu lesen und sie durch eine neue Konstante zu ersetzen, führen Sie diese Ersetzung durch Ersetzen des konstanten Knotens durch einen neuen Knoten durch, der die Multiplikation ausführt.
Hier erstellen Sie, sobald Sie einen konstanten Knoten gefunden haben, einen neuen Multiplikationsknoten, dessen untergeordnete Elemente die ursprünglichen Konstanten sind, und die Konstante 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;
}
Erstellen Sie eine neue Struktur, indem Sie den ursprünglichen Knoten durch den Ersatz ersetzen. Sie überprüfen dies durch Kompilieren und Ausführen der ersetzten Struktur.
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);
Das Erstellen einer neuen Struktur ist eine Kombination aus dem Zugriff auf die Knoten in der vorhandenen Struktur und dem Erstellen und Einfügen neuer Knoten in die Struktur. Das obige Beispiel zeigt, wie wichtig es ist, dass Ausdrucksbaumstrukturen unveränderlich sind. Beachten Sie, dass die im obigen Code erstellte Struktur eine Mischung aus neu erstellten Knoten und Knoten aus der vorhandenen Struktur enthält. Knoten können in beiden Strukturen verwendet werden, da die Knoten in der vorhandenen Struktur nicht geändert werden können. Die Wiederverwendung von Knoten führt zu erheblichen Speichereffizienzen. Die gleichen Knoten können in der gesamten Struktur oder in mehreren Ausdrucksbaumstrukturen verwendet werden. Da Knoten nicht geändert werden können, kann der gleiche Knoten wiederverwendet werden, wenn er benötigt wird.
Durchlaufen und Ausführen einer Addition
Lassen Sie uns die neue Struktur überprüfen, indem Sie einen zweiten Besucher erstellen, der die Struktur der Additionsknoten durchläuft und das Ergebnis berechnet. Nehmen Sie einige Änderungen an dem Besucher vor, den Sie bisher gesehen haben. In dieser neuen Version gibt der Besucher die partielle Summe des Additionsvorgangs bis zu diesem Punkt zurück. Für einen konstanten Ausdruck ist dies einfach der Wert des konstanten Ausdrucks. Für einen Additionsausdruck ist das Ergebnis die Summe der linken und rechten Operanden, sobald diese Strukturen durchlaufen wurden.
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);
Dies ist einiges an Code, aber die Konzepte sind zugänglich. Dieser Code besucht untergeordnete Elemente in einer ersten tiefgründigen Suche. Wenn er einen konstanten Knoten erkennt, gibt der Besucher den Wert der Konstanten zurück. Nachdem der Besucher auf beide untergeordnete Elemente zugegriffen hat, haben diese untergeordneten Elemente die Summe für die Unterstruktur berechnet. Der Additionsknoten kann jetzt seine Summe berechnen. Sobald alle Knoten in der Ausdrucksbaumstruktur aufgerufen wurden, ist die Summe berechnet worden. Sie können die Ausführung verfolgen, indem Sie das Beispiel im Debugger ausführen und die Ausführung verfolgen.
Wir erleichtern die Verfolgung, wie die Knoten analysiert werden und wie die Summe berechnet wird, indem wir die Struktur durchlaufen. Hier ist eine aktualisierte Version der Aggregatmethode, die ziemlich viel Ablaufverfolgungsinformationen enthält:
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");
}
Die Ausführung auf demselben sum-Ausdruck ergibt die folgende Ausgabe:
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
Verfolgen Sie die Ausgabe und folgen Sie dem obigen Code. Sie sollten in der Lage sein zu ermitteln, wie der Code auf jeden Knoten zugreift und die Summe berechnet, während er die Struktur durchläuft und die Summe ermittelt.
Jetzt sehen wir uns eine andere Ausführung mit dem von sum1 zur Verfügung gestellten Ausdruck an:
Expression<Func<int>> sum1 = () => 1 + (2 + (3 + 4));
Hier ist die Ausgabe von der Untersuchung dieses Ausdrucks:
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
Während die endgültige Antwort identisch ist, ist das Durchlaufen der Struktur unterschiedlich. Die Knoten werden in einer anderen Reihenfolge zurückgelegt, da die Struktur mit verschiedenen Vorgängen zuerst erstellt wurde.
Erstellen einer geänderten Kopie
Erstellen Sie ein neues Konsolenanwendungsprojekt. Fügen Sie der Datei eine using-Anweisung für den System.Linq.Expressions-Namespace hinzu. Fügen Sie die AndAlsoModifier-Klasse in Ihr Projekt ein.
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);
}
}
Diese Klasse erbt die ExpressionVisitor-Klasse und ist darauf spezialisiert, Ausdrücke zu verändern, die bedingte AND-Vorgänge darstellen. Es ändert diese Vorgänge von einem bedingten AND in ein bedingtes OR. Die Klasse setzt die VisitBinary-Methode des Basistyps außer Kraft, weil bedingte AND-Ausdrücke als binäre Ausdrücke dargestellt werden. Für die VisitBinary-Methode gilt Folgendes: Wenn der an die Methode übergebene Ausdruck eine bedingte AND-Operation darstellt, erstellt der Code einen neuen Ausdruck, der den bedingten Operator OR anstelle des bedingten Operators AND enthält. Wenn der an VisitBinary übergebene Ausdruck keinen bedingten AND-Vorgang darstellt, verzögert die Methode die Implementierung der Basisklasse. Die Basisklassenmethode erstellt Knoten, die den übergebenen Ausdrucksbaumstrukturen gleichen. In diesem Fall sind die Teilstrukturen der Knoten jedoch durch die vom Besucher rekursiv erstellten Ausdrucksbaumstrukturen ersetzt.
Fügen Sie der Datei eine using-Anweisung für den System.Linq.Expressions-Namespace hinzu. Fügen Sie der Main-Methode in der Datei „Program.cs“ Code hinzu, um eine Ausdrucksbaumstruktur zu erstellen, und übergeben Sie diese Struktur an die Methode, die sie ändert.
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"))
*/
Der Code erstellt einen Ausdruck, der einen bedingten AND-Vorgang enthält. Er erstellt anschließend eine Instanz der AndAlsoModifier-Klasse und übergibt den Ausdruck an die Modify-Methode dieser Klasse. Sowohl der ursprüngliche als auch der geänderte Ausdrucksbaum werden ausgegeben, um die Änderungen zu zeigen. Kompilieren Sie die Anwendung, und führen Sie sie aus.
Weitere Informationen
Dieses Beispiel zeigt eine kleine Teilmenge des Codes, den Sie erstellen möchten, um die durch eine Ausdrucksbaumstruktur dargestellten Algorithmen zu durchlaufen und zu interpretieren. Informationen zur Erstellung einer allgemeinen Bibliothek, die Ausdrucksbaumstrukturen in eine andere Sprache übersetzt, finden Sie in dieser Serie von Matt Warren. Es wird bis ins Detail erklärt, wie jeder Code übersetzt wird, den Sie in einer Ausdrucksbaumstruktur finden könnten.
Jetzt haben Sie die tatsächliche Leistungsfähigkeit von Ausdrucksbaumstrukturen gesehen. Sie untersuchen einen Satz von Code, nehmen alle gewünschten Änderungen für diesen Code vor, und führen die geänderte Version aus. Da die Ausdrucksbaumstrukturen unveränderlich sind, erstellen Sie neue Strukturen mithilfe der Komponenten vorhandener Strukturen. Die Wiederverwendung von Knoten minimiert die zum Erstellen geänderter Ausdrucksbaumstrukturen erforderliche Arbeitsspeichermenge.
