Halo. Dalam esai ini, saya akan menunjukkan kepada Anda bagaimana saya mengimplementasikan kompilasi ekspresi matematika (numerik dan logis) ke dalam delegasi menggunakan Ekspresi Linq.
Navigasi: Masalah · Aturan Kompilasi · Kompiler · Aturan default · API yang bagus · Kinerja · Contoh pekerjaan · Kesimpulan · Tautan
Apa yang kita inginkan?
Kami ingin mengompilasi ekspresi menjadi fungsi sejumlah argumen arbitrer dari tipe arbitrer, tidak hanya numerik, tetapi juga boolean. Contohnya,
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
Apa yang kita punya
Karena saya melakukan ini dalam kerangka pustaka aljabar simbolik yang ada, kita akan segera melanjutkan ke kompilasi, yang sudah memiliki parser dan pohon ekspresi.
Kami memiliki kelas Entitas dasar dan pohon keturunan.
Entity
|
+--Operators
|
+--Sumf
|
+--Minusf
|
...
+--Trigonometry
|
+--Sinf
|
+--Cosf
|
...
+--Discrete
|
+--Andf
|
+--Lessf
|
Seperti inilah bentuk pohon tipe. Pohon ekspresi hanyalah grafik di mana anak-anak dari sebuah node adalah operan dari sebuah operator / fungsi.
Setiap jenis bersifat abstrak (hanya berfungsi untuk menggeneralisasi jenis) atau tertutup. Yang terakhir hanyalah operator / fungsi / konstanta / entitas nyata lainnya yang terjadi dalam ekspresi (baik itu plus, sinus, konjungsi, bilangan, himpunan, dll.).
Misalnya, ini adalah bagaimana operator penjumlahan didefinisikan.
Protokol kompilasi
/ , , 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 dari proyek AngouriMath , tempat saya melakukan kompilasi
Kompilasi di sini
Tes kompilasi dapat ditemukan di sini