Выражение деревьев для чайников?

Ответ 1

Дерево выражений - это механизм для преобразования исполняемого кода в данные. Используя дерево выражений, вы можете создать структуру данных, представляющую вашу программу.

В С# вы можете работать с деревом выражений, создаваемым лямбда-выражениями, с помощью класса Expression<T>.

В традиционной программе вы пишете такой код:

double hypotenuse = Math.Sqrt(a*a + b*b);

Этот код заставляет компилятор генерировать назначение и что он. В большинстве случаев это все, что вам нужно.

С помощью обычного кода ваше приложение не может вернуться назад и посмотреть hypotenuse, чтобы определить, что оно было создано путем выполнения вызова Math.Sqrt(); эта информация просто не является частью того, что включено.

Теперь рассмотрим лямбда-выражение, подобное следующему:

Func<int, int, int> hypotenuse = (a, b) => Math.Sqrt(a*a + b*b);

Это немного отличается от предыдущего. Теперь hypotenuse на самом деле является ссылкой на блок исполняемого кода. Если вы вызываете

hypotenuse(3, 4);

вы получите возвращаемое значение 5.

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

Expression<Func<int, int, int>> addTwoNumbersExpression = (x, y) => x + y;
BinaryExpression body = (BinaryExpression) addTwoNumbersExpression.Body;
Console.WriteLine(body);

Это дает:

(x + y)

Более сложные методы и манипуляции возможны с деревьями выражений.

Ответ 2

Лучшее объяснение в деревьях выражений, которые я когда-либо читал, эта статья Чарли Калверта.

Подводя итог:

Дерево выражений представляет что, а не , как, которое вы хотите сделать.

Рассмотрим следующее очень простое лямбда-выражение:
Func<int, int, int> function = (a, b) => a + b;

Этот оператор состоит из трех разделов:

• Объявление: Func<int, int, int> function
• Оператор равенства: =
• Лямбда-выражение: (a, b) => a + b;

Переменная function указывает на необработанный исполняемый код, который знает, как добавить два числа.

Это самое важное различие между делегатами и выражениями. Вы вызываете function, не зная, что он будет делать с двумя целыми числами, которые вы передали. Он берет два и возвращает один, что может знать ваш код.

В предыдущем разделе вы увидели, как объявить переменную, указывающую на необработанный исполняемый код. Деревья выражений не являются исполняемым кодом, они являются формой структуры данных.

Теперь, в отличие от делегатов, ваш код может знать, что должно делать дерево выражений.

LINQ предоставляет простой синтаксис для перевода кода в структуру данных, называемую деревом выражений. Первым шагом является добавление оператора using для представления пространства имен Linq.Expressions:

using System.Linq.Expressions;

Теперь мы можем создать дерево выражений:
Expression<Func<int, int, int>> expression = (a, b) => a + b;

Тождественное лямбда-выражение, показанное в предыдущем примере, преобразуется в дерево выражений, объявленное как тип Expression<T>. Идентификатор expression не является исполняемым кодом; это структура данных, называемая деревом выражений.

Это означает, что вы не можете просто вызвать дерево выражений, как вы могли бы вызвать делегата, но вы можете его проанализировать. Итак, что может понять ваш код, анализируя переменную expression?

// `expression.NodeType` returns NodeType.Lambda.
// `expression.Type` returns Func<int, int, int>.
// `expression.ReturnType` returns Int32.

var body = expression.Body;
// `body.NodeType` returns ExpressionType.Add.
// `body.Type` returns System.Int32.

var parameters = expression.Parameters;
// `parameters.Count` returns 2.

var firstParam = parameters[0];
// `firstParam.Name` returns "a".
// `firstParam.Type` returns System.Int32.

var secondParam = parameters[1].
// `secondParam.Name` returns "b".
// `secondParam.Type` returns System.Int32.

Здесь мы видим, что есть много информации, которую мы можем получить из выражения.

Но зачем нам это нужно?

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

Запрос LINQ to SQL не выполняется внутри вашей программы на С#. Вместо этого он преобразуется в SQL, отправляется по проводке и выполняется на сервере базы данных. Другими словами, следующий код никогда не выполняется внутри вашей программы:
var query = from c in db.Customers where c.City == "Nantes" select new { c.City, c.CompanyName };

Сначала он преобразуется в следующий оператор SQL, а затем выполняется на сервере:
SELECT [t0].[City], [t0].[CompanyName] FROM [dbo].[Customers] AS [t0] WHERE [t0].[City] = @p0

Код, найденный в выражении запроса, должен быть переведен в SQL-запрос, который может быть отправлен другому процессу в виде строки. В этом случае этот процесс является базой данных SQL-сервера. Очевидно, будет намного проще перевести структуру данных, такую ​​как дерево выражений в SQL, чем преобразовать необработанный IL или исполняемый код в SQL. Чтобы преувеличивать сложность проблемы, просто представьте, что вы пытаетесь перевести серию нулей и единиц в SQL!

Когда пришло время перевести выражение запроса в SQL, дерево выражений, представляющее ваш запрос, будет разобрано и проанализировано так же, как мы разделили наше простое дерево лямбда-выражения в предыдущем разделе. Разумеется, алгоритм анализа дерева выражений LINQ to SQL намного сложнее, чем тот, который мы использовали, но принцип тот же. После того, как он проанализировал части дерева выражений, LINQ обдумывает их и решает наилучший способ написать инструкцию SQL, которая вернет запрошенные данные.

Деревья выражений были созданы для того, чтобы задача преобразования кода, такого как выражение запроса, в строку, которая может быть передана другому процессу и выполнена там. Это так просто. Здесь нет великой тайны, нет волшебной палочки, которую нужно махать. Один просто берет код, преобразует его в данные и затем анализирует данные, чтобы найти составные части, которые будут переведены в строку, которая может быть передана другому процессу.

Поскольку запрос приходит к компилятору, инкапсулированному в такой абстрактной структуре данных, компилятор может свободно интерпретировать его практически любым способом. Он не вынужден выполнять запрос в определенном порядке или определенным образом. Вместо этого он может анализировать дерево выражений, обнаруживать, что вы хотите сделать, а затем решить, как это сделать. По крайней мере, теоретически, он имеет право рассматривать любое количество факторов, таких как текущий сетевой трафик, нагрузку на базу данных, текущие результаты, которые он имеет, и т.д. На практике LINQ to SQL не учитывает все эти факторы, но теоретически свободно делать то, что он хочет. Кроме того, можно передать это дерево выражений на какой-то пользовательский код, который вы пишете вручную, который мог бы проанализировать его и перевести его во что-то очень отличающееся от того, что создается LINQ to SQL.

И снова мы видим, что деревья выражений позволяют нам представлять (выражать?) то, что мы хотим сделать. И мы используем переводчиков, которые решают , как выполняются наши выражения.

Ответ 3

Деревья выражений являются представлением выражения в памяти, например. арифметическое или булево выражение. Например, рассмотрим арифметическое выражение

a + b*2

Так как * имеет более высокий приоритет оператора, чем +, дерево выражений построено так:

    [+]
  /    \
 a     [*]
      /   \
     b     2

Имея это дерево, оно может быть оценено для любых значений a и b. Кроме того, вы можете преобразовать его в другие деревья выражений, например, чтобы получить выражение.

Когда вы реализуете дерево выражений, я бы предложил создать базовый класс Expression. Получившись от этого, класс BinaryExpression будет использоваться для всех двоичных выражений, таких как + и *. Затем вы можете ввести выражение VariableReferenceExpression для ссылки на переменные (такие как a и b) и другое выражение ConstantExpression класса (для примера 2).

Дерево выражений во многих случаях построено как результат разбора ввода (от пользователя напрямую или из файла). Для оценки дерева выражений я бы предложил использовать шаблон посетителя.

Ответ 4

Короткий ответ: Приятно иметь возможность написать один и тот же запрос LINQ и указать его на любой источник данных. Без него не может быть запрошен "Language Integrated".

Длинный ответ: Как вы, наверное, знаете, когда вы компилируете исходный код, вы трансформируете его с одного языка на другой. Обычно с языка высокого уровня (С#) на нижний рычаг (IL).

В основном вы можете сделать это двумя способами:

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

Последнее - это то, что делают все программы, которые мы знаем как "компиляторы".

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

Теперь в LINQ to SQL деревья выражений превращаются в команду SQL, а затем отправляются по проводке на сервер базы данных. Насколько я знаю, они не делают ничего действительно при переводе кода, но могли. Например, поставщик запросов мог создать другой код SQL в зависимости от условий сети.

Ответ 5

IIUC, дерево выражений похоже на абстрактное дерево синтаксиса, но выражение обычно имеет единственное значение, тогда как AST может представлять целую программу (с классами, пакетами, функциями, операторами и т.д.).

Во всяком случае, для выражения (2 + 3) * 5 дерево:

    *
   / \ 
  +   5
 / \
2   3

Оцените каждый node рекурсивно (снизу вверх), чтобы получить значение в корневом каталоге node, то есть значение выражения.

У вас могут быть, например, унарные (отрицательные) или триниальные (if-then-else) операторы, а также функции (n-ary, т.е. любое количество ops), если это позволяет ваш язык выражений.

Оценка типов и управление типом осуществляется по аналогичным деревьям.

Ответ 6

DLR
Деревья выражений являются добавлением к С# для поддержки динамического языка Runtime (DLR). DLR также отвечает за предоставление нам "var" метода объявления переменных. (var objA = new Tree();)

Подробнее о DLR.

По сути, Microsoft хотела открыть CLR для динамических языков, таких как LISP, SmallTalk, Javascript и т.д. Чтобы сделать это, им нужно было время синтаксически анализировать и оценивать выражения. Это было невозможно до появления DLR.

К моему первому предложению, деревья выражений являются дополнением к С#, что открывает возможность использования DLR. До этого С# был гораздо более статическим языком - все типы переменных должны были быть объявлены как определенный тип, и весь код должен был быть написан во время компиляции.

Используя его с данными
Деревья выражений открывают потоковые ворота динамическому коду.

Скажем, например, что вы создаете сайт недвижимости. На этапе проектирования вы знаете все фильтры, которые вы можете применить. Для реализации этого кода у вас есть два варианта: вы можете написать цикл, который сравнивает каждую точку данных с серией проверок If-Then; или вы можете попытаться построить запрос на динамическом языке (SQL) и передать его программе, которая может выполнить поиск для вас (база данных).

С помощью деревьев выражений теперь вы можете изменить код в своей программе - на лету - и выполнить поиск. В частности, вы можете сделать это через LINQ.

(Подробнее: MSDN: Как использовать деревья выражений для создания динамических запросов).

Помимо данных
Основное использование для деревьев выражений предназначено для управления данными. Однако они также могут использоваться для динамически генерируемого кода. Итак, если вам нужна функция, которая определяется динамически (ala Javascript), вы можете создать Дерево выражений, скомпилировать ее и оценить результаты.

Я бы пошел немного глубже, но этот сайт делает гораздо лучшую работу:

Деревья выражений как компилятор

В число приведенных примеров входит создание родовых операторов для типов переменных, ручных лямбда-выражений, высокопроизводительное мелкое клонирование и динамическое копирование свойств чтения/записи с одного объекта на другой.

Резюме
Деревья выражений представляют собой представления кода, который компилируется и оценивается во время выполнения. Они позволяют использовать динамические типы, которые полезны для обработки данных и динамического программирования.

Ответ 7

Является ли дерево выражений, на которое вы ссылаетесь, является деревом оценки выражений?

Если да, то это дерево, построенное парсером. Parser использовал Lexer/Tokenizer для идентификации токенов из программы. Parser создает двоичное дерево из токенов.

Здесь - подробное объяснение