Traslare alberi delle espressioni

Informazioni su come visitare ogni nodo in un albero delle espressioni, creando una copia modificata di tale albero delle espressioni. Gli alberi delle espressioni vengono traslati per comprendere gli algoritmi in modo che possano essere traslati in un altro ambiente. Si modifica l'algoritmo creato. È possibile aggiungere la registrazione, intercettare chiamate al metodo e tenerne traccia, oltre ad altri scopi.

Il codice compilato per traslare un albero delle espressioni è un'estensione di tutto questo, utile per visitare tutti i nodi in un albero. Quando si trasla un albero delle espressioni, tutti i nodi vengono visitati e durante la visita viene compilato il nuovo albero. Il nuovo albero può contenere riferimenti ai nodi originali o ai nuovi nodi posizionati nell'albero.

Si esaminerà ora un albero delle espressioni e si creerà un nuovo albero con alcuni nodi sostitutivi. In questo esempio, sostituiamo qualsiasi costante con una costante dieci volte maggiore. In alternativa, possiamo lasciare l'albero delle espressioni intatto. Invece di leggere il valore della costante e sostituirla con una nuova costante, eseguiremo una sostituzione del nodo della costante con un nuovo nodo che esegue la moltiplicazione.

In questo caso, dopo aver trovato il nodo di una costante, si crea un nuovo nodo di moltiplicazione i cui figli rappresentino 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 tra la visita ai nodi nell'albero esistente e la creazione e l'inserimento di nuovi nodi nell'albero. L'esempio precedente mostra l'importanza dell'immutabile 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 in uno o più alberi delle espressioni. Dal momento che i nodi non possono essere modificati, lo stesso nodo può essere riutilizzato secondo necessità.

Attraversare ed eseguire un'addizione

Esamineremo ora questi aspetti creando un secondo visitatore che percorre l'albero dei nodi di addizione 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, la somma corrisponde semplicemente al valore dell'espressione costante. Per un'espressione di addizione, il risultato è la somma degli operandi sinistro e destro, dopo l'attraversamento degli alberi.

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 useremo un po’ di codice, ma i concetti sono molto intuitivi. Questo codice visita gli elementi figlio in una prima ricerca profondità. Quando incontra un nodo della costante, il visitatore restituisce il valore della costante. Dopo che il visitatore ha visitato entrambi gli elementi figlio, verrà calcolata la somma per essi, per questo sottoalbero. A questo punto, il nodo di addizione può calcolare la somma. Dopo aver visitato tutti i noti dell'albero delle espressioni, verrà calcolata la somma. È possibile tracciare l'esecuzione eseguendo l'esempio nel debugger.

È possibile semplificare il tracciamento dell'analisi dei nodi e delle modalità di calcolo della somma tramite l'attraversamento dell'albero. Di seguito è riportata una versione aggiornata del metodo Aggregate che include una certa quantità di informazioni di tracciamento:

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 restituisce 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. È possibile comprendere in che modo il codice visiti ogni nodo e calcoli la somma attraversando l'albero e trovando la somma.

Esaminiamo ora un'esecuzione diversa, con l'espressione rappresentata da sum1:

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

Di seguito è riportato 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 attraversati in un ordine diverso, perché l'albero è stato costruita con diverse operazioni che si verificano prima.

Creare una copia modificata

Creare un nuovo progetto Applicazione console. Aggiungere al file una direttiva using per lo spazio dei nomi System.Linq.Expressions. Aggiungere la classe AndAlsoModifier 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);
    }
}

La classe eredita la classe ExpressionVisitor ed è specializzata per modificare le espressioni che rappresentano operazioni AND condizionali. Modifica tali operazioni da un'operazione AND condizionale a un'operazione OR condizionale. La classe esegue l'override del metodo VisitBinary del tipo di base, perché le espressioni AND condizionali vengono rappresentate come espressioni binarie. Se l'espressione che viene passata al metodo VisitBinary rappresenta un'operazione AND condizionale, il codice costruisce una nuova espressione che contiene l'operatore condizionale OR anziché l'operatore condizionale AND. Se l'espressione passata a VisitBinary non rappresenta un'operazione di AND condizionale, il metodo passa all'implementazione della classe di base. I metodi della classe base costruiscono nodi simili agli alberi delle espressione passati, ma i sottoalberi dei nodi vengono sostituiti con gli alberi delle espressioni che vengono generati in modo ricorsivo dal visitatore.

Aggiungere al file una direttiva using per lo spazio dei nomi System.Linq.Expressions. Aggiungere codice al metodo Main nel file Program.cs per creare un albero delle espressioni e passarlo al metodo che lo modificherà.

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 AND condizionale. Viene quindi creata un'istanza della classe AndAlsoModifier e l'espressione viene passata al metodo Modify della classe. Sia l'albero delle espressioni originale che quello modificato vengono inclusi nell'output per illustrare le modifiche. Compilare l'applicazione ed eseguirla.

Altre informazioni

Questo esempio illustra un piccolo sottoinsieme del codice creato 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. La serie spiega in dettaglio come traslare il codice di un albero delle espressioni.

Abbiamo percepito la vera potenza degli alberi delle espressioni. Si esamina un set di codice, si apportano modifiche a tale codice e si esegue la versione modificata. Dal momento che gli alberi delle espressioni sono immutabili, è 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.