Översätta uttrycksträd

I den här artikeln får du lära dig hur du besöker varje nod i ett uttrycksträd när du skapar en modifierad kopia av uttrycksträdet. Du översätter uttrycksträd för att förstå algoritmerna så att de kan översättas till en annan miljö. Du ändrar algoritmen som har skapats. Du kan lägga till loggning, avlyssna metodanrop och spåra dem eller andra syften.

Koden som du skapar för att översätta ett uttrycksträd är ett tillägg till det du redan har sett för att besöka alla noder i ett träd. När du översätter ett uttrycksträd besöker du alla noder och skapar det nya trädet när du besöker dem. Det nya trädet kan innehålla referenser till de ursprungliga noderna eller nya noder som du har placerat i trädet.

Nu ska vi gå till ett uttrycksträd och skapa ett nytt träd med några ersättningsnoder. I det här exemplet ska vi ersätta alla konstanter med en konstant som är 10 gånger större. Annars lämnar du uttrycksträdet intakt. I stället för att läsa värdet för konstanten och ersätta den med en ny konstant ersätter du den genom att ersätta konstantnoden med en ny nod som utför multiplikationen.

När du hittar en konstant nod skapar du en ny multiplikationsnod vars underordnade är den ursprungliga konstanten och konstanten 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;
}

Skapa ett nytt träd genom att ersätta den ursprungliga noden med ersättningen. Du verifierar ändringarna genom att kompilera och köra det ersatta trädet.

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

Att skapa ett nytt träd är en kombination av att besöka noderna i det befintliga trädet och skapa nya noder och infoga dem i trädet. I föregående exempel visas vikten av att uttrycksträd är oföränderliga. Observera att det nya trädet som skapades i föregående kod innehåller en blandning av nyskapade noder och noder från det befintliga trädet. Noder kan användas i båda träden eftersom noderna i det befintliga trädet inte kan ändras. Återanvändning av noder resulterar i betydande minneseffektivitet. Samma noder kan användas i ett träd eller i flera uttrycksträd. Eftersom noder inte kan ändras kan samma nod återanvändas när den behövs.

Bläddra igenom och köra ett tillägg

Nu ska vi verifiera det nya trädet genom att skapa en andra besökare som går igenom trädet med additionsnoder och beräknar resultatet. Gör några ändringar i besökaren som du har sett hittills. I den här nya versionen returnerar besökaren den partiella summan av additionsåtgärden fram till den här punkten. För ett konstant uttryck är det helt enkelt värdet för det konstanta uttrycket. För ett tilläggsuttryck är resultatet summan av de vänstra och högra operanderna, när dessa träd har korsats.

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

Det finns en hel del kod här, men begreppen kan användas. Den här koden besöker underordnade i en djup första sökning. När en konstant nod påträffas returnerar besökaren värdet för konstanten. När besökaren har besökt båda barnen har dessa barn beräknat summan som beräknats för det underträdet. Additionsnoden kan nu beräkna sin summa. När alla noder i uttrycksträdet har besökts har summan beräknats. Du kan spåra körningen genom att köra exemplet i felsökningsprogrammet och spåra körningen.

Nu ska vi göra det enklare att spåra hur noderna analyseras och hur summan beräknas genom att gå igenom trädet. Här är en uppdaterad version av metoden Aggregate som innehåller en hel del spårningsinformation:

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

Om du kör det på sum uttrycket får du följande utdata:

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

Spåra utdata och följ med i föregående kod. Du bör kunna ta reda på hur koden besöker varje nod och beräknar summan när den går genom trädet och hittar summan.

Nu ska vi titta på en annan körning, med uttrycket som anges av sum1:

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

Här är utdata från att undersöka det här uttrycket:

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

Även om det slutliga svaret är detsamma är trädbläddningen annorlunda. Noderna överförs i en annan ordning, eftersom trädet skapades med olika åtgärder som inträffar först.

Skapa en ändrad kopia

Skapa ett nytt konsolprogramprojekt . Lägg till ett using direktiv i filen för System.Linq.Expressions namnområdet. Lägg till klassen i AndAlsoModifier projektet.

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

Den här klassen ärver ExpressionVisitor klassen och är specialiserad på att ändra uttryck som representerar villkorsstyrda AND åtgärder. De här åtgärderna ändras från en villkorlig AND till en villkorsstyrd OR. Klassen åsidosätter VisitBinary metoden för bastypen eftersom villkorsuttryck AND representeras som binära uttryck. VisitBinary Om uttrycket som skickas till metoden i metoden representerar en villkorsstyrd AND åtgärd konstruerar koden ett nytt uttryck som innehåller villkorsoperatorn OR i stället för den villkorsstyrda AND operatorn. Om uttrycket som skickas till VisitBinary inte representerar en villkorsstyrd AND åtgärd, defersar metoden till basklassimplementeringen. Basklassmetoderna konstruerar noder som liknar de uttrycksträd som skickas in, men noderna får sina underträd ersatta med uttrycksträden som genereras rekursivt av besökaren.

Lägg till ett using direktiv i filen för System.Linq.Expressions namnområdet. Lägg till Main kod i metoden i filen Program.cs för att skapa ett uttrycksträd och skicka den till den metod som ändrar den.

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

Koden skapar ett uttryck som innehåller en villkorsstyrd AND åtgärd. Sedan skapas en instans av AndAlsoModifier klassen och uttrycket skickas till metoden för den Modify här klassen. Både det ursprungliga och det ändrade uttryckets träd matas ut för att visa ändringen. Kompilera och kör programmet.

Läs mer

Det här exemplet visar en liten delmängd av koden som du skapar för att bläddra igenom och tolka algoritmerna som representeras av ett uttrycksträd. Information om hur du skapar ett bibliotek för generell användning som översätter uttrycksträd till ett annat språk finns i den här serien av Matt Warren. Den går in i detalj på hur du översätter någon av koden som du kan hitta i ett uttrycksträd.

Du har nu sett den sanna kraften i uttrycksträd. Du undersöker en uppsättning kod, gör eventuella ändringar som du vill ha i koden och kör den ändrade versionen. Eftersom uttrycksträden är oföränderliga skapar du nya träd med hjälp av komponenterna i befintliga träd. Om du återanvänder noder minimeras mängden minne som behövs för att skapa modifierade uttrycksträd.