.net - LINQ 表达式树图灵完备吗？

Question

正如他们在.Net 3.5中一样。我知道它们在 4.0 中，因为这就是 DLR 的工作方式，但我对我们现在拥有的版本感兴趣。

Answer 1

在 C# 3.0 规范的早期草案中，表达式树部分的边缘有一条评论说：

我有一个非常了不起的图灵完备性证明，这个边距太窄而无法包含。

可悲的是，没有人能够找出谁写了它或开发了证明。

Answer 2

如果不定义将执行树的东西，我们不知道。在 CLR 自己的解释中（当您将它们编译为委托时）它们是。但是如果你将它们翻译成 SQL，它们就不是，你可以用你喜欢的任何属性来创造你自己对它们的令人困惑的解释。

在您决定如何解释它们之前，它们只是数据结构。

Answer 3

LINQ 表达式树可以表示您可以放入普通 C# 表达式中的任何内容。因此，它们不能用于直接表示while循环、for循环等。

但是，理论上可以使用 lambda 表达式和递归来执行您可能需要的任何迭代。Enumerable在实践中，将方法放入树中可能更容易。

Answer 4

那么，你为什么不尝试证明呢？我敢打赌这是一个有趣的挑战；）

但是表达式树仅代表一个表达式，因此您必须定义允许执行的操作，如 Earwicker 所述。

如果您允许表达式树使用递归，您可以实现重复，即 for 循环等。

然而，无类型的 lambda 演算是图灵完备的 Turing_completeness#Examples 但 Lambda 演算本身不允许递归 Lambda_calculus#Recursion 这一切都很冒险。

我会得出结论，表达式可能是图灵完备的，但需要更熟悉这一点的人来确认它。