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

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

Подвести итог;

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

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

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

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

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

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

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

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

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 не выполняется внутри вашей программы C #. Вместо этого он транслируется в 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.

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

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

a + b*2

Поскольку * имеет более высокий приоритет оператора, чем +, дерево выражений строится следующим образом:

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

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

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

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

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

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

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

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

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

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

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

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

В любом случае, для выражения (2 + 3) * 5 дерево выглядит следующим образом:

    *
   / \ 
  +   5
 / \
2   3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вот подробное объяснение