¿Los árboles de expresión LINQ son árboles apropiados?

Question

¿Los árboles de expresión LINQ son árboles propios, como en, gráficos (dirigidos o no, la wikipedia no parece estar muy de acuerdo) sin ciclos? ¿Cuál es la raíz de un árbol de expresiones a partir de la siguiente expresión C#?

árbol

(string s) => s.Length 

La expresión se parece a esto, con "->" indica el nombre de la propiedad del nodo al otro nodo es accesible a través.

 ->Parameters[0] 
Lambda---------Parameter(string s) 
    \    /
    \->Body  /->Expression 
     \   /
     Member(Length) 

Al utilizar ExpressionVisitor para visitar LambdaExpression, el parámetro ParameterExpression se visita dos veces. ¿Hay alguna manera de usar ExpressionVisitor para visitar LambdaExpression de manera que todos los nodos se visiten exactamente una vez, y en un orden específico y conocido (preorden, en orden, pedido posterior, etc.)?

Answer 1

tipo de, sí. El "tronco" real (si se quiere) de un LambdaExpression es el .Body; los parámetros son metadatos necesarios sobre la estructura del árbol (y lo que necesita), pero .Parameters en la parte superior (su línea punteada) no es realmente parte del gráfico funcional del árbol; es solo cuando esos nodos se usan más adelante en el cuerpo real del árbol que son interesantes, como sustituciones de valores.

El ParameterExpression que se visita dos veces es esencial, por lo que es posible que alguien cambie los parámetros si lo desea; por ejemplo, para construir un nuevo LambdaExpression con el mismo número de parámetros, pero instancias de parámetros diferentes (tal vez el tipo).

El pedido será bastante estable, pero se debe considerar como un detalle de implementación. Por ejemplo, dado un nodo como Add(A,B), no debería haber diferencia semántica si visito ese A -primero frente a B -primero.

Answer 2

Sólo para añadir un poco a la respuesta correcta de Marc:

Son árboles de expresión LINQ dirigidos gráficos sin ciclos?

En primer lugar, sí, un árbol de expresión es un DAG - un gráfico acíclico dirigido.

Sabemos que son acíclicos porque los árboles de expresión son inmutables, y por lo tanto tienen que construirse desde las hojas hacia arriba. En tal situación no hay forma de hacer un ciclo porque todos los nodos en el ciclo tendrían que ser asignados últimos, y claramente eso no va a suceder.

Como las partes son inmutables, la expresión "árbol" no necesita ser realmente un árbol per se. Como Marc señala, es necesario que reutilice la referencia para el parámetro; así es como determinamos cuándo se usa un parámetro declarado. Es algo extraño, aunque legal, reutilizar otras partes también. Por ejemplo, si quisiera representar el árbol de expresiones para el cuerpo de (int x)=>(x + 1) * (x + 1), podría hacer un árbol de expresiones para (x + 1) y luego hacer un nodo de multiplicación donde ambos hijos fueran ese árbol de expresiones.

Al usar ExpressionVisitor para visitar LambdaExpression, el parámetro ParameterExpression se visita dos veces. ¿Hay alguna manera de usar ExpressionVisitor para visitar LambdaExpression de manera que todos los nodos se visiten exactamente una vez, y en un orden específico y conocido (preorden, en orden, pedido posterior, etc.)?

ExpressionVisitor es una clase abstracta. Puedes hacer tu propia versión concreta que tenga la semántica que te gusta. Por ejemplo, puede anular el método Visit de modo que mantenga un HashSet de nodos ya visto, y no llame a Accept en los nodos que haya aceptado previamente.