Доброго времени суток. Деревья выражений, особенно в сочетании с паттерном Visitor, всегда являлись довольно запутанной темой. Поэтому чем больше разнообразной информации по этой теме, чем больше примеров, тем легче интересующимся будет найти что-то, что им понятно и полезно.
Статья построена как обычно — начинается с концептуальных основ и определений и заканчивается примерами и способами использования. Оглавление ниже.
Основы деревьев выражений
Синтаксис деревьев выражений
Типы выражений
Паттерн Матчинг
Наивный визитор
Классический визитор
Ну и целью не является навязать определенное решение или сказать, что одно лучше другого. Выводы предлагаю делать самим с учетом всех нюансов в вашем случае. Я же выскажу свое мнение на своем примере.
Для начала необходимо разобраться с деревьями выражений. Под ними понимают тип Expression или любой из его наследников (о них речь пойдет позже). При обычном раскладе выражение/алгоритмы представляются в виде выполняемого кода/инструкций, с которыми пользователь может не так и много чего делать (в основном выполнять). Тип Expression позволяет представить выражение/алгоритм (как правило лямбды, но не обязательно) как данные, организованные в виде древовидной структуры, к которой пользователь имеет доступ. Древовидный способ организации информации об алгоритме и название класса и дают нам «деревья выражений».
Для понятности разберем простой пример. Допустим, у нас есть лямбда
(х) => Console.WriteLine(х + 5)
Это можно представить в виде следующего дерева
Корень дерева — вершина "MethodCall", параметры метода — также выражения, следовательно может иметь сколько угодно потомков.
В нашем случае потомок один — вершина "ArithmeticOperation". В ней содержится информация о том, какая конкретно это операция и левый и правый операнды — также выражения. У такой вершины будет всегда 2 потомка.
Операнды представлены константой (Constant) и параметром (Parameter). У таких выражений нет потомков.
Это очень упрощенные примеры, но полностью отражающие суть.
Основная особенность деревьев выражений — это то, что их можно парсить и вычитывать всю необходимую информацию о том, что алгоритм должен делать. С какой-то точки зрения, это противоположность атрибутам. Атрибуты — средство декларативного описания поведения (очень условно, но конечная цель примерно такая). В то время как деревья выражений — использование функции/алгоритма для описания данных.
Используются они, например, в провайдерах entity framework. Применение очевидно — распарсить дерево выражений, понять, что там должно выполниться и составить по этому описанию SQL. Из менее известных примеров — библиотека для мокинга moq. Деревья выражений также нашли применение в DLR (dynamic language runtime). Разработчики компилятора используют их при обеспечении совместимости между динамической природой и dotnet, вместо генерации MSIL.
Также стоит упомянуть, что деревья выражений неизменяемы.
Следующее, что стоит обговорить — синтаксис. Существуют 2 основных способа:
Создание деревьев выражений через статические методы класса Expression используется реже (в особенности с пользовательской точки зрения). Это громоздко, но довольно просто, в нашем
распоряжении множество базовых кирпичиков, из которых можно построить довольно сложные
вещи. Создание происходит через статические методы, т.к. конструкторы выражений имеют модификатор internal. И это не означает, что нужно расчехлять рефлексию.
В качестве примера привожу создание выражения с примера выше:
(х) => Console.WriteLine(х + 5)
Может, это и не очень удобный способ, зато он полностью отражает внутреннюю структуру деревьев выражений. Плюс данный способ дает больше возможностей и фич, которые можно использовать в деревьях выражений: начиная от циклов, условий, try-catch, goto, присваивания, заканчивая блоками fault, отладочной информацией для точек останова, dynamic и тд.
Использование лямбд в качестве выражений — более частый способ. Работает очень просто — умный компилятор на этапе компиляции смотрит, в качестве чего используется лямбда. И компилирует ее либо в делегат, либо в выражение. На уже освоенном примере, выглядит следующим образом
Стоит уточнить такую вещь — выражение — это исчерпывающее описание. И его достаточно чтобы
получить результат. Деревья выражений типа LambdaExpression или его наследников могут быть
cконвертировано в выполняемый IL. Остальные типы нельзя напрямую cконвертировать в выполняемы код (но это и не имеет много смысла).
Кстати, если кому-то критична быстрая компиляция выражения, можно взглянуть на этот сторонний проект.
Обратное же в общем случае неверно. Делегат не может просто так взять и представится выражением (но это все равно возможно).
Не все лямбды могут быть cконвертированы в деревья выражений. К таковым относятся:
Предлагаю бегло ознакомится с доступными типами, чтобы представлять, какие возможности мы имеем. Все они находятся в пространстве имен System.Linq.Expressions
Я предлагаю для начала ознакомится с несколькими действительно интересными и необычными возможностями. Более простые типы выражений я собрал в табличку с кратким описанием.
С помощью DynamicExpression есть возможность использовать dynamic и все его фишки в деревьях выражений. Там довольно запутанное API, над этим примером я сидел дольше, чем над всеми остальными вместе взятыми. Вся запутанность обеспечивается кучей разного рода флагов. И некоторые из них похожи на те, которые вы ищите, но не обязательно ими являются. А при работе с dynamic в деревьях выражений говорящую ошибку получить сложно. Пример:
Я явно указал, откуда берется Binder во избежание путаницы с биндером из System.Reflection. Из интересностей — мы можем делать ref и out параметры, именованные параметры, унарные операции да и в принципе все, что можно сделать через dynamic, однако это потребует определенной сноровки.
Второе, на что обращу внимание — try/catch/finally/fault функциональность, а точнее на то,
что у нас есть доступ к fault блоку. Он не доступен в C#, однако есть в MSIL.Это своеобразный
аналог finally, который выполнится в случае любого исключения. В примере ниже выбросится исключение, после чего будет выведено «Hi» и программа будет ждать ввода. Только после этого она упадет окончательно. Не рекомендую эту практику к использованию.
Данных сведений достаточно, чтобы приступить к сравнению методов работы с деревьями выражений. Я решил разобрать это все на примере нахождения производной. Все возможные варианты я не предусматривал — лишь базовые. Но если кто-то зачем-то решил доработать и использовать — буду рад, если поделитесь улучшениями через реквест в мой репозиторий.
Итак, задача состоит в том, чтобы сделать тулу-считалку производных. Можно прикинуть следующее: есть пару правил нахождения производной для разных типов операции — умножение, деление и тд. В зависимости от операции необходимо выбрать определенную формулу. В такой банальной формулировке задача идеально ложиться на switch/case. А в последней версии языка нам представили switch/case 2.0 или сопоставление с образцом (pattern matching).
Здесь сложно что-то обсуждать. На хабре такое количесво кода выглядит громоздко и плохо читается, поэтому предлагаю смотреть на github. На примере производной вышло так:
Выглядит немного непривычно, но интересно. Писать такое было приятно — все условия органично ложатся в одну строку.
Пример говорит сам за себя, словами лучше и не опишешь.
В такой задаче тут же на ум приходит про expression tree visitor, который наводит много шума
и чуть-чуть паники среди любителей обсудить аджайл на кухне. «Бойся ни незнания, а ложного знания. Лучше ничего не знать, чем считать правдой то, что неправда». Вспомнив сие чудную фразу Толстого, признав незнание и заручившись поддержкой гугла можно найти следующее руководство.
У меня данная ссылка является первой (после Сибири в 1949) по запросу «Expression tree visitor».
На первый взгляд это именно то, что надо. Название статьи подходит к тому, что мы хотим сделать, а классы в примерах называются с суффиксом Visitor.
Ознакомившись со статьей и сделав по аналогии для нашего примера с производными получим:
Ссылка на github.
По сути — мы размазали свитч кейсы по разным классам. Меньше их не стало, магии не появилось. Все те же кейсы, гораздо больше строк. А где же обещанная двойная double dispatch диспетчеризация?
Здесь уже стоит рассказать про сам шаблон "Посетитель", он же Visitor, который и положен в основу Expression tree visitor'а. Разберем его как раз на примере деревьев выражений.
На секунду предположим, что мы разрабатываем деревья выражений. Мы хотим дать пользователям возможность итерироваться по дереву выражений и в зависимости от типов узлов (типов Expression'а) делать определенные действия.
Первый вариант — ничего не делать. То есть заставлять пользователей использовать switch/case. Это не такой и плохой вариант. Но здесь возникает такой нюанс: мы размазываем логику, отвечающую за конкретный тип. Говоря проще, полиморфизм и виртуальные вызовы (ака позднее связывание) дают возможность переложить определение типа на среду выполнения и убрать эти проверки из нашего кода. Нам достаточно иметь логику, которая создает экземпляр нужного типа, далее все будет сделано средой выполнения за нас.
Второй вариант. Очевидное решение — вынести логику в виртуальные методы. Переопределив виртуальный метод в каждом наследнике мы можем забыть о switch/case. Механизм полиморфных вызовов решит за нас. Здесь будет работать таблица методов, методы будут вызываться по смещению в ней. Но это тема на целую статью, так что не будем увлекаться. Кажется, что виртуальные методы решают нашу проблему. Но к сожалению, они создают другую. Для нашей задачи мы могли бы добавить метод GetDeriviative(). Но теперь сами классы выражений выглядят странно. Мы могли бы добавить таких методов на все случаи жизни, но они не вписываются под общую логику класса. Да и мы так и не предоставили возможность делать нечто подобное пользователям (адекватным путем, разумеется). Нам нужно дать пользователю определять логику для каждого конкретного типа, но сохранить полиморфизм (который доступен нам).
Одними лишь усилиями пользователя сделать это не удастся.
Вот тут и кроется настоящий визитор. В базовом типе иерархии (Expression в нашем случае) мы определим метод вида
В наследниках данный метод будет переопределен.
Сам ExpressionVisitor — базовый класс, содержащий по виртуальному методу с той же сигнатурой
на каждый тип иерархии. На примере класса ExpressionVisitor — VisitBinary(...), VisitMethodCall(...), VisitConstant(...), VisitParameter(...).
Данные методы вызываются в соответствующем классе нашей иерархии.
Т.е. метод Accept в классе BinaryExpression будет выглядеть следующим образом:
В итоге для того, чтобы определить новое поведение, пользователю необходимо лишь создать наследника класса ExpressionVisitor, в котором будут переопределены соответствующие методы для решения одной задачи. В нашем случае создается DerivativeExpressionVisitor.
Далее мы имеем некие объекты наследников Expression, но каких — неизвестно, но и не надо.
Мы вызываем виртуальный метод Accept с нужной нам реализацией ExpressionVisitor, т.е. с DerivativeExpressionVisitor. Благодаря динамической диспетчеризации вызовется переопределенная реализация Accept типа времени выполнения, скажем BinaryExpression. В теле этого метода мы прекрасно понимаем, что мы в BinaryExpression, но не знаем, какой именно наследник ExpressionVisitor к нам пришел. Но т.к. VisitBinary также виртуальный, нам не нужно знать. Опять же просто вызываем по ссылке на базовый класс, вызов динамически (во время выполнения) диспетчеризуется и вызывается переопределенная реализация VisitBinary типа времени выполнения. Вот вам и двойная диспетчеризация — пинг-понг в стиле «ты выполняй» — «нет, ты».
Что нам это дает. Фактически, это дает возможность «добавлять» виртуальные методы извне, не
изменяя класса. Звучит здорово, но имеет свои обратные стороны:
Но природа деревьев выражений допускает данные издержки из-за специфики работы с выражениями, ведь данного рода обходы — одна из основных их особенностей.
Здесь можно посмотреть все методы доступные для перегрузки.
Итак, посмотрим как в итоге это выглядит.
Ссылка на github.
Пожалуй, как в большинстве задач программирования, однозначного ответа дать нельзя. Все, как всегда, зависит от конкретной ситуации. Мне нравится обычный паттерн матчинг для моего примера, т.к. я его не развил до масштабов промышленной разработки. В случае, если бы данное выражение бесконтролируемо увеличивалось, стоило бы задуматься о визиторе. И даже наивный визитор имеет право на жизнь — ведь это неплохой способ раскидать большое количество кода по классам, если иерархия не предоставила поддержку со своей стороны. И даже тут бывают исключения.
Точно также и сама поддержка визитора со стороны иерархии — очень спорная вещь.
Но я надеюсь, что предоставленной здесь информации хватит, чтобы сделать правильный выбор.
Статья построена как обычно — начинается с концептуальных основ и определений и заканчивается примерами и способами использования. Оглавление ниже.
Основы деревьев выражений
Синтаксис деревьев выражений
Типы выражений
Паттерн Матчинг
Наивный визитор
Классический визитор
Ну и целью не является навязать определенное решение или сказать, что одно лучше другого. Выводы предлагаю делать самим с учетом всех нюансов в вашем случае. Я же выскажу свое мнение на своем примере.
Деревья Выражений
Основы
Для начала необходимо разобраться с деревьями выражений. Под ними понимают тип Expression или любой из его наследников (о них речь пойдет позже). При обычном раскладе выражение/алгоритмы представляются в виде выполняемого кода/инструкций, с которыми пользователь может не так и много чего делать (в основном выполнять). Тип Expression позволяет представить выражение/алгоритм (как правило лямбды, но не обязательно) как данные, организованные в виде древовидной структуры, к которой пользователь имеет доступ. Древовидный способ организации информации об алгоритме и название класса и дают нам «деревья выражений».
Для понятности разберем простой пример. Допустим, у нас есть лямбда
(х) => Console.WriteLine(х + 5)
Это можно представить в виде следующего дерева
Корень дерева — вершина "MethodCall", параметры метода — также выражения, следовательно может иметь сколько угодно потомков.
В нашем случае потомок один — вершина "ArithmeticOperation". В ней содержится информация о том, какая конкретно это операция и левый и правый операнды — также выражения. У такой вершины будет всегда 2 потомка.
Операнды представлены константой (Constant) и параметром (Parameter). У таких выражений нет потомков.
Это очень упрощенные примеры, но полностью отражающие суть.
Основная особенность деревьев выражений — это то, что их можно парсить и вычитывать всю необходимую информацию о том, что алгоритм должен делать. С какой-то точки зрения, это противоположность атрибутам. Атрибуты — средство декларативного описания поведения (очень условно, но конечная цель примерно такая). В то время как деревья выражений — использование функции/алгоритма для описания данных.
Используются они, например, в провайдерах entity framework. Применение очевидно — распарсить дерево выражений, понять, что там должно выполниться и составить по этому описанию SQL. Из менее известных примеров — библиотека для мокинга moq. Деревья выражений также нашли применение в DLR (dynamic language runtime). Разработчики компилятора используют их при обеспечении совместимости между динамической природой и dotnet, вместо генерации MSIL.
Также стоит упомянуть, что деревья выражений неизменяемы.
Синтаксис
Следующее, что стоит обговорить — синтаксис. Существуют 2 основных способа:
- Создание деревьев выражений через статические методы класса Expression
- Использование лямбда выражения, компилирующееся в Expression
Статические методы класса Expression
Создание деревьев выражений через статические методы класса Expression используется реже (в особенности с пользовательской точки зрения). Это громоздко, но довольно просто, в нашем
распоряжении множество базовых кирпичиков, из которых можно построить довольно сложные
вещи. Создание происходит через статические методы, т.к. конструкторы выражений имеют модификатор internal. И это не означает, что нужно расчехлять рефлексию.
В качестве примера привожу создание выражения с примера выше:
(х) => Console.WriteLine(х + 5)
ParameterExpression parameter = Expression.Parameter(typeof(double));
ConstantExpression constant = Expression.Constant(5d, typeof(double));
BinaryExpression add = Expression.Add(parameter, constant);
MethodInfo writeLine = typeof(Console).GetMethod(nameof(Console.WriteLine), new[] { typeof(double) });
MethodCallExpression methodCall = Expression.Call(null, writeLine, add);
Expression<Action<double>> expressionlambda = Expression.Lambda<Action<double>>(methodCall, parameter);
Action<double> delegateLambda = expressionlambda.Compile();
delegateLambda(123321);
Может, это и не очень удобный способ, зато он полностью отражает внутреннюю структуру деревьев выражений. Плюс данный способ дает больше возможностей и фич, которые можно использовать в деревьях выражений: начиная от циклов, условий, try-catch, goto, присваивания, заканчивая блоками fault, отладочной информацией для точек останова, dynamic и тд.
Ламбда выражения
Использование лямбд в качестве выражений — более частый способ. Работает очень просто — умный компилятор на этапе компиляции смотрит, в качестве чего используется лямбда. И компилирует ее либо в делегат, либо в выражение. На уже освоенном примере, выглядит следующим образом
Expression<Action<double>> write = х => Console.WriteLine(х + 5);Стоит уточнить такую вещь — выражение — это исчерпывающее описание. И его достаточно чтобы
получить результат. Деревья выражений типа LambdaExpression или его наследников могут быть
cконвертировано в выполняемый IL. Остальные типы нельзя напрямую cконвертировать в выполняемы код (но это и не имеет много смысла).
Кстати, если кому-то критична быстрая компиляция выражения, можно взглянуть на этот сторонний проект.
Обратное же в общем случае неверно. Делегат не может просто так взять и представится выражением (но это все равно возможно).
Не все лямбды могут быть cконвертированы в деревья выражений. К таковым относятся:
- Содержащие оператор присваивания
- Содерщащие dynamic
- Асинхронные
- C телом (фигурные скобки)
double variable;
dynamic dynamic;
Expression<Action> assignment = () => variable = 5; //Compiler error: An expression tree may not contain an assignment operator
Expression<Func<double>> dynamically = () => dynamic; //Compiler error: An expression tree may not contain a dynamic operation
Expression<Func<Task>> asynchon = async () => await Task.CompletedTask; //Compiler error: Async lambda cannot be converted to expresiion trees
Expression<Action> body = () => { }; //Compiler error: A lambda expression with a statement body cannot be converted to an expression tree
Типы выражений
Предлагаю бегло ознакомится с доступными типами, чтобы представлять, какие возможности мы имеем. Все они находятся в пространстве имен System.Linq.Expressions
Я предлагаю для начала ознакомится с несколькими действительно интересными и необычными возможностями. Более простые типы выражений я собрал в табличку с кратким описанием.
Dynamic
С помощью DynamicExpression есть возможность использовать dynamic и все его фишки в деревьях выражений. Там довольно запутанное API, над этим примером я сидел дольше, чем над всеми остальными вместе взятыми. Вся запутанность обеспечивается кучей разного рода флагов. И некоторые из них похожи на те, которые вы ищите, но не обязательно ими являются. А при работе с dynamic в деревьях выражений говорящую ошибку получить сложно. Пример:
var parameter1 = Expression.Parameter(typeof(object), "name1");
var parameter2 = Expression.Parameter(typeof(object), "name2");
var dynamicParam1 = CSharpArgumentInfo.Create(CSharpArgumentInfoFlags.None, null);
var dynamicParam2 = CSharpArgumentInfo.Create(CSharpArgumentInfoFlags.None, null);
CallSiteBinder csb = Microsoft.CSharp.RuntimeBinder.Binder.BinaryOperation(CSharpBinderFlags.None, ExpressionType.Add, typeof(Program), new[] { dynamicParam1, dynamicParam2 });
var dyno = Expression.Dynamic(csb, typeof(object), parameter1, parameter2);
Expression<Func<dynamic, dynamic, dynamic>> expr = Expression.Lambda<Func<dynamic, dynamic, dynamic>>(dyno, new[] { parameter1, parameter2 });
Func<dynamic, dynamic, dynamic> action = expr.Compile();
var res = action("1", "2");
Console.WriteLine(res); //12
res = action(1, 2);
Console.WriteLine(res); //3
Я явно указал, откуда берется Binder во избежание путаницы с биндером из System.Reflection. Из интересностей — мы можем делать ref и out параметры, именованные параметры, унарные операции да и в принципе все, что можно сделать через dynamic, однако это потребует определенной сноровки.
Блоки перехвата исключений
Второе, на что обращу внимание — try/catch/finally/fault функциональность, а точнее на то,
что у нас есть доступ к fault блоку. Он не доступен в C#, однако есть в MSIL.Это своеобразный
аналог finally, который выполнится в случае любого исключения. В примере ниже выбросится исключение, после чего будет выведено «Hi» и программа будет ждать ввода. Только после этого она упадет окончательно. Не рекомендую эту практику к использованию.
var throwSmth = Expression.Throw(Expression.Constant(new Exception(), typeof(Exception)));
var log = Expression.Call(null, typeof(Console).GetMethod(nameof(Console.WriteLine), new[] { typeof(string) }), Expression.Constant("Hi", typeof(string)));
var read = Expression.Call(null, typeof(Console).GetMethod(nameof(Console.ReadLine)));
var fault = Expression.TryFault(throwSmth, Expression.Block(new[] { log, read }));
Expression<Action> expr = Expression.Lambda<Action>(fault);
Action compiledExpression = expr.Compile();
compiledExpression();
Краткое описание доступных типов деревьев выражений
Также в этом пространстве имен есть
Таблица
| Тип | Краткое описание |
|---|---|
| Основные | |
| Expression | Абстрактный тип, являющийся базовым для остальных типов выражений. Также содержит полезную статические методы, через которые создаются необходимые типы выражений |
| Expression<TDelegate> | Представляет дерево выражений для лямбды |
| Простые действия | |
| BinaryExpression | Тип выражений для бинарных операторов (+, — и тд) |
| UnaryExpression | Унарные операторы(+, -), а также выражение throw |
| ConstantExpression | Константа — просто некий экземпляр |
| ParameterExpression | Задает параметр |
| MethodCallExpression | Представляет вызов метода, принимает MethodInfo |
| IndexExpression | Индексатор |
| BlockExpression | Блок, содержащий последовательность выражений. В нем может быть объявлена переменная |
| Управление потоком выполнения | |
| ConditionalExpression | Выражение условного оператора — if-else |
| LabelTarget | Лейбл для скачков goto |
| LabelExpression | Выражение лейбла, которое можно поместить в структуру дерева выражений для последующего скачка к нему. Создается при помощи LabelTarget. Если на него прыгнули, получит значение соответствующего GotoExpression, в противном случае — значение по умолчанию. Можно использовать с void, тогда присвоения не будет. |
| GotoExpression | Собственно безусловный переход. Может быть разных типов. (В т.ч. «break») |
| LoopExpression | Бесконечный цикл, выходится с помощью «break» |
| SwitchCase | Используется для представления элементов SwitchExpression |
| SwitchExpression | Собственно обычный switch/case |
| TryExpression | Тип выражения для представления try/catch/finally/fault блока |
| CatchBlock | Тип, не являющийся выражением, но содержащий их внутри |
| Инициализация | |
| ElementInit | Инициализатор одного элемента в IEnumerable. Используется в ListInitExpression |
| ListInitExpression | Вызов конструктора + инициализация коллекции элементами |
| DefaultExpression | Значение по умолчанию для типа или пустое выражение |
| NewArrayExpression | Инициализация нового массива + инициализация элементов |
| NewExpression | Вызов конструктора |
| Действия с полями/свойствами | |
| MemberAssignment | Присваивание полю или свойству объекта |
| MemberBinding | Предоставляет базовый класс, из которого наследуются классы, представляющие биндинги, которые используются для инициализации членов вновь созданного объекта |
| MemberExpression | Доступ к полю/свойству |
| MemberInitExpression | Вызов конструктора и инициализация полей созданного обьекта |
| MemberListBinding | Инициализация свойства/поля типа коллекции |
| MemberMemberBinding | Инициализация поля/свойства обьекта, который сам является полем/свойством |
| Прочее | |
| LambdaExpression | Лямбда |
| InvocationExpression | Применяет делегатное или лямбда-выражение к списку выражений аргументов |
| DebugInfoExpression | Задает или очищает точку останова для отладочной информации. Это позволяет отладчику выделять правильный исходный код при отладке |
| SymbolDocumentInfo | Хранит информацию об символах отладки для исходного файла, в частности имя файла и уникальный идентификатор языка. |
| DynamicExpression | Представляет динамическую операцию (разобрано выше) |
| RuntimeVariablesExpression | Выражение представляющее права чтения/записи для переменных времени выполнения |
| TypeBinaryExpression | Проверяет, является ли объект таким типом (is) |
Также в этом пространстве имен есть
- ExpressionVisitor — дает визитора для деревьев выражений. Рассмотрим позже.
- DynamicExpressionVisitor — сделан с учетом работы с DynamicExpression (метод VisitDynamic)
Данных сведений достаточно, чтобы приступить к сравнению методов работы с деревьями выражений. Я решил разобрать это все на примере нахождения производной. Все возможные варианты я не предусматривал — лишь базовые. Но если кто-то зачем-то решил доработать и использовать — буду рад, если поделитесь улучшениями через реквест в мой репозиторий.
Сопоставление с образцом (pattern matching)
Итак, задача состоит в том, чтобы сделать тулу-считалку производных. Можно прикинуть следующее: есть пару правил нахождения производной для разных типов операции — умножение, деление и тд. В зависимости от операции необходимо выбрать определенную формулу. В такой банальной формулировке задача идеально ложиться на switch/case. А в последней версии языка нам представили switch/case 2.0 или сопоставление с образцом (pattern matching).
Здесь сложно что-то обсуждать. На хабре такое количесво кода выглядит громоздко и плохо читается, поэтому предлагаю смотреть на github. На примере производной вышло так:
Пример
public class PatterntMatchingDerivative
{
private readonly MethodInfo _pow = typeof(Math).GetMethod(nameof(Math.Pow));
private readonly MethodInfo _log = typeof(Math).GetMethod(nameof(Math.Log), new[] { typeof(double) });
private readonly ConstantExpression _zero = Expression.Constant(0d, typeof(double));
private readonly ConstantExpression _one = Expression.Constant(1d, typeof(double));
public Expression<Func<double, double>> ParseDerivative(Expression<Func<double, double>> function)
{
return Expression.Lambda<Func<double, double>>(ParseDerivative(function.Body), function.Parameters);
}
private Expression ParseDerivative(Expression function) => function switch
{
BinaryExpression binaryExpr => function.NodeType switch
{
ExpressionType.Add => Expression.Add(ParseDerivative(binaryExpr.Left), ParseDerivative(binaryExpr.Right)),
ExpressionType.Subtract => Expression.Subtract(ParseDerivative(binaryExpr.Left), ParseDerivative(binaryExpr.Right)),
ExpressionType.Multiply => (binaryExpr.Left, binaryExpr.Right) switch
{
(ConstantExpression _, ConstantExpression _) => _zero,
(ConstantExpression constant, ParameterExpression _) => constant,
(ParameterExpression _, ConstantExpression constant) => constant,
_ => Expression.Add(Expression.Multiply(ParseDerivative(binaryExpr.Left), binaryExpr.Right), Expression.Multiply(binaryExpr.Left, ParseDerivative(binaryExpr.Right)))
},
ExpressionType.Divide => (binaryExpr.Left, binaryExpr.Right) switch
{
(ConstantExpression _, ConstantExpression _) => _zero,
(ConstantExpression constant, ParameterExpression parameter) => Expression.Divide(constant, Expression.Multiply(parameter, parameter)),
(ParameterExpression _, ConstantExpression constant) => Expression.Divide(_one, constant),
_ => Expression.Divide(Expression.Subtract(Expression.Multiply(ParseDerivative(binaryExpr.Left), binaryExpr.Right), Expression.Multiply(binaryExpr.Left, ParseDerivative(binaryExpr.Right))), Expression.Multiply(binaryExpr.Right, binaryExpr.Right))
},
},
MethodCallExpression methodCall when methodCall.Method == _pow => (methodCall.Arguments[0], methodCall.Arguments[1]) switch
{
(ConstantExpression constant, ParameterExpression _) => Expression.Multiply(methodCall, Expression.Call(null, _log, constant)),
(ParameterExpression param, ConstantExpression constant) => Expression.Multiply(constant, Expression.Call(null, _pow, param, Expression.Constant((double)constant.Value - 1, typeof(double)))),
(ConstantExpression constant, Expression expression) => Expression.Multiply(Expression.Multiply(ParseDerivative(expression), methodCall), Expression.Call(null, _log, constant)),
},
_ => function.NodeType switch
{
ExpressionType.Constant => _zero,
ExpressionType.Parameter => _one,
_ => throw new OutOfMemoryException("Bitmap best practice")
}
};
}
Выглядит немного непривычно, но интересно. Писать такое было приятно — все условия органично ложатся в одну строку.
Пример говорит сам за себя, словами лучше и не опишешь.
Наивный visitor
В такой задаче тут же на ум приходит про expression tree visitor, который наводит много шума
и чуть-чуть паники среди любителей обсудить аджайл на кухне. «Бойся ни незнания, а ложного знания. Лучше ничего не знать, чем считать правдой то, что неправда». Вспомнив сие чудную фразу Толстого, признав незнание и заручившись поддержкой гугла можно найти следующее руководство.
У меня данная ссылка является первой (после Сибири в 1949) по запросу «Expression tree visitor».
На первый взгляд это именно то, что надо. Название статьи подходит к тому, что мы хотим сделать, а классы в примерах называются с суффиксом Visitor.
Ознакомившись со статьей и сделав по аналогии для нашего примера с производными получим:
Ссылка на github.
Пример
public class CustomDerivativeExpressionTreeVisitor
{
public Expression<Func<double, double>> Visit(Expression<Func<double, double>> function)
{
return Expression.Lambda<Func<double, double>>(Visitor.CreateFromExpression(function.Body).Visit(), function.Parameters);
}
}
public abstract class Visitor
{
protected static readonly MethodInfo Pow = typeof(Math).GetMethod(nameof(Math.Pow));
protected static readonly MethodInfo Log = typeof(Math).GetMethod(nameof(Math.Log), new[] { typeof(double) });
protected readonly ConstantExpression Zero = Expression.Constant(0d, typeof(double));
protected readonly ConstantExpression One = Expression.Constant(1d, typeof(double));
public abstract Expression Visit();
public static Visitor CreateFromExpression(Expression node)
=> node switch
{
BinaryExpression be => new BinaryVisitor(be),
MethodCallExpression mce when mce.Method == Pow => new PowMethodCallVisitor(mce),
_ => new SimpleVisitor(node),
};
}
public class BinaryVisitor : Visitor
{
private readonly BinaryExpression _node;
public BinaryVisitor(BinaryExpression node)
{
_node = node;
}
public override Expression Visit()
=> _node.NodeType switch
{
ExpressionType.Add => Expression.Add(ParseDerivative(binaryExpr.Left), ParseDerivative(binaryExpr.Right)),
ExpressionType.Subtract => Expression.Subtract(ParseDerivative(binaryExpr.Left), ParseDerivative(binaryExpr.Right)),
ExpressionType.Multiply => (binaryExpr.Left, binaryExpr.Right) switch
{
(ConstantExpression _, ConstantExpression _) => _zero,
(ConstantExpression constant, ParameterExpression _) => constant,
(ParameterExpression _, ConstantExpression constant) => constant,
_ => Expression.Add(Expression.Multiply(ParseDerivative(binaryExpr.Left), binaryExpr.Right), Expression.Multiply(binaryExpr.Left, ParseDerivative(binaryExpr.Right)))
},
ExpressionType.Divide => (binaryExpr.Left, binaryExpr.Right) switch
{
(ConstantExpression _, ConstantExpression _) => _zero,
(ConstantExpression constant, ParameterExpression parameter) => Expression.Divide(constant, Expression.Multiply(parameter, parameter)),
(ParameterExpression _, ConstantExpression constant) => Expression.Divide(_one, constant),
_ => Expression.Divide(Expression.Subtract(Expression.Multiply(ParseDerivative(binaryExpr.Left), binaryExpr.Right), Expression.Multiply(binaryExpr.Left, ParseDerivative(binaryExpr.Right))), Expression.Multiply(binaryExpr.Right, binaryExpr.Right))
},
};
}
public class PowMethodCallVisitor : Visitor
{
private readonly MethodCallExpression _node;
public PowMethodCallVisitor(MethodCallExpression node)
{
_node = node;
}
public override Expression Visit()
=> (_node.Arguments[0], _node.Arguments[1]) switch
{
(ConstantExpression constant, ParameterExpression _) => Expression.Multiply(_node, Expression.Call(null, Log, constant)),
(ParameterExpression param, ConstantExpression constant) => Expression.Multiply(constant, Expression.Call(null, Pow, param, Expression.Constant((double)constant.Value - 1, typeof(double)))),
(ConstantExpression constant, Expression expression) => Expression.Multiply(Expression.Multiply(CreateFromExpression(expression).Visit(), _node), Expression.Call(null, Log, constant)),
};
}
public class SimpleVisitor : Visitor
{
private readonly Expression _node;
public SimpleVisitor(Expression node)
{
_node = node;
}
public override Expression Visit()
=> _node.NodeType switch
{
ExpressionType.Constant => Zero,
ExpressionType.Parameter => One,
};
}
По сути — мы размазали свитч кейсы по разным классам. Меньше их не стало, магии не появилось. Все те же кейсы, гораздо больше строк. А где же обещанная двойная double dispatch диспетчеризация?
Классический visitor и двойная диспетчеризация
Здесь уже стоит рассказать про сам шаблон "Посетитель", он же Visitor, который и положен в основу Expression tree visitor'а. Разберем его как раз на примере деревьев выражений.
На секунду предположим, что мы разрабатываем деревья выражений. Мы хотим дать пользователям возможность итерироваться по дереву выражений и в зависимости от типов узлов (типов Expression'а) делать определенные действия.
Первый вариант — ничего не делать. То есть заставлять пользователей использовать switch/case. Это не такой и плохой вариант. Но здесь возникает такой нюанс: мы размазываем логику, отвечающую за конкретный тип. Говоря проще, полиморфизм и виртуальные вызовы (ака позднее связывание) дают возможность переложить определение типа на среду выполнения и убрать эти проверки из нашего кода. Нам достаточно иметь логику, которая создает экземпляр нужного типа, далее все будет сделано средой выполнения за нас.
Второй вариант. Очевидное решение — вынести логику в виртуальные методы. Переопределив виртуальный метод в каждом наследнике мы можем забыть о switch/case. Механизм полиморфных вызовов решит за нас. Здесь будет работать таблица методов, методы будут вызываться по смещению в ней. Но это тема на целую статью, так что не будем увлекаться. Кажется, что виртуальные методы решают нашу проблему. Но к сожалению, они создают другую. Для нашей задачи мы могли бы добавить метод GetDeriviative(). Но теперь сами классы выражений выглядят странно. Мы могли бы добавить таких методов на все случаи жизни, но они не вписываются под общую логику класса. Да и мы так и не предоставили возможность делать нечто подобное пользователям (адекватным путем, разумеется). Нам нужно дать пользователю определять логику для каждого конкретного типа, но сохранить полиморфизм (который доступен нам).
Одними лишь усилиями пользователя сделать это не удастся.
Вот тут и кроется настоящий визитор. В базовом типе иерархии (Expression в нашем случае) мы определим метод вида
virtual Expression Accept(ExpressionVisitor visitor);В наследниках данный метод будет переопределен.
Сам ExpressionVisitor — базовый класс, содержащий по виртуальному методу с той же сигнатурой
на каждый тип иерархии. На примере класса ExpressionVisitor — VisitBinary(...), VisitMethodCall(...), VisitConstant(...), VisitParameter(...).
Данные методы вызываются в соответствующем классе нашей иерархии.
Т.е. метод Accept в классе BinaryExpression будет выглядеть следующим образом:
protected internal override Expression Accept(ExpressionVisitor visitor)
{
return visitor.VisitBinary(this);
}
В итоге для того, чтобы определить новое поведение, пользователю необходимо лишь создать наследника класса ExpressionVisitor, в котором будут переопределены соответствующие методы для решения одной задачи. В нашем случае создается DerivativeExpressionVisitor.
Далее мы имеем некие объекты наследников Expression, но каких — неизвестно, но и не надо.
Мы вызываем виртуальный метод Accept с нужной нам реализацией ExpressionVisitor, т.е. с DerivativeExpressionVisitor. Благодаря динамической диспетчеризации вызовется переопределенная реализация Accept типа времени выполнения, скажем BinaryExpression. В теле этого метода мы прекрасно понимаем, что мы в BinaryExpression, но не знаем, какой именно наследник ExpressionVisitor к нам пришел. Но т.к. VisitBinary также виртуальный, нам не нужно знать. Опять же просто вызываем по ссылке на базовый класс, вызов динамически (во время выполнения) диспетчеризуется и вызывается переопределенная реализация VisitBinary типа времени выполнения. Вот вам и двойная диспетчеризация — пинг-понг в стиле «ты выполняй» — «нет, ты».
Что нам это дает. Фактически, это дает возможность «добавлять» виртуальные методы извне, не
изменяя класса. Звучит здорово, но имеет свои обратные стороны:
- Какой-то левак в виде метода Accept, который отвечает за все и ни за что одновременно
- Волновой эффект хорошей хэш-функции — при добавлении всего одного наследника в иерархию в худшем случае всем придется доделывать свои визиторы
Но природа деревьев выражений допускает данные издержки из-за специфики работы с выражениями, ведь данного рода обходы — одна из основных их особенностей.
Здесь можно посмотреть все методы доступные для перегрузки.
Итак, посмотрим как в итоге это выглядит.
Ссылка на github.
Пример
public class BuildinExpressionTreeVisitor : ExpressionVisitor
{
private readonly MethodInfo _pow = typeof(Math).GetMethod(nameof(Math.Pow));
private readonly MethodInfo _log = typeof(Math).GetMethod(nameof(Math.Log), new[] { typeof(double) });
private readonly ConstantExpression _zero = Expression.Constant(0d, typeof(double));
private readonly ConstantExpression _one = Expression.Constant(1d, typeof(double));
public Expression<Func<double, double>> GetDerivative(Expression<Func<double, double>> function)
{
return Expression.Lambda<Func<double, double>>(Visit(function.Body), function.Parameters);
}
protected override Expression VisitBinary(BinaryExpression binaryExpr)
=> binaryExpr.NodeType switch
{
ExpressionType.Add => Expression.Add(Visit(binaryExpr.Left), Visit(binaryExpr.Right)),
ExpressionType.Subtract => Expression.Subtract(Visit(binaryExpr.Left), Visit(binaryExpr.Right)),
ExpressionType.Multiply when binaryExpr.Left is ConstantExpression && binaryExpr.Right is ConstantExpression => _zero,
ExpressionType.Multiply when binaryExpr.Left is ConstantExpression && binaryExpr.Right is ParameterExpression => binaryExpr.Left,
ExpressionType.Multiply when binaryExpr.Left is ParameterExpression && binaryExpr.Right is ConstantExpression => binaryExpr.Right,
ExpressionType.Multiply => Expression.Add(Expression.Multiply(Visit(binaryExpr.Left), binaryExpr.Right), Expression.Multiply(binaryExpr.Left, Visit(binaryExpr.Right))),
ExpressionType.Divide when binaryExpr.Left is ConstantExpression && binaryExpr.Right is ConstantExpression => _zero,
ExpressionType.Divide when binaryExpr.Left is ConstantExpression && binaryExpr.Right is ParameterExpression => Expression.Divide(binaryExpr.Left, Expression.Multiply(binaryExpr.Right, binaryExpr.Right)),
ExpressionType.Divide when binaryExpr.Left is ParameterExpression && binaryExpr.Right is ConstantExpression => Expression.Divide(_one, binaryExpr.Right),
ExpressionType.Divide => Expression.Divide(Expression.Subtract(Expression.Multiply(Visit(binaryExpr.Left), binaryExpr.Right), Expression.Multiply(binaryExpr.Left, Visit(binaryExpr.Right))), Expression.Multiply(binaryExpr.Right, binaryExpr.Right)),
};
protected override Expression VisitMethodCall(MethodCallExpression methodCall)
=> (methodCall.Arguments[0], methodCall.Arguments[1]) switch
{
(ConstantExpression constant, ParameterExpression _) => Expression.Multiply(methodCall, Expression.Call(null, _log, constant)),
(ParameterExpression param, ConstantExpression constant) => Expression.Multiply(constant, Expression.Call(null, _pow, param, Expression.Constant((double)constant.Value - 1, typeof(double)))),
(ConstantExpression constant, Expression expression) => Expression.Multiply(Expression.Multiply(Visit(expression), methodCall), Expression.Call(null, _log, constant)),
};
protected override Expression VisitConstant(ConstantExpression _) => _zero;
protected override Expression VisitParameter(ParameterExpression b) => _one;
}
Выводы
Пожалуй, как в большинстве задач программирования, однозначного ответа дать нельзя. Все, как всегда, зависит от конкретной ситуации. Мне нравится обычный паттерн матчинг для моего примера, т.к. я его не развил до масштабов промышленной разработки. В случае, если бы данное выражение бесконтролируемо увеличивалось, стоило бы задуматься о визиторе. И даже наивный визитор имеет право на жизнь — ведь это неплохой способ раскидать большое количество кода по классам, если иерархия не предоставила поддержку со своей стороны. И даже тут бывают исключения.
Точно также и сама поддержка визитора со стороны иерархии — очень спорная вещь.
Но я надеюсь, что предоставленной здесь информации хватит, чтобы сделать правильный выбор.
