Date: May 12, 2015
I wanted to share a new pattern I developed for perform generic mathematics in C# using runtime compilation.
Over the years I've been coding I have seen several versions of generic math in C#, but none of them have been particularly good. In this section I would like to step through some examples I have seen, and explain why they do not make good patterns for generic math.
I developed this pattern to use as part of my Seven Framework project. Please check out the project here if you are interested: https://github.com/ZacharyPatten/SevenFramework
Author Edit (2020.7.26): The "SevenFramework" GitHub repository is still publicly available, but it is now archived. The library has gone through several iterations, and the most recent version is here: https://github.com/ZacharyPatten/Towel.
First off, the fundamental problem is that generic types in C# are treated like base objects. They have no implied members other than the base System.Object. This means they do not have the arithmatic operators or conversions from standard value types (int, double, decimal, etc.). EXAMPLE 1 would be ideal, but this code will not compile in standard C#:
// EXAMPLE 1 ----------------------------------------
namespace ConsoleApplication
{
public class Program
{
public static void Main(string[] args)
{
Sum<int>(new int[] { 1, 2, 3, 4, 5 });
}
public static T Sum<T>(T[] array)
{
T sum = 0; // (1) cannot convert int to generic
for (int i = 0; i < array.Length; i++)
sum += array[i]; // (2) cannot assume addition operator on generic
return sum;
}
}
}So, EXAMPLE 1 will not compile because:
- Type "T" is not guaranteed to have an implicit cast from an int value
- Type "T" is not guaranteed to have an addition operator.
Now that we know the fundamental problem, let’s start looking at some methods of overcoming it.
The "where" clause in C# is a constraint that enforces generics to be of a certain type. However, this requires that there be a base numeric type, wich does not exist in C#. The closest thing C# has to a base numeric type is enforcing that the generic type is a value type, but this doesn’t help us with mathematics at all. EXAMPLE 2 still won’t compile on it’s own, but it will if we make our own base numeric type.
// EXAMPLE 2 ----------------------------------------
namespace ConsoleApplication
{
public class Program
{
public static void Main(string[] args)
{
Sum<int>(new int[] { 1, 2, 3, 4, 5 });
}
public static T Sum<T>(T[] array)
where T : number// (1) there is no base "number" type in C#
{
T sum = 0;
for (int i = 0; i < array.Length; i++)
sum += array[i];
return sum;
}
}
}EXAMPLE 2 will not compile yet because:
- There is no base "number" type in C#.
We can make it compile if we implement our own base "number" type. All we need to do is enforce that numeric types have arithmatic operators and conversions from the primitive C# value types. Logically, this should be an interface.
However, even if we make our own numeric interface, we will still have one major issue. We will not be able to do generic mathematics on the primitive types in C# because we cannot alter the source code of int, double, decimal, etc to implement our interface. So, not only will we have to make our own base interface, but we will also be required to write wrappers around all the primitive types in C#.
In EXAMPLE 3, we have our base numeric interface, Number, and a wrapper around the primitive int, Integer32.
// EXAMPLE 3 ----------------------------------------
namespace ConsoleApplication
{
public class Program
{
public static void Main(string[] args)
{
Sum(new Number[]
{
new Integer32(1), // (1) initialization nightmares...
new Integer32(2),
new Integer32(3),
new Integer32(4),
new Integer32(5)
});
}
public static Number Sum(Number[] array)
{
Number sum = array[0].GetZero(); // (2) instance-based factory methods are terrible design
for (int i = 0; i < array.Length; i++)
sum = sum.Add(array[i]);
return sum;
}
}
public interface Number
{
Number GetZero(); // (2) again... instance based factory methods are awful
Number Add(Number other);
}
public struct Integer32 : Number // (3) C# primitives cannot implement "Number"
{
int _value;
public Integer32(int value)
{
this._value = value;
}
Number Number.GetZero()
{
return new Integer32(0);
}
// (4) you will have to re-write these functions for every single type
Number Number.Add(Number other)
{
return new Integer32(_value + ((Integer32)other)._value);
}
}
}
// (5) this code is incredibly slowOkay, so EXAMPLE 3 compiles, but it is just horrid. Here is why:
- Initializing variables when coding with interfaces can be very ugly.
- You should never have a factory method or constructor as an instance method because it is bad design and can easily cause null reference exceptions all over the place.
- You cannot make the primitive types in C# implement the "Number" interface so you can only work with custom types.
- It is not actually generic math because you will have to write a custom implementation for every single type.
- This code is horribly slow mainly due to the wrapper around a primitive type.
If your generic math library cannot perform math on the generic types in C#, no one will ever use it. So, let’s tackle that problem next. If we will never be able to alter the primitive types in C# to implement our interfaces, then we must create another type that will handle the mathematics for those types. This is the standard "provider" pattern used quite often in the .Net Framework.
SIDE NOTE / VENTING: Personally, I hate the "provider" pattern. I have yet to find an example that cannot be better handled using delegates. They didn’t have delegates when a lot of the providers were made.
When we use the provider pattern, we will essentially be doing the same thing as before, but our provider class will be the one handling all the mathematics. Check out EXAMPLE 4:
//EXAMPLE 4 ----------------------------------------
namespace ConsoleApplication
{
public class Program
{
public static void Main(string[] args)
{
Sum<int>(new int[] { 1, 2, 3, 4, 5}, new MathProvider_int());
}
// (1) all the methods need access to the provider
public static T Sum<T>(T[] array, MathProvider<T> mathProvider)
{
T sum = mathProvider.GetZero();
for (int i = 0; i < array.Length; i++)
sum = mathProvider.Add(sum, array[i]);
return sum;
}
}
public interface MathProvider<T>
{
T GetZero(); // (2) you still need instance factory methods
T Add(T left, T right);
}
public class MathProvider_int : MathProvider<int>
{
public MathProvider_int() { }
int MathProvider<int>.GetZero()
{
return 0;
}
// (3) you still have to implement each function for every single type
int MathProvider<int>.Add(int left, int right)
{
return left + right;
}
}
}
// (4) can be slow depending on implementation (this version is slow)By moving all the functionality into a helper class in EXAMPLE 4, we are able to perform mathematics on the primitive types in C#. Howwever, this only fixed 1 of our issues from EXAMPLE 3. We still have all this to deal with:
- All the methods will need access to the math provider. Although you can code it to where you don’t have to pass in the provider into every function, the same principle applies in one form or another.
- You still require instance based factory methods. In this case it is a conversion from an int.
- You still have to implement the functionality for every single type in the source code.
- Unless you do some clever storage with your providers, this is still fairly slow. The passing around or look-up of providers really adds up.
Now we have tried using interfaces on both the numeric type itself (EXAMPLE 3) and an external provider (EXAMPLE 4). There isn’t really much else we can do with interfaces. Sure we can work in some clever storage hacks, but we will always end up with the same problem: we will always have to make a custom implementation for every single type we want to support.
The bottom line is... interfaces cannot be used for effective generic mathematics in C#.
Everything in C# is cast-able to a System.Object. Therefore, we can just cast everything to an object and handle it with control flow. Let’s give is a shot:
// EXAMPLE 5 ----------------------------------------
namespace ConsoleApplication
{
public class Program
{
public static void Main(string[] args)
{
MathProvider<int>.Sum(new int[] { 1, 2, 3, 4, 5});
}
}
public static class MathProvider<T>
{
public static T Sum(T[] array)
{
// (1) still requires a custom implementation for every type
if (typeof(T) == typeof(int))
{
T sum = (T)(object)0; // (2) largescale casting is very glitch prone
for (int i = 0; i < array.Length; i++)
sum = (T)(object)((int)(object)sum + ((int)(object)array[i]));
return sum;
}
throw new System.Exception("UNSUPPORTED TYPE"); // (3) runtime errors
}
}
}
// (4) horribly slow...Actually, this is looking much better than the interface approches. The code iteslf is simple and easy to use. However, we still have many of the problems as before:
- We still need to create a custom implementation for every type.
- Now we have a lot of object casting which can result in possible exceptions and is slow
- Now we have runtime errors for non-supported types.
- The function is still slow.
NOTE: I’m not sure if they are still doing this in F#, but when I was looking through the standard generic math functions in the F# language, it looked like all they are doing is object casting at the lowest level. Shame! :P
Object casting is another dead end, but it is very simple to use at least.
Delegates... are... amazing!
We cannot do mathematics on generic types efficiently. We just can’t. The compiler can’t make assumptions without some form of inheritance, and we cannot make the C# primitives inherit our classes.
So let’s move the functionality of the generic code outside of the generic class! How can we do this? Delegates! Just store a delegate inside the generic class and assign it at runtime from an external location where the types are known by the compiler.
However, we can place a delegate in the generic class, and then build the delegate in an external location and assign it at runtime.
// EXAMPLE 6 ----------------------------------------
namespace ConsoleApplication
{
public class Program
{
public static void Main(string[] args)
{
// (1) requires a constructor method to be called prior to use
MathProviderConstructors.Construct();
MathProvider<int>.Sum(new int[] { 1, 2, 3, 4, 5});
}
}
public static class MathProviderConstructors
{
public static void Construct()
{
// (2) still requires a custom implementation for every type
MathProvider<int>.Sum = (int[] array) =>
{
int sum = 0;
for (int i = 0; i < array.Length; i++)
sum = sum + array[i];
return sum;
};
}
}
public static class MathProvider<T>
{
// (3) still have runtime errors for non-implemented types (null-ref)
public static System.Func<T[], T> Sum;
}
}EXAMPLE 6 is by far the best example of generic math yet. It is fast, it can work on any type, and it is very easy to use aside from making sure the static constructor method is called. However, it still has flaws...
- It requires that constructor method be called
- It still requires a custom implementation for every type.
- It still throws runtime errors.
Ther is one major benefit to using delegates. The library can be altered at runtime. Other developers can alter the lmath library however they want. They can fix bugs at runtime. Here is EXAMPLE 6 again, but where the function has been overriden:
// EXAMPLE 6-1 ----------------------------------------
namespace ConsoleApplication
{
public class Program
{
public static void Main(string[] args)
{
// (1) requires a constructor method to be called prior to use
MathProviderConstructors.Construct();
// OVERRIDE THE MATH LIBRARY
MathProvider<int>.Sum = (int[] array) =>
{
int sum = 0;
foreach (int integer in array)
sum = integer;
return sum;
};
MathProvider<int>.Sum(new int[] { 1, 2, 3, 4, 5});
}
}
public static class MathProviderConstructors
{
public static void Construct()
{
// (2) still requires a custom implementation for every type
MathProvider<int>.Sum = (int[] array) =>
{
int sum = 0;
for (int i = 0; i < array.Length; i++)
sum = sum + array[i];
return sum;
};
}
}
public static class MathProvider<T>
{
// (3) still have runtime errors for non-implemented types (null-ref)
public static System.Func<T[], T> Sum;
}
} The ability to override and alter code at runtime without ever touching the source code of the math library itself is a great feature.
Delegates are definitely the way to go, but in order to keep improving, we will have to combine delgates with another technique.
So far, delegates are appear like the way to go, but we are still struggling with the issue of having to implement the functions for every single type. There must be a way around this. If we were coding in C, we would probably try to do some macro magic. But wait... why can’t we do macros in C#? We can Using runtime compilation!
Here is my current version of a generic mathematics pattern:
// EXAMPLE 7 (CURRENT) --------------------------
using Microsoft.CSharp;
using System;
using System.CodeDom.Compiler;
using System.Reflection;
namespace RuntimeCodeCompiling
{
public static class Program
{
public static Action action;
public static void Main(string[] args)
{
Console.WriteLine("Sum(double): " + Generic_Math<double>.Sum(new double[] { 1, 2, 3, 4, 5 }));
Console.WriteLine("Sum(int): " + Generic_Math<int>.Sum(new int[] { 1, 2, 3, 4, 5 }));
Console.WriteLine("Sum(decimal): " + Generic_Math<decimal>.Sum(new decimal[] { 1, 2, 3, 4, 5 }));
Console.ReadLine();
}
#region Generic Math Library Example
public static class Generic_Math<T>
{
public static Func<T[], T> Sum = (T[] array) =>
{
// This implementation will make this string be stored in memory during runtime, so it might be better to read it from a file
string code = "(System.Func<NUMBER[], NUMBER>)((NUMBER[] array) => { NUMBER sum = 0; for (int i = 0; i < array.Length; i++) sum += array[i]; return sum; })";
// This requires that "T" has an implicit converter from int values and a "+" operator
code = code.Replace("NUMBER", typeof(T).ToString());
// This small of an example requires no namspaces or references
Generic_Math<T>.Sum = Generate.Object<Func<T[], T>>(new string[] { }, new string[] { }, code);
return Generic_Math<T>.Sum(array);
};
}
/// <summary>Generates objects at runtime.</summary>
internal static class Generate
{
/// <summary>Generates a generic object at runtime.</summary>
/// <typeparam name="T">The type of the generic object to create.</typeparam>
/// <param name="references">The required assembly references.</param>
/// <param name="name_spaces">The required namespaces.</param>
/// <param name="code">The object to generate.</param>
/// <returns>The generated object.</returns>
internal static T Object<T>(string[] references, string[] name_spaces, string code)
{
string full_code = string.Empty;
if (name_spaces != null)
for (int i = 0; i < name_spaces.Length; i++)
full_code += "using " + name_spaces[i] + ";";
full_code += "namespace Seven.Generated {";
full_code += "public class Generator {";
full_code += "public static object Generate() { return " + code + "; } } }";
CompilerParameters parameters = new CompilerParameters();
foreach (string reference in references)
parameters.ReferencedAssemblies.Add(reference);
parameters.GenerateInMemory = true;
CompilerResults results = new CSharpCodeProvider().CompileAssemblyFromSource(parameters, full_code);
if (results.Errors.HasErrors)
{
string error = string.Empty;
foreach (CompilerError compiler_error in results.Errors)
error += compiler_error.ErrorText.ToString() + "\n";
throw new Exception(error);
}
MethodInfo generate = results.CompiledAssembly.GetType("Seven.Generated.Generator").GetMethod("Generate");
return (T)generate.Invoke(null, null);
}
}
#endregion
}
}HOW IT WORKS:
If you store the generic mathematics code as a string, you can use string hacking (macros aka string replace) to alter the code at runtime. This allows us to write one function and then alter the types that function uses. Thus, we can force the assumption that the generic type has the necessary mathematics operators needed to complete the function.
Upon calling the generic "Func" the first time, it will construct itself and re-assign itself. This way we don’t have to deal with a silly constructor method, and it only constructs generic methods as we need them.
As far as I am aware, you cannot compile a single object using the rutime compiler, so instead I just compiled a method that will return the type I need. Yay hacks... There might be alternatives to this methodology especially by using serialization techniques, but I’m not very experienced in the serialization formats, so this was easier for me personally.
PROS:
- Only one version of the code is required for every type.
- There are no constructors or setup functions to call, and methods construct themselves as they are required.
- Fast! The only overhead to this methodology (that I can tell) is invoking a delegate.
- Developers can override the functions without altering the source code, and you can change functionality at runtime. Got a math bug on a server? Just update the delegate! You don’t need to restart the server.
MINOR CONS: (kind of... all of these "cons" can be handled)
- It can be annoying to writing the generic math function as a string. FIX: I recommend that the generic code be made in a seperate file and parsed. This way the string is not permanently in memory, and you can still edit it as if it were standard C# in Visual studio.
- This example is not cross platform. FIX: It can be easily made to be cross platform. According to their website, it looks like the Mono project has a reflection and runtime compilation library. So, just make the "Generate"Object" function cross platform by dynamically finding the runtime compiler.
- If the generic type "typeof(T).ToString()" has nested generic types, my current code will break. FIX: make a function that will take a type and create a proper string representation of it for source code purposes.
- We still don’t have compiler errors for the generic mathematics. Say we have a custom type "struct Fraction128" and we forgot to code a "+" operator for that type. This will throw a runtime error. FIX: This issue can be fixed by writing a plugin to Visual Studio to also check that any type used in generic mathematics has the basic arithmetic operators during compilation. I’m not about to do this, but I’m just pointing out that it is possible. Until then, just don’t be stupid. 😛
By using runtime compilation, you can force the assumption that mathematics operators and value type conversions exist allowing you to do truly generic mathematics. It is fast, easy to maintain (compared to the other methods presented in this article), and very powerful.
This isn’t the end though... I already have several improvements in mind. If you have any sugguestions, I would love to hear them. Thanks!
Back when I wrote this article I did not yet know about the System.Linq.Expressions namespace. This namespace allows for much easier runtime compilation than the method I was using in the final example of the above article. Here is the new pattern I am currently using. It is much cleaner.
using System;
using System.Linq.Expressions;
using System.Numerics;
using static Towel.Syntax;
namespace Example
{
public class Program
{
static void Main(string[] args)
{
int a = Addition(1, 2);
float b = Addition(1.2f, 3.4f);
double c = Addition(1.23d, 4.56d);
decimal d = Addition(1.234m, 5.678m);
BigInteger e = Addition(new BigInteger(12345), new BigInteger(67890));
Console.WriteLine(a);
Console.WriteLine(b);
Console.WriteLine(c);
Console.WriteLine(d);
Console.WriteLine(e);
}
}
}
namespace Towel
{
public static class Syntax
{
public static T Addition<T>(T a, T b)
{
return AdditionImplementation<T>.Function(a, b);
}
internal static class AdditionImplementation<T>
{
internal static Func<T, T, T> Function = (T a, T b) =>
{
ParameterExpression A = Expression.Parameter(typeof(T));
ParameterExpression B = Expression.Parameter(typeof(T));
Expression BODY = Expression.Add(A, B);
Function = Expression.Lambda<Func<T, T, T>>(BODY, A, B).Compile();
return Function(a, b);
};
}
}
}This updated version of the code has been included in the https://github.com/ZacharyPatten/Towel repository. Check it out if you want to see more code like it.