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

83

Я манекен в этом сценарии.

Я пытался прочитать в Google, что это такое, но не понимаю. Может ли кто-нибудь дать мне простое объяснение того, что это такое и почему они полезны?

edit: я говорю о функции LINQ в .Net.


источник
1
Я знаю, что этот пост довольно старый, но в последнее время я заглядывал в деревья выражений. Я заинтересовался этим после того, как начал использовать Fluent NHibernate. Джеймс Грегори широко использует то, что известно как статическое отражение, и у него есть введение: jagregory.com/writings/introduction-to-static-reflection Чтобы увидеть статическое отражение и деревья выражений в действии, ознакомьтесь с исходным кодом Fluent NHibernate ( fluentnhibernate.org ). Это очень чисто и очень круто.
Джим Шуберт,

Ответы:

89

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

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

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

Рассмотрим следующее очень простое лямбда-выражение:
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.

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

Шафак Гюр
источник
2
Один из лучших ответов.
Джонни
4
отличный ответ. один небольшой аспект, который следует добавить к этому блестящему объяснению, заключается в том, что деревья выражений можно использовать еще и в том, что вы можете изменять дерево выражений на лету во время выполнения по своему усмотрению, прежде чем подавать его на выполнение, что иногда бывает чрезвычайно полезно.
Yan D
41

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

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


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

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

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

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

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

Func<int, int, double> 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)

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

АнархистГик
источник
7
Хорошо, я был с тобой до самого конца, но до сих пор не понимаю, почему это так важно. Мне сложно думать о приложениях.
1
Он использовал упрощенный пример; истинная сила заключается в том, что ваш код, исследующий дерево выражений, также может быть ответственным за его интерпретацию и применение семантического значения к выражению.
Pierreten
2
Да, этот ответ был бы лучше, если бы он / она объяснил, почему (x + y) действительно был нам полезен. Зачем нам исследовать (x + y) и как это сделать?
Пол Мэтьюз
Вы не должны изучить его, вы делаете это только чтобы узнать , что ваш запрос и что будет переведен на какой - то другой язык , в этом случае к SQL
stanimirsp
15

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

a + b*2

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

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

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

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

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

EFrank
источник
15

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

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

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

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

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

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

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

Родрик Чепмен
источник
6

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

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

    *
   / \ 
  +   5
 / \
2   3

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

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

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

Macke
источник
5


Деревья выражений 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), вы можете создать дерево выражений, скомпилировать его и оценить результаты.

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

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

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

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

Ричард
источник
Да, я знаю, что опаздываю в игру, но я хотел написать этот ответ, чтобы самому понять его. (Этот вопрос стал популярным в моем поиске в Интернете.)
Ричард
Хорошая работа. Хороший ответ.
Rich Bryant
5
Ключевое слово var не имеет ничего общего с DLR. Вы путаете это с «динамическим».
Ярик
Это хороший небольшой ответ на var, который показывает, что Ярик прав. Однако благодарен за остальной ответ. quora.com/…
johnny
1
Это все неправильно. varявляется синтаксическим сахаром времени компиляции - он не имеет ничего общего с деревьями выражений, DLR или средой выполнения. var i = 0компилируется, как если бы вы написали int i = 0, поэтому вы не можете использовать его varдля представления типа, который не известен во время компиляции. Деревья выражений не являются «дополнением для поддержки DLR», они введены в .NET 3.5 для поддержки LINQ. DLR, с другой стороны, представлен в .NET 4.0, чтобы разрешить использование динамических языков (например, IronRuby) и dynamicключевое слово. Деревья выражений фактически используются DLR для обеспечения взаимодействия, а не наоборот.
Şafak Гур
-3

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

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

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

Vinay
источник
Хотя верно, что дерево выражений, на которое ссылается OP, работает аналогично и с той же базовой концепцией, что и дерево синтаксического анализа, оно выполняется динамически во время выполнения с помощью кода, однако обратите внимание на введение компилятора Roslyn в строку разделение между ними стало действительно размытым, если не полностью устраненным.
Йоэль Халб 04