Tradurre alberi di espressioni

Questo articolo illustra come visitare ogni nodo in un albero delle espressioni durante la creazione di una copia modificata dell'albero delle espressioni. Traduci gli alberi delle espressioni per capire gli algoritmi in modo che possano essere tradotti in un altro ambiente. Si modifica l'algoritmo creato. È possibile aggiungere la registrazione, intercettare le chiamate al metodo e tenerle traccia o altri scopi.

Il codice compilato per tradurre un albero delle espressioni è un'estensione di ciò che si è già visto per visitare tutti i nodi di un albero. Quando si traduce un albero delle espressioni, si visitano tutti i nodi e, durante la visita, si costruisce il nuovo albero. Il nuovo albero può contenere riferimenti ai nodi originali o ai nuovi nodi inseriti nell'albero.

Si esaminerà ora un albero delle espressioni e si creerà un nuovo albero con alcuni nodi sostitutivi. In questo esempio si sostituirà qualsiasi costante con una costante 10 volte superiore. In caso contrario, si lascia intatto l'albero delle espressioni. Anziché leggere il valore della costante e sostituirlo con una nuova costante, sostituire il nodo costante con un nuovo nodo che esegue la moltiplicazione.

In questo caso, dopo aver trovato un nodo costante, si crea un nuovo nodo di moltiplicazione i cui elementi figlio sono la costante originale e la costante 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;
}

Creare un nuovo albero sostituendo il nodo originale con il sostituto. Per verificare le modifiche, compilare ed eseguire l'albero sostituito.

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

La creazione di un nuovo albero è una combinazione di visitare i nodi nell'albero esistente e creare nuovi nodi e inserirli nell'albero. L'esempio precedente mostra l'importanza dell'immutabilità degli alberi delle espressioni. Si noti che il nuovo albero creato nel codice precedente contiene una combinazione di nodi appena creati e nodi dall'albero esistente. I nodi possono essere usati in entrambi gli alberi perché i nodi nell'albero esistente non possono essere modificati. Il riutilizzo dei nodi comporta un'efficienza significativa della memoria. Gli stessi nodi possono essere usati sia in tutto un albero sia in più alberi di espressioni. Poiché i nodi non possono essere modificati, lo stesso nodo può essere riutilizzato ogni volta che è necessario.

Attraversare ed eseguire un'addizione

Verifichiamo il nuovo albero costruendo un secondo visitatore che attraversa il percorso dei nodi di somma e calcola il risultato. Apportare un paio di modifiche al visitatore che hai visto finora. In questa nuova versione, il visitatore restituisce la somma parziale dell'operazione di addizione fino a questo punto. Per un'espressione costante è semplicemente il valore dell'espressione costante. Per un'espressione di addizione, il risultato è la somma degli operandi sinistro e destro, dopo che tali alberi sono stati attraversati.

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

Qui c'è un po' di codice, ma i concetti sono avvicinabili. Questo codice visita i nodi figli in una ricerca in profondità. Quando rileva un nodo costante, il visitatore restituisce il valore della costante. Dopo che il visitatore ha visitato entrambi gli elementi figlio, tali elementi figlio hanno calcolato la somma calcolata per tale sottoalbero. Il nodo di addizione può ora calcolare la somma. Dopo aver visitato tutti i nodi nell'albero delle espressioni, la somma è stata calcolata. È possibile tracciare l'esecuzione eseguendo l'esempio nel debugger e tracciando l'esecuzione.

È ora più semplice tracciare il modo in cui i nodi vengono analizzati e come viene calcolata la somma attraversando l'albero. Ecco una versione aggiornata del metodo Aggregate che include alcune informazioni di traccia:

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

L'esecuzione nell'espressione sum produce l'output seguente:

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

Tracciare l'output e seguire la procedura nel codice precedente. Dovrebbe essere possibile determinare il modo in cui il codice visita ogni nodo e calcola la somma mentre passa attraverso l'albero e trova la somma.

Ora esaminiamo una diversa esecuzione, con l'espressione fornita da sum1.

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

Ecco l'output dell'analisi di questa espressione:

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

Mentre la risposta finale è la stessa, l'attraversamento dell'albero è diverso. I nodi vengono trasferiti in un ordine diverso, perché l'albero è stato costruito con operazioni diverse che si verificano per prime.

Creare una copia modificata

Creare un nuovo progetto applicazione console . Aggiungere una direttiva using al file per il namespace System.Linq.Expressions. Aggiungere la AndAlsoModifier classe al progetto.

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

Questa classe eredita la ExpressionVisitor classe ed è specializzata per modificare le espressioni che rappresentano operazioni condizionali AND . Cambia queste operazioni da un condizionale AND a un condizionale OR. La classe esegue l'override del VisitBinary metodo del tipo di base, perché le espressioni condizionali AND sono rappresentate come espressioni binarie. VisitBinary Nel metodo , se l'espressione passata a essa rappresenta un'operazione condizionaleAND, il codice costruisce una nuova espressione che contiene l'operatore condizionale OR anziché l'operatore condizionaleAND. Se l'espressione passata a VisitBinary non rappresenta un'operazione condizionale, il metodo rinvia all'implementazione AND della classe base. I metodi della classe base costruiscono nodi che sono simili agli alberi delle espressioni passati come parametri, ma i nodi hanno i rispettivi sottoalberi sostituiti con gli alberi delle espressioni prodotti in modo ricorsivo dal visitatore.

Aggiungere una direttiva using al file per il namespace System.Linq.Expressions. Aggiungere codice al Main metodo nel file Program.cs per creare un albero delle espressioni e passarlo al metodo che lo modifica.

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

Il codice crea un'espressione che contiene un'operazione condizionale AND . Crea quindi un'istanza della AndAlsoModifier classe e passa l'espressione al Modify metodo di questa classe. Sia gli alberi delle espressioni originali che gli alberi delle espressioni modificati vengono restituiti per visualizzare la modifica. Compilare ed eseguire l'applicazione.

Ulteriori informazioni

In questo esempio viene illustrato un piccolo subset del codice da compilare per attraversare e interpretare gli algoritmi rappresentati da un albero delle espressioni. Per informazioni sulla creazione di una libreria per utilizzo generico che converte gli alberi delle espressioni in un'altra lingua, leggere questa serie di Matt Warren. Illustra in modo dettagliato come tradurre qualsiasi codice presente in un albero delle espressioni.

Ora hai visto la vera potenza degli alberi delle espressioni. Si esamina un set di codice, si apportano modifiche al codice e si esegue la versione modificata. Poiché gli alberi delle espressioni non sono modificabili, è possibile creare nuovi alberi usando i componenti degli alberi esistenti. Il riutilizzo dei nodi riduce al minimo la quantità di memoria necessaria per creare alberi delle espressioni modificati.