Árboles de Expresiones

Ahora que ya hemos visto que es una expresión lambda podemos ver otra nueva característica mucho más “rara” de C# 3.0: los árboles de expresiones. En algunos lenguajes, como Lisp, se permite manejar el código como si fueran datos y los datos como si fueran código (hace un par de días leyendo el blog del gran Eric Lippert descubrí que a esto se le llama homoiconic). Los árboles de expresión son la forma que tiene C# de implementar esta funcionalidad (de forma algo limitada).

Por ejemplo, en el artículo anterior teníamos la expresión lambda:

num => num < 5

Que devolvía si un número era menor que cinco o no. Expresado en forma de un delegado del tipo Func, el código sería:

Func<int, bool> f = num => num < 5;

Y la forma de poner lo mismo usando un árbol de expresiones es:

System.Linq.Expressions.Expression<Func<int, bool>> e = num => num < 5;

La diferencia entre Func y Expression es que f es una función que se puede ejecutar:

bool result = f(10);

Pero para ejecutar e tenemos que hacer lo siguiente:

bool result = e.Compile()(10);

Es decir: para ejecutar un árbol de expresiones primero tenemos que compilarlo (porque son datos que representan código, no código en sí) y una vez compilado ya podemos utilizar el resultado como si fuera un método normal.

De forma gráfica, e internamente está representado por el siguiente árbol:

treePero lo interesante de los árboles de expresiones es que en vez de dejar que el compilador los genere automáticamente, podemos construirlos nosotros a mano. Una vez tenemos una idea de como se representan internamente generarlos por código es bastante fácil (aunque algo tedioso):

ParameterExpression param = Expression.Parameter(typeof(int), "num");
ConstantExpression five = Expression.Constant(5, typeof(int));
BinaryExpression lessThan = Expression.LessThan(param, five);
Expression<Func<int, bool>> e = Expression.Lambda<Func<int, bool>> (lessThan, new ParameterExpression[] { param });

Si hacemos un poco de memoria, en el mini motor de RPGs una parte bastante importante del código se encargaba de trabajar con las expresiones matemáticas que definen los valores de las variables de los objetos (los puntos de vida, el bonificador de ataque,…). Lo que hacíamos era definir el modificador en algún sitio (un fichero, una BD, …) como una expresión infijo, es decir, como esto:

(a) Attack = 3 * Level + 4 / 7 ^ 34 - 345

Se aplicaba el algoritmo de Shunting-Yard para transformarla en una expresión postfijo:

(b) Attack = 3 Level * 4 7 34 ^ / + 345 -

Y una vez teníamos (b) en forma postfijo se utilizaba un algoritmo para evaluar la expresión que lo que hace es construir un árbol con la siguiente pinta:

postfixevalY sinceramente, este árbol se parece un montón al árbol del ejemplo anterior :) Así que el cambio realizado en la librería de RPGs va a utilizar árboles de expresiones para permitirnos pasar de esto:

string strExp = "3 * Level + 4 / 7 ^ 34 - 345";

A esto:

Func<Evaluator, double> func = (evaluator) => 3 * evaluator.Chain(Level) + 4 / 7 ^ 34 - 345;

¡Hemos transformado una cadena de texto en una función en C#! Esta función recibe un objeto del tipo Evaluator (que se utiliza para calcular el valor de las variables como Level, Dexterity,… de forma recursiva) y devuelve un double (el valor de la fórmula).

El código que realiza esto es bastante sencillo (es una modificación del algoritmo de evaluación):

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using SLE = System.Linq.Expressions;
 
namespace GravityAge.Rpg
{
    public static class Experiments
    {
        #region Methods
 
        public static SLE.Expression<Func<Evaluator, double>> ToExpressionTree(this Expression expression)
        {
            Stack<SLE.Expression> operands;
            SLE.Expression op1, op2;
 
            SLE.ParameterExpression parameter = SLE.Expression.Parameter(typeof(Evaluator), "evaluator");
 
            operands = new Stack<SLE.Expression>();
 
            for (int i = 0; i < expression.Terms.Count; i++)
            {
                switch (expression.Terms[i].TermType)
                {
                    case TermType.Number:
                        {
                            operands.Push(SLE.Expression.Constant(expression.Terms[i].Value, typeof(double)));
                            break;
                        }
 
                    case TermType.Variable:
                        {
                            operands.Push(SLE.Expression.Call(parameter, "Chain", new Type[] { }, SLE.Expression.Constant(expression.Terms[i].Text)));
                            break;
                        }
 
                    case TermType.Operator:
                        {
                            op2 = operands.Pop();
                            op1 = operands.Pop();
 
                            switch (expression.Terms[i].TermOperator)
                            {
                                case TermOperator.Add:
                                    {
                                        operands.Push(SLE.Expression.Add(op1, op2));
                                        break;
                                    }
 
                                case TermOperator.Subtract:
                                    {
                                        operands.Push(SLE.Expression.Subtract(op1, op2));
                                        break;
                                    }
 
                                case TermOperator.Multiply:
                                    {
                                        operands.Push(SLE.Expression.Multiply(op1, op2));
                                        break;
                                    }
 
                                case TermOperator.Divide:
                                    {
                                        operands.Push(SLE.Expression.Divide(op1, op2));
                                        break;
                                    }
 
                                case TermOperator.Power:
                                    {
                                        operands.Push(SLE.Expression.Power(op1, op2));
                                        break;
                                    }
                            }
 
                            break;
                        }
 
                    default:
                        {
                            throw new ArgumentException("An undefined token (" + expression.Terms[i].Text + ") appeared while calculating an expression.");
                        }
                }
            }
 
            if (operands.Count == 1)
            {
                return SLE.Expression.Lambda<Func<Evaluator, double>>(operands.Pop(), parameter);
            }
            else
            {
                return null;
            }
        }
 
        #endregion
    }
}

Como podréis ver el código se encuentra dentro de una clase llamada Experiments, ya que no tenía muy claro si iba a ser capaz de hacer esto o no cuando empecé :p Así que estos días me dedicaré a refactorizar y pulir algunas cosas y en breve subiré una nueva versión de la librería a Kartones por si a alguien le interesa.