Traduire des arborescences d’expressions

Dans cet article, vous allez apprendre à visiter chaque nœud d’une arborescence d’expressions lors de la création d’une copie modifiée de cette arborescence d’expressions. Vous traduisez des arborescences d’expressions pour comprendre les algorithmes afin qu’ils puissent être traduits dans un autre environnement. Vous modifiez l’algorithme qui a été créé. Vous pouvez ajouter la journalisation, intercepter des appels de méthode et les suivre, entre autres.

Le code que vous générez pour traduire une arborescence d’expressions est une extension de ce que vous avez déjà vu pour visiter tous les nœuds d’une arborescence. Lorsque vous traduisez une arborescence d'expressions, vous visitez tous les nœuds et, en les visitant, construisez la nouvelle arborescence. La nouvelle arborescence peut contenir des références aux nœuds d’origine, ou de nouveaux nœuds que vous avez placés dans l’arborescence.

Nous allons visiter une arborescence d’expressions et créer une nouvelle arborescence avec certains nœuds de remplacement. Dans cet exemple, nous allons remplacer toute constante par une constante qui est de 10 fois plus grande. Pour le reste, vous laisserez l’arborescence d’expressions intacte. Au lieu de lire la valeur de la constante et de la remplacer par une nouvelle constante, vous effectuez ce remplacement en remplaçant le nœud constant par un nouveau nœud qui effectue la multiplication.

Ici, une fois que vous trouvez un nœud constant, vous créez un nœud de multiplication dont les enfants sont la constante d’origine et la constante 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;
}

Créez une nouvelle arborescence en remplaçant le nœud d'origine par le remplaçant. Vous vérifiez les modifications en compilant et en exécutant l’arborescence remplacée.

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 création d’une nouvelle arborescence est une combinaison de visites des nœuds dans l’arborescence existante et de la création de nouveaux nœuds et de leur insertion dans l’arborescence. L’exemple précédent montre l’importance pour les arborescences d’expressions d’être immuables. Notez que la nouvelle arborescence créée dans le code précédent contient un mélange de nœuds nouvellement créés et de nœuds de l’arborescence existante. Les nœuds peuvent être utilisés dans les deux arborescences, car les nœuds de l’arborescence existante ne peuvent pas être modifiés. La réutilisation des nœuds entraîne une efficacité significative de la mémoire. Les mêmes nœuds peuvent être utilisés dans une arborescence ou dans plusieurs arborescences d’expressions. Étant donné que les nœuds ne peuvent pas être modifiés, le même nœud peut être réutilisé chaque fois qu’il est nécessaire.

Parcours et exécution d’une addition

Vérifions la nouvelle arborescence en créant un deuxième visiteur qui guide l’arborescence des nœuds d’ajout et calcule le résultat. Apportez quelques modifications au visiteur que vous avez vu jusqu’à présent. Dans cette nouvelle version, le visiteur retourne la somme partielle de l’opération d’addition jusqu’à ce point. Pour une expression constante, il s’agit simplement de la valeur de l’expression constante. Pour une expression d’addition, le résultat est la somme des opérandes gauche et droit, une fois ces arborescences parcourues.

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

Il y a un peu de code ici, mais les concepts sont accessibles. Ce code visite les enfants avec une recherche en profondeur. Quand il rencontre un nœud de constante, le visiteur retourne la valeur de la constante. Une fois que le visiteur a visité les deux enfants, ces enfants ont calculé la somme calculée pour cette sous-arborescence. Le nœud d’ajout peut maintenant calculer sa somme. Une fois que tous les nœuds de l’arborescence d’expressions ont été visités, la somme a été calculée. Vous pouvez suivre l’exécution en exécutant l’exemple dans le débogueur.

Nous allons faciliter le suivi de la façon dont les nœuds sont analysés et comment la somme est calculée en parcourant l’arborescence. Voici une version mise à jour de la méthode Aggregate qui inclut un peu d’informations de suivi :

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’exécution sur l’expression sum génère la sortie suivante :

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

Tracez la sortie et suivez le code précédent. Vous devez être en mesure de déterminer comment le code visite chaque nœud et calcule la somme à mesure qu’il passe par l’arborescence et trouve la somme.

À présent, jetons un œil à une autre exécution, avec l’expression donnée par sum1 :

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

Voici la sortie de l’examen de cette 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

Bien que la réponse finale soit la même, le parcours d’arborescence est différent. Les nœuds sont parcourus dans un ordre différent, car l’arborescence a été construite avec différentes opérations se produisant en premier.

Créer une copie modifiée

Créez un projet d’application console . Ajoutez une directive using au fichier pour l'espace de noms System.Linq.Expressions. Ajoutez la AndAlsoModifier classe à votre projet.

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

Cette classe hérite de la ExpressionVisitor classe et est spécialisée pour modifier des expressions qui représentent des opérations conditionnelles AND . Il modifie ces opérations d’un conditionnel AND à un conditionnel OR. La classe remplace la VisitBinary méthode du type de base, car les expressions conditionnelles AND sont représentées en tant qu’expressions binaires. Dans la VisitBinary méthode, si l’expression passée à elle représente une opération conditionnelle AND , le code construit une nouvelle expression qui contient l’opérateur conditionnel OR au lieu de l’opérateur conditionnel AND . Si l’expression passée à VisitBinary ne représente pas une opération conditionnelle AND , la méthode reporte à l’implémentation de classe de base. Les méthodes de classe de base construisent des nœuds qui sont comme les arborescences d’expressions passées, mais les nœuds voient leurs sous-arborescences remplacées par les arborescences d’expressions produites de manière récursive par le visiteur.

Ajoutez une directive using au fichier pour l'espace de noms System.Linq.Expressions. Ajoutez du code à la Main méthode dans le fichier Program.cs pour créer une arborescence d’expressions et la transmettre à la méthode qui la modifie.

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

Le code crée une expression qui contient une opération conditionnelle AND . Il crée ensuite une instance de la AndAlsoModifier classe et transmet l’expression à la Modify méthode de cette classe. Les arborescences d’expressions d’origine et modifiées sont générées pour afficher la modification. Compilez et exécutez l’application.

Pour en savoir plus

Cet exemple montre un petit sous-ensemble du code que vous générez pour parcourir et interpréter les algorithmes représentés par une arborescence d’expressions. Pour plus d’informations sur la création d’une bibliothèque à usage général qui traduit des arborescences d’expressions dans une autre langue, lisez cette série par Matt Warren. Il explique en détail comment traduire l’un des codes que vous pouvez trouver dans une arborescence d’expressions.

Cet article aura mis en évidence toute la puissance des arborescences d’expressions. Vous examinez un ensemble de code, apportez les modifications souhaitées à ce code et exécutez la version modifiée. Étant donné que les arborescences d’expressions sont immuables, vous créez des arborescences à l’aide des composants des arborescences existantes. La réutilisation des nœuds réduit la quantité de mémoire nécessaire pour créer des arborescences d’expressions modifiées.