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

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

(string s) => s.Length

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

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

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

Ответ 1

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

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

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

Ответ 2

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

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

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

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

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

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

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