Hallo. In diesem Aufsatz werde ich Ihnen zeigen, wie ich die Kompilierung mathematischer (numerischer und logischer) Ausdrücke mithilfe von Linq Expression in einen Delegaten implementiert habe.
Navigation: Problem · Kompilierungsregeln · Compiler · Standardregeln · Schöne API · Leistung · Arbeitsbeispiele · Schlussfolgerung · Links
Was wollen wir?
Wir wollen den Ausdruck in eine Funktion einer beliebigen Anzahl von Argumenten eines beliebigen Typs kompilieren, nicht nur numerisch, sondern auch boolesch. Zum Beispiel,
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
Was haben wir?
Da ich dies im Rahmen der vorhandenen Bibliothek für symbolische Algebra mache, werden wir sofort mit der Kompilierung fortfahren und bereits einen Parser und einen Ausdrucksbaum haben.
Wir haben eine Basisentitätsklasse und einen Nachkommenbaum.
Entity
|
+--Operators
|
+--Sumf
|
+--Minusf
|
...
+--Trigonometry
|
+--Sinf
|
+--Cosf
|
...
+--Discrete
|
+--Andf
|
+--Lessf
|
So sieht der Typbaum aus. Ein Ausdrucksbaum ist nur ein Diagramm, in dem die untergeordneten Elemente eines Knotens die Operanden eines Operators / einer Funktion sind.
Jeder Typ ist entweder abstrakt (dient nur zur Verallgemeinerung von Typen) oder versiegelt. Letzteres sind nur reale Operatoren / Funktionen / Konstanten / andere Entitäten, die in einem Ausdruck vorkommen (sei es Plus, Sinus, Konjunktion, Zahl, Menge usw.).
Zum Beispiel ist dies , wie die Summe Operator definiert ist.
Kompilierungsprotokoll
/ , , 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
Entity expr
- , .
Type? returnType
- . "" , .
CompilationProtocol protocol
- ,
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
Entity expr
- , .
Dictionary<Entity, ParameterExpression> cachedSubexpressions
- ( , ).
List<Expression> variableAssignments
- .
List<ParameterExpression> newLocalVars
-BuildTree
( ).
CompilationProtocol protocol
- ,Entity
Linq.Expression
.BuildTree
.
- 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
.
DownCast
Entity.Number - :
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");
}
object
, Expression.Constant
. : ?
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
Math
Complex
. if-, Math
, Complex
, BigInteger. , Math
int Pow(int, int)
, .
MathAllMethods ( T4), , .
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) });
T4-
<# 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
( - , , . , ).
Linq.Expression
.
, , .
, , .
, , . , .
! .
GitHub des AngouriMath-Projekts , in dem ich die Kompilierung durchgeführt habe
Zusammenstellung hier
Zusammenstellungstests finden Sie hier