Übersetzen von AusdrucksbaumstrukturenTranslating Expression Trees

Vorheriges – Erstellen von AusdrückenPrevious -- Building Expressions

In diesem letzten Abschnitt erfahren Sie, wie Sie auf jeden Knoten in einer Ausdrucksbaumstruktur zugreifen, während eine geänderte Kopie dieser Ausdrucksbaumstruktur erstellt wird.In this final section, you'll learn how to visit each node in an expression tree while building a modified copy of that expression tree. Dies sind die Techniken, die Sie in zwei wichtigen Szenarios verwenden werden.These are the techniques that you will use in two important scenarios. Die erste besteht darin, die Algorithmen zu verstehen, die durch eine Ausdrucksbaumstruktur ausgedrückt werden, sodass sie in eine andere Umgebung übersetzt werden können.The first is to understand the algorithms expressed by an expression tree so that it can be translated into another environment. Die zweite ist, wenn Sie den erstellten Algorithmus ändern möchten.The second is when you want to change the algorithm that has been created. Dies könnte zum Beispiel dazu dienen, Protokollierung hinzuzufügen oder Methodenaufrufe abzufangen und zu verfolgen.This might be to add logging, intercept method calls and track them, or other purposes.

Übersetzen bedeutet ZugreifenTranslating is Visiting

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.The code you build to translate an expression tree is an extension of what you've already seen to visit all the nodes in a tree. Wenn Sie eine Ausdrucksbaumstruktur übersetzen, greifen Sie auf alle Knoten zu, und erstellen während des Zugriffs auf diese die neue Struktur.When you translate an expression tree, you visit all the nodes, and while visiting them, build the new tree. Die neue Struktur enthält Verweise auf den ursprünglichen Knoten oder neue Knoten, die Sie in der Struktur platziert haben.The new tree may contain references to the original nodes, or new nodes that you have placed in the tree.

Betrachten wir dies in Aktion durch Zugriff auf eine Ausdrucksbaumstruktur und Erstellen einer neuen Struktur mit einigen Knoten zum Ersetzen.Let's see this in action by visiting an expression tree, and creating a new tree with some replacement nodes. Ersetzen wir in diesem Beispiel jede Konstante durch eine Konstante, die zehnmal so groß ist.In this example, let's replace any constant with a constant that is ten times larger. Ansonsten werden wir die Ausdrucksbaumstruktur intakt lassen.Otherwise, we'll leave the expression tree intact. Anstatt den Wert der Konstante zu lesen und sie durch eine neue Konstante zu ersetzen, führen wir diese Ersetzung durch Ersetzen des konstanten Knotens durch einen neuen Knoten durch, der die Multiplikation ausführt.Rather than reading the value of the constant, and replacing it with a new constant, we'll make this replacement by replacing the constant node with a new node that performs the multiplication.

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:Here, once you find a constant node, you create a new multiplication node whose children are the original constant, and the constant 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;
}

Durch Ersetzen des ursprünglichen Knotens durch den Ersatz wird eine neue Struktur gebildet, die unsere Änderungen enthält.By replacing the original node with the substitute, a new tree is formed that contains our modifications. Wir können dies durch Kompilieren und Ausführen der ersetzten Struktur überprüfen.We can verify that by compiling and executing the replaced tree.

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.Building a new tree is a combination of visiting the nodes in the existing tree, and creating new nodes and inserting them into the tree.

Dieses Beispiel zeigt, wie wichtig es ist, dass Ausdrucksbaumstrukturen unveränderlich sind.This example shows the importance of expression trees being immutable. Beachten Sie, dass die weiter oben erstellte neue Struktur eine Mischung aus neu erstellten Knoten und Knoten aus der vorhandenen Struktur enthält.Notice that the new tree created above contains a mixture of newly created nodes, and nodes from the existing tree. Dies ist sicher, da die Knoten in der vorhandenen Struktur nicht geändert werden können.That's safe, because the nodes in the existing tree cannot be modified. Dies kann zu beträchtlicher Effizienz beim Speicherplatz führen.This can result in significant memory efficiencies. Die gleichen Knoten können in der gesamten Struktur oder in mehreren Ausdrucksbaumstrukturen verwendet werden.The same nodes can be used throughout a tree, or in multiple expression trees. Da Knoten nicht geändert werden können, kann der gleiche Knoten wiederverwendet werden, wenn er benötigt wird.Since nodes can't be modified, the same node can be reused whenever its needed.

Durchlaufen und Ausführen einer AdditionTraversing and Executing an Addition

Lassen Sie uns dies überprüfen, indem Sie einen zweiten Besucher erstellen, der die Struktur der Additionsknoten durchläuft und das Ergebnis berechnet.Let's verify this by building a second visitor that walks the tree of addition nodes and computes the result. Hierzu können Sie einige Änderungen an dem Besucher vornehmen, den Sie bisher gesehen haben.You can do this by making a couple modifications to the vistor that you've seen so far. In dieser neuen Version wird der Besucher die partielle Summe des Additionsvorgangs bis zu diesem Punkt zurückgeben.In this new version, the visitor will return the partial sum of the addition operation up to this point. Für einen konstanten Ausdruck ist dies einfach der Wert des konstanten Ausdrucks.For a constant expression, that is simply the value of the constant expression. Für einen Additionsausdruck ist das Ergebnis die Summe der linken und rechten Operanden, sobald diese Strukturen durchlaufen wurden.For an addition expression, the result is the sum of the left and right operands, once those trees have been traversed.

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

Es ist einiges an Code, aber die Konzepte sind sehr zugänglich.There's quite a bit of code here, but the concepts are very approachable. Dieser Code besucht untergeordnete Elemente in einer ersten tiefgründigen Suche.This code visits children in a depth first search. Wenn er einen konstanten Knoten erkennt, gibt der Besucher den Wert der Konstanten zurück.When it encounters a constant node, the visitor returns the value of the constant. Nachdem der Besucher auf beide untergeordnete Elemente zugegriffen hat, werden diese untergeordneten Elemente die Summe berechnet haben, die für die Unterstruktur berechnet wurde.After the visitor has visited both children, those children will have computed the sum computed for that sub-tree. Der Additionsknoten kann jetzt seine Summe berechnen.The addition node can now compute its sum. Sobald alle Knoten in der Ausdrucksbaumstruktur aufgerufen wurden, wird die Summe berechnet worden sein.Once all the nodes in the expression tree have been visited, the sum will have been computed. Sie können die Ausführung verfolgen, indem Sie das Beispiel im Debugger ausführen und die Ausführung verfolgen.You can trace the execution by running the sample in the debugger and tracing the execution.

Wir erleichtern die Verfolgung, wie die Knoten analysiert werden und wie die Summe berechnet wird, indem wir die Struktur durchlaufen.Let's make it easier to trace how the nodes are analyzed and how the sum is computed by travsersing the tree. Hier ist eine aktualisierte Version der Aggregatmethode, die ziemlich viel Ablaufverfolgungsinformationen enthält:Here's an updated version of the Aggregate method that includes quite a bit of tracing information:

private static int Aggregate(Expression exp)
{
    if (exp.NodeType == ExpressionType.Constant)
    {
        var constantExp = (ConstantExpression)exp;
        Console.Error.WriteLine($"Found Constant: {constantExp.Value}");
        return (int)constantExp.Value;
    }
    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");
}

Es auf demselben Ausdruck auszuführen, ergibt die folgende Ausgabe:Running it on the same expression yields the following output:

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.Trace the output and follow along in the code above. 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.You should be able to work out how the code visits each node and computes the sum as it goes through the tree and finds the sum.

Jetzt sehen wir uns eine andere Ausführung mit dem von sum1 zur Verfügung gestellten Ausdruck an:Now, let's look at a different run, with the expression given by sum1:

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

Hier ist die Ausgabe von der Untersuchung dieses Ausdrucks:Here's the output from examining this expression:

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.While the final answer is the same, the tree traversal is completely different. Die Knoten werden in einer anderen Reihenfolge zurückgelegt, da die Struktur mit verschiedenen Vorgängen zuerst erstellt wurde.The nodes are traveled in a different order, because the tree was constructed with different operations occurring first.

Weitere InformationenLearning More

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.This sample shows a small subset of the code you would build to traverse and interpret the algorithms represented by an expression tree. Für eine vollständige Beschreibung aller notwendigen Arbeiten zur Erstellung einer allgemeinen Bibliothek, die Ausdrucksbaumstrukturen in eine andere Sprache übersetzt, lesen Sie diese Serie von Matt Warren.For a complete discussion of all the work necessary to build a general purpose library that translates expression trees into another language, please read this series by Matt Warren. Es wird bis ins Detail erklärt, wie jeder Code übersetzt wird, den Sie in einer Ausdrucksbaumstruktur finden könnten.It goes into great detail on how to translate any of the code you might find in an expression tree.

Ich hoffe, dass Sie jetzt die tatsächliche Leistungsfähigkeit von Ausdrucksbaumstrukturen gesehen haben.I hope you've now seen the true power of expression trees. Sie können einen Satz von Code untersuchen, alle Änderungen vornehmen, die Sie für diesen Code haben möchten, und die geänderte Version ausführen.You can examine a set of code, make any changes you'd like to that code, and execute the changed version. Da die Ausdrucksbaumstrukturen unveränderlich sind, können Sie neue Strukturen mithilfe der Komponenten von vorhandenen Strukturen erstellen.Because the expression trees are immutable, you can create new trees by using the components of existing trees. Dies minimiert die Menge an erforderlichem Arbeitsspeicher, um geänderte Ausdrucksbaumstrukturen zu erstellen.This minimizes the amount of memory needed to create modified expression trees.

Weiter – SchlussbemerkungNext -- Summing up