Expression Tree. Просто о сложном

Сегодня мы постараемся посмотреть на сложные вещи с простой стороны. Благодаря глубокому размышлению над темой деревьев выражений в языке C#, я понял, почему эта область считается такой сложной и много авторов попросту стараются либо избегать ее, либо затрагивать лишь вскользь. У популярных авторов книг по языку C#, как, например, Рихтер, Скитт, Албахари, тема деревьев выражений не раскрыта или раскрыта очень слабо. Для интереса я посмотрел множество книг по языку C# и обнаружил, что о деревьях выражений написано очень мало. Обычно на приведении какого-то простого примера материал о деревьях выражений попросту заканчивается.
Я решил пойти от обратного и постараться объяснить сложные вещи простым языком, чтобы новички, только начавшие знакомство с языком C#, не пугались данной темы. Это очень сложная задача для меня, потому что нужно было продумать множество примеров и декомпозировать (расписать в обратном порядке) каждый из них настолько, чтобы пример можно было объяснить простыми терминами и словами.

Рассмотрим, что же такое деревья выражений и зачем они нужны. Деревья выражений представляют код в виде древовидной структуры данных, каждый узел в которой является выражением, например, вызовом метода или двоичной операцией, такой как x < y. Давайте последовательно разберем, как представлять код в виде древовидной структуры. Рассмотрим классический простой пример, в котором создадим функцию Add для суммирования двух элементов.

class Program

{

    static void Main(string[] args)

    {

        int result = Add(3, 4);

        Console.WriteLine(result);

    }

    public static int Add(int a, int b)

    {

        return a + b;

    }

}

Имеем простой и примитивный код для получения суммы двух чисел. В результате на экране после запуска данного приложения получим число "7", что равняется сумме чисел 3 и 4, которые передаются как параметры в данную функцию. Ниже приведена немного хаотическая картинка, в которой расписано каждое действие, проделанное действие функцией Add.

Но в данном случае у нас созданная функция явно с именем Add, которая выполняет необходимое действие. Может быть множество вариантов, в которых нам не нужна отдельная явная функция с именем, а мы можем воспользоваться анонимными функциями на основании делегатов. Если не углубляться в детали, то делегат является указателем на функцию. Это самый базовый вариант описания делегата. Поскольку делегат является указателем на функцию, мы можем вспомнить, что в языке C# уже есть типы делегатов, которые подходят нам для выполнения нужного действия. У нас есть Action, делегат, который инкапсулирует метод, который не принимает ни одного параметра и не возвращает значений (возвращает тип void). Пример использования делегата Action приведен ниже.

static void Main(string[] args)

{

    Action action = () => Console.WriteLine("Hello World");

    action();

}

У нас есть также Action<T>, делегат, который имеет множество разных перегруженных методов, с разным количеством принимаемых аргументов. То есть, данный делегат инкапсулирует метод, который может принимать от 1 до 16 аргументов и ничего не возвращает.

Пример:

static void Main(string[] args)

{

    Action<string> action = a => Console.WriteLine(a);

    action("Hello World");

}

В результате запуска на экране будет выведено текст "Hello World". Также есть тип делегата Func<T, TResult>,  который инкапсулирует значение с одним параметром и возвращает значение типа, указанного в TResult. Этот делегат может принимать от 1-го до 16-ти входящих параметров. А теперь давайте вернемся к нашей функции Add. Если посмотреть на нее внимательно, то перед нами не что иное, как делегат Func с двумя входящими параметрами и возвращаемым типом int. Если переписать нашу функции Add через делегат, то мы получим такую форму записи:

static void Main(string[] args)

{

    Func<int, int, int> action = delegate(int a, int b)

    {

        return a + b;

    };

    var result = action(3, 4);

    Console.WriteLine(result);

}

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

Func<int, int, int> action = (a, b) =>

{

    return a + b;

};

Или еще более короткую запись:

Func<int, int, int> action = (a, b) => a + b;

Вот мы и приблизились к тому, что у нас метод Add аналогичный по сигнатуре методу, который мы переписали с помощью делегата Func<int,int,int>. А теперь давайте вплотную приблизимся к деревьям выражений. Наш делегат выше мы можем преобразовать в дерево выражений следующим способом:

Expression<Func<int, int, int>> expression = (a, b) => a + b;

Expression<Func<T>> организовывается в структуру данных дерева для лямбда-выражения. Эта структура дерева описывает, что лямбда-выражение будет с конкретным выражением. Например, это дерево может содержать в себе информацию о переменных, методах вызова, константных значениях и т.д. То есть, мы можем сами скомпоновать то выражение, которое максимально подходит нам, и преобразовать его к актуальному методу, используя метод Expression.Compile(). Метод Compile() компилирует код, предоставляемый деревом выражений в исполняемый делегат. Мы можем создавать наши деревья выражений, а компилировать их только по надобности. Получаем использование компилятора как сервиса.

Чтобы представить, что же представляет собой дерево expression, приведенное на картинке и в примере выше, мы можем запустить ExpressionTreeVisualizer с примеров, которые можно скачать по ссылке для Visual Studio 2008. Там мы сможем увидеть следующий результат:

Давайте рассмотрим наше дерево как можно детальнее.

Если мы увидели, в какое дерево превращается наш метод, мы можем, с помощью API интерфейса класса Expression, сами собрать исходное дерево по рисунку, приведенному выше.

static void Main(string[] args)

{

    var a = Expression.Parameter(typeof(int), "a"); //Параметр "а"

    var b = Expression.Parameter(typeof(int), "b"); //Параметр "b"

    BinaryExpression addExpr = Expression.Add(a, b); //Сумма "a" + "b"

    var expressionFunc = Expression.Lambda<Func<int, int, int>>

        (

            addExpr, //Сумма "a" + "b"

            new[] { a, b } //Аргументы для передачи "a" и "b" которые указываются снаружи

        );

    Func<int, int, int> add = expressionFunc.Compile();

    int result = add(3, 4);

    Console.WriteLine(result);

}

Код расписан пошагово комментариями. Передавать аргументы можно так, как это сделано как в примере выше, а также воспользовавшись Expression.Block. Пока что ничего сложного. Главное знать, какая функция за что отвечает.  Для этого вы можете ознакомиться с серией статьей, в которой я рассматривал все деревья выражений, которые доступны под .NET Framework 4.0 и выше.

static void Main(string[] args)

{

    int result = 0;

    for (int i = 0; i <= 5; i++)

    {

        result += i;

    }

    Console.WriteLine(result);

}

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

static void Main(string[] args)

{

    Func<int, int> sum = n =>

    {

        int result = 0;

        for (int i = 0; i <= 5; i++)

        {

            result += i;

        }

        return result;

    };

    Console.WriteLine(sum(5));

}

Но если мы заменим наш делегат на дерево выражений и допишем к Func<int,int> запись Expression<Func<int,int>>, то наш проект не скомпилируется.

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

Теперь давайте рассмотрим это дерево более детально. Начнем из разбора цикла. С разбором цикла в дерево выражений есть несколько условий. Как мы помним, классический цикл for выглядит следующим образом:

К сожалению, Expression.Loop в деревьях выражений работает по принципу цикла while, используя для завершения break, goto, return. Если нам нужно перейти на следующую итерацию, то мы можем воспользоваться оператором continue. В деревьях выражений есть класс GotoExpression, который и представляет эти все метки. Ниже на рисунке представлена вся таблица меток, доступных в языке C#, и аналогов операторов с языка C#, которые имеют соответствие в функциях для построения дерева выражений.

Наш код с циклом for можно интерпретировать в цикл while следующим образом:

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

Но здесь есть одна проблема. Как я уже говорил, у нас для дерева выражений должны быть метки перехода. Нельзя без них написать цикл. Для опытных разработчиков переписать код с цикла for в цикл while легко. Для новичков может понадобиться небольшая практика. Для дерева выражений нужна практика еще больше, так как с помощью деревьев выражений ваш код может напоминать такой вид:

Как выглядит переписанный код с for на while с использованием метода перехода:

static void Main(string[] args)

{

    Func<int, int> sum = n =>

    {

        int result = 0;

        int i = 0;

        while (true)

        {

            if (!(i <= n))

                goto breakLoop;

            result += i;

            i++;

        }

        breakLoop:

        return result;

    };

    Console.WriteLine(sum(5));

}

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

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

private static void Main(string[] args)

{

    //Параметр "n" который передается в метод

    ParameterExpression n = Expression.Parameter(typeof (int), "n");

    //Локальная переменная "result"

    ParameterExpression result = Expression.Variable(typeof (int), "result");

    //Локальная переменная "i"

    ParameterExpression i = Expression.Variable(typeof (int), "i");

    //Метка break для выхода из цикла

    LabelTarget endLoop = Expression.Label();

    // {

    Expression block = Expression.Block(

        // int result, i

        new[] { result, i },

        // result = 0

        Expression.Assign(result, Expression.Constant(0)),

        // i = 1

        Expression.Assign(i, Expression.Constant(1)),

        // while (true)

        Expression.Loop(

            // {

            Expression.Block(

                // if

                Expression.IfThen(

                    // (!

                    Expression.Not(

                        // i <= n

                        Expression.LessThanOrEqual(i, n)),

                    // break

                    Expression.Break(endLoop)),

                // result += i

                Expression.AddAssign(result, i),

                // i++

                Expression.PostIncrementAssign(i)

                // )

                ),

            endLoop),

        result);

    // Func<int, int> sum (block - BlockExpression - тело выражения, n - параметр)

    Func<int, int> sum = Expression.Lambda<Func<int, int>>(block, n).Compile();

    Console.WriteLine(sum(5));

}

Сейчас набросаем простую таблицу, в которой выпишем последовательность операций.

Функция Expression.Block позволяет создавать блок дерева выражений, комбинируя разные функции класса Expression. Первым параметром в нашем примере мы передаем список входящих параметров, которые нужно инициализировать. В данном случае это параметры result и i. 
Операция Expression.Assign позволяет присвоить первому параметру значение со второго параметра. Expression.Constant позволяет просто установить неизменяемое начальное значение для начальных параметров. Expression.Loop эквивалентно операции while(true), Expression.IfThen – оператору if, Expression.Not представляет собой операцию поразрядного дополнения. Подробнее об этом можно посмотреть в статье (Deep understanding expression. Part 3), но поскольку поразрядная операция в языке C# определена для целых чисел int, uint, long и ulong, но для булевых выражений данная операция эквивалентна оператору "!" для определения логической операции NOT. Просто будьте с этим бдительны. 
Операция LessThanOrEqual равна операции проверки на меньше или равно. Expression.Break – равносильно оператору break. Expression.AddAssign создает дерево выражений для суммирования двух выражений и сохранения результата в первое выражение. PostIncrementAssign в языке C# равносильна постинкрементной операции. И, наконец, Expression.Lambda создает дерево выражений, которое можно скомпилировать, вызвав метод Compile, и получить составной делегат, который получился в итоге.

Для того, чтобы начать быстро работать с деревьями выражений, вам понадобится некоторый пул функций, которые вы могли бы использовать. Ниже будет приведена таблица функций и их эквивалентов в языке C#, для того чтобы вам можно было использовать данные функции как можно раньше.

Для математических операций как Add/Multiply и т.д. есть функции с приставкой Assign в конце, для того чтобы не только выполнить нужную операцию, а и сохранить результат выполнения в первый параметр. Также есть для таких методов операции с контролем переполнения. В языке C# это равносильно использованию оператора checked. В этих же функциях приставка Checked добавлена к имени функции. Например, функция MultiplyChecked. Функция Molulo позволяет получить значение по модулю, а если сказать проще, то остаток от деления. Поскольку в C# нет оператора, для того чтобы получить значения по модулю, я изобразил ее так, как это сделано в высшей математике. С приходом .NET Framework у нас появились функции для работы с оператором switch, а также функции для обработки ошибок.

Создание параметров мы уже рассмотрели в примерах, но, на всякий случай, припомним их сейчас. Это методы Expression.Parameter и Expression.Variable. Теперь перейдем к операциям сравнения, без которых вы не сможете написать свои логические проверки.

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

Для работы с простыми операциями в языке C# приведенных функций для создания нужных деревьев выражений должно хватить. Множество примеров для каждой функции вы можете найти у меня в блоге, поскольку до этого я почти на каждую из 120 функций, доступных в .NET Framework 4.0, написал, как минимум, по одному примеру. Ссылка на примеры: Deep understanding expression. 
Надеюсь, что такой разбор деревьев выражений получился не очень сложным, и вы сможете подойти к изучению этого довольно таки сложного предмета в мире .NET с уверенностью, так как уже будете понимать, что вас ждет. Я постараюсь не останавливаться на достигнутом, и в ближайшее время мы рассмотрим, как создать элегантный синтаксис для построения деревьев выражений, который намного легче читать и понимать, чем тот код, который мы рассматривали в примерах. 
Поскольку чем сложнее тема, тем меньше конкурентов на пути, и тем выше вы становитесь как профессиональный разработчик. Поверьте, очень мало разработчиков уровня Senior/Team Lead могут похвастаться тем, что они знают, как работают Expression. А тех, которые умеют эти знания применять на практике, еще меньше. Так что будет очень неплохо, если вы сможете освоить эту область, а также умело подходить к разработке ПО с точки зрения деревьев выражений. Если вы поняли, как работают деревья выражений, то как минимум, сможете понять принцип работы LINQ и то, как он строит свои запросы (например, LINQ to Entities). Спасибо за потраченное время на данную статью. Буду рад ответить на вопросы, которые у вас возникли в комментариях.