Traducir árboles de expresión

En este artículo, aprenderá a visitar cada nodo de un árbol de expresiones al crear una copia modificada de ese árbol de expresiones. Los árboles de expresión se traducen para comprender los algoritmos para que se puedan traducir en otro entorno. Cambia 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 compila para traducir un árbol de expresión es una extensión de lo que ya ha visto para visitar todos los nodos de un árbol. Al traducir un árbol de expresión, visite todos los nodos y, al visitarlos, compile el nuevo árbol. El nuevo árbol puede contener referencias a los nodos originales o a los nodos nuevos que ha colocado en el árbol.

Vamos a visitar un árbol de expresiones y a crear un nuevo árbol con algunos nodos de reemplazo. En este ejemplo, vamos a reemplazar cualquier constante por una constante que sea 10 veces mayor. De lo contrario, dejas intacto el árbol de expresión. En lugar de leer el valor de la constante y reemplazarlo por una nueva constante, este reemplazo se realiza reemplazando el nodo constante por un nuevo nodo que realiza la multiplicación.

Aquí, una vez que encuentre un nodo constante, cree 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. Para comprobar los cambios, compile y ejecute el á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 nuevo árbol es una combinación de visitar los nodos del árbol existente y crear nuevos nodos e insertarlos en el árbol. En el ejemplo anterior se muestra la importancia de que los árboles de expresión sean inmutables. Observe que el nuevo árbol creado en el código anterior contiene una combinación de nodos recién creados y nodos del árbol existente. Los nodos se pueden usar en ambos árboles porque no se pueden modificar los nodos del árbol existente. 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 reutilizar 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 suma y calcula el resultado. Haz un par de modificaciones en el visitante que has visto hasta ahora. 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);

Hay bastante código aquí, 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 suma ahora puede calcular su suma. Una vez que se han visitado todos los nodos del árbol de expresión, se ha calculado la suma. Puede realizar un seguimiento de la ejecución al ejecutar el ejemplo en el depurador y rastrear el proceso.

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 Aggregate que incluye bastante 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");
}

Ejecutarlo en la sum expresión 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 un seguimiento de la salida y siga los pasos descritos en el código anterior. Debería poder averiguar cómo el código visita cada nodo y calcula la suma a medida que pasa por el árbol y encuentra la suma.

Ahora, echemos un vistazo a una ejecución diferente, con la expresión dada 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 desplazan en un orden diferente, ya que el árbol se construyó con diferentes operaciones que se produjeron primero.

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 AndAlsoModifier clase 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 ExpressionVisitor clase y está especializada en modificar expresiones que representan operaciones condicionales AND . Cambia estas operaciones de un condicional AND a un condicional OR. La clase invalida el VisitBinary método del tipo base, ya que las expresiones condicionales AND se representan como expresiones binarias. En el VisitBinary método , si la expresión que se pasa a ella representa una operación condicional AND , el código construye una nueva expresión que contiene el operador condicional OR en lugar del operador condicional AND . 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 Main método 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 condicional AND . A continuación, crea una instancia de la AndAlsoModifier clase y pasa la expresión al Modify método de esta clase. Tanto los árboles de expresión originales como los modificados se generan para mostrar el cambio. Compile y ejecute la aplicación.

Aprende más

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 expresiones. Para obtener información sobre cómo crear una biblioteca de uso general que traduzca árboles de expresión a otro lenguaje, lea esta serie de Matt Warren. Incluye detalles excelentes sobre cómo traducir cualquiera de los códigos que puede encontrar en un árbol de expresiones.

Ahora ha visto el verdadero poder de los árboles de expresión. Examine un conjunto de código, realice los cambios que desee en ese código y ejecute la versión modificada. Dado que los árboles de expresión son inmutables, se crean nuevos árboles mediante los componentes de los árboles existentes. La reutilización de nodos minimiza la cantidad de memoria necesaria para crear árboles de expresión modificados.