Traduire des arborescences d’expressions
Dans cet article, découvrez comment visiter chaque nœud dans une arborescence d’expressions lors de la génération d’une copie modifiée de cette arborescence d’expressions. Vous traduisez les arborescences d’expressions pour comprendre les algorithmes exprimés pour pouvoir traduire 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 dans une arborescence. Quand vous traduisez une arborescence d’expressions, vous visitez tous les nœuds et, ce faisant, vous générez la nouvelle arborescence. Celle-ci 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 en créant une nouvelle arborescence avec certains nœuds de substitution. Dans cet exemple, nous allons remplacer une constante par une autre 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 allez remplacer le nœud de constante par un nouveau nœud qui effectue la multiplication.
Ici, une fois que vous avez trouvé un nœud de constante, 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 arborescence en remplaçant le nœud d’origine par le substitut. Vous pouvez vérifier les changements 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);
Pour générer une nouvelle arborescence, il faut visiter les nœuds dans l’arborescence existante, créer de nouveaux nœuds et les insérer dans l’arborescence. L’exemple précédent montre l’importance du caractère immuable des arborescences d’expressions. Notez que la nouvelle arborescence créée dans le code précédent contient une combinaison 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 amélioration significative de l’efficacité de la mémoire. Les mêmes nœuds sont utilisables dans toute une arborescence, ou dans plusieurs arborescences d’expressions. Les nœuds ne pouvant 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
Nous allons vérifier cette nouvelle arborescence en générant un deuxième visiteur qui parcourt l’arborescence de nœuds d’addition et calcule le résultat. Apportez quelques modifications au visiteur que nous avons vu jusqu’ici. 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 pas mal de code ici, mais les concepts sont abordables. 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, ceux-ci ont calculé la somme calculée pour cette sous-arborescence. Le nœud d’addition peut maintenant calculer sa somme. Une fois que tous les nœuds dans 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 simplifier le suivi de l’analyse des nœuds et du calcul de la somme en parcourant l’arborescence. Voici une version mise à jour de la méthode Aggregate qui comprend des 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");
}
Son 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
Suivez la sortie et suivez le code précédent. Vous devriez pouvoir déterminer comment le code visite chaque nœud et calcule la somme à mesure qu’il parcourt 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 survenant en premier.
Créer une copie modifiée
Créez un projet Application console. Ajoutez une directive using au fichier pour l’espace de noms System.Linq.Expressions. Ajoutez la classe AndAlsoModifier à 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 classe AND et est spécialisée pour modifier les expressions qui représentent des opérations ExpressionVisitor conditionnelles. Elle convertit ces opérations d’un AND conditionnel en un OR conditionnel. La classe substitue la méthode VisitBinary du type de base, car les expressions AND conditionnelles sont représentées sous forme d’expressions binaires. Dans la méthode VisitBinary, si l’expression passée représente une opération AND conditionnelle, le code construit une nouvelle expression qui contient l’opérateur OR conditionnel au lieu de l’opérateur AND conditionnel. Si l’expression passée à VisitBinary ne représente pas une opération AND conditionnelle, la méthode emploie 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 le code à la méthode Main dans le fichier Program.cs pour créer une arborescence d’expressions, et passez-le à la méthode qui le 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 AND conditionnelle. Il crée ensuite une instance de la classe AndAlsoModifier et passe l’expression à la méthode Modify de cette classe. Les arborescences d’expressions d’origine et modifiée sont toutes deux générées pour montrer la modification. Compilez et exécutez l'application.
En savoir plus
Cet exemple montre un petit sous-ensemble du code que vous créeriez pour parcourir et interpréter les algorithmes représentés par une arborescence d’expressions. Pour des informations sur la génération d’une bibliothèque à usage général qui traduit des arborescences d’expressions dans un autre langage, consultez cette série de Matt Warren. Elle décrit en détail comment traduire le code que vous pourriez rencontrer dans une arborescence d’expressions.
Cet article aura mis en évidence toute la puissance des arborescences d’expressions. Vous examinez un ensemble de code, y apportez les modifications souhaitées et exécutez la version modifiée. Les arborescences d’expressions étant immuables, vous créez des arborescences à l’aide de composants d’arborescences existantes. La réutilisation des nœuds réduit la quantité de mémoire nécessaire pour créer des arborescences d’expressions.
