Являются ли деревья выражений LINQ правильными деревьями?

Question

Являются ли деревья выражений LINQ собственными деревьями, как, например, графы (направленные или нет, википедия не кажется слишком согласной) без циклов? Каков корень дерева выражений из следующего выражения C #?

(string s) => s.Length

Дерево выражений выглядит следующим образом: «->» обозначает имя свойства узла, через который доступен другой узел.

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

При использовании ExpressionVisitor для посещения LambdaExpression, ParameterExpression посещается дважды. Есть ли способ использовать ExpressionVisitor для посещения LambdaExpression, чтобы все узлы посещались ровно один раз и в определенном, хорошо известном порядке (предварительный заказ, заказ, пост-заказ и т. Д.)?

Answer 1

Просто добавлю немного правильного ответа Марка:

Являются ли деревья выражений LINQ ориентированными графами без циклов?

Прежде всего, да, дерево выражений - это DAG - ориентированный ациклический граф.

Мы знаем, что они являются ациклическими, потому что деревья выражений неизменны , и поэтому должны быть построены из листьев. В такой ситуации невозможно создать цикл, потому что все узлы в цикле должны быть выделены last , и, очевидно, этого не произойдет.

Поскольку части являются неизменяемыми, выражение «дерево» не обязательно должно быть деревом как таковым. Как указывает Марк, необходимо повторно использовать ссылку для параметра; так мы определяем, когда используется объявленный параметр. Несколько странно, хотя и законно, повторно использовать и другие части. Например, если вы хотите представить дерево выражений для тела (int x)=>(x + 1) * (x + 1), вы можете создать дерево выражений для (x + 1), а затем создать узел умножения, в котором оба потомка были этим деревом выражений.

При использовании ExpressionVisitor для посещения LambdaExpression, ParameterExpression посещается дважды. Есть ли способ использовать ExpressionVisitor для посещения LambdaExpression, чтобы все узлы посещались ровно один раз и в определенном, хорошо известном порядке (предварительный заказ, заказ, пост-заказ и т. Д.)?

ExpressionVisitor - абстрактный класс. Вы можете сделать свою собственную конкретную версию, имеющую семантику, которая вам нравится. Например, вы можете переопределить метод Visit так, чтобы он поддерживал HashSet уже увиденных узлов и не вызывал Accept на узлах, которые он ранее принял.

Answer 2

Вроде да. Фактический «ствол» (если хотите) LambdaExpression - это .Body; параметры - это необходимые метаданные о структуре дерева (и о том, что ему нужно), но .Parameters вверху (ваша пунктирная линия) на самом деле не является частью функционального графа дерева - это только когда эти узлы используются позже в фактическом теле дерева, которые они интересны, как подстановки значений.

Необходимо посещать ParameterExpression дважды, так что кто-то может поменять местами параметры, если захочет, например, построить новый LambdaExpression с тем же числом параметров, но с разными экземплярами параметров. (возможно, сменив тип).

Порядок будет достаточно стабильным, но его следует рассматривать как деталь реализации. Например, для данного узла, такого как Add(A,B), не должно быть семантической разницы, посещаю ли я этот A -первый против B -первый.