Übersetzen von Ausdrucksbaumstrukturen

In diesem Artikel erfahren Sie, wie Sie jeden Knoten in einer Ausdrucksstruktur besuchen, während Sie eine geänderte Kopie dieser Ausdrucksstruktur erstellen. Sie übersetzen Ausdrucksbaumstrukturen, um die Algorithmen zu verstehen, sodass sie in eine andere Umgebung übersetzt werden können. Sie ändern den Algorithmus, der erstellt worden ist. Sie können Protokollierung hinzufügen, Methodenaufrufe abfangen und nachverfolgen oder andere Zwecke verwenden.

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 die ursprünglichen Knoten oder neue Knoten enthalten, die Sie in der Struktur platziert haben.

Wir betrachten eine Ausdrucksbaumstruktur und erstellen eine neue Struktur mit einigen Ersetzungsknoten. In diesem Beispiel ersetzen wir eine beliebige Konstante durch eine Konstante, die 10 mal größer ist. Ansonsten lassen Sie die Ausdrucksbaumstruktur intakt. Anstatt den Wert der Konstante zu lesen und durch eine neue Konstante zu ersetzen, ersetzen Sie diesen Ersatz, indem Sie den Konstantenknoten durch einen neuen Knoten ersetzen, der die Multiplikation durchführt.

Sobald Sie einen Konstantenknoten gefunden haben, erstellen Sie einen neuen Multiplikationsknoten, dessen untergeordnete Elemente die ursprüngliche Konstante und die Konstante 10sind:

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 einen neuen Baum, indem Sie den ursprünglichen Knoten durch den Ersatzknoten ersetzen. Sie überprüfen die Änderungen, indem Sie die ersetzte Struktur kompilieren und ausführen.

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 eines neuen Baumes ist eine Kombination aus dem Besuch der Knoten im vorhandenen Baum und dem Erstellen neuer Knoten sowie ihrer Einfügung in den Baum. Das vorherige Beispiel zeigt die Bedeutung von Ausdrucksstrukturen, die unveränderlich sind. Beachten Sie, dass die im vorherigen Code erstellte neue Struktur eine Mischung aus neu erstellten Knoten und Knoten aus der vorhandenen Struktur enthält. Knoten können in beiden Bäumen verwendet werden, da die Knoten im vorhandenen Baum nicht geändert werden können. Die Wiederverwendung von Knoten führt zu erheblichen Speichereffizienzen. Die gleichen Knoten können im gesamten Baum oder in mehreren Ausdrucksbäumen verwendet werden. Da Knoten nicht geändert werden können, kann derselbe Knoten bei Bedarf wiederverwendet werden.

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 Teilsumme des Additionsvorgangs bis zu diesem Punkt zurück. Bei einem Konstantenausdruck ist es einfach der Wert des Konstantenausdrucks. 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);

Hier gibt es ein wenig Code, aber die Konzepte sind erreichbar. 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 nun seine Summe berechnen. Sobald alle Knoten in der Ausdrucksbaumstruktur aufgerufen wurden, ist die Summe berechnet worden. Sie können die Ausführung nachverfolgen, indem Sie das Beispiel im Debugger ausführen und die Ausführung nachverfolgen.

Lassen Sie uns es einfacher machen, nachzuvollziehen, wie die Knoten analysiert werden und wie die Summe berechnet wird, indem wir den Baum 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 für den using Namespace eine System.Linq.Expressions Direktive hinzu. Fügen Sie die AndAlsoModifier Klasse zu Ihrem Projekt hinzu.

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 ändern, die bedingte AND Vorgänge darstellen. Sie verändert diese Vorgänge von einer bedingten AND zu einer bedingten OR. Die Klasse überschreibt die VisitBinary Methode des Basistyps, da bedingte AND Ausdrücke als binäre Ausdrücke dargestellt werden. In der VisitBinary-Methode, wenn der Ausdruck, der an sie übergeben wird, einen bedingten AND-Vorgang darstellt, erstellt der Code einen neuen Ausdruck, der den bedingten OR-Operator anstelle des bedingten AND-Operators enthält. Wenn der Ausdruck, der an VisitBinary übergeben wird, keinen bedingten AND Vorgang darstellt, greift die Methode auf die Implementierung der Basisklasse zurück. 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 für den using Namespace eine System.Linq.Expressions Direktive 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. Anschließend wird eine Instanz der AndAlsoModifier Klasse erstellt und der Ausdruck an die Modify Methode dieser Klasse übergeben. Sowohl der ursprüngliche als auch der geänderte Ausdrucksbaum werden ausgegeben, um die Veränderung anzuzeigen. Kompilieren Sie die Anwendung, und führen Sie sie aus.

Erfahren Sie mehr

Dieses Beispiel zeigt eine kleine Teilmenge des Codes, den Sie erstellen würden, um die algorithmen zu durchlaufen und zu interpretieren, die durch eine Ausdrucksstruktur dargestellt werden. Informationen zum Erstellen einer allgemeinen Bibliothek, die Ausdrucksbäume in eine andere Sprache übersetzt, lesen Sie in dieser Serie von Matt Warren. Es wird ausführlich beschrieben, wie Sie jeden Code, den Sie möglicherweise in einem Ausdrucksbaum finden, übersetzen können.

Sie haben nun die wahre Kraft von Ausdrucksbäumen gesehen. Sie untersuchen einen Codesatz, nehmen alle Gewünschten Änderungen an diesem Code vor und führen die geänderte Version aus. Da die Ausdrucksstrukturen unveränderlich sind, erstellen Sie neue Strukturen mithilfe der Komponenten vorhandener Bäume. Die Wiederverwendung von Knoten minimiert die zum Erstellen geänderter Ausdrucksbaumstrukturen erforderliche Arbeitsspeichermenge.