{"id":392021,"date":"2024-06-29T10:10:22","date_gmt":"2024-06-29T10:10:22","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=392021"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=392021","title":{"rendered":"Compilation of math functions into Linq.Expression<\/span>"},"content":{"rendered":"
<\/div>\n
\n
\n
\n
\n

Hello.\u00a0In this article, I want to demonstrate how I implemented compilation of mathematical (both numerical and logical) expressions into a delegate using Linq Expression.<\/p>\n

Navigation:\u00a0<\/strong>Problem\u00a0<\/em><\/strong><\/a>\u00b7\u00a0<\/em><\/strong>Compilation rules\u00a0<\/em><\/strong><\/a>\u00b7\u00a0<\/em><\/strong>Compiler\u00a0<\/em><\/strong><\/a>\u00b7\u00a0<\/em><\/strong>Default rules\u00a0<\/em><\/strong><\/a>\u00b7\u00a0<\/em><\/strong>Fancy API\u00a0<\/em><\/strong><\/a>\u00b7\u00a0<\/em><\/strong>Performance\u00a0<\/em><\/strong><\/a>\u00b7\u00a0<\/em><\/strong>Examples of compilation\u00a0<\/em><\/strong><\/a>\u00b7\u00a0<\/em><\/strong>Conclusion\u00a0<\/em><\/strong><\/a>\u00b7\u00a0<\/em><\/strong>References<\/em><\/strong><\/a><\/p>\n

<\/a><\/p>\n

What do we want?<\/h4>\n

We want to compile an expression into a function of an arbitrary number of arguments of an arbitrary type, not only numeric, but also boolean.\u00a0For instance,<\/p>\n

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<\/code><\/pre>\n
What do we have already?<\/h4>\n
Since I am doing this within an existing symbolic algebra library, we will immediately proceed to compilation, already having a parser and an expression tree.<\/p>\n
We have base class Entity<\/code>class and its type hierarchy, looking like this:<\/p>\n
Entity | +--Operators   |   +--Sumf   |   +--Minusf   |   ... +--Trigonometry   |   +--Sinf   |   +--Cosf   |   ... +--Discrete   |   +--Andf   |   +--Lessf   |<\/code><\/pre>\n
An expression tree is just a graph where the children of a node are the operands of an operator \/ function.<\/p>\n
Each type is either abstract (only used to generalize other types) or sealed.\u00a0The latter can be a real operator \/ function \/ constant \/ other entity that occurs in an expression (be it plus, sine, conjunction, number, set, etc.).<\/p>\n
For example,\u00a0this is<\/a>\u00a0how the plus operator is defined.<\/p>\n
<\/a><\/p>\n
Compilation protocol<\/h4>\n
This is how I named the interface \/ data class that will define how Entity<\/code>‘s subtypes are mapped to Linq.Expression<\/code>‘s structures, operators, or functions.\u00a0Since we do not know what types the user will request as input and output, the user will have to provide this information.<\/p>\n
This is what it will look like:<\/p>\n
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; } }<\/code><\/pre>\n
Note: <\/strong>We will implement\u00a0ConstantConverter<\/code>\u00a0,\u00a0BinaryNodeConverter<\/code>and\u00a0UnaryNodeConverter<\/code> at the end of the article.<\/p>\n
Our compiler will call all these lambdas internally when converting unary nodes, binary nodes, constant nodes, and multiple nodes into Linq.Expression<\/code>.<\/p>\n
That is, now we know by what rules we will transform each node.\u00a0Now it’s time to write the «compiler» itself, or rather the algorithm that will build a tree.<\/p>\n
<\/a><\/p>\n
Compiler<\/h4>\n
The prototype for the method we want to write looks like this:<\/p>\n
internal static TDelegate Compile<TDelegate>(             Entity expr,              Type? returnType,             CompilationProtocol protocol,             IEnumerable<(Type type, Variable variable)> typesAndNames             ) where TDelegate : Delegate<\/code><\/pre>\n
    \n
  1. \n
    Entity expr<\/code>\u00a0is an expression that we compile.<\/p>\n<\/li>\n
  2. \n
    Type? returnType<\/code>is the return type.\u00a0We can’t extract it from the delegate type, so we have to pass it as a separate argument.<\/p>\n<\/li>\n
  3. \n
    CompilationProtocol protocol<\/code>\u00a0— this is the protocol of rules by which we will transform each node of the expression.<\/p>\n<\/li>\n
  4. \n
    IEnumerable<(Type type, Variable variable)> typesAndNames<\/code>is a set of type-variable tuples that the user will to pass to the resulting delegate.\u00a0For example, if instead of x we \u200b\u200bwant to substitute an integer, and instead of y to pass a complex one, we will writenew[] { (typeof(int), \"x\"), (typeof(Complex), \"y\") }<\/code><\/p>\n<\/li>\n<\/ol>\n
    And here is the implementation of the method:<\/p>\n
    internal static TDelegate Compile<TDelegate>(Entity expr, Type? returnType, CompilationProtocol protocol, IEnumerable<(Type type, Variable variable)> typesAndNames) where TDelegate : Delegate {   \/\/ We keep local variables for every subtree here     var subexpressionsCache = typesAndNames.ToDictionary(c => (Entity)c.variable, c => Expression.Parameter(c.type));   \/\/ Unlike local variables, these parameters are function's arguments     var functionArguments = subexpressionsCache.Select(c => c.Value).ToArray(); \/\/ copying   \/\/ We will save local variables to this list     var localVars = new List<ParameterExpression>();   \/\/ That is a list of assignments of subtrees to local variables     var variableAssignments = new List<Expression>();    \/\/ Building a tree with the provided data     var tree = BuildTree(expr, subexpressionsCache, variableAssignments, localVars, protocol);   \/\/ Then, we create Expression.Block passing the local variables, referenced in the tree     var treeWithLocals = Expression.Block(localVars, variableAssignments.Append(tree));   \/\/ If the user passed returnType, then we try to cast the expression into it     Expression entireExpresion = returnType is not null ? Expression.Convert(treeWithLocals, returnType) : treeWithLocals;   \/\/ Create a lambda with the given expression and the passed function's arguments     var finalLambda = Expression.Lambda<TDelegate>(entireExpresion, functionArguments);    \/\/ finally, compile into a delegate     return finalLambda.Compile(); }<\/code><\/pre>\n
    Its main purpose is to create the necessary containers for the cache of subtrees, local variables, and some other things.\u00a0The most interesting function here is\u00a0BuildTree<\/code>.\u00a0It will build a linq expression tree from\u00a0Entity<\/code>.\u00a0This is what its prototype looks like:<\/p>\n
    internal static Expression BuildTree(     Entity expr,      Dictionary<Entity, ParameterExpression> cachedSubexpressions,      List<Expression> variableAssignments,      List<ParameterExpression> newLocalVars,     CompilationProtocol protocol)<\/code><\/pre>\n
    \nMore about the BuildTree’s arguments<\/summary>\n
    \n
      \n
    1. \n
      Entity expr<\/code>\u00a0— an expression or subexpression to build a tree from.<\/p>\n<\/li>\n
    2. \n
      Dictionary<Entity, ParameterExpression> cachedSubexpressions<\/code>\u00a0— a dictionary of cached subtrees (that is, those that are already written to existing local variables).<\/p>\n<\/li>\n
    3. \n
      List<Expression> variableAssignments<\/code>\u00a0— a list of assignments of unique subtrees to local variables.<\/p>\n<\/li>\n
    4. \n
      List<ParameterExpression> newLocalVars<\/code>— local variables, created by\u00a0BuildTree<\/code>. (for storing results of subtrees).<\/p>\n<\/li>\n
    5. \n
      CompilationProtocol protocol<\/code>— the rules by which we transform a node\u00a0Entity<\/code>into a node\u00a0Linq.Expression<\/code>.\u00a0It remains unchanged and is simply passed on to all calls of\u00a0BuildTree<\/code>.<\/p>\n<\/li>\n<\/ol>\n<\/div>\n<\/details>\n
      And here is the most important function —\u00a0BuildTree<\/code>:<\/p>\n
      internal static Expression BuildTree(Entity expr, ...) {     \/\/ if this subtree was already processed, we return a local variable to which     \/\/ we assigned the subtree's value     if (cachedSubexpressions.TryGetValue(expr, out var readyVar))         return readyVar;      Expression subTree = expr switch     {       ...                  \/\/ A constant goes processed through ConstantConverter         Entity.Boolean or Number => protocol.ConstantConverter(expr),          \/\/ Same mechanism with unary, binary and n-ary nodes         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)     };      \/\/ we create a local variable for this subtree     var newVar = Expression.Variable(subTree.Type);          \/\/ add an instruction like var5 = subTree     variableAssignments.Add(Expression.Assign(newVar, subTree));          \/\/ match the subtree to the variable     cachedSubexpressions[expr] = newVar;          \/\/ trach a newly created variable     newLocalVars.Add(newVar);          return newVar; }<\/code><\/pre>\n
      I have omitted large chunks of code for the sake of readability.\u00a0For each subtree, we either immediately return the local variable corresponding to this expression, or we build a new Linq.Expression tree, store it in a new local variable, and return it.<\/p>\n
      Actually, that’s about it, the compiler is implemented.\u00a0But we have not implemented any rules for converting our expressions to\u00a0Linq.Expression<\/code>, because we expect these rules to be provided by the user.\u00a0But why not provide some default rules for built-in types?<\/p>\n
      The rest of the article will be about creating a default protocol.<\/p>\n
      <\/a><\/p>\n
      Assumptions<\/h4>\n
      The method itself\u00a0Compile<TDelegate>(Entity, Type?, CompilationProtocol, IEnumerable<(Type, Variable)>)<\/code>will be provided to the user, but it is obvious that this is a very long and clumsy construction, you will have to write a huge amount of code describing the transformation of each node and constant, and the method declaration itself is quite long and unclear.<\/p>\n
      So we can provide a default compilation protocol, which will work with some built-in primitives (\u00a0bool<\/code>,\u00a0int<\/code>,\u00a0long<\/code>,\u00a0float<\/code>,\u00a0double<\/code>,\u00a0Complex<\/code>,\u00a0BigInteger<\/code>).<\/p>\n
      ConstantConverter:<\/strong><\/p>\n
      This rule converts a constant from Entity <\/code>to Linq.Constant<\/code> and looks like this:<\/p>\n
      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\")     };<\/code><\/pre>\n
      The Entity.Number<\/code> is casted to a number depending on its type, a boolean constant is unconditionally converted into bool<\/code>.<\/p>\n
      \nMore about DownCast<\/summary>\n
      \n
      This function converts Entity.Number to some of the built-in types and is implemented as follows:<\/p>\n
      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\"); }<\/code><\/pre>\n
      Returns\u00a0object<\/code>because this is exactly what\u00a0Expression.Constant<\/code>\u00a0expects as an argument.\u00a0This is what we would like to see: we can cast the number to any class, and it’s still a constant.<\/p>\n<\/div>\n<\/details>\n
      UnaryNodeConverter:<\/strong><\/p>\n
      This protocol’s rule is a delegate that converts a node with one argument to a\u00a0Linq.Expression<\/code>.<\/p>\n
      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\")     };<\/code><\/pre>\n
      I’ve omitted some big blocks (all code\u00a0here\u00a0<\/a>).\u00a0So, here we consider the possible types of our node, and for each we select the desired overload of a function.\u00a0GetDef<\/code>finds the function we want by name.<\/p>\n
      \nAbout GetDef<\/summary>\n
      \n
      At first I thought of calling all the necessary functions from modules\u00a0Math<\/code>and\u00a0Complex<\/code>.\u00a0I had to write a lot of conditional statments everywhere, consider cases when I should use\u00a0Math<\/code>,\u00a0Complex<\/code>, and BigInteger<\/code>.\u00a0Another issue is that\u00a0Math<\/code>\u00a0does not have some overloads, for instance,\u00a0int Pow(int, int)<\/code>.<\/p>\n
      Therefore, I created the\u00a0MathAllMethods<\/a>\u00a0class\u00a0(in T4), where I created all the necessary overloads for all the necessary functions.<\/p>\n
      GetDef<\/code>searches for the required method with the given number of arguments and type in this class.\u00a0This allowed us to get rid of the spaghetti code and write down all calls to the necessary functions by these types in a beautiful and concise manner.<\/p>\n<\/div>\n<\/details>\n
      BinaryNodeConverter:<\/strong><\/p>\n
      This rule converts a two-argument node to a\u00a0Linq.Expression<\/code>.<\/p>\n
      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\")     }; }<\/code><\/pre>\n
      There is an\u00a0upcast<\/code>.\u00a0Since we may have two expressions of different types, we want to find the most primitive type to which both operands are cast.\u00a0To do this, I assigned a level to every type:<\/p>\n
      Complex:   10 double:     9 float:      8 long:       8 BigInteger: 8 int:        7<\/code><\/pre>\n
      If the types are the same, MaxType<\/code>will return one of them.\u00a0For example,MaxType(int, int) -> int<\/code>.<\/p>\n
      If the level of the operand A’s type is higher than that of operand B’s type, then B is casted to A. For example,\u00a0MaxType(long, double) -> double<\/code>.<\/p>\n
      If the levels are equal, but the types are not, then the closest common vertex is found, that is, any such type whose level is higher by 1.\u00a0For example, MaxType(long, float) -> double<\/code>.<\/p>\n
      Operands, if necessary, are cast to the selected type, and then we simply find the required overload or operator.\u00a0For example, for\u00a0Sumf<\/code>we choose\u00a0Expression.Add<\/code>, and for conjunction,\u00a0Andf<\/code>will be turned into\u00a0Expression.And<\/code>.<\/p>\n
      What happened?<\/strong><\/p>\n
      Great, we have defined all the necessary rules for our protocol.\u00a0Now, during creation, we can pass these rules to the required protocol properties.<\/p>\n
      <\/a><\/p>\n
      Fancy API<\/h4>\n
      This is the low-level version of what we want to see in the final API:<\/p>\n
      public TDelegate Compile<TDelegate>(CompilationProtocol protocol, Type returnType, IEnumerable<(Type type, Variable variable)> typesAndNames) where TDelegate : Delegate<\/code><\/pre>\n
      It is inconvenient and requires a lot of work to be performed before we can call one.\u00a0But we can pass our default protocol AND overload this method for delegates from one argument, two, three, and so on.\u00a0Since I already\u00a0assign\u00a0<\/a>our rules to the default protocol properties, when passing the protocol, we simply create an instance of it.\u00a0The second is a little more complicated — I solved it by generating the code using the T4 Text Template.\u00a0Here’s an example of the generated code:<\/p>\n
      \/\/ specifying the input and output types                            Here we pass the variables corresponding to the types public Func<TIn1, TIn2, TIn3, TOut> Compile<TIn1, TIn2, TIn3, TOut>(Variable var1, Variable var2, Variable var3)                                      \/\/ The delegate we want to get     We know the output type   new() as we create default rules               => IntoLinqCompiler.Compile<Func<TIn1, TIn2, TIn3, TOut>>(this, typeof(TOut),         new(),                  new[] { (typeof(TIn1), var1), (typeof(TIn2), var2) , (typeof(TIn3), var3)  });<\/code><\/pre>\n
      It’s in the\u00a0source\u00a0<\/a>.<\/p>\n
      \nT4-template text to generate<\/summary>\n
      \n
      <# 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 #>) <# } #> }); <# } #><\/code><\/pre>\n<\/div>\n<\/details>\n
      We create extension methods in the same way.\u00a0Here is an example of generated code:<\/p>\n
      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)  });<\/code><\/pre>\n
      Now we need to measure the performance.<\/p>\n
      <\/a><\/p>\n
      Performance<\/h4>\n
      BenchNormalSimple <\/code>is a simple lambda, declared right in the code.<\/p>\n
      BenchMySimple <\/code>is the same lambda, but compiled by me.<\/p>\n
      BenchNormalComplicated <\/code>is a big fat lambda with a bunch of identical subtrees, declared right in the code.<\/p>\n
      BenchmyComplicated <\/code>— the same lambda, but compiled by me.<\/p>\n
      |                 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 |<\/code><\/pre>\n
      Simple things work equally fast, and where there are identical subtrees, my compilation beats the normal one.\u00a0In general, the result is predictable, and there is nothing extraordinary here.<\/p>\n
      The benchmark is\u00a0here\u00a0<\/a>.<\/p>\n
      <\/a><\/p>\n
      Examples of work<\/h4>\n
      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<\/code><\/pre>\n
      (The last example is an example of how the user themselves declares the protocol instead of using the existing one. The result of this compilation is a lambda, concatenating strings).<\/p>\n
      <\/a><\/p>\n
      Conclusion<\/h4>\n
        \n
      1. \n
        Linq.Expression<\/code>\u00a0is truly a brilliant thing.<\/p>\n<\/li>\n
      2. \n
        In this short article, we well implemented a compilation process for mathematical expressions.<\/p>\n<\/li>\n
      3. \n
        To ensure that the types are arbitrary, we came up with a protocol for translating an expression.<\/p>\n<\/li>\n
      4. \n
        To avoid making the user write the same code over and over again, we offer a number of overloads with a default protocol that works great with a number of built-in types.\u00a0This protocol will automatically upcast types in binary operators and functions to the nearest generic type, if necessary.<\/p>\n<\/li>\n<\/ol>\n
        Such functionality can be used where you would like to get a fast-working mathematical function from a string at runtime.\u00a0Maybe the community will come up with some other useful application.\u00a0By the way, I have already used\u00a0runtime compilation\u00a0in another\u00a0project\u00a0<\/a>, in which dynamic compilation of nested loops allowed us to avoid recursion (and save precious nanoseconds).<\/p>\n
        Thank you for your attention!\u00a0The next article\u00a0will\u00a0probably<\/em>\u00a0be about symbolic limits or parsing from a string.<\/p>\n
        <\/a><\/p>\n
        References<\/h4>\n
          \n
        1. \n
          GitHub of the AngouriMath project<\/a>\u00a0, within which I developed the compilation<\/p>\n<\/li>\n
        2. \n
          Compilation’s code\u00a0here<\/a><\/p>\n<\/li>\n
        3. \n
          Compilation’s tests can be found\u00a0here<\/a><\/p>\n<\/li>\n<\/ol>\n<\/div>\n<\/div>\n<\/div>\n
          <\/div>\n

           \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438            https:\/\/habr.com\/ru\/articles\/546926\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
          <\/div>\n
          \n
          \n
          \n
          \n
          Hello.\u00a0In this article, I want to demonstrate how I implemented compilation of mathematical (both numerical and logical) expressions into a delegate using Linq Expression.<\/p>\n
          Navigation:\u00a0<\/strong>Problem\u00a0<\/em><\/strong><\/a>\u00b7\u00a0<\/em><\/strong>Compilation rules\u00a0<\/em><\/strong><\/a>\u00b7\u00a0<\/em><\/strong>Compiler\u00a0<\/em><\/strong><\/a>\u00b7\u00a0<\/em><\/strong>Default rules\u00a0<\/em><\/strong><\/a>\u00b7\u00a0<\/em><\/strong>Fancy API\u00a0<\/em><\/strong><\/a>\u00b7\u00a0<\/em><\/strong>Performance\u00a0<\/em><\/strong><\/a>\u00b7\u00a0<\/em><\/strong>Examples of compilation\u00a0<\/em><\/strong><\/a>\u00b7\u00a0<\/em><\/strong>Conclusion\u00a0<\/em><\/strong><\/a>\u00b7\u00a0<\/em><\/strong>References<\/em><\/strong><\/a><\/p>\n
          <\/a><\/p>\n
          What do we want?<\/h4>\n
          We want to compile an expression into a function of an arbitrary number of arguments of an arbitrary type, not only numeric, but also boolean.\u00a0For instance,<\/p>\n
          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<\/code><\/pre>\n
          What do we have already?<\/h4>\n
          Since I am doing this within an existing symbolic algebra library, we will immediately proceed to compilation, already having a parser and an expression tree.<\/p>\n
          We have base class Entity<\/code>class and its type hierarchy, looking like this:<\/p>\n
          Entity | +--Operators   |   +--Sumf   |   +--Minusf   |   ... +--Trigonometry   |   +--Sinf   |   +--Cosf   |   ... +--Discrete   |   +--Andf   |   +--Lessf   |<\/code><\/pre>\n
          An expression tree is just a graph where the children of a node are the operands of an operator \/ function.<\/p>\n
          Each type is either abstract (only used to generalize other types) or sealed.\u00a0The latter can be a real operator \/ function \/ constant \/ other entity that occurs in an expression (be it plus, sine, conjunction, number, set, etc.).<\/p>\n
          For example,\u00a0this is<\/a>\u00a0how the plus operator is defined.<\/p>\n
          <\/a><\/p>\n
          Compilation protocol<\/h4>\n
          This is how I named the interface \/ data class that will define how Entity<\/code>‘s subtypes are mapped to Linq.Expression<\/code>‘s structures, operators, or functions.\u00a0Since we do not know what types the user will request as input and output, the user will have to provide this information.<\/p>\n
          This is what it will look like:<\/p>\n
          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; } }<\/code><\/pre>\n
          Note: <\/strong>We will implement\u00a0ConstantConverter<\/code>\u00a0,\u00a0BinaryNodeConverter<\/code>and\u00a0UnaryNodeConverter<\/code> at the end of the article.<\/p>\n
          Our compiler will call all these lambdas internally when converting unary nodes, binary nodes, constant nodes, and multiple nodes into Linq.Expression<\/code>.<\/p>\n
          That is, now we know by what rules we will transform each node.\u00a0Now it’s time to write the «compiler» itself, or rather the algorithm that will build a tree.<\/p>\n
          <\/a><\/p>\n
          Compiler<\/h4>\n
          The prototype for the method we want to write looks like this:<\/p>\n
          internal static TDelegate Compile<TDelegate>(             Entity expr,              Type? returnType,             CompilationProtocol protocol,             IEnumerable<(Type type, Variable variable)> typesAndNames             ) where TDelegate : Delegate<\/code><\/pre>\n
            \n
          1. \n
            Entity expr<\/code>\u00a0is an expression that we compile.<\/p>\n<\/li>\n
          2. \n
            Type? returnType<\/code>is the return type.\u00a0We can’t extract it from the delegate type, so we have to pass it as a separate argument.<\/p>\n<\/li>\n
          3. \n
            CompilationProtocol protocol<\/code>\u00a0— this is the protocol of rules by which we will transform each node of the expression.<\/p>\n<\/li>\n
          4. \n
            IEnumerable<(Type type, Variable variable)> typesAndNames<\/code>is a set of type-variable tuples that the user will to pass to the resulting delegate.\u00a0For example, if instead of x we \u200b\u200bwant to substitute an integer, and instead of y to pass a complex one, we will writenew[] { (typeof(int), \"x\"), (typeof(Complex), \"y\") }<\/code><\/p>\n<\/li>\n<\/ol>\n
            And here is the implementation of the method:<\/p>\n
            internal static TDelegate Compile<TDelegate>(Entity expr, Type? returnType, CompilationProtocol protocol, IEnumerable<(Type type, Variable variable)> typesAndNames) where TDelegate : Delegate {   \/\/ We keep local variables for every subtree here     var subexpressionsCache = typesAndNames.ToDictionary(c => (Entity)c.variable, c => Expression.Parameter(c.type));   \/\/ Unlike local variables, these parameters are function's arguments     var functionArguments = subexpressionsCache.Select(c => c.Value).ToArray(); \/\/ copying   \/\/ We will save local variables to this list     var localVars = new List<ParameterExpression>();   \/\/ That is a list of assignments of subtrees to local variables     var variableAssignments = new List<Expression>();    \/\/ Building a tree with the provided data     var tree = BuildTree(expr, subexpressionsCache, variableAssignments, localVars, protocol);   \/\/ Then, we create Expression.Block passing the local variables, referenced in the tree     var treeWithLocals = Expression.Block(localVars, variableAssignments.Append(tree));   \/\/ If the user passed returnType, then we try to cast the expression into it     Expression entireExpresion = returnType is not null ? Expression.Convert(treeWithLocals, returnType) : treeWithLocals;   \/\/ Create a lambda with the given expression and the passed function's arguments     var finalLambda = Expression.Lambda<TDelegate>(entireExpresion, functionArguments);    \/\/ finally, compile into a delegate     return finalLambda.Compile(); }<\/code><\/pre>\n
            Its main purpose is to create the necessary containers for the cache of subtrees, local variables, and some other things.\u00a0The most interesting function here is\u00a0BuildTree<\/code>.\u00a0It will build a linq expression tree from\u00a0Entity<\/code>.\u00a0This is what its prototype looks like:<\/p>\n
            internal static Expression BuildTree(     Entity expr,      Dictionary<Entity, ParameterExpression> cachedSubexpressions,      List<Expression> variableAssignments,      List<ParameterExpression> newLocalVars,     CompilationProtocol protocol)<\/code><\/pre>\n
            \nMore about the BuildTree’s arguments<\/summary>\n
            \n
              \n
            1. \n
              Entity expr<\/code>\u00a0— an expression or subexpression to build a tree from.<\/p>\n<\/li>\n
            2. \n
              Dictionary<Entity, ParameterExpression> cachedSubexpressions<\/code>\u00a0— a dictionary of cached subtrees (that is, those that are already written to existing local variables).<\/p>\n<\/li>\n
            3. \n
              List<Expression> variableAssignments<\/code>\u00a0— a list of assignments of unique subtrees to local variables.<\/p>\n<\/li>\n
            4. \n
              List<ParameterExpression> newLocalVars<\/code>— local variables, created by\u00a0BuildTree<\/code>. (for storing results of subtrees).<\/p>\n<\/li>\n
            5. \n
              CompilationProtocol protocol<\/code>— the rules by which we transform a node\u00a0Entity<\/code>into a node\u00a0Linq.Expression<\/code>.\u00a0It remains unchanged and is simply passed on to all calls of\u00a0BuildTree<\/code>.<\/p>\n<\/li>\n<\/ol>\n<\/div>\n<\/details>\n
              And here is the most important function —\u00a0BuildTree<\/code>:<\/p>\n
              internal static Expression BuildTree(Entity expr, ...) {     \/\/ if this subtree was already processed, we return a local variable to which     \/\/ we assigned the subtree's value     if (cachedSubexpressions.TryGetValue(expr, out var readyVar))         return readyVar;      Expression subTree = expr switch     {       ...                  \/\/ A constant goes processed through ConstantConverter         Entity.Boolean or Number => protocol.ConstantConverter(expr),          \/\/ Same mechanism with unary, binary and n-ary nodes         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)     };      \/\/ we create a local variable for this subtree     var newVar = Expression.Variable(subTree.Type);          \/\/ add an instruction like var5 = subTree     variableAssignments.Add(Expression.Assign(newVar, subTree));          \/\/ match the subtree to the variable     cachedSubexpressions[expr] = newVar;          \/\/ trach a newly created variable     newLocalVars.Add(newVar);          return newVar; }<\/code><\/pre>\n
              I have omitted large chunks of code for the sake of readability.\u00a0For each subtree, we either immediately return the local variable corresponding to this expression, or we build a new Linq.Expression tree, store it in a new local variable, and return it.<\/p>\n
              Actually, that’s about it, the compiler is implemented.\u00a0But we have not implemented any rules for converting our expressions to\u00a0Linq.Expression<\/code>, because we expect these rules to be provided by the user.\u00a0But why not provide some default rules for built-in types?<\/p>\n
              The rest of the article will be about creating a default protocol.<\/p>\n
              <\/a><\/p>\n
              Assumptions<\/h4>\n
              The method itself\u00a0Compile<TDelegate>(Entity, Type?, CompilationProtocol, IEnumerable<(Type, Variable)>)<\/code>will be provided to the user, but it is obvious that this is a very long and clumsy construction, you will have to write a huge amount of code describing the transformation of each node and constant, and the method declaration itself is quite long and unclear.<\/p>\n
              So we can provide a default compilation protocol, which will work with some built-in primitives (\u00a0bool<\/code>,\u00a0int<\/code>,\u00a0long<\/code>,\u00a0float<\/code>,\u00a0double<\/code>,\u00a0Complex<\/code>,\u00a0BigInteger<\/code>).<\/p>\n
              ConstantConverter:<\/strong><\/p>\n
              This rule converts a constant from Entity <\/code>to Linq.Constant<\/code> and looks like this:<\/p>\n
              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\")     };<\/code><\/pre>\n
              The Entity.Number<\/code> is casted to a number depending on its type, a boolean constant is unconditionally converted into bool<\/code>.<\/p>\n
              \nMore about DownCast<\/summary>\n
              \n
              This function converts Entity.Number to some of the built-in types and is implemented as follows:<\/p>\n
              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\"); }<\/code><\/pre>\n
              Returns\u00a0object<\/code>because this is exactly what\u00a0Expression.Constant<\/code>\u00a0expects as an argument.\u00a0This is what we would like to see: we can cast the number to any class, and<\/p>\n<\/div>\n<\/details>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-392021","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/392021","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=392021"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/392021\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=392021"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=392021"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=392021"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}