.net - LINQ表達式樹Turing是否完整?



expression-trees dynamic-language-runtime (3)

就像他們在.Net 3.5中一樣。 我知道他們在4.0,因為這是DLR的工作,但我對我們現在的版本感興趣。


Answer #1

LINQ表達式樹可以代表任何你可以放在一個正常的C#表達式。 因此,它們不能用於直接表示while循環, for循環等。

不過,理論上可以使用lambda表達式和遞歸來執行您可能需要的任何迭代。 在實踐中,將Enumerable方法放到樹中可能會更容易。


Answer #2

沒有定義將執行樹的東西,我們不知道。 在CLR自己的解釋中(當你把它們編成代表時)是這樣的。 但是如果你把它們翻譯成SQL,那麼它們不是,你可以用你喜歡的任何屬性來發明你自己的混淆解釋。

在你決定如何解釋它們之前,它們只是數據結構。


Answer #3

那麼,你為什麼不試圖證明呢? 我敢打賭,這是一個有趣的挑戰;)

但是表達式樹只代表一個表達式,就像Earwicker所說的那​​樣,你必須定義你允許做的事情。

如果你允許表達式樹使用遞歸,你可以實現重複,即循環等。

然而,無類型的lambda微積分是圖靈完備的Turing_completeness#例子,但Lambda微積分不允許遞歸本身Lambda_calculus#遞歸它都是非常危險的。

我會得出結論表達可能是圖靈完成,但它會需要一個更熟悉這個來確認它的人。





turing-complete