¿Árboles de expresión para tontos? [cerrado]

83

Yo soy el muñeco en este escenario.

He intentado leer en Google cuáles son, pero no lo entiendo. ¿Alguien puede darme una explicación simple de qué son y por qué son útiles?

editar: estoy hablando de la función LINQ en .Net.


fuente
1
Sé que esta publicación es bastante antigua, pero últimamente he estado investigando árboles de expresión. Me interesé después de que comencé a usar Fluent NHibernate. James Gregory usa ampliamente lo que se conoce como reflexión estática y tiene una introducción: jagregory.com/writings/introduction-to-static-reflection Para ver la reflexión estática y los árboles de expresión en acción, consulte el código fuente de Fluent NHibernate ( fluentnhibernate.org ). Es muy limpio y un concepto genial.
Jim Schubert

Respuestas:

88

La mejor explicación sobre los árboles de expresión que he leído es este artículo de Charlie Calvert.

Para resumirlo;

Un árbol de expresión representa lo que quiere hacer, no cómo quiere hacerlo.

Considere la siguiente expresión lambda muy simple:
Func<int, int, int> function = (a, b) => a + b;

Esta declaración consta de tres secciones:

  • Una declaración: Func<int, int, int> function
  • Un operador igual: =
  • Una expresión lambda: (a, b) => a + b;

La variable functionapunta al código ejecutable sin procesar que sabe cómo sumar dos números .

Esta es la diferencia más importante entre delegados y expresiones. Llamas function(a Func<int, int, int>) sin saber nunca qué hará con los dos enteros que pasaste. Toma dos y devuelve uno, eso es lo máximo que puede saber su código.

En la sección anterior, vio cómo declarar una variable que apunta a un código ejecutable sin procesar. Los árboles de expresión no son código ejecutable , son una forma de estructura de datos.

Ahora, a diferencia de los delegados, su código puede saber qué debe hacer un árbol de expresión.

LINQ proporciona una sintaxis simple para traducir código en una estructura de datos llamada árbol de expresión. El primer paso es agregar una declaración de uso para introducir el Linq.Expressionsespacio de nombres:

using System.Linq.Expressions;

Ahora podemos crear un árbol de expresión:
Expression<Func<int, int, int>> expression = (a, b) => a + b;

La expresión lambda idéntica que se muestra en el ejemplo anterior se convierte en un árbol de expresión declarado de tipo Expression<T>. El identificador expression no es un código ejecutable; es una estructura de datos llamada árbol de expresión.

Eso significa que no puede simplemente invocar un árbol de expresión como podría invocar a un delegado, sino que puede analizarlo. Entonces, ¿qué puede entender su código al analizar la variable expression?

// `expression.NodeType` returns NodeType.Lambda.
// `expression.Type` returns Func<int, int, int>.
// `expression.ReturnType` returns Int32.

var body = expression.Body;
// `body.NodeType` returns ExpressionType.Add.
// `body.Type` returns System.Int32.

var parameters = expression.Parameters;
// `parameters.Count` returns 2.

var firstParam = parameters[0];
// `firstParam.Name` returns "a".
// `firstParam.Type` returns System.Int32.

var secondParam = parameters[1].
// `secondParam.Name` returns "b".
// `secondParam.Type` returns System.Int32.

Aquí vemos que hay una gran cantidad de información que podemos obtener de una expresión.

Pero, ¿por qué necesitaríamos eso?

Ha aprendido que un árbol de expresión es una estructura de datos que representa código ejecutable. Pero hasta ahora no hemos respondido a la pregunta central de por qué uno querría hacer tal conversión. Esta es la pregunta que hicimos al principio de este artículo, y ahora es el momento de responderla.

Una consulta LINQ to SQL no se ejecuta dentro de su programa C #. En cambio, se traduce a SQL, se envía a través de un cable y se ejecuta en un servidor de base de datos. En otras palabras, el siguiente código nunca se ejecuta realmente dentro de su programa:
var query = from c in db.Customers where c.City == "Nantes" select new { c.City, c.CompanyName };

Primero se traduce a la siguiente declaración SQL y luego se ejecuta en un servidor:
SELECT [t0].[City], [t0].[CompanyName] FROM [dbo].[Customers] AS [t0] WHERE [t0].[City] = @p0

El código que se encuentra en una expresión de consulta debe traducirse en una consulta SQL que se puede enviar a otro proceso como una cadena. En este caso, ese proceso pasa a ser una base de datos de servidor SQL. Obviamente, será mucho más fácil traducir una estructura de datos como un árbol de expresión a SQL que traducir IL sin formato o código ejecutable a SQL. Para exagerar un poco la dificultad del problema, ¡imagínese tratando de traducir una serie de ceros y unos a SQL!

Cuando llega el momento de traducir su expresión de consulta a SQL, el árbol de expresión que representa su consulta se desarma y analiza, tal como desarmamos nuestro árbol de expresión lambda simple en la sección anterior. Por supuesto, el algoritmo para analizar el árbol de expresiones LINQ to SQL es mucho más sofisticado que el que usamos, pero el principio es el mismo. Una vez que ha analizado las partes del árbol de expresión, LINQ las analiza y decide la mejor manera de escribir una declaración SQL que devolverá los datos solicitados.

Los árboles de expresión se crearon para realizar la tarea de convertir código, como una expresión de consulta, en una cadena que se puede pasar a algún otro proceso y ejecutar allí. Es así de simple. No hay un gran misterio aquí, no hay una varita mágica que deba agitarse. Uno simplemente toma el código, lo convierte en datos y luego analiza los datos para encontrar las partes constituyentes que se traducirán en una cadena que se puede pasar a otro proceso.

Debido a que la consulta llega al compilador encapsulada en una estructura de datos tan abstracta, el compilador es libre de interpretarla de la forma que desee. No está obligado a ejecutar la consulta en un orden particular, o de una manera particular. En su lugar, puede analizar el árbol de expresión, descubrir qué desea que se haga y luego decidir cómo hacerlo. Al menos en teoría, tiene la libertad de considerar cualquier número de factores, como el tráfico de red actual, la carga en la base de datos, los conjuntos de resultados actuales que tiene disponibles, etc. En la práctica, LINQ to SQL no considera todos estos factores. , pero en teoría es libre de hacer prácticamente lo que quiera. Además, uno podría pasar este árbol de expresión a algún código personalizado que escriba a mano que podría analizarlo y traducirlo a algo muy diferente de lo que produce LINQ to SQL.

Una vez más, vemos que los árboles de expresión nos permiten representar (¿expresar?) Lo que queremos hacer. Y usamos traductores que deciden cómo se usan nuestras expresiones.

Şafak Gür
fuente
2
Una de las mejores respuestas.
johnny
4
excelente respuesta. Un pequeño aspecto para agregar a esta brillante explicación es: otro uso de los árboles de expresión es que puede modificar el árbol de expresión sobre la marcha en el tiempo de ejecución como mejor le parezca antes de alimentarlo para que se ejecute, lo que a veces es extremadamente útil.
Yan D
41

Un árbol de expresión es un mecanismo para traducir código ejecutable en datos. Usando un árbol de expresión, puede producir una estructura de datos que represente su programa.

En C #, puede trabajar con el árbol de expresión producido por expresiones lambda usando la Expression<T>clase.


En un programa tradicional, escribe código como este:

double hypotenuse = Math.Sqrt(a*a + b*b);

Este código hace que el compilador genere una asignación, y eso es todo. En la mayoría de los casos, eso es todo lo que le importa.

Con el código convencional, su aplicación no puede retroactivamente y mirar hypotenusepara determinar que fue producida al realizar una Math.Sqrt()llamada; esta información simplemente no es parte de lo que se incluye.

Ahora, considere una expresión lambda como la siguiente:

Func<int, int, double> hypotenuse = (a, b) => Math.Sqrt(a*a + b*b);

Esto es un poco diferente que antes. Ahora hypotenusees en realidad una referencia a un bloque de código ejecutable . Si llamas

hypotenuse(3, 4);

obtendrá el valor 5devuelto.

Podemos usar árboles de expresión para explorar el bloque de código ejecutable que se produjo. Prueba esto en su lugar:

Expression<Func<int, int, int>> addTwoNumbersExpression = (x, y) => x + y;
BinaryExpression body = (BinaryExpression) addTwoNumbersExpression.Body;
Console.WriteLine(body);

Esto produce:

(x + y)

Las técnicas y manipulaciones más avanzadas son posibles con árboles de expresión.

AnarchistGeek
fuente
7
Está bien, estuve contigo hasta el final, pero todavía no entiendo por qué esto es tan importante. Estoy teniendo dificultades para pensar en aplicaciones.
1
Estaba usando un ejemplo simplificado; el verdadero poder radica en el hecho de que su código que explora el árbol de expresión también puede ser responsable de interpretarlo y aplicar un significado semántico a la expresión.
Pierreten
2
Sí, esta respuesta hubiera sido mejor si él / ella explicara por qué (x + y) fue realmente útil para nosotros. ¿Por qué querríamos explorar (x + y) y cómo lo hacemos?
Paul Matthews
No tiene que explorarlo, lo hace solo para ver cuál es su consulta y qué se traducirá a algún otro idioma en ese caso a SQL
stanimirsp
15

Los árboles de expresión son una representación en memoria de una expresión, por ejemplo, una expresión aritmética o booleana. Por ejemplo, considere la expresión aritmética

a + b*2

Dado que * tiene una precedencia de operadores mayor que +, el árbol de expresión se construye así:

    [+]
  /    \
 a     [*]
      /   \
     b     2

Teniendo este árbol, se puede evaluar para cualquier valor de ay b. Además, puede transformarlo en otros árboles de expresión, por ejemplo, para derivar la expresión.

Cuando implemente un árbol de expresión, sugeriría crear una expresión de clase base . Derivado de eso, la clase BinaryExpression se usaría para todas las expresiones binarias, como + y *. Luego, podría introducir una VariableReferenceExpression para hacer referencia a variables (como ayb) y otra clase ConstantExpression (para el 2 del ejemplo).

En muchos casos, el árbol de expresión se crea como resultado de analizar una entrada (directamente del usuario o de un archivo). Para evaluar el árbol de expresión, sugeriría usar el patrón Visitor .

EFrank
fuente
15

Respuesta corta: es bueno poder escribir el mismo tipo de consulta LINQ y apuntar a cualquier fuente de datos. No podría tener una consulta "Language Integrated" sin ella.

Respuesta larga: como probablemente sepa, cuando compila el código fuente, lo está transformando de un idioma a otro. Por lo general, de un lenguaje de alto nivel (C #) a un nivel más bajo en (IL).

Básicamente, hay dos formas de hacer esto:

  1. Puede traducir el código usando buscar y reemplazar
  2. Analiza el código y obtiene un árbol de análisis.

Esto último es lo que hacen todos los programas que conocemos como "compiladores".

Una vez que tenga un árbol de análisis, puede traducirlo fácilmente a cualquier otro idioma y esto es lo que los árboles de expresión nos permiten hacer. Dado que el código se almacena como datos, puede hacer lo que quiera, pero probablemente solo quiera traducirlo a otro idioma.

Ahora, en LINQ to SQL, los árboles de expresión se convierten en un comando SQL y luego se envían por cable al servidor de la base de datos. Hasta donde yo sé, no hacen nada realmente elegante al traducir el código, pero podrían hacerlo . Por ejemplo, el proveedor de consultas podría crear un código SQL diferente según las condiciones de la red.

Rodrick Chapman
fuente
6

IIUC, un árbol de expresión es similar a un árbol de sintaxis abstracta, pero una expresión generalmente arroja un valor único, mientras que un AST puede representar un programa completo (con clases, paquetes, funciones, declaraciones, etc.)

De todos modos, para una expresión (2 + 3) * 5, el árbol es:

    *
   / \ 
  +   5
 / \
2   3

Evalúe cada nodo de forma recursiva (de abajo hacia arriba) para obtener el valor en el nodo raíz, es decir, el valor de la expresión.

Por supuesto, también puede tener operadores unarios (negación) o trinarios (if-then-else) y funciones (n-ary, es decir, cualquier número de operaciones) si su lenguaje de expresión lo permite.

La evaluación de tipos y el control de tipos se realizan sobre árboles similares.

Macke
fuente
5

Los
árboles de expresión DLR son una adición a C # para admitir Dynamic Language Runtime (DLR). El DLR es también el que se encarga de darnos el método "var" para declarar variables. ( var objA = new Tree();)

Más sobre el DLR .

Esencialmente, Microsoft quería abrir CLR para lenguajes dinámicos, como LISP, SmallTalk, Javascript, etc. Para hacer eso, necesitaban poder analizar y evaluar expresiones sobre la marcha. Eso no era posible antes de que surgiera el DLR.

Volviendo a mi primera oración, los árboles de expresión son una adición a C # que abre la capacidad de usar el DLR. Antes de esto, C # era un lenguaje mucho más estático: todos los tipos de variables debían declararse como un tipo específico y todo el código debía escribirse en tiempo de compilación.

Usarlo con
árboles de expresión de datos abre las puertas de inundación al código dinámico.

Digamos, por ejemplo, que está creando un sitio inmobiliario. Durante la fase de diseño, conoce todos los filtros que puede aplicar. Para implementar este código, tiene dos opciones: puede escribir un bucle que compare cada punto de datos con una serie de comprobaciones If-Then; o puede intentar crear una consulta en un lenguaje dinámico (SQL) y pasarla a un programa que pueda realizar la búsqueda por usted (la base de datos).

Con los árboles de expresión, ahora puede cambiar el código en su programa - sobre la marcha - y realizar la búsqueda. Específicamente, puede hacer esto a través de LINQ.

(Ver más: MSDN: Cómo: usar árboles de expresión para crear consultas dinámicas ).

Más allá de los datos
Los usos principales de los árboles de expresión son la gestión de datos. Sin embargo, también se pueden utilizar para código generado dinámicamente. Entonces, si desea una función que se defina dinámicamente (como Javascript), puede crear un árbol de expresión, compilarlo y evaluar los resultados.

Me gustaría profundizar un poco más, pero este sitio hace un trabajo mucho mejor:

Árboles de expresión como compilador

Los ejemplos enumerados incluyen la creación de operadores genéricos para tipos de variables, expresiones lambda manuales, clonación superficial de alto rendimiento y copia dinámica de propiedades de lectura / escritura de un objeto a otro.

Los
árboles de expresión de resumen son representaciones de código que se compila y evalúa en tiempo de ejecución. Permiten tipos dinámicos, lo que es útil para la manipulación de datos y la programación dinámica.

Ricardo
fuente
Sí, sé que llego tarde al juego, pero quería escribir esta respuesta como una forma de entenderlo yo mismo. (Esta pregunta me la hicieron alto en mi búsqueda en Internet.)
Richard
Buen trabajo. Es una buena respuesta.
Rich Bryant
5
La palabra clave "var" no tiene nada que ver con DLR. Lo estás confundiendo con la "dinámica".
Yarik
Esta es una buena respuesta pequeña sobre var aquí, que muestra que Yarik está en lo correcto. Sin embargo, agradecido por el resto de la respuesta. quora.com/…
johnny
1
Todo esto está mal. vares un azúcar sintáctico en tiempo de compilación; no tiene nada que ver con árboles de expresión, DLR o el tiempo de ejecución. var i = 0se compila como si escribiera int i = 0, por lo que no puede usarlo varpara representar un tipo que no se conoce en el tiempo de compilación. Los árboles de expresión no son "una adición para admitir DLR", se introducen en .NET 3.5 para permitir LINQ. DLR, por otro lado, se introduce en .NET 4.0 para permitir lenguajes dinámicos (como IronRuby) y la dynamicpalabra clave. En realidad, los árboles de expresión son utilizados por DLR para proporcionar interoperabilidad, no al revés.
Şafak Gür
-3

¿El árbol de expresiones al que hace referencia es el árbol de evaluación de expresiones?

Si es así, entonces es un árbol construido por el analizador. El analizador usó Lexer / Tokenizer para identificar los tokens del programa. El analizador construye el árbol binario a partir de los tokens.

Aquí está la explicación detallada

Vinay
fuente
Bueno, si bien es cierto que un árbol de expresión al que se refiere el OP funciona de manera similar y con el mismo concepto subyacente que un árbol de análisis, se realiza dinámicamente en tiempo de ejecución con código, sin embargo, tenga en cuenta que con la introducción del compilador de Roslyn la línea de La división entre los dos se volvió realmente borrosa si no se eliminó por completo.
yoel halb