Sind LINQ-Expressionsbäume Turing vollständig?

Question

Wie in .Net 3.5. Ich weiß, dass sie in 4.0 sind, da das DLR damit arbeitet, aber ich bin an der Version interessiert, die wir jetzt haben.

Answer 1

LINQ-Ausdrucksbäume können alles darstellen, was Sie in einen normalen C# -Ausdruck eingeben können. Als solche können sie nicht direkt verwendet werden while Schleifen darstellen, for Schleifen usw.

Allerdings ist es theoretisch möglich, Lambda-Ausdrücke und Rekursion zu verwenden, jede Iteration auszuführen Sie benötigen. In der Praxis kann es einfacher sein, Enumerable Methoden in Ihrem Baum zu löschen.

Answer 2

Ohne zu definieren, was den Baum ausführen wird, wissen wir nicht. In der eigenen Interpretation der CLR (wenn Sie sie zu Delegierten zusammenstellen) sind sie. Aber wenn Sie sie in SQL übersetzen, sind sie es nicht, und Sie können Ihre eigene verwirrende Interpretation von ihnen mit irgendwelchen Eigenschaften erfinden, die Sie mögen.

Bis Sie entschieden haben, wie Sie sie interpretieren, sind sie nur Datenstrukturen.

Answer 3

Nun, warum versuchst du es nicht zu beweisen? Ich wette, es ist eine lustige Herausforderung;)

Aber Ausdruck Bäume nur einen Ausdruck darstellen und als solche müssen Sie definieren, was Sie tun dürfen, wie von Earwicker angegeben.

Wenn Sie zulassen, dass Ausdrucksbäume Rekursion verwenden, können Sie Wiederholungen erzielen, d. H. Für Schleifen und ähnliches.

Untypisierte Lambda-Kalkül ist jedoch Turing-komplette Turing_vollständigkeit # Beispiele aber Lambda Kalkül erlaubt keine Rekursion per se Lambda_calculus # Rekursion ist alles sehr heikel.

Ich würde schließen, dass Ausdruck wahrscheinlich Turing abgeschlossen sind, aber es erfordert jemanden, der mehr damit vertraut ist, um es zu bestätigen.

Answer 4

Im frühen Entwurf des C# 3.0-Spezifikation ein Kommentar an den Rand des Abschnitts auf die Expression Bäume gab es, die sagte:

ich einen wahrhaft wunderbaren Beweis für Turing-Vollständigkeit haben, die diese Marge ist auch schmal zu enthalten.

Leider konnte niemand herausfinden, wer es geschrieben oder den Beweis entwickelt hat.