CRTP and non-type generic parameters in C♯

N.B.

All code snippets in this entry are MIT-licensed;

The entry itself has all rights reserved; without written permission, you can reblog this entry by providing the link to this page;

You can jump directly to the code that implements non-type generic parameters.

Today I was writing code concerning applied crypto. Normally that kind of code should be written in C++. A major drawback is that there is hardly a unified choice of basic facilities including strings, streams, etc. I love the richness of the .NET library, or the ‘basic facilities provided by C♯’. So I temporarily moved to C♯, and will probably return to C++ later. And one more thing is that I am writing a protocol compiler, so I might well just stick to C♯ for implementing it, which outputs compiled protocols in C++. The above is basically the background of this entry.

A good old friend in crypto is finite prime fields, i.e., ${\mathbb{Z}}/{p\mathbb{Z}}$ for prime $p$ . This is easily implemented in C++ as shown below:

template <unsigned p>
struct Z
{
    unsigned value;
    /* other members (constructors,
     * operators, functions) omitted.
     */
};

template <typename TRing>
struct Foo
{
    /* Use TRing as a black-box ring
     * with operators +, - and *.
     */

    struct AffineTransform
    {
        TRing k, b;
        TRing operator () (TRing x) const
        {
            return k * x + b;
        }
    };

    static std::function<TRing(TRing)>
    CreateAffineTransform(TRing k, TRing b)
    {
        AffineTransform aff;
        aff.k = k;
        aff.b = b;
        return aff;
    }
};

/* ... */
std::cout << (unsigned)((Z<19>)1 / 5 + 2);

Here Foo is something (probably cryptographic or just your usual computational thing) built upon a ring, and the field structure can be used as a template parameter.

However, in C♯, generics are much more limited. For example, you cannot use operators on a generic type, nor can you declare the requirement that such operators are available. So Foo is not as simple as it is in C++.

An idiomatic way to solve this is to employ what I call the ‘IComparer pattern’. Another approach is to use the ‘IComparable pattern’, which is actually the celebrated curiously recurring template pattern often found in C++. Let’s take rings for example.

namespace Mathematics
{
    public interface IRing<T>
    {
        T Add(T other);
        T Multiply(T other);
        T Negate();
        T MakeRandom();
    }

    public struct Z19 : IRing<Z19>
    {
        // Implementation omitted.
    }

    // new T() must represent zero.
    public class Foo<T> where T : IRing<T>, new()
    {
        // Use T as a black-box ring.
        public static Func<T, T> CreateAffineTransform(T k, T b)
        {
            return x => k.Multiply(x).Add(b);
        }
    }
}

You might have noticed another painful pitfall here — since generics in C♯ do not take non-type values, we seem to have to write separate code for each prime field. There are two homely workarounds:

Use a text template to generate code for prime fields, and modify the template on-demand;
Embed the divisor as a field, and throw an InvalidOperationException if the two operands do not coincide.

The first method is not inherently C♯, and the second one increases the run-time cost and suddenly doubles the space required for each ring element.

The answer is to wrap values in types. The following general implementation provides efficient and unified facility.

namespace GenericHelpers
{
    public interface IGenericParameter<TValue>
    {
        TValue Value { get; }
    }

    public static class GenericParameter<TValue, TProvider>
        where TProvider : struct, IGenericParameter<TValue>
    {
        public static readonly TValue Value;

        static GenericParameter()
        {
            Value = default(TProvider).Value;
        }
    }
}

Then one consumes the utility by:

using GenericHelpers;

namespace Mathematics
{
    public interface IRing<T>
    {
        T Add(T other);
        T Multiply(T other);
        T Negate();
        T MakeRandom();
    }

    public struct Z<TMod> : IRing<Z<TMod>>
        where TMod : struct, IGenericParameter<uint>
    {
        public static readonly uint Modulo;

        static Z()
        {
            Modulo = GenericParameter<uint, TMod>.Value;
        }

        // Implementation omitted.
    }

    public class Foo<T> where T : IRing<T>, new()
    {
        // Use T as a black-box ring.
        public static Func<T, T> CreateAffineTransform(T k, T b)
        {
            return x => k.Multiply(x).Add(b);
        }
    }
}

Each time we need to supply a value of type TValue to some generic parameter, we implement a new structure TProvider implementing IGenericParameter<TValue>. It is clear that the Value property might even have different values across runs. However, one can always keep their life simple by sticking to the idiomatic usage.

using GenericHelpers;
using Mathematics;

namespace Usage
{
    public struct _19 : IGenericParameter<uint>
    {
        public uint Value { get { return 19; } }
    }

    static class Program
    {
        static void Main()
        {
            // Foo<Z<_19>>.CreateAffineTransform(...);
        }
    }
}

MIT license (code snippets)

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the ‘Software’), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED ‘AS IS’, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.