¿Están terminados los árboles de expresión de LINQ Turing?

Question

Como están en .Net 3.5. Sé que están en 4.0, ya que es con lo que trabaja DLR, pero estoy interesado en la versión que tenemos ahora.

Answer 1

Los árboles de expresión LINQ pueden representar cualquier cosa que pueda poner en una expresión C# normal. Como tal, no se pueden usar para representar directamente los bucles while, for bucles, etc.

Sin embargo, teóricamente es posible utilizar expresiones lambda y recursión para llevar a cabo cualquier iteración que pueda necesitar. En la práctica, puede ser más fácil eliminar los métodos Enumerable en su árbol.

Answer 2

Sin definir lo que ejecutará el árbol, no lo sabemos. En la propia interpretación del CLR (cuando los compila en delegados) lo son. Pero si los traduce a SQL, no lo son, y puede inventar su propia interpretación confusa de ellos con las propiedades que desee.

Hasta que haya decidido cómo interpretarlos, solo son estructuras de datos.

Answer 3

Bueno, ¿por qué no intentas probarlo? Apuesto a que es un desafío divertido;)

Pero los árboles de expresión solo representan una expresión y, por lo tanto, tendrás que definir lo que puedes hacer, como afirma Earwicker.

Si permite que los árboles de expresión usen la recursión puede lograr la repetición, es decir, para bucles y demás.

Sin embargo, el cálculo lambda sin tipo es Turing-completo Complejidad-Turing # Ejemplos pero el cálculo Lambda no permite la recursión per se Lambda_calculus # Recursion todo es muy incierto.

Concluiré que la expresión probablemente sea Turing completa pero requerirá que alguien que esté más familiarizado con esto lo confirme.

Answer 4

En el primer borrador de la especificación C# 3.0 había un comentario en el margen de la sección sobre los árboles de expresión que dijo:

tengo una demostración verdaderamente maravillosa de Turing-completo pero este margen es demasiado estrecho para contener.

Lamentablemente, nadie ha sido capaz de averiguar quién lo escribió o desarrollar la prueba.