Traslado de árboles de expresión
En este artículo, obtendrá información sobre cómo visitar cada nodo en un árbol de expresión, mientras se crea una copia modificada de ese árbol de expresión. Trasladará los árboles de expresión para comprender los algoritmos para poder trasladarlos a otro entorno. Cambiará el algoritmo que se ha creado. Podría agregar el registro, interceptar las llamadas de método y realizar un seguimiento de ellas, o con otros fines.
El código que se compila para trasladar un árbol de expresión es una extensión de lo que ya se vio para visitar todos los nodos de un árbol. Al trasladar un árbol de expresión, se visitan todos los nodos y mientras se visitan, se crea el árbol nuevo. El nuevo árbol puede contener referencias a los nodos originales o a nodos nuevos que haya colocado en el árbol.
Visitaremos un árbol de expresión y crearemos un árbol nuevo con varios nodos de reemplazo. En este ejemplo, se van a sustituir todas las constantes con una constante que es diez veces mayor. De lo contrario, dejará el árbol de expresión intacto. En lugar de leer el valor de la constante y reemplazarlo con una constante nueva, hará este cambio reemplazando el nodo constante con un nuevo nodo que realiza la multiplicación.
Aquí, una vez que se encuentre un nodo constante, se crea un nuevo nodo de multiplicación cuyos elementos secundarios son la constante original y 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;
}
Cree un nuevo árbol reemplazando el nodo original por el sustituto. Puede comprobar los cambios mediante la compilación y ejecución del árbol reemplazado.
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 creación de un árbol nuevo es una combinación de visitar los nodos del árbol existente y crear nodos nuevos e insertarlos en el árbol. En el ejemplo anterior se muestra la importancia de la inmutabilidad de los árboles de expresión. Observe que el nuevo árbol creado anteriormente contiene una mezcla de los nodos recién creados y los nodos del árbol existente. Los nodos se pueden usar en ambos árboles porque los nodos del árbol existente no se pueden modificar. La reutilización de nodos da lugar a importantes eficiencias de memoria. Los mismos nodos se pueden usar en un árbol o en varios árboles de expresión. Dado que los nodos no se pueden modificar, se puede volver a usar el mismo nodo siempre que sea necesario.
Recorrer y ejecutar una adición
Vamos a comprobar el nuevo árbol mediante la creación de un segundo visitante que recorre el árbol de nodos de adición y calcula el resultado. Haga algunas modificaciones en el visitante visto hasta el momento. En esta nueva versión, el visitante devolverá la suma parcial de la operación de adición hasta este punto. Para una expresión constante, es simplemente el valor de la expresión constante. Para una expresión de adición, el resultado es la suma de los operandos izquierdo y derecho, una vez que se recorren esos árboles.
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);
Aquí hay gran cantidad de código, pero los conceptos son accesibles. Este código visita los elementos secundarios en una primera búsqueda de profundidad. Cuando encuentra un nodo constante, el visitante devuelve el valor de la constante. Tras la visita a los dos elementos secundarios por parte del visitante, dichos elementos han obtenido la suma calculada para ese subárbol. El nodo de adición ahora puede calcular la suma. Una vez que se visiten todos los nodos en el árbol de expresión, se habrá calculado la suma. Se puede hacer el seguimiento de la ejecución ejecutando el ejemplo en el depurador y realizando el seguimiento de la ejecución.
Vamos a facilitar el seguimiento de cómo se analizan los nodos y cómo se calcula la suma mediante el recorrido del árbol. Esta es una versión actualizada del método agregado que incluye gran cantidad de información de seguimiento:
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");
}
Al ejecutarla en la expresión sum, produce el siguiente resultado:
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
Realice el seguimiento del resultado y siga el código anterior. Debería poder averiguar cómo el código visita cada nodo y calcula la suma mientras recorre el árbol y busca la suma.
Ahora, veremos una ejecución diferente, con la expresión proporcionada por sum1:
Expression<Func<int>> sum1 = () => 1 + (2 + (3 + 4));
Este es el resultado de examinar esta expresión:
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
Aunque la respuesta final es la misma, el recorrido del árbol es diferente. Los nodos se recorren en un orden diferente, porque el árbol se construyó con diferentes operaciones que se producen en primer lugar.
Creación de una copia modificada
Cree un nuevo proyecto de aplicación de consola. Agregue una directiva using al archivo para el espacio de nombres System.Linq.Expressions. Agregue la clase AndAlsoModifier al proyecto.
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);
}
}
Esta clase hereda la clase ExpressionVisitor y está especializada en la modificación de expresiones que representan operaciones AND condicionales. Cambia estas operaciones de una expresión AND condicional a una expresión OR condicional. La clase invalida el método VisitBinary del tipo base, porque las expresiones AND condicionales se representan como expresiones binarias. En el método VisitBinary, si la expresión que se pasa representa una operación AND condicional, el código construye una nueva expresión que contiene el operador OR condicional en lugar del operador AND condicional. Si la expresión que se pasa a VisitBinary no representa una operación AND condicional, el método defiere a la implementación de la case base. Los métodos de clase base construyen nodos que son como los árboles de expresiones que se pasan, pero los subárboles de los nodos se reemplazan por los árboles de expresiones que genera de forma recursiva el visitante.
Agregue una directiva using al archivo para el espacio de nombres System.Linq.Expressions. Agregue código al método Main en el archivo Program.cs para crear un árbol de expresión y pasarlo al método que 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"))
*/
El código crea una expresión que contiene una operación AND condicional. Luego crea una instancia de la clase AndAlsoModifier y pasa la expresión al método Modify de esta clase. Se generan los árboles de expresiones tanto originales como modificados para mostrar el cambio. Compile y ejecute la aplicación.
Más información
En este ejemplo se muestra un pequeño subconjunto del código que se compilaría para recorrer e interpretar los algoritmos representados por un árbol de expresión. Para información sobre la compilación de una biblioteca de propósito general que traduce árboles de expresión a otro lenguaje, lea esta serie de Matt Warren. Describe en detalle cómo traducir cualquier código que es posible encontrar en un árbol de expresión.
Ahora ha visto la verdadera eficacia de los árboles de expresión. Examine un conjunto de código, realice los cambios que quiera en ese código y ejecute la versión modificada. Como los árboles de expresión son inmutables, crea árboles nuevos mediante el uso de los componentes de árboles existentes. La reutilización de los nodos minimiza la cantidad de memoria necesaria para crear árboles de expresión modificados.
