Визуализация деревьев выражений с помощью TeX

Для затравки. Хотите узнать, как из вот такого выражения на языке C#:

Expression<Func<double>> bondPriceValueExpression = 
    () => C * ((1 - Math.Pow(1 + i, -n)) / i) + M / Math.Pow(1 + i, n);

Получить вот такую картинку:

Если это так, то милости прошу под кат.

Любознательный читатель (каких, как известно, великое множество) может удивиться сочетанию столь отдаленных друг от друга понятий, как деревья выражений в .Net и старого, как мир, языка разметки TeX. Однако если немного подумать, то найти точку соприкосновения этих технологий не так и сложно. Одной из задач детища Дональда Кнута (это я про TeX) является визуализация математических формул, а эти самые формулы могут выражаться и на некотором языке программирования, таком как C#, для выполнения определенных действий. Мы привыкли, что эти формулы выражаются в виде некоторых функций, которые содержат всю необходимую логику, однако для этого прекрасно подойдут как анонимные функции, так и деревья выражений.

Постановка задачи

Давайте предположим, что мы занимаемся приложением, которое выполняет некоторые финансовые расчеты. Но поскольку бизнесс-пользователи этого приложения, хотя и доверяют практически безгранично его разработчикам, все же предпочитают проверять самостоятельно определенные моменты и видеть не только результаты вычислений, но и, так сказать, сам процесс, в виде «сырых» формул, а также формул с подставленными актуальными значениями. Давайте сделаем предположение (последнее, честное слово), что в этом приложении есть некоторая форма (не важно, веб-форма или окно десктопного приложения), в которой вычисляется текущая стоимость облигации (Bond Price), основная часть которой является вычисление текущей стоимости периодических платежей (Present Value of an Ordinary Annuity) по этой облигации.

На самом деле, ничего особенно хитрого в этом конкретном случае нет, и все вычисления сводятся к тому, что деньги, на самом деле, имеют разную ценность, в зависимости от того, когда они попадут к нам в руки. Так, 1000$ сегодня – это не то же самое, что 1000$ через год, поскольку сегодня вы, как минимум, можете положить эти деньги в банк под 10% и получить дополнительные 100$ через год. Таким образом, любой денежный поток, который вы получаете, не важно, по облигациям, по депозиту в вашем любимом банке или на работе, можно привести к некоторому периоду времени, например, к сегодняшнему дню с помощью весьма нехитрых вычислений. Именно этот процесс показан на рисунке 1, когда одна и та же сумма денег, получаемая с течением времени «дешевеет» по отношению к сегодняшнему дню. Эта же идея лежит в основе определения текущей стоимости облигации, по которой инвестор сможет судить о выгодности одной облигации по сравнению с другой. (Вычисления стоимости облигация показаны в формуле на рисунке 2

Рисунок 1 – Определение текущей стоимости периодических платежей

Рисунок 2 – Определение текущей стоимости облигации

На этом экономическая составляющая заканчивается, а все будущие инвесторы или просто интересующиеся этой темой читатели, могут почерпнуть дополнительную информацию в статье “Advanced Bond Concepts: Bond Pricing”, откуда эти картинки и были взяты или воспользоваться вселенским разумом в виде гугла.

Теперь мы точно знаем, что нам нужно рассчитать и у нас осталось всего два вопроса: каким образом прикрутить TeX к .Net-у и как преобразовать наш код в формат, понятный парсеру TeX-а. С первым вопросом поможет справиться бесплатная утилита, Wpf-Math, которая по сути, является портом Java утилиты под названием JMathTeX. Ну, а со вторым вопросом вполне по силам справиться деревьям выражений в .Net.

Деревья выражений

Давайте начнем с выражения наших формул в языке C# с помощью деревьев выражений.

Как большинство читателей наверняка знает, в C# 3.0 появилась такая замечательная вещь, как лямбда-выражения. Однако менее известным фактом является то, что лямбда-выражения представляют собой не только более короткую форму записи анонимных функций (anonymous functions) (*), но еще и может представлять код в виде данных. По сути, это еще одна форма анонимных функций (anonymous functions) (*), однако лямбда-выражения могут представлять собой не только «указатель» на функцию, сгенерированную за нас компилятором, но и представлять код в виде данных.

Func<int, int> func = x => (x + 1) * 2; //1
Expression<Func<int, int>> expression = x => (x + 1) * 2; //2
 
Console.WriteLine(func(2)); //6
 
Func<int, int> compiledExpression = expression.Compile();
Console.WriteLine(compiledExpression(2)); //6

В первом случае мы получаем простую функцию, принимающую аргумент типа double и возвращающую удвоенное произведение своего аргумента. Единственное отличие от нормальной функции заключается в том, что реальная функция будет создана за нас компилятором и не будет видна разработчику напрямую. Второй пример несколько сложнее, поскольку в этом случае мы создаем дерево выражений (expression tree), которое содержит этот же код в виде данных:

ParameterExpression x = Expression.Parameter(typeof(int), "x");
Expression<Func<int, int>> expression = Expression.Lambda<Func<int, int>>(
    // Основное выражение вида: (x + 1)*2
    Expression.Multiply(
    // Вложенное выражение вида: x + 1
        Expression.Add(
            x,
            Expression.Constant(1)
        ),
        Expression.Constant(2)
    ),
    x // Параметр лямбда-выражения
);
Console.WriteLine(expression); // x => ((x + 1)*2)

Код может выглядеть несколько пугающим с первого взгляда, но нам достаточно понимать, что выражение представляется собой некоторую иерархическую структуру данных, каждый узел которой является другим выражением. При этом разные типы выражений представляют разные операции, выполняемые кодом: это могут быть операции с двумя операндами (binary operations), такие как сложение или умножение; обращения к свойствам, вызовы методов или конструкторов, а начиная с C# 4.0 выражения могут содержать также локальные переменные, условные операторы, блоки try/catch и многое другое (правда предназначено это для Dynamic Language Runtime, DLR, а не для лямбда-выражений, так что создавать такие выражения придется вручную De Smet [2009], Albahari [2010]).

Основная особенность деревьев выражений заключается в том, что мы их можем проанализировать, изменить одно выражение на другое или сгенерировать по этому выражению код для выполнения на другой платформе. Именно эта идея лежит в основе таких инструментов как LINQ 2 SQL или Entity Framework и именно ею мы можем воспользоваться для преобразования из языка, понятного компилятору C#, в язык, понятный компилятору TeX.

Навигация по дереву выражений

Начиная с версии 4.0 в составе .Net Framework появился класс ExpressionVisitor, который как раз и предназначен для навигации и изменения (в случае необходимости) деревьев выражений. Для навигации по дереву выражения достаточно отнаследоваться от указанного выше класса и переопределить методы типа VisitBinary, VisitUnary, VisityMethodCall и т.п.

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

public class TeXExpressionVisitor : ExpressionVisitor
{
    // Сюда мы будет сохранять "пройденные" части выражения
    private readonly StringBuilder _sb = new StringBuilder();
 
    // Конструктор принимает выражение, которое будет преобразовано в формат TeX-а
    public TeXExpressionVisitor(Expression expression)
    {
        Visit(expression);
    }
 
    // Лямбда-выражение анализируется несколько по-иному, поскольку нам нужно только тело
    // выражения, без первого параметра
    public TeXExpressionVisitor(LambdaExpression expression)
    {
        Visit(expression.Body);
    }
 
    // Остальные методы
}

Теперь нам осталось добавить пару вспомогательных методов, почитать о формате формул в TeX-е и реализовать соответствующие виртуальные функции, которые будут вызываться при встрече с соответствующими типами выражения.

ПРИМЕЧАНИЕ
Полный исходный код примеров, вместе с тестовым проектом, а также с немного исправленной версией библиотеки Wpf-Math и тестовым приложением для парсинга языка TeX с последующим отображением формул можно найти здесь.

Так, например, формат отображения дроби в формате TeX выглядит следующим образом: \frac{x+1}{y+3}, что требует соответствующей реализации метода VisitDivideExpression, который будет вызываться из метода VisitBinaryExpression:

// Оператор деления \fract требует иного порядка аргументов:
// \frac{arg1}{arg2}
private Expression VisitDivideExpression(BinaryExpression node)
{
    // Для деления (x + 2) на 3, мы должны получить следующее выражение
    // \frac{x + 2}{3}
    switch (node.NodeType)
    {
        case ExpressionType.Divide:
            _sb.Append(@"\frac");
            break;
        default:
            throw new InvalidOperationException("Unknown prefix BinaryExpression " + node.Type);
    }
 
    _sb.Append("{");
    Visit(node.Left);
    _sb.Append("}");
 
    _sb.Append("{");
    Visit(node.Right);
    _sb.Append("}");
    return node;
}

Нечто подобное требуется также для операторов сложения, вычитания и деления, однако в отличие от деления у этих операторов более привычный формат: {lhs} operator {rhs}, где lhs – это левый операнд, а rhs – правый. Возведение в степень (которое в языке C# выглядит в виде вызова метода Math.Pow), записывается как {lhs}^{rhs}, что требует переопределения виртуального метода VIsitMethodCall. Я не хочу утомлять вас кодом, как я уже упоминал, можно просто загрузить весь солюшен и покопаться в нем; но идея, я думаю, понятна.

Теперь, обладая таким замечательным классом, как TeXExpressionVisualizer, мы можем преобразовать выражение расчета текущей стоимости облигации в формат TeX-а следующим образом:

Expression<Func<double, int, int, double, double>> bondPrice =
        (double C, int i, int n, double M) 
            => C * ((1 - Math.Pow(1 + i, -n)) / i) + M/Math.Pow(1 + i, n);
var visitor = new TeXExpressionVisitor(bondPrice);
string texExpression = visitor.GenerateTeXExpression("BondPrice");

В результате переменная texExpression будет содержать следующее значение: {BondPrice}{=}C*\frac{(1-(1+i)^{-n})}{i}+\frac{M}{(1+i)^{n}}

Теперь, эту строку достаточно передать парсеру TeX, в нашем случае – классу TexFormulaParser из библиотеки Wpf-Math, в результате чего мы получим следующую картинку:

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

Подстановка актуальных значений

Теперь нам нужно решить вторую часть задачи, которая заключается в следующем: для простого выражения, например, x + y, получить выражение вида 2 + 3, где 2 и 3 – это соответственно, значения переменных x и y. Для этого нам понадобится еще один класс «посетителя», основной задачей которого будет замена в выражении всех свойств некоторого объекта на их актуальные значения.

Здесь все значительно проще, поскольку нам достаточно переопределить всего один метод VisitMember, найти член с заданным именем в некотором объекте и заменить выражение доступа к этому члену на ConstantExpression:

/// <summary>
/// Класс "посетителя" для "подстановки" актуальных значний в дерево выражения
/// </summary>
public class TeXEvaluationExpressionVisitor : ExpressionVisitor
{
    // Вспомогательный класс для хранения значения и типа свойств
    private class TypeValuePair
    {
        public object Value { get; set; }
        public Type Type { get; set; }
    }
        
    // Мапа для хранения значения и типа свойств по имени свойства
    private readonly Dictionary<string, TypeValuePair> _memberProperties;
 
    // Конструктор принимает выражение и объект, значения свойств которого будут подставлены
    // в заданное выражение
    public TeXEvaluationExpressionVisitor(Expression expression, object memberObject)
    {
        // Получаю все свойства переданного объекта
        System.Reflection.PropertyInfo[] memberProps = memberObject.GetType().GetProperties();
            
        // И получаю ассоциативный массив типа свойства и значения по имени свойства
        _memberProperties = memberProps.ToDictionary(pi => pi.Name,
                                    pi => new TypeValuePair
                                            {
                                                Value = pi.GetValue(memberObject, null),
                                                Type = pi.PropertyType
                                            });
            
        ConvertedExpression = Visit(expression);
    }
 
    // "Обновленное" выражение с "подставленными" значениями свойств
    public Expression ConvertedExpression { get; private set; }
 
    // Заменяем обращение к члену на соответствующее значение
    protected override Expression VisitMember(MemberExpression memberExpression)
    {
        // Пробуем найти значение члена с указанным именем
        TypeValuePair typeValuePair;
        if (_memberProperties.TryGetValue(memberExpression.Member.Name, out typeValuePair))
        {
            // И заменяем его на соответствующее константное выражение
            return Expression.Constant(value: typeValuePair.Value, 
                                        type: typeValuePair.Type);
        }
        return memberExpression;
    }
}

Теперь нам достаточно «скормить» наше исходное выражение этому визитору, получить сконвертированное выражение и передать его предыдущему визитору. Вот это один из тех случаев, когда это проще показать в коде, нежели описать словами:

/// <summary>
/// Класс для расчета стоимости облигации (BondPrice)
/// </summary>
public class BondPriceEvaluator
{
    // Данные, необходимые для расчета стоимости облигации
    private object _bondEvaluationData;
    // Выражение для расчета стоимости облигации
    private readonly Expression<Func<double>> _bondPriceValueExpression;
    // Функция расчета стоимости облигации
    private readonly Func<double> _bondPriceValueFunction;
    // C - платеж по облигации (Coupon Payment)
    // M - Номинальная стоимость (Par Value)
    // i - Полугодовая процентная ставка (Semi-annual yield)
    // n - Количество выплат
 
    public BondPriceEvaluator(double C, double i, int n, double M)
    {
        // Создаем объект анонимного типа с соответствующим набором свойств
        _bondEvaluationData = new { C, i, n, M };
 
        // Создаем выражение расчета стоимости облигации
        // C * (1 - (1 + i) ^ (-n)) + M/((1 + i)^n)
        _bondPriceValueExpression =
            () => C * ((1 - Math.Pow(1 + i, -n)) / i) + M / Math.Pow(1 + i, n);
 
        // Функция расчета - это "откомпилированное" выражение
        _bondPriceValueFunction = _bondPriceValueExpression.Compile();
    }
 
    // Получение исходного выражения в формате TeX
    public string GetTeXExpression()
    {
        var visitor = new TeXExpressionVisitor(_bondPriceValueExpression);
        return visitor.GenerateTeXExpression("BondPrice");
    }
 
    // Получение выражения с "подставленными" актуальными значениями
    public string GetTeXEvaluatedExpression()
    {
        // С помощью класса TeXEvaluationExpressionVisitor "подставляем" значения
        // в выражение расчета стоимости облигации
        var evaluationVisitor = new TeXEvaluationExpressionVisitor(_bondPriceValueExpression, _bondEvaluationData);
 
        // Теперь получаем строкове представление этого выражения в формате TeX
        var texVisitor = new TeXExpressionVisitor(evaluationVisitor.ConvertedExpression);
        string evaluatedExpression = texVisitor.GenerateTeXExpression("BondPrice");
 
        // Вычисляем значение стоимости облигации
        double bondPrice = _bondPriceValueFunction();
 
        // И добавляем это значение в окончательную формулу в формате TeX
        return evaluatedExpression + "{=}{" + bondPrice.ToString(".##") + "}";
    }
}

Теперь нам достаточно создать экземпляр этого класса, передав нужные значения параметров и вызывать методы GetTeXExpression или GetTeXEvaluationExpression, чтобы получить выражения расчета стоимости облигации в формате TeX; при этом в первом случае мы получим простое выражение (которое мы уже видели), а во втором случае – выражение с подставленными значениями и вычисленным результатом:

Заключение

Итак, что же мы получили в результате? В данном примере мы взяли формулу расчета текущей стоимости облигации, записали ее в виде выражения на языке C#, а затем получили «визуальное» представления этих вычислений в виде изображения в двух представлениях: в виде исходного выражения, а также в виде выражения с подставленными значениями и вычисленным результатом:

Выражение на языке C#:

() => C * ((1 - Math.Pow(1 + i, -n)) / i) + M / Math.Pow(1 + i, n);

Визуальное представление исходного выражения:

Визуальное представление выражения с подставленными значениями:

Конечно, приведенный подход нельзя назвать универсальным, и он обладает несколькими ограничениями. Во-первых, далеко не любое вычисление можно представить в виде одного выражения на языке C# и в таком случае, вам придется либо отказаться от этого подхода, либо разбить все вычисление на несколько выражений и визуализировать каждое из них по отдельности. Во-вторых, текущее решение «из коробки» может не содержать необходимого функционала для преобразования некоторых функций в соответствующие команды TeX-а, однако при помощи справочника “TeX Reference Card” (или чего-то подобного) и минимального желания, решить эту проблему довольно просто.

Ссылки

1. [Skeet2010] Jon Skeet “C# in Depth”
2. [Albahari2010] Joseph Albahari, Ben Albahari “C# 4.0 in a Nutshell”
3. [De Smet2009] Bart De Smet “Expression Trees, Take Two - Introducing System.Linq.Expressions v4.0”
4. С.М. Львовский. Набор и верстка в системе LaTeX. 2003
5. Noldorin “Rendering TeX Math in WPF”

------------------------------------------

(*) Здесь может возникнуть некоторая терминологическая путаница. В языке C# термин анонимные функции (anonymous functions) – является более общим термином, который покрывает и анонимные методы (anonymous methods) и лямбда-выражения, при этом анонимными методами называются методы, созданные с помощью синтаксиса анонимных делегатов в языке C# 2.