Компиляция математических выражений

Привет. В этом очерке расскажу, как я реализовывал компиляцию математических (численных и логических) выражений в делегат при помощи Linq Expression.

Навигация: Проблема · Правила компиляции · Компилятор · Дефолтные правила · Красивый API · Производительность · Примеры работы · Заключение · Ссылки

Что мы хотим?

Мы хотим скомпилировать выражение в функцию от произвольного числа аргументов произвольного типа, причем не только численного, но и булевого. Например,

var func = "x + sin(y) + 2ch(0)".Compile<Complex, double, Complex>("x", "y");
Console.WriteLine(func(new(3, 4), 1.2d));
>>> (5.932039085967226, 4)
  
var func = "x > 3 and (a implies b)".Compile<int, bool, bool, bool>("x", "a", "b");
Console.WriteLine(func(4, false, true));
>>> True

Что у нас есть?

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

У нас есть базовый класс Entity и дерево наследников.

Entity
|
+--Operators
  |
  +--Sumf
  |
  +--Minusf
  |
  ...
+--Trigonometry
  |
  +--Sinf
  |
  +--Cosf
  |
  ...
+--Discrete
  |
  +--Andf
  |
  +--Lessf
  |

Примерно так выглядит дерево типов. Дерево выражений - это просто граф, где дети ноды это операнды оператора/функции.

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

Например, так определен оператор суммы.

Протокол компиляции

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

Так он будет выглядеть:

public sealed record CompilationProtocol
{
	public Func<Entity, Expression> ConstantConverter { get; init; }

	public Func<Expression, Expression, Entity, Expression> BinaryNodeConverter { get; init; }

	public Func<Expression, Entity, Expression> UnaryNodeConverter { get; init; }

	public Func<IEnumerable<Expression>, Entity, Expression> AnyArgumentConverter { get; init; }
}

Важно: ConstantConverter, BinaryNodeConverter, и UnaryNodeConverter мы будем писать в конце статьи.

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

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

Компилятор

Прототип метода, который мы хотим написать, выглядит так:

internal static TDelegate Compile<TDelegate>(
            Entity expr, 
            Type? returnType,
            CompilationProtocol protocol,
            IEnumerable<(Type type, Variable variable)> typesAndNames
            ) where TDelegate : Delegate

1. Entity expr - это выражение с переменными, которое мы компилируем.

2. Type? returnType - это возвращаемый тип. Мы не можем "вытащить" его из типа делегата, поэтому приходится передавать его отдельно.

3. CompilationProtocol protocol - это тот самый протокол правил, по которым мы будем преобразовывать каждый узел выражения

4. IEnumerable<(Type type, Variable variable)> typesAndNames - это набор пар тип-переменная, которые пользователь хочет передать в свой делегат. Например, если вместо x мы хотим подставлять целочисленное, а вместо y передавать комплексное, мы напишем new[] { (typeof(int), "x"), (typeof(Complex), "y") }

А вот и имплементация метода:

internal static TDelegate Compile<TDelegate>(Entity expr, Type? returnType, CompilationProtocol protocol, IEnumerable<(Type type, Variable variable)> typesAndNames) where TDelegate : Delegate
{
  // для каждого поддерева есть локальная переменная, которую мы держим здесь
	var subexpressionsCache = typesAndNames.ToDictionary(c => (Entity)c.variable, c => Expression.Parameter(c.type));
  // это параметры функции: те переменные, которые будут передаваться в нее, а не создаваться локально
	var functionArguments = subexpressionsCache.Select(c => c.Value).ToArray(); // copying
  // а это локальные переменные, мы их сохраняем в этом списке
	var localVars = new List<ParameterExpression>();
  // это список инструкций-присваиваний (о нем позже)
	var variableAssignments = new List<Expression>();

  // по всем данным строим дерево
	var tree = BuildTree(expr, subexpressionsCache, variableAssignments, localVars, protocol);
  // построив, создаем блок, в котором объявляем локальные переменные, используемые в дереве
	var treeWithLocals = Expression.Block(localVars, variableAssignments.Append(tree));
  // если пользователь передал returnType, то попытаемся явно скастить в него
	Expression entireExpresion = returnType is not null ? Expression.Convert(treeWithLocals, returnType) : treeWithLocals;
  // создаем лямбду с аргументами функции
	var finalLambda = Expression.Lambda<TDelegate>(entireExpresion, functionArguments);

  // компилируем
	return finalLambda.Compile();
}

Главная его задача - создать необходимые контейнеры для кеша поддеревьев, локальных переменных, и некоторых других вещей. Самая интересная тут функция это BuildTree. Она будет строить дерево linq-выражения по Entity. Вот так выглядит ее прототип:

internal static Expression BuildTree(
	Entity expr, 
	Dictionary<Entity, ParameterExpression> cachedSubexpressions, 
	List<Expression> variableAssignments, 
	List<ParameterExpression> newLocalVars,
	CompilationProtocol protocol)

А вот и самая главная функция - BuildTree:

internal static Expression BuildTree(Entity expr, ...)
{
  // если поддерево встречалось, возвращаем переменную, в которую оно присвоено
	if (cachedSubexpressions.TryGetValue(expr, out var readyVar))
		return readyVar;

	Expression subTree = expr switch
	{
	  ...
		
    // если константа - прогоняем через ConstantConverter
		// нашего протокола
		Entity.Boolean or Number => protocol.ConstantConverter(expr),

    // аналогичная логика с унарной, бинарной, и n-арными нодами
		IUnaryNode oneArg
			=> protocol.UnaryNodeConverter(BuildTree(oneArg.NodeChild, ...), expr),

		IBinaryNode twoArg
			=> protocol.BinaryNodeConverter(
				BuildTree(twoArg.NodeFirstChild, ...), 
				BuildTree(twoArg.NodeSecondChild, ...), 
				expr),

		var other => protocol.AnyArgumentConverter(
				other.DirectChildren.Select(c => BuildTree(c, ...)), 
			expr)
	};

  // для этого поддерева создадим локальную переменную
	var newVar = Expression.Variable(subTree.Type);
	
	// добавим запись вида var5 = subTree
	variableAssignments.Add(Expression.Assign(newVar, subTree));
	
	// запомним, что для этого поддерева используется эта переменная
	cachedSubexpressions[expr] = newVar;
	
	// запомним, что мы вообще такую создали
	newLocalVars.Add(newVar);
	
	return newVar;
}

Я опустил большие куски для читаемости. Итак, в ней для каждого поддерева мы либо сразу возвращаем локальную переменную, отвечающую за это выражение, либо строим новое дерево Linq.Expression, запоминаем его в новую локальную переменную, и возвращаем ее.

Собственно, это все, компилятор готов. Но мы не реализовали ни одного правила преобразования наших выражений в Linq.Expression, потому что эти правила мы ждем от пользователя. Но почему бы не предоставить какую-то возможность по умолчанию для встроенных типов?

Остаток статьи будет о создании дефолтного протокола.

Предположения (assumptions)

Сам метод Compile<TDelegate>(Entity, Type?, CompilationProtocol, IEnumerable<(Type, Variable)>) будет предоставлен пользователю, но становится очевидно, что это очень длинная и неуклюжая конструкция, придется писать огромное количество логики, описывающее преобразование каждой ноды и константы, да и само объявление метода достаточно длинное и неочевидное.

Поэтому я предполагаю, что по умолчанию мы можем предложить протокол компиляции, который позволит работать с некоторыми встроенными примитивами (bool, int, long, float, double, Complex, BigInteger).

ConstantConverter:

Это правило преобразует константу из Entity в Linq.Constant и выглядит следующим образом:

public static Expression ConverterConstant(Entity e)
	=> e switch
	{
		Number n => Expression.Constant(DownCast(n)),
		Entity.Boolean b => Expression.Constant((bool)b),
		_ => throw new AngouriBugException("Undefined constant type")
	};

Число преобразуем в число в зависимости от его типа, булеву константу безусловно в примитивный bool.

private static object DownCast(Number num)
{
	if (num is Integer)
		return (long)num;
	if (num is Real)
		return (double)num;
	if (num is Number.Complex)
		return (System.Numerics.Complex)num;
	throw new InvalidProtocolProvided("Undefined type, provide valid compilation protocol");
}

UnaryNodeConverter:

Это поле протокола - делегат, преобразующий ноду с одним аргументом в Linq.Expression.

public static Expression OneArgumentEntity(Expression e, Entity typeHolder)
  => typeHolder switch
	{
		Sinf =>         Expression.Call(GetDef("Sin", 1, e.Type), e),
		...
		Cosecantf =>    Expression.Call(GetDef("Csc", 1, e.Type), e),

		Arcsinf =>      Expression.Call(GetDef("Asin", 1, e.Type), e),
		...
		Arccosecantf => Expression.Call(GetDef("Acsc", 1, e.Type), e),

		Absf =>         Expression.Call(GetDef("Abs", 1, e.Type), e),
		Signumf =>      Expression.Call(GetDef("Sgn", 1, e.Type), e),

		Notf =>         Expression.Not(e),

		_ => throw new AngouriBugException("A node seems to be not added")
	};

Я опустил некоторые большие блоки (весь код здесь). Итак, здесь мы рассматриваем возможные типы нашей ноды, и на каждую выбираем нужный оверлоад нужной функции. GetDef находит нужную функцию по имени.

BinaryNodeConverter:

Это правило преобразует ноду с двумя аргументами в Linq.Expression.

public static Expression TwoArgumentEntity(Expression left, Expression right, Entity typeHolder)
{
	var typeToCastTo = MaxType(left.Type, right.Type);
	if (left.Type != typeToCastTo)
		left = Expression.Convert(left, typeToCastTo);
	if (right.Type != typeToCastTo)
		right = Expression.Convert(right, typeToCastTo);
	return typeHolder switch
	{
		Sumf => Expression.Add(left, right),
		...
		Andf => Expression.And(left, right),
		...
		Lessf => Expression.LessThan(left, right),
		...
		_ => throw new AngouriBugException("A node seems to be not added")
	};
}

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

Complex:   10
double:     9
float:      8
long:       8
BigInteger: 8
int:        7

Если типы одинаковые, MaxType вернет один из них. Например, MaxType(int, int) -> int.

Если у типа операнда A уровень выше, чем у типа операнда B, то B кастится в A. Например, MaxType(long, double) -> double.

Если уровни одинаковые, а типы - нет, то находится ближайшая общая вершина, то есть любой такой тип, у которого уровень на один выше. Например, MaxType(long, float) -> double.

Операнды, при необходимости, кастятся к выбранному типу, и далее мы просто находим нужный оверлоад или оператор. Например, для Sumf мы выберем Expression.Add, а для конъюкции, Andf, будет Expression.And.

Осознаем.

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

Красивое API

Начали мы с метода, который в конечном API выглядит так:

public TDelegate Compile<TDelegate>(CompilationProtocol protocol, Type returnType, IEnumerable<(Type type, Variable variable)> typesAndNames) where TDelegate : Delegate

Он неудобный и требует много усилий. Но мы можем передавать наш дефолтный протокол И перегрузить этот метод для делегатов от одного аргумента, двух, трех, и так далее. Так как я уже присваиваю наши правила свойствам протокола по умолчанию, то передавая протокол, мы просто создаем его инстанс. Со вторым чуть сложнее - я решил это генерацией кода с помощью T4 Text Template. Вот пример сгенерированного кода:

// указываем типы аргументов и выходной                             а здесь указываем соответствующие переменные из самого выражения
public Func<TIn1, TIn2, TIn3, TOut> Compile<TIn1, TIn2, TIn3, TOut>(Variable var1, Variable var2, Variable var3)
                                       // делегат генерируем сами        выходной тип известен   new() так как создаем правила по умолчанию  
            => IntoLinqCompiler.Compile<Func<TIn1, TIn2, TIn3, TOut>>(this, typeof(TOut),         new(), 
                new[] { (typeof(TIn1), var1), (typeof(TIn2), var2) , (typeof(TIn3), var3)  });

Он же в исходниках.

<# for (var i = 1; i <= 8; i++) { #>
        public Func<<# for(var t=1;t<=i;t++){ #>TIn<#= t #>, <# } #>TOut> Compile<<# for(var t=1;t<=i;t++){ #>TIn<#= t #>, <# } #>TOut>(Variable var1<# for(var t=2; t<=i; t++){ #>, Variable var<#= t #><# } #>)
            => IntoLinqCompiler.Compile<Func<<# for(var t=1;t<=i;t++){ #>TIn<#= t #>, <# } #>TOut>>(this, typeof(TOut), new(), 
                new[] { (typeof(TIn1), var1)<# for(var t=2;t<=i;t++){ #>, (typeof(TIn<#= t #>), var<#= t #>) <# } #> });
<# } #>

Аналогичным образом создаем методы расширения. Вот пример сгенерированного:

public static Func<TIn1, TIn2, TOut> Compile<TIn1, TIn2, TOut>(this string @this, Variable var1, Variable var2)
	=> IntoLinqCompiler.Compile<Func<TIn1, TIn2, TOut>>(@this, typeof(TOut), new(), 
		new[] { (typeof(TIn1), var1), (typeof(TIn2), var2)  });

Теперь надо померить производительность.

Производительность

BenchNormalSimple - простая лямбда, объявленная прямо в коде.

BenchMySimple - та же лямбда, но скомпилированная мною.

BenchNormalComplicated - большая толстая лямбда с кучей идентичных поддеревьев, объявленная прямо в коде.

BenchmyComplicated - та же лямбда, но скомпилированная мною.

|                 Method |       Mean |    Error |   StdDev |
|----------------------- |-----------:|---------:|---------:|
|      BenchNormalSimple |   189.1 ns |  3.75 ns |  5.83 ns |
|          BenchMySimple |   195.7 ns |  3.92 ns |  5.50 ns |
| BenchNormalComplicated | 1,383.0 ns | 26.82 ns | 35.80 ns |
|     BenchMyComplicated |   293.6 ns |  5.74 ns |  8.77 ns |

Простые штуки работают одинаково быстро, а там, где есть идентичные поддеревья, моя компиляция выигрывает. В общем-то предсказуемо, и ничего гениального тут нет.

Бенчмарк тут.

Примеры работы

var func = "sin(x)".Compile<double, double>("x");
Console.WriteLine(func(Math.PI / 2));
>>> 1

var func1 = "a > b".Compile<float, int, bool>("a", "b");
Console.WriteLine(func1(5.4f, 4));
Console.WriteLine(func1(4f, 4));
>>> True
>>> False

var cr = new CompilationProtocol()
{ 
    ConstantConverter = ent => Expression.Constant(ent.ToString()),
    BinaryNodeConverter = (a, b, t) => t switch
    {
        Sumf => Expression.Call(typeof(string)
            .GetMethod("Concat", new[] { typeof(string), typeof(string) }) ?? throw new Exception(), a, b),
        _ => throw new Exception()
    }
};
var func2 = "a + b + c + 1234"
    .Compile<Func<string, string, string, string>>(
        cr, typeof(string), 
        
        new[] { 
            (typeof(string), Var("a")), 
            (typeof(string), Var("b")), 
            (typeof(string), Var("c")) }

        );
Console.WriteLine(func2("White", "Black", "Goose"));
>>> WhiteBlackGoose1234

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

Заключение

1. Linq.Expression по истине гениальная вещь.

2. В этой небольшой статье мы, не особо напрягаясь, скомпилировали математическое выражение.

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

4. Чтобы избежать написания одного и того же кода, мы предложили целый ряд оверлоадов с дефолтным протоколом, отлично работающим с целым рядом встроенных типов. Этот протокол автоматически апкастит типы в бинарных операторах и функциях до ближайшего общего типа, если есть необходимость.

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

Спасибо за внимание! Следующая статья возможно будет про символьные пределы или парсинг.

Ссылки

1. GitHub проекта AngouriMath, в рамках которого я и делал компиляцию

2. Компиляция здесь

3. Тесты компиляции можно посмотреть здесь