DEV Community: Patrick Kelly

C#'s Generic Math from F#

Patrick Kelly — Mon, 12 Dec 2022 11:40:00 +0000

At this rate I should just legally rename myself to the language bindings guy or something. Fourth year in a row and I've got more to talk about when it comes to .NET bindings. But hey, I'm not the only one this time! This year? The team introduced some goodies with .NET 7.0 and C# 11. Generic Math is one of particular interest for use from F#, because of how well it fits with how F# already works. Like everything Microsoft has developed however, it clearly was rushed and has some rough spots. We'll be exploring those, and how I've found for working around them.

Getting Started

I must really be milking this subject, right? You've read my last articles, you know how this is going to work. The generic math feature introduced with C# 11 and .NET 7.0 is just methods off generic interfaces. We can just call them directly like this:

let inline abs (value:^a) = ^a.Abs(value)

And that's it! I don't need to write another article on this again. Try it though. It fails. Miserably. The syntax analyzer will recognize the problem: this just isn't valid F#.

So what about this?

let inline abs (value:^a) = INumberBase< ^a>.Abs(value)

Not invalid syntax anymore, but this still won't compile. So how do we actually call this then? The trick is in a simplified form of what we've already done before:

public static T Abs<T>(this T value)
    where T : INumberBase<T> => T.Abs(value);

and

let inline abs (value) = Extensions.Abs(value)

This actually solves another problem as well, or, at least what I consider a problem: numerical functions from the Generic Math API have poor discoverability the way they were implemented. If you don't want extension methods on the C# side, just remove the this part; no other changes are necessary.

Cranking to 11

Okay, that was simple, just unexpected. Surely that's it, and I'm still just milking an article. Four years straight of this? Well... We're about to need to dive into the internals of the F# standard library and features that only exist inside of it. Yeah, this just went hard. The problem lies with a few of the Generic Math interfaces that are kinda already represented in F#, but not in the same way: operators. What do I mean? Let's look at how F# implements the operators:

let inline (+) (x: ^T) (y: ^U) : ^V = 
    AdditionDynamic<(^T),(^U),(^V)>  x y 
    when ^T : int32       and ^U : int32      = (# "add" x y : int32 #)
    when ^T : float       and ^U : float      = (# "add" x y : float #)
    when ^T : float32     and ^U : float32    = (# "add" x y : float32 #)
    when ^T : int64       and ^U : int64      = (# "add" x y : int64 #)
    when ^T : uint64      and ^U : uint64     = (# "add" x y : uint64 #)
    when ^T : uint32      and ^U : uint32     = (# "add" x y : uint32 #)
    when ^T : nativeint   and ^U : nativeint  = (# "add" x y : nativeint #)
    when ^T : unativeint  and ^U : unativeint = (# "add" x y : unativeint #)
    when ^T : int16       and ^U : int16      = (# "conv.i2" (# "add" x y : int32 #) : int16 #)
    when ^T : uint16      and ^U : uint16     = (# "conv.u2" (# "add" x y : uint32 #) : uint16 #)
    when ^T : char        and ^U : char       = (# "conv.u2" (# "add" x y : uint32 #) : char #)
    when ^T : sbyte       and ^U : sbyte      = (# "conv.i1" (# "add" x y : int32 #) : sbyte #)
    when ^T : byte        and ^U : byte       = (# "conv.u1" (# "add" x y : uint32 #) : byte #)
    when ^T : string      and ^U : string     = (# "" (String.Concat((# "" x : string #),(# "" y : string #))) : ^T #)
    when ^T : decimal     and ^U : decimal    = (# "" (Decimal.op_Addition((# "" x : decimal #),(# "" y : decimal #))) : ^V #)
    // According to the somewhat subtle rules of static optimizations,
    // this condition is used whenever ^T is resolved to a nominal type or witnesses are available
    when ^T : ^T = ((^T or ^U): (static member (+) : ^T * ^U -> ^V) (x,y))

If you've never seen (# #) blocks in F# before, congratulations, we're about to learn about something you can never use in your own code! This is a special feature only usable within the F# standard library, allowing for inline "IL" to be written. Kinda. It's mostly IL but there's some conveniences. We can't use this, but it is useful to understand what is going on in this method, to see what we can or can't do about it. If we want to include the Generic Math operators, this behavior has to be reimplemented in entirety. So let's break this down.

AdditionDynamic<(^T),(^U),(^V)>  x y

This is clearly some internal from the standard library, so, what does that look like?

let AdditionDynamic<'T1, 'T2, 'U> (x: 'T1) (y: 'T2) : 'U =
    if type3eq<'T1, 'T2, 'U, int32> then convPrim<_,'U> (# "add" (convPrim<_,int32> x) (convPrim<_,int32> y) : int32 #) 
    elif type3eq<'T1, 'T2, 'U, float> then convPrim<_,'U> (# "add" (convPrim<_,float> x) (convPrim<_,float> y) : float #) 
    elif type3eq<'T1, 'T2, 'U, float32> then convPrim<_,'U> (# "add" (convPrim<_,float32> x) (convPrim<_,float32> y) : float32 #) 
    elif type3eq<'T1, 'T2, 'U, int64> then convPrim<_,'U> (# "add" (convPrim<_,int64> x) (convPrim<_,int64> y) : int64 #) 
    elif type3eq<'T1, 'T2, 'U, uint64> then convPrim<_,'U> (# "add" (convPrim<_,uint64> x) (convPrim<_,uint64> y) : uint64 #) 
    elif type3eq<'T1, 'T2, 'U, uint32> then convPrim<_,'U> (# "add" (convPrim<_,uint32> x) (convPrim<_,uint32> y) : uint32 #) 
    elif type3eq<'T1, 'T2, 'U, nativeint> then convPrim<_,'U> (# "add" (convPrim<_,nativeint> x) (convPrim<_,nativeint> y) : nativeint #) 
    elif type3eq<'T1, 'T2, 'U, unativeint> then convPrim<_,'U> (# "add" (convPrim<_,unativeint> x) (convPrim<_,unativeint> y) : unativeint #) 
    elif type3eq<'T1, 'T2, 'U, int16> then convPrim<_,'U> (# "conv.i2" (# "add" (convPrim<_,int16> x) (convPrim<_,int16> y) : int32 #) : int16 #)
    elif type3eq<'T1, 'T2, 'U, uint16> then convPrim<_,'U> (# "conv.u2" (# "add" (convPrim<_,uint16> x) (convPrim<_,uint16> y) : uint32 #) : uint16 #)
    elif type3eq<'T1, 'T2, 'U, char> then convPrim<_,'U> (# "conv.u2" (# "add" (convPrim<_,char> x) (convPrim<_,char> y) : uint32 #) : char #)
    elif type3eq<'T1, 'T2, 'U, sbyte> then convPrim<_,'U> (# "conv.i1" (# "add" (convPrim<_,sbyte> x) (convPrim<_,sbyte> y) : int32 #) : sbyte #)
    elif type3eq<'T1, 'T2, 'U, byte> then convPrim<_,'U> (# "conv.u1" (# "add" (convPrim<_,byte> x) (convPrim<_,byte> y) : uint32 #) : byte #)
    elif type3eq<'T1, 'T2, 'U, string> then convPrim<_,'U> (String.Concat(convPrim<_,string> x, convPrim<_,string> y))
    elif type3eq<'T1, 'T2, 'U, decimal> then convPrim<_,'U> (Decimal.op_Addition(convPrim<_,decimal> x, convPrim<_,decimal> y))
    else BinaryOpDynamicImplTable<OpAdditionInfo, 'T1, 'T2, 'U>.Invoke "op_Addition" x y

Oh dear god, this is a mess, and it's still not even the entire thing, because there's that BinaryOpDynamicImplTable<OpAdditionInfo, 'T1, 'T2, 'U> type as well. However, we have everything we need to look at here, to see what behavior we need to provide. Going back to the (+) definition, let's look at one of the lines.

when ^T : int32       and ^U : int32      = (# "add" x y : int32 #)

This isn't too bad. When ^T and ^U, which are both input types, are both int32, do (# "add" x y : int32 #); just a simple add instruction. There's many more lines like this that you can interpret the same way. So let's look at one with a bit more going on.

when ^T : int16       and ^U : int16      =
    (# "conv.i2" (# "add" x y : int32 #) : int16 #)

You recognize the (# "add" x y : int32 #) part from before. Critically here though, you'll recognize the : int32 portion clashes with the int16 type of the parameters. However, if you're used to C#, you might recognize this is correct behavior. .NET adds smaller numbers as 32-bit numbers. You have to convert back if you want smaller numbers again. (# "conv.i2" is the instruction for converting the top of the stack to an i2, or a two-byte integer; in F# you know this as a 16-bit integer, or int16. And lastly : int16 #) is just a typemark, which we now know matches the i2 part of conv.

To summarize at this point, we've seen two behaviors. For numerics larger than 32-bits, they are added directly. For numerics smaller than 32-bits, they are upsized, added, and then converted back to their input size.

when ^T : string      and ^U : string     = (# ""
    (String.Concat((# "" x : string #),(# "" y : string #)))
    : ^T #)

There's parts of this that I could explain but won't. The critical part is something you've probably already figured out: when the input is two strings, concatenate them. We see this behavior in C# as well, and it's exactly the same.

This is now three different behaviors. Lovely.

when ^T : decimal     and ^U : decimal    = (# ""
    (Decimal.op_Addition((# "" x : decimal #),(# "" y : decimal #)))
    : ^V #)

Read this the same as the string one, and you can see that given two decimal, we're calling Decimal.op_Addition on them. This is the internal name for the addition operator, however your language presents it.

That leaves one last line in the main section:

when ^T : ^T = ((^T or ^U):
    (static member (+) : ^T * ^U -> ^V) (x,y))

And uhh... this is one I understand but don't understand, if you understand me. (static member (+) : ^T * ^U -> ^V) (x,y)) is something you've seen before if you've read my previous articles. We're calling op_Addition on the parameters. when ^T : ^T is the part I'm a little confused by. Not constraining ^T at all theoretically makes sense as a catch all, but considering I could never actually get this line of code to execute, I think they've made a mistake here. Regardless, the intention is for the standard + operator to fallback to any defined op_Addition that exists.

So what about the next block, the AdditionDynamic part? I'll let you read through that. It's another case where I understand but don't understand. It's basically a repeat of what we already covered, but is supposed to include behavior to automatically convert compatible types. If this sounds like something F# doesn't do, congratulations, you see why I'm confused.

So why do I say F#'s fallback addition doesn't work? Well, the reference project I have for writing this has the following definitions:

/// <inheritdoc/>
public static Percent<T> operator +(Percent<T> left, Percent<T> right) =>
    new(left.Value + right.Value);

/// <inheritdoc/>
public static T operator +(T left, Percent<T> right) =>
    left + right.Of(left);

The thing is, the ^T percent -> ^T percent -> ^T percent one works fine, it's the ^T -> ^T percent -> ^T one that doesn't. Looking back at the + definition, it should have caught this, so, what's going on here?

Let's review what necessary behaviors we're after:

Numerics greater than the working size of .NET (32-bit) can be added together directly and their results returned.
Numerics lesser than the working size of .NET (32-bit) must be converted to 32-bit numerics of compatible typeclass then added together, with their results converted back to the origin type.
Strings are concatenated together.
Any types with a defined op_Addition should have that used.

Is there another way we can get all this behavior? Well, yeah, actually. Let's start with this:

/// <summary>Adds two values together to compute their sum.</summary>
let inline ( + ) (left:^left) (right:^right):^result =
    ((^left or ^right) :
    (static member (+) : ^left -> ^right -> ^result)(left, right))

As you can probably tell, this is very similar to that catch-all line from the standard definition, although there's some differences. Funnily enough, this works in almost all of the cases we need it to. For 1, 3, and 4 of the requirements we laid out, this already works great. All of these tests will compile and pass fine:

Assert.Equal(2, 1 + 1)
Assert.Equal(2.0, 1.0 + 1.0)
Assert.Equal("hello!", "hello" + "!")
Assert.Equal(12.5, 10.0 + percent(25.0))

And that's pretty awesome, because there's wayyyyy less code on our end.

But what about requirement 2?

I'll leave this one to you to fix, as practice makes perfect and there's a lot to digest in this article. My tip is that the solution is something we covered right here in this article, but there's another way to solve it that comes from a prior article. As it stands now, adding numerics smaller than 32-bits adds fine, but returns a 32-bit numeric, which is standard behavior for .NET itself, C#, and VB. All that needs to be done is that in these cases, the return value be converted back to the origin type. In the rest of the cases, we're already got correct behavior.

If you've made it this far, the good news is that I've already done all the work in implementing both the base library and F# bindings for this.

Real World F# Interop

Patrick Kelly — Sat, 25 Dec 2021 11:12:24 +0000

For various reasons my past few years in development have involved a lot of language bindings, both reading up on others techniques and my own experimentation. I've written before about writing advanced bindings, and designing around bindings. However, these articles always used trivial examples. I've never talked before about the bindings I've written, why I used the techniques I did, and why I didn't use other approaches.

Today, that changes.

I have several libraries I maintain. For various reasons, several of these have been greatly simplified recently. The general idea is that each serves some domain, some with large amounts of custom methods and types, and others as simply large collections of extensions. Critically, some of these depend on another, and share method names. Because of this, use of a library that depends on another should extend the bindings. This can be a surprising challenge.

Numbersome

This is just a small convenience library meant to provide basic functionality more easily, and patch up some areas I needed to use often that weren't covered by larger math libraries. It also shows off something I couldn't until recently. Prior to this last .NET release (6.0) generic math was a problem to write, and was typically easier to write in F# and make C# bindings for instead. That's changed. Consider:

public static T Crd<T>(this T value) where T : IFloatingPoint<T> {
    T two = T.One + T.One;
    return two * T.Sin(value / two);
}

A simple Chord function. You don't see it much anymore, although it is useful at times, and often isn't used enough to remember one of the identities, so it's a suitable candidate. Luckily, this is easy, as we can write a very direct mapping.

let inline crd< ^t when ^t :> IFloatingPoint< ^t>> (value:^t) =
    value.Crd()

This is possible without more complex techniques precisely because there's only one method that this ever needs to bind to, and that method is sufficiently generic. The compiler doesn't need to be tricked; it just needs to be told what ^t is. An in doing so, this could be considered exactly identical to the C# signature. There's a method, a generic type constrained to a CRTP interface, a single parameter of that generic type, and a return of that type. If you have a single generic method that needs to be bound to, this is the least effort. Easy enough.

It won't be very obvious yet, but eventually it would become clear how operator overloading will become an issue. "Would" might have been overlooked, but I do mean past tense. There's numerous ways to address this, an in the past some of them were terrible. It's not that way anymore. Numbersome includes many definitions that work exactly like the standard F# operators and look like this:

let inline ( + ) (left:^a) (right:^b):^c =
    ((^a or ^b or ^c) :
     (static member op_Addition : ^a -> ^b -> ^c)(left, right))

This winds up only being a slight bit of complexity over the aforementioned binding. What we're saying here can be broken up into several parts. (^a or ^b or ^c) says the member constraint we're looking for can be found on any of the types: lefthand, righthand, or return. This forms a critical part of covering both preexisting types, and extending seamlessly to new types. (static member op_Addition tells the compiler we're binding to a static member, which all operators are, called op_Addition, which is the special name the compiled IL uses, that CLS Compliant languages understand as the + operator. ^a -> ^b -> ^c is, of course, the signature of the operator. By using different type definitions we can potentially have unique types in different parameters, but, of course, can all be unified to the same type like the standard F# operators. This yields more flexibility than the standard F# definition, which, yay.

Collectathon

Collectathon used to be a data structures library. Because of increasing demands on my personal life, I've decided to squash this down to the bare minimum required to get what I needed out of a good DS API. I've reworked things into a broad set of extension methods for the existing data structures. It's not quite the design I wanted, and imposes some trickier issues with method binding.

Consider Contains() which exists only for Span<T> and ReadOnlySpan<T>. Arguments can definitely be made about Memory<T>, how it should be conceptualized, what it should support, but arrays? Really? No one thought to include a method to check arrays for a value? Sure, the loop isn't hard to write, except that more efficient checks which use partial loop unrolling or vectorization are actually non-trivial, and clutter code. Implementing this was simple enough:

public static Boolean Contains<T>(this T[]? collection, T element)
    where T : IEquatable<T> =>
    MemoryExtensions.Contains(collection.AsSpan(), element);

But now we have a slight problem. This, and others, are in a different static class as the ones for Span<T> and ReadOnlySpan<T>. I wrote before about binding to multiple overloads when they're all in a single static class, so I won't cover that again. But as for multiple? It's doable, but it's a closed extension.

let inline Contains< ^t, ^u, ^a, ^b when (^t or ^u or ^a or ^b) :
    (static member Contains : ^a -> ^b -> Boolean)>
    collection element =
    ((^t or ^u or ^a or ^b) :
    (static member Contains : ^a -> ^b -> Boolean)
    (collection, element))

The only thing that's different about the overloading part is the additional ^u. The function signature looks like this:

let inline contains (collection:^a) (element:^b) =
    Contains<CollectathonExtensions, MemoryExtensions, ^a, ^b>
    collection element

This winds up working better than F# side binder types in this scenario. As long as new extensions are added to either of the declared static types it will automatically be available on the F# side as well. A method of the same name and compatible signature in another static class in a scoped namespace? That works in C# but not F#. At least not with this technique. I am looking for an open extension mechanism here, but for now, only closed sets.

Interestingly, this closed set technique does have quite a limitation when you take this further. Consider extending types in both System.Collections.Generic and System.Collections.Immutable. Say we add a Requeue method for both respective Queue types. This isn't an easy problem to solve, and one or the other will collide and cause problems. Of course, standard extension method calls are viable.

Stringier

A lot of this library is, from a binding standpoint, conceptually identical to the methods in Collectathon, only it additionally binds to its own overloads as well. This just means an extra static class parameter in each of the bindings, so this doesn't need to be covered.

However, those of you who know my work know this isn't all that needs to be addressed. And let me tell you, the work I've been doing on optimizations here caused some problems that weren't easy to address.

type pattern = Pattern

Please do this. It's self explainatory, but it does make things more pleasant on the F# side where types are often lowercase.

Pattern has many predefined patterns, especially for UNICODE Categories or Contributory Properties. Luckily, these are also very straightforward.

let letter = Pattern.Letter

Similarly, there's some factory functions defined there as well. These should not be mapped directly in my case, because of the overloading of textual types.

let inline blockComment (start:^a) (stop:^b) =
    BlockComment<Pattern, ^a, ^b> start stop

The overloading part looks exactly as you'd expect.

Now, while there are techniques for overloading in F#, it's not as advanced as you might expect, and different parameter counts must have different functions for them. This creates the following two functions:

let inline fuzzy (pattern:^a):pattern =
    Fuzzy<Pattern, ^a> pattern

let inline fuzzy2 (maxEdits:int) (pattern:^a):pattern =
    Fuzzy2<Pattern, ^a> pattern maxEdits

I want to bring up an important detail here, that even if I've brought up before, I want to hammer home. What we would call the "caller" in OOP is a (typically) implicit first parameter. However, in FP this parameter should instead be the last parameter, because when using function piping, the piped values are placed last. 2 as a suffix is a well understood convention, so downstream will generally understand it. Preferably however, use a clarifying suffix.

Pattern construction is where things start to go south.

let inline many (pattern:^a):pattern =
    Many<StringierPatternsExtensions, ^a> pattern

The modifiers are straight forwards, since (now) all of them are extension methods. This actually has an incredibly nice effect in that, unless the pattern is a single literal, every single part will implicitly convert. So what about the single literals? Pattern has constructors, but .NET doesn't like constraining on parameterized constructors. Well, F# doesn't care too much.

let inline ptn (pattern:^a):pattern =
    (^t : (new : ^a -> Pattern) pattern)

Yup. You can use this pretty easily inside of functions that need more complex logic. Essentially, this is the constructor, as long as it's only one parameter.

I used to call this p, taking after the FParsec pchar and pstring conventions, but I've decided more recently that's too vague. ptn seems to strike a good ballance between succinct and clear.

Now we get into problems. "Or", or alternates, is something a lot of parser engines struggle with how to create syntax for. FParsec went with <|>, it's own operator. Most just assume you're going to use the C# API. You can use || or ||| however, without creating issues, as long as you put it together with a few things we've covered earlier.

let inline ( || ) (left) (right) =
    Or<StringierPatternsExtensions, NumbersomeExtensions, _, _, _>
    left right

Yeah, I hid something from you earlier 😜 We still have the closed extension problem from earlier, but we can add behavior to an operator. Just know that if anyone else does this you start to have collisions. I'm including both of these because it depends on the symbol you overload.

public static Boolean Or(this Boolean left, Boolean right) =>
    left || right;

public static T Or<T>(this T left, T right)
    where T : IBitwiseOperators<T, T, T> =>
    left | right;

This allows the F# operator to still behave as expected, while also allowing a familiar "or" operator for pattern construction. I suppose you'd call me antagonistic towards idiomatic F#, and I suppose you'd be correct.

Now is where it all falls apart. Yeah. For many parts of this we're into undocumented and unintended abuse of language features to make this stuff work in extensible and low effort ways. But there be dragons.

let parse (source:^a) (location:byref<int>) (pattern:pattern):^b option

This is the signature I want. Unlike typical bindings, this is almost idiomatic F#. If I were to wrap up source and location into a record or something, it could be entirely idiomatic F#. Since the signature is so different, you run into issues, but I really do want to make this work. What I do know, is that a technique I've never covered here is useful. Sometimes you might not want to bind to the public API, but rather, recompose internal APIs into the same effect. Enter: InternalsVisibleToAttribute. When this is applied, it allows other assemblies to still access internal members.

let inline parse (source:^a) (location:byref<int>)
(pattern:pattern):^b option =
    let start:int = location
    match pattern.Head.Consume(
    source, &location, Unchecked.defaultof<StringComparison>) with
    | null -> Some(source[start..location])
    | _ -> None

This almost works. Almost. F# wants to resolve ^a to ReadOnlySpan<Char>. I think I can write an overloader for Consume and have this work, although the additional slicing has me unsure. If I manually declare ^a and ^b as String, it does work.

Alternatively, one of the F# side binder types may do the trick here.

Closing

I have, however, run out of time. I work 50 hours a week, and in school, and do this development on the side. As of yesterday (Dec 24th), this is as far as I've gotten in my own code.

Last time I had as a footnote the possibility of Haskell style Variadic Functions. As far as I can tell this "feature" isn't possible anymore. That's probably a good thing 😂 But it would have been a fun tool in the toolbox.

I do have a few things to track down. While playing with things, I think I found a mechanism by which it's possible to have a F# function overloaded on both instance and static members. This would have huge implications for certain areas, like where some types have instance methods but others only extension methods for the same features.

Pattern Combinators

Patrick Kelly — Sun, 20 Dec 2020 15:14:21 +0000

My conference talk on the theoretical model behind the parsing framework I developed.

Designing Around F# Interop

Patrick Kelly — Wed, 09 Dec 2020 13:36:01 +0000

Last year I wrote about Advanced F# Interop techniques. It was based on tackling the least ideal situation of language interop: A C# (or VB) library that was never designed with F# in mind. The techniques used were straight up abuse of the language, but were able to warp incredibly non-FP code into FP code.

I still want to cover these points, but I don't want C# and VB programmers thinking it's acceptable to never consider interop. There's techniques which make it easier to design C# and VB libraries while also making it easier to create the F# bindings. And yes, there's techniques for doing this the other way around as well, which I'll cover in time.

For almost two years now I've been developing and maintaining a set of libraries where cross language compatibility is a hard design requirement. Obviously, I want this to be effective while not requiring a ton of effort. This article covers my findings, and integrated contributions of others towards that goal. The hope is that this will help library authors support the entire .NET ecosystem with a better overall feel, because we're better together.

The Past

A quick primer on what was done in the past, if you hadn't read my previous article. I'll be carving it up, simplifying it immensely by the end of this.

I turned this:

let stack = DoubleStack()
let mutable result = ref 0.0
stack.Push(3.0)
stack.Push(5.0)
stack.Multiply(result)

into this:

let stack = 3.0 |=> 5.0 |> mul |=> 8.0 |> sub
Assert.Equal(7.0, peek stack)

mostly through this:

type Pipeline =
    static member Pipe(left:DoubleStack, right:float) =
        left.Push(right)
        left
    static member Pipe(left:float, right:float) =
        let result = DoubleStack()
        result.Push(left)
        result.Push(right)
        result

let inline private pipe< ^t, ^a when (^t or ^a) : (static member Pipe : ^a * float -> DoubleStack)> left right =
    ((^t or ^a) : (static member Pipe : ^a * float -> DoubleStack)(left, right))

let inline ( |=> )(left:^a)(right:float) = pipe<Pipeline, ^a> left right

I don't want to go deep into explaining because we're going to remove much of this, but:

|=> doesn't need to be an operator, I was just trying to be creative. Any F# function will work, and currying is recommended but not required. This tells the compiler it needs to resolve types at the callsite. pipe is what sets up the binding. It looks for, and then calls, a static Pipe() on either ^t or ^a. In |=> we've said that ^t is Pipeline, which is where Pipe() is declared. You can't specify only ^t, as multiple type parameters are required to "confuse" the compiler.

The end result is when the public function, |=> in this case, is compiled, the compiler attempts to resolve a Pipe() with a signature that matches the types at the callsite.

In a normal C# binding situation Pipe() would be calling C# methods, or pipe would be a member binding, not a static member binding. But as I said, we're going to design around simplifying this entire thing.

Traits

I've wrote previously on how C# does support traits and even added it as far back as C# 3.0. Borrowing a key definition from that article, we have:

Let's make sure we're all on the same page about what a trait is. This will also be useful in explaining why this approach works.
A trait is a specific feature of a type. A method it supports. A property. Whatever. It's just saying: "I have this thing".

On the C# side this is actually a little less than idea. It's limiting in that unlike a first-class trait system, there's no way in C# to add traits to existing types. Extension methods allow for adding a method with the same name and signature as it would have if there was first-class traits, but this is less than ideal.

F#'s functions have one of the more powerful and sophisticated generic constraint systems I've seen, only being bested by Ada. Because of this sophistication it's very easy to define trait-based functions in F#. In fact, you've certainly done this normally when writing F# functions, even without explicit constraints.

So what we're left with is using a trait-pattern in C# allows for a high degree of consistency in name and signature, which F# bindings need. But also inconsistency in whether those methods are instance or static members. That's a problem.

Null tollerance

Admittedly, I stumbled upon this completely unrelated to anything regarding F#, but quickly realized its application here as well. I try to avoid exceptions. They have their role, and I'll certainly use them before I start returning Int32 as an error code. But they are heavy. NullArgumentException and NullDereferenceException are particularly annoying ones for many. I happened to have many instances where a well defined action could be taken if the caller was null. But if instance methods always have an implicit caller, how do we check if that's null? This was always something that bugged me about C#, having also programmed extensively in Ada. Conceptually, I knew how to deal with this; I knew it shouldn't be anywhere near as big of a problem.

I worked out how, and wrote about it here. If you haven't read that entire article, the short version is roughly: if you want to know how many items are in a bag, and you don't even have a bag, how many items do you have? You don't get a NullDereferenceException irl, you have no items. So let's code for that by adding null-tollerance into extension methods, then calling the non-public instance methods. Cumbersome for many? Maybe. I figured it was most applicable for library authors, and only when well defined graceful action could be taken for a null caller. But it had unintentional side effects.

I could now provide default interface implementations and have them show up across every type with that trait, callable like normal instance methods.

And...

I just pushed all methods into static classes. F# functions had a fully consistent constraint to bind to.

Refined F# Bindings / Putting It All Together

Unlike before, I'm lifting these examples directly from the libraries I've mentioned, so you can see a real life applied case of this.

public interface IAddable<TElement> {
    void Add(TElement element);

    void Add(params TElement[] elements) {
        if (elements is null) {
            return;
        }
        foreach (TElement element in elements) {
            Add(element);
        }
    }

    void Add(Memory<TElement> elements) => Add(elements.Span);

    void Add(ReadOnlyMemory<TElement> elements) => Add(elements.Span);

    void Add(Span<TElement> elements) => Add((ReadOnlySpan<TElement>)elements);

    void Add(ReadOnlySpan<TElement> elements) {
        foreach (TElement element in elements) {
            Add(element);
        }
    }

    void Add<TEnumerator>(IEnumerable<TElement, TEnumerator> elements) where TEnumerator : IEnumerator<TElement> {
        if (elements is null) {
            return;
        }
        foreach (TElement element in elements) {
            Add(element);
        }
    }
}

Here we have a straightforward but featureful "trait". All an implementer needs to provide is an implementation of Add(TElement), and they get the {,ReadOnly}{Memory,Span}<TElement> and IEnumerable<TElement, TEnumerator> variants for free. Why is IEnumerable<> different? You can ignore that, it's a library specific thing; you want to use the one in System.Collections.Generic. Like mentioned before, on its own this really isn't useful, since you need to call these off the interface, which forces a very particular style that is problematic with such "anemic" interfaces.

public static partial class TraitExtensions {
    public static void Add<TElement>(this IAddable<TElement> collection, TElement element) {
        if (collection is null) {
            return;
        }
        collection.Add(element);
    }

    public static void Add<TElement>(this IAddable<TElement> collection, params TElement[] elements) {
        if (collection is null) {
            return;
        }
        collection.Add(elements);
    }

    public static void Add<TElement>(this IAddable<TElement> collection, Memory<TElement> elements) {
        if (collection is null) {
            return;
        }
        collection.Add(elements);
    }

    // And so on...
}

Whether Add() should do nothing with a null collection is debatable, of course. My thinking was similar to writing to /dev/null versus an actual file.

This is where four of the important things I had mentioned took place. We've now added graceful handling of null callers. We've now allowed the default interface implementations to be called off the implementing type, not just the interface. We've greatly reduced the amount of code in large code bases by providing single implementations of many things. And, if we need to add And() or whatever other method to a preexisting type, we can do that inside of this static class and have everything consistent for the F# side of things.

Lastly, the F# binding side is just this now:

module internal Bindings =
    let inline Add< ^t, ^a, ^b when (^t or ^a) : (static member Add : ^a * ^b -> unit)> collection elements = ((^t or ^a) : (static member Add : ^a * ^b -> unit)(collection, elements))

[<AutoOpen>]
module Functions =
    let inline add (elements) (collection) =
        Add<TraitExtensions, _, _> collection elements
        collection

This works like before, but I'm going to summarize again for those unfamiliar with the previous approach, and to be extra clear about how this interacts with the newer design.

You call add, which, due to being inline has its types resolved at the callsite. It, in turn, calls Add, which specifies TraitExtensions as a place to look for members, and says the other parameter types can be anything. Then, because an F# function is generally expected to return something other than unit, it returns the collection which can be further pipelined.

Add sets up the binding just like before. It says to look for a static member on ^t or ^a called Add, with the signature ^a * ^b -> unit. Because ^t is always TraitExtensions, then what is being said is specifically: Look on TraitExtensions and the type of collection for the static member: Add : ^a * ^b -> unit.

We now have a function, add (elements) (collection) which will work for any collection of IAddable<TElement>, and allow adding any of the overloads of elements defined in IAddable<TElement>.

No seriously. Here's examples lifted directly out of my F# unit tests.

let array = DynamicArray<Int32>(8n)

Assert.Equal(0n, array.Length)

array

|> add 1

|> ignore

Assert.Equal(1n, array.Length)

Assert.Equal(1, array.[0n])

array

|> add [| 2; 3; 4 |]

|> ignore

Assert.Equal(4n, array.Length)

Assert.Equal(1, array.[0n])

Assert.Equal(2, array.[1n])

Assert.Equal(3, array.[2n])

Assert.Equal(4, array.[3n])

Summary

Part of what I find brilliant about this solution is not only are the F# bindings easier to write, they're also easier to maintain. Previously, I struggled with ensuring there was strict 1:1 parity between them, but now that just happens every time I add new overload. While this approach would add work to very small libraries, it reduced the amount of code by roughly 11% (I'm not done some changes and don't have a precise number) without removing a single feature.

Would this be easier the other way around? Implement in F# and provide C#/VB bindings? I'm not sure, but it's something I'm very interested in and need to explore. Certain features F# was lacking kept me from trying this before, but with F# 5.0 I believe everything I need is now present. This, and some other things will be a topic for the future.

Now, let me be clear: this still isn't the most ideal situation. What I would love is for the C# team to provide ways to generate the same metadata F# uses. Things like being able to decare a C# static method has a curried form that F# can use without any bindings necessary. But with the current state of things, if you have to implement in C# and want to provide good functional and pipeline focused experiences for F# consumers, this seems to be one of the better ways to go about it.

Going Further

Just a few days before this article, I came across Gustavo Leon's experiment with Variadic Functions. I've come to expect flack from some of the more purist/fundamentalist members of the F# community, so I don't mind talking about this and even experimenting with whether it's useful in this context. Is it a "haskellism"? Yes. Is it potentially useful in this context? Yes. Should it be done in a pure F# context? Probably not. I'll report back later on whether F#-first/C#-bindings or variadic functions have uses in the context of multi-language libraries.

The (non) Monorepo Mistake

Patrick Kelly — Sat, 24 Oct 2020 19:28:47 +0000

I messed up and am paying the price for it. Hopefully, others can learn from my mistake. Everything I've been working on should have been in a monorepo, and I didn't do that.

I did the opposite.

Let me just get this out there right now. This is not going to be explaining why you should use a monorepo. There's a good chance you should not. This is why I should have. And even more specifically, why I should have for only one project. I have other projects that should stay discrete repos.

The benefits of monorepos are well documented. [1] [2] [3] [4]. So are the detriments. [1]

Since I didn't, let's go over why I didn't first, but then what I learned each time. Following along with Matt Kleins excellent article:

Theoretical monorepo benefits...

Easier collaboration...

I actually disagreed with this for much of the same reasons Klein disagrees with it. In fact, I still do. But I'd even go further to add that very large repos are intimidating to collaborators and increases the burden of onboarding. There's part of what I learned that shoots a hole straight through this argument though. Klein states "or to search through it using tools like grep ... must provide ... sophisticated source code indexing/searching/discovery capabilities as a service". Well, yeah, exactly! Any time I need to look through the .NET Core runtime, it's a huge PIA. It's hopeless to try to find your way and you have to rely on search tools. Break things apart and you can navigate manually far easier. So this is a good thing, right! The fallacy here is that discoverability is a function of modularity or lack-thereof, when it is in fact a function of the overall size of the code base. Breaking it apart introduced an even bigger problem. With code split across repo boundaries, search tools would fail. And you were still left with navigation problems just with a different level of abstraction. What was "what folder might this be in" was changed to "what repo might this be in". I didn't solve anything, I just traded some problems for others. The problems I had before were already solved by in-editor tooling, and are therefore preferable. Where he states "given that a developer will only access small portions .. is there any real different between checking out a small portion or checking out multiple repositories..."; I agree with this for the most part, this is more of a prodecural than functional thing and has little significant effect to ops. He further goes on to state "In terms of source code indexing/..." which is absolutely correct. However, this requires contributors to be familiar with an additional tool, and even worse, a tool that exists outside of the editor they are familiar with, to navigate your overall project. With the monorepo everything is searchable with the tooling you should already be familiar with, and, importantly, works the way you've gotten familiar with. You don't need additional tooling in this instance.

Single build...

No, he's entirely right here from my experiences. The build tools that work well for monorepos dgaf and work well for submoduling or other polyrepo styles. Furthermore, there's also techniques to pull off a single build pipeline of multiple discrete repos in various DevOps solutions. This purported benefit is highly dubious.

Code refactors...

He rightfully points out a fallacy but also falls prey to the fallacy of scale himself. I still question the efficacy of massive monorepos like Google does. However, in my case we're talking a small monorepo that's completely reasonable to check out the entire thing on a single machine.

But I'd also like to address a few points. "a developer can clone and edit the entire codebase ... how often does that actually happen?" In my case, actually quite often, as adding a new feature may potentially involve adding subfeatures in numerous locations. As I'm adding in a serialization framework right now, this involves adding files to Defender, Collectathon, and Philosoft, because the overall feature spans multiple scopes. And because serialization is useless without the ability to stream the serialized data, whether to disk or across the network, this necessary addition also needs to be added to the streams API I've written. Whether the core stream API remains in Stringier is still unknown, but regardless, this feature spans across the entire overall project. "They can give up, and work around the API issue...", I was actually doing this far more with things split up polyrepo style. As I merge things into the monorepo I'm finding numerous cases where I've done this and am syncing everything back up.

Unique monorepo downsides

Tight coupling...

He opens with "a monorepo encourages tight coupling", to which I can say, yes I believe this does. However that's why I'm trying to find a very careful boundary for this, because I have code that is very tightly coupled.

But tight coupling is bad!

Hol' up. Let me explain real quick what's going on here and we'll address this point again. Stringier, Collectathon, Defender, and others are part of an overall project where I'm developing a language runtime and standard library for a DSL I've needed. That language is being developed with cross-language compatibility in mind, and is part of why it's being developed with .NET languages, because of CLS compliance. A language runtime is inherently tightly coupled. This being said, reducing coupling is always a good thing, and I've been fighting to find various boundaries. Historically, Stringier was broken up into multiple subprojects but I've been undoing that. However, the aforementioned projects are hard boundaries that I've identified and have not struggled with since. This is why I can do things like write an article about using guard clauses and how Defender offers these, and not having to explain how this ties directly to or is dependent on other things. Because of modularity and CLS compliance, these components are available to other consumers like C# and F#.

So is coupling bad? Well, there's a sweet spot. I could potentially go through an insane amount of decoupling where each individual function is its own project with its own artifact that's published as a nuget package. But that's insane and imposes an inordinant amount of additional work on me. Some level of coupling enables efficient compatibility. Let's look at it this way: If a contractor built your house without any bolts or nails you'd be concerned, and "But coupling is bad and I've ensured everything is modular" would be anything but reassuring. But you can definately couple way too much as well. If you walked into your new home and your furniture was bolted to the floor, that would be equally concerning for entirely different reasons. There's an ideal amount of coupling that's important, and too much or too little is problematic in their own ways.

Klein then says, "If an organization wishes to create or easily consume OSS, using a polyrepo is required.". This one in particular bugs me. Scale might be important here, because I found the exact opposite. I shot myself in the foot by splitting things up. Where I originally thought I would be making things easier to navigate and discover, I actually trashed the amount of navigation to my repo. I can safely say trashed because as I merge things back into a single repo, I'm back up to the traffic numbers I was at before.

VCS scalability

"Scaling a single VCS to hundreds of developers, hundreds of millions lines of code, and a rapid rate of submissions is a monumental task.", completely agreed, although I'd add that scaling anything to that size is a monumental task.

Other arguments.

We're done with Kleins article and this has to do with other things I've read or heard that shaped my decision, to which I'm now backtracking on.

Dependencies

Okay, this is straight up bullshit right? Dependabot can keep polyrepo dependencies up to date no problem.

And it can. But that's missing a key thing. However, it's a key thing in my case that I've never heard about once. In the majority of cases, good use of Dependabot can completely avoid this purported claim.

So what's my case? Analyzers. I make extensive use of analyzers for code review. There's a lot of them that are suppressed, sure, either at the local level because of a specific exception, or at the project level because of disagreement with that specific analyzer. In any case, there's a justification for the suppression that goes along with it. In many of these cases, that justification is that the issue is complex and requires human review to adequately assess. The majority of analyzers still stand, diligently doing their job of helping me manage an absurdly large and still growing codebase for a single person. As I learn of more and more useful analyzers, I'd add them to the projects. With the polyrepo set up, these analyzers have to be added to each project within each repo. This is obviously less than ideal and meant the analyzers were out of sync. Not in that the version numbers were out of sync; no, Dependabot kept that in order. But rather, different projects were using different analyzers. Some are quick to jump on the fact that Visual Studio can install many of these analyzers as extensions and apply them to any project. This has several faults. Firstly, it assumes I use Visual Studio, which I do. Secondly, it assumes I only use Visual Studio, which I don't. Thirdly, it assumes I'm going to keep my extensions in sync across all my Visual Studio installs, which is just the exact same problem at a different level. How does the monorepo help in this instance? Directory.Build.props and Directory.Build.targets! These inject, at various times, properties to all projects within that directory. Put at the top level, it ensures every project is utilizing the same analyzer. This had other unintended benefits of course, such as being able to set properties for repo url, project url, copyright date, and others universally, also keeping those in sync.

Documentation

I never see this brought up, ever. Documentation is incredibly easier to deal with in the monorepo setting. Just add in a single project, remove the template sources you probably had, add in a docfx dependency, build it once to set up the scaffolding, and then configure it as appropriate. Now, every single build will build your docs, keeping them in sync. This might be a bit tedious for development purposes, so what I do is set the configuration to not build this in debug mode, and build it in release mode. Since I upload nuget packages in release mode, this ensures the docs are built and up-to-date on the releases.

As I mentioned, however, I've been merging everything into a monorepo. So I wasn't using a monorepo before. How'd I deal with docs?

Cries in DevOps

There was three repos dealing with documentation. One held articles, one held the built documentation, and one held the documentation project. There was a build pipeline that would check out the documentation project, clone the articles repo into it, clone the build documentation into it, clone all the actual projects into it, proceed to build the documentation, make a commit of the built documentation and then push that documentation. Note that this implicitly requires everything I mentioned for the monorepo case above.

I supposed this is a bit easier for me to see, since I'm wearing so many hats in this project. The monorepo isn't only about the developer. Documentation was immensely simpler and easier to keep in sync in the monorepo case.

Testing

Specifically I'm gonna talk about test coverage. It's easier to calculate and more correct in the coverage numbers when you have all the sources present. That's all.

Summary

In summary, this was the right decision for me, although I'm sure there'll be refinements as time goes on, just as there has already been. No project is the same, and it takes experience to determine what exactly works best for any given project.

Is this the right decision for you? Well, I'm nowhere near presumptuous enough to tell you what you should do. If my reasons make sense to you then maybe it is. If my reasons seem like I'm an idiot, then maybe I am, and maybe you shouldn't use a monorepo. These are my reasons, and I'm only explaining my reasons.

Avoiding Nulls with Extension Methods

Patrick Kelly — Wed, 14 Oct 2020 21:08:19 +0000

I've programmed in Ada more and longer than C#. Something that always bugged me about any .NET or really any heavily object-oriented language was how your rate of null-dereferences shoots through the roof. Considering how I can probably have no null dereferences in a non-trivial Ada program, it was particularly weird hearing .NET programmers complain about this so much, and as I used C# more, it annoyed me as well.

But the problem isn't the languages themselves; although this statement is very pedantic. Rather, it's a result of the design patterns those languages encourage.

Let's show off a little about how things are done, and the problem should start to become clear.

class Person {
    void Move();
}

Person p;
p.Move();

The problem is you didn't initialize p!

Yes, in this specific extremely trivial case, and in the most pedantic sense, that is the problem. The point is, how we're calling Move(). Say p was actually an iteration variable in a collection of people. You queried a database and got sent back an IEnumerable<Person>. Or, it could be a deserialized object, even though that should be throwing an exception, but hey, most serializers aren't written well. We're getting p somehow and code flow analysis alone can't say it's not null.

That's just the way it is, right? This is why null chaining exists. What I really should be doing is p?.Move(), obviously!

But this doesn't sit right with me. As a developer primarily writing other libraries, I try to make the callsites as easy and error-proof as possible. Forgetting to use ?. instead of . is just too easy. It's not easy to grep the problem. And putting ?. everywhere is actually problematic for its own reasons.

But that's just the way it is, right? No!

type Person is tagged null record; --fieldless "class"

procedure Move(Self : in out Person);

p : Person;
p.Move; --object.Method() style
Move(p); --Procedure(object) style

Neither of these will throw a null dereference exception!

Now a huge part of this has to do with language semantics. Ada initializes all objects upon declaration even without an explicit declaration, although analyzers will generally report this with a warning or error still. Obviously we can't change C# semantics. So while this is great, we can't do much about this.

There's a solution and good lord is it obtuse. If you're cranking out products for clients then this isn't going to be the least bit useful for you. But if you're a library author this may be of interest.

Notice one thing about Ada's function/procedure declaration. Even if it's dispatching off a type, we're still explicitly declaring that parameter. Do we have something like this in C#? Yes! The extension method. So let's try this again.

class Person {
    void Move();
}

static class Operations {
    static void Move(this Person person) => person.Move();
}

Person p;
p.Move(); //This is still Person.Move, not Operations.Move

Uh oh. Problem is, instance methods are preferentially resolved; they are checked before extension methods. We could using static Operations and call with Move(p) everywhere, but that's very anti-C#. There's a solution though, and it's a simple visibility change.

class Person {
    internal void Move();
}

static class Operations {
    static void Move(this Person person) => person.Move();
}

Person p;
p.Move(); //This is Operations.Move now!

Fantastic. Although we're only redirecting a call at this point. We'll still get a null dereference exception. How do we gracefully handle null?

That's not actually a joke. There's a simple calculus to explain this, and it's so simple I don't even need to get all theoretical, just a bit metaphysical.

If we move nothing, what happens? Well, nothing happens. What is null? A pointer/reference to nothing. So an operation upon nothing does nothing. We can codify this like so:

static void Move(this Person person) {
    if (person is null) {
        return;
    }
    person.Move();
}

Now a call to p.Move() will either move p as described by Person.Move() or will do nothing.

If you have a return type, it's a little different. But the same line of metaphysical thinking reveals the answers. If you're counting occurrences of something in a collection, and the collection is empty, how many occurrences are there? Well, 0, obviously. More tangibly, if you're counting the amount of apples you have in a bag, and the bag is empty, how many apples are there? 0. If you're counting the amount of apples in a bag, and you don't have the bag, how many apples are there in the bag you don't have. 0. Remember, it's a bag that doesn't exist, not a bag that you don't own.

Do I see this as useful for most people? No absolutely not. More than anything, this is a neat curiosity. But it's certainly something for library authors to keep in mind. I can definitely see this being interesting for things which focus very highly on usability, as this helps avoid many cases of errors. But do note that not every method should be "null proof" like this. There are methods which absolutely should be called off the instance itself and need to throw a null dereference exception as part of their semantics. This is just a neat tool for those looking to increasingly harden their API's.

Functional Collections

Patrick Kelly — Sun, 11 Oct 2020 17:47:51 +0000

Next up in Collectathon is something I've seen quite a large amount of programmers express a desire for, although I didn't quite implement it to the extent they express. I'll explain why as I explain what this is.

Functional Programming is a small but very vocal and influential paradigm. I'll admit, I have mixed feelings about it. It's rife with performance problems, and puts the burden of knowledge on the downstream programmer which I consider an unreasonably UX. I feel like it's the wrong level of abstraction in most cases, with either declarative or imperative being more suitable. But it does have some fantastic parts, and it'd be great to incorporate them. Of especial interest here is higher-order functions. Collectathon offers these.

Most collections are enumerable, the ones that aren't implement IContainable<TElement>, and in many cases, both are true. No matter what, this means that a collection has a Contains() method supplied from somewhere. Every collections library out there supports testing if a collection contains a specific element. That's simple and straightforward. I don't think a collections library would be very usable without it. But what about whether a collection has any elements that meet some specific criteria? Collections are generic, far too generic for a declarative API to be possible. This is Functional Programming's ideal niche!

DoublyLinkedList<Int32> list = DoublyLinkedList<Int32>() { 2, 4, 6, 8 };
Assert.True(list.Contains(IsPrime)); // Assuming IsPrime() exists

This example is a bit contrived, but it can be especially useful. Consider seeing if a collection of customers has any customers of a specific geographic region.

In fact, any method where accepting a predicate makes sense should have an overload that accepts a predicate. Methods like IndexOf(), Occurrences(), Remove(), and Replace() already have higher-order variants defined.

Functional Programming also defines some well understood conventional functions as well though, and Collectathon intends to support these in their entirety. Currently defined are functions like Map():

DynamicArray<Int32> array = new Int32[] { 1, 2, 3, 4, 5 };
array.Map<Int32, DynamicArray<Int32>>((x) => x * 2);
Assert.Equal<Int32>(new Int32[] { 2, 4, 6, 8, 10 }, array);

It works! I'm not happy about the callsite in C#. It's ugly and there's no other way to put that. I'm still looking into options to get that to resolve without being explicitly told what the types are. Maybe Map() must be supported via its own trait rather than implemented with existing traits (It currently requires ICountable and IIndexable<Int64, TElement>).

However, this is a fantastic opportunity to bring up what I've been doing for the people most likely to be using a functional paradigm anyways: F# bindings!

That same operation in F# looks like this:

let array = DynamicArray<Int32>(8)
            |> add [| 1; 2; 3; 4; 5 |]
            |> map (fun (x) -> x * 2)
Assert.Equal([| 2; 4; 6; 8; 10 |], array)

No explicit types! Which makes total sense as F# is meant for this kinda stuff. And these F# functions aren't their own implementations; they are the existing definitions, just with a little marshalling as appropriate.

let inline Add< ^t, ^a, ^b when (^t or ^a)
    : (static member Add : ^a * ^b -> unit)> collection element =
    ((^t or ^a) : (static member Add : ^a * ^b -> unit 
    (collection, element))

let inline add (element) (collection) =
        Add<Collection, _, _> collection element
        collection

let inline map (func) (collection) =
        Collection.Map(collection, Func<_, _>(func))
        collection

Similarly, Fold() is supported right now, but FoldLeft() and FoldRight() aren't. How does that work? Well, Fold() requires the delegate to be a magma, while the other two require left-associative or right-associative respectively. The most common case of folding is the magma fold, so it made sense to implement this first.

let array = DynamicArray<Int32>(8)
            |> add [| 1; 2; 3; 4; 5 |]
let sum = array |> fold (fun (a)(b) -> a + b) 0
Assert.Equal(15, sum)

There's still that nagging part of me that wants this to be declarative even though that requires an exponential amount of work. A single magma Fold() can support all kinds of operations, whereas a declarative Sum() only works for the single numeric type for which it was defined. It does conveniently express intent better, and not require the downstream programmer to know what the delegates identity is (0 for addition). In some cases, determining identity is remarkably difficult. But I'm glad this exists. This is a hugely powerful, and to reiterate, appropriate for this level of abstraction.

Consider all this another tool in the toolbox Collectathon provides.

Proper Sets

Patrick Kelly — Tue, 06 Oct 2020 15:09:42 +0000

A while ago I wrote about how ISet<T> should be considered harmful. While criticisms are absolutely valid, it's even better if I can show a better solution that avoids these problems.

Enter Set<TElement>. I'm still not 100% sure on the public API, and this whole project is still in beta anyways, so if you've got a better idea on how to do something I show off, please let me know so I can look into it.

First off, there is no interface. Rather, this is an abstract type from which you can derive, but has internal derivations within the library that you can't directly access but will wind up working with. I promise this makes sense in practice.

Instead of the typical way I see sets implemented, this isn't a mutable data structure. Rather, what elements it starts with are there forever. Instead, you build up more complex sets through set algebra, which has well defined axioms, and identities that can be utilized. But let's cover the most basic sets first.

readonly Set<Int32> smallPrimes = Set.From(2, 3, 5, 7);

At this point, smallPrimes cannot change, both in that the instance isn't mutable, and the reference is readonly. Testing for existence within a set is simple and obvious.

Assert.True(smallPrimes.Contains(5));
Assert.False(smallPrimes.Contains(6));
Assert.False(smallPrimes.Contains(11));

But there's another type of simple set that we should cover! Consider how, with ISet<T> one would define a set of all even or odd numbers, or even just all numbers! The standard set of even numbers for a 32-bit integer would use up 8,589,934,588 bytes of memory! I don't know about you but I don't have a computer than can use that approach. I'm not Microsoft with millions of dollars spent on server farms and distributed computing technologies to allow for that. Maybe that's why they weren't concerned about it? 🤔

readonly Set<Int32> evens = Set.From((x) => x % 2 == 0);

Congratulations, you now have a set of all even numbers, and it doesn't explode your computer!

Let's also consider the following sets:

readonly Set<Int32> odds = Set.From((x) => x % 2 != 0);
readonly Set<Int32> positive = Set.From(x) => x > 0);
readonly Set<Int32> negative = Set.From(x) => x < 0);
readonly Set<Int32> empty = Set.Empty<Int32>();
readonly Set<Int32> universe = Set.Universe<Int32>();

The empty set is obvious: it's a set with no elements. The universe isn't so obvious, but it's the compliment of the empty set: it's a set with all elements.

That's right, we've defined sets for every single number, every single even number, and every single odd number, all in single lines of code.

Remember how in algebra class there were identities? These were typically 0 or 1, like how x/x = 1 or x-x = 0 or x+0 = x. They are extremely useful for math overall, and the centuries without identities and 0 especially were rife with problems. Well, in set algebra the empty set and universe set are those identities. Trying to do set algebra without these identities is like trying to do abstract algebra (the stuff you learned in school) without 0 and 1. You're gonna have a bad time!

So let's use these in some simple algebraic operations.

readonly Set<Int32> positiveEvens = positive & evens;

Here, we just did the intersection between all positive numbers and all even numbers. Any negative numbers, even or odd, will not test true for existence, even though one of the constituent sets would.

There's a useful way to understand the operators used for this: what operator would you use for testing existence in two arrays? In this case, you loop through the "positive array" and loop through the "even array", and only if it's in both, is it part of the set.

readonly Set<Int32> oddsWithoutSmallPrimes = odds - smallPrimes;

Here, we just did the difference between the set of odd numbers and the set of all small prime numbers. So you don't have to scroll up, smallPrimes was defined as [2, 3, 5, 7]. Taking 2 out of all odd numbers doesn't do anything, because it was never in there to begin with. Taking the rest out makes then test false instead.

Assert.True(oddsWithoutSmallPrimes.Contains(1));
Assert.False(oddsWithoutSmallPrimes.Contains(2));
Assert.False(oddsWithoutSmallPrimes.Contains(3));
Assert.False(oddsWithoutSmallPrimes.Contains(5));
Assert.False(oddsWithoutSmallPrimes.Contains(7));
Assert.True(oddsWithoutSmallPrimes.Contains(9));
Assert.True(oddsWithoutSmallPrimes.Contains(11));

Hopefully this makes sense.

Overall, the following set operations have been defined with the corresponding C# operators.

C#	Set Operation
-	Difference
!	Complement
&	Intersection
^	Disjunction
\|	Union

Again, every operator was chosen to correspond with the equivalent logical operator that would be performed if testing these yourself. Except - of course, where that's the difference just like in abstract algebra.

So how does all this work? Through expression trees. It's worth pointing out that this has nothing to do with the LINQ expression trees. Rather, this is an actual data structure, itself a type of multiway tree. Any literal set is not modified, but set operators build up a tree representing the expression as you wrote it, and return that tree as a new set. This seems expensive at first, but remember how much memory using a delegate to describe the set saves? Expression trees can actually yield even more savings, although only above very simple usage. Because each set is immutable, we can freely reuse them across sets, which means arbitrary composition of sets reuses existing instances, saving even more memory. Fantastic.

Now what about cases where you want a list or tree or whatever, of unique elements. If the element is already in the collection, it shouldn't be added again. Well I got news for you. That's not a set. That's a unique whatever-the-base-collection-was, which is its own concept. Combining the two is a huge part of why the ISet<T> abstraction is so convoluted and irregular.

Linked Lists

Patrick Kelly — Thu, 01 Oct 2020 12:02:22 +0000

Last time, we covered variations of advanced arrays. I mentioned ways of achieving degrees of flexibility, but also mentioned there were some strong limitations. When you need even more flexibility, but your data still looks like an array, you need linked lists.

As a quick aside, some people will be quick to bring up binary trees for this because "faster indexing", and while that's true in the most naive cases, it's only true in the most naive cases. We'll get to that.

`SinglyLinkedList<TElement>` and `SinglyLinkedList<TIndex, TElement>`

Just like with the arrays, we have both a standard and associative variant. This time, however, we don't have an array, even though the overall API is extremely similar. Collectathon even utilizes an approach to ensure what APIs are implemented are exactly identical. So what's these links and why is it single?

Linkage

One of the most common strategies for implementing dynamic data structures is linkage of nodes, and, in fact, you can create nearly any structure with this approach. The idea is, you have nodes that hold an element in the collection, but that also hold pointers or references to other nodes. What's a node?

Nodes

Nodes are aggregate data structures, like struct or class with fields for elements and fields for links. In the most basic sense, a node will contain a single element, but it doesn't always have to be this way. The amount of links and the direction of them are completely arbitrary.

How it works?

Let's start with an empty list, since we can feasibly do that now, and build up a small list.

SinglyLinkedList<Int32> list = new SinglyLinkedList<Int32>();
// List is now: []
list.Add(2);
// List is now: [2]
list.Add(4,5,6);
// List is now [2,4,5,6]
list.Insert(1,3);
// List is now [2,3,4,5,6]
list.Map((x) => x - 1);
// List is now [1,2,3,4,5]

Every time we added a new node, regardless of how we did it, we did several things under the hood. First, since this is .NET we're talking about, all these live on the heap, so there's heap allocations associated with each. Second is, regardless of where the data is stored, each value has a hidden extra cost: the links. While the singly-linked list is the most compact simple list, each node holds a reference to the next node. This means that at the end of just a few operations, our list is using up 480 bits of memory on a 64-bit computer, while the array would only be using up 160 bits. Actually, I lied. It's worse than you probably thought. Because we can't create the nodes through unmanaged structs, each node has a tag that also uses up memory, although the amount is hard to determine. On top of that, the 480 bits was only how much the nodes used up, because the list object is also going to use up space! Not only for its own tag, but also an additional 192 bits for two references and a counter. That sounds horrible but hold on. When I was explaining arrays I said that the allocate-copy-swap-deallocate resizing technique that dynamic arrays use was extremely expensive. That's what lists address. If you're doing a lot of resizing, which is quite common, linked lists are the preferrable data structure. Singly-linked lists are an attempt at compromising on this, because they use less memory than their more commonly used counterpart, at the expense of a feature that's easier to explain when explaining the counterpart.

`DoublyLinkedList<TElement>` and `DoublyLinkedList<TIndex, TElement>`

Double-linkage addresses a shortcoming of single-linkage that doesn't effect everyone, but if it effects you there's no effective way around it. While a single link points to the next node, how do you move back? Double-linkage adds an additional pointer or reference for moving backwards. Doubly-linked lists don't offer much more additional functionality. Other than the possibility of a reverse enumerator, the reverse links only help optimize certain operations and even then only in certain situations. But you pay for it. In our example of just 5 elements, the doubly-linked list would consume 800 bits, not including the overhead of tags on the nodes, nor the list object.

Now I don't mean this as an attack on doubly-linked lists. In fact, I would recommend that you start your development with them, and only switch off after getting a stable library/application. Switch to what? Well that's why you wait. You need to understand what operations you're using, as well as profiling/benchmarking various things to make the appropriate call. Doubly-linked lists offer the overall best compromise across every factor. But they aren't the end-all-be-all. There's actually several techniques rarely seen in collections libraries for addressing this. Why? Laziness is my guess. They aren't new research in most cases.

Partial Unrolling

Arrays offer exceptional performance in most situations with either inflexibility or catastrophic performance for only one operation. Simple linked lists offer great flexibility at the cost of high memory usage and reduced performance, both in real and asymptotic time. Wouldn't it be nice if we could combine them? If only.

Unrolling lists bam straight off the presses, new research, people haven't had time to implement it yet, published in the recent... 1994. 1994! I seriously have never seen an implementation of the partially unrolled linked list in my life. I'm aware of two companies that had implemented them internally for certain products, but that's it. Even trying to scan Nuget for an implementation led me a dozen pages in without finding one.

As of this writing I do provide UnrolledLinkedList<TElement> but not its associative variant. There are currently some implementation problems, even though it passes the tests. It's still in beta, but it does exist.

Partial-unrolling works off the idea that... yeah, let's just straight up combine them. In Collectathon this is accomplished by creating a special node called a chunk, which is derived from BoundedArray<TElement>. This is also why we're covering these in a build-up way: the whole library is built up. When a chunk is still below a certain capacity, elements are added to the list just like they would be to an array. When the chunk grows above a certain capacity, a new chunk is allocated, linked together, and the elements are added to that one now. Essentially, it's the DynamicArray<TElement> only we're using up a tiny bit of extra memory to avoid the dreaded allocate-copy-swap-deallocate resizing technique. Do keep in mind though, that depending on what operations are occurring, the list may be constructed with a lot of empty spots in the arrays. If the chunk size is 32 slots, and we're using Int32 again, this means each chunk uses up 1024 bits before even factoring in links and tags. While partial-unrolling is a great optimization, it's potentially vulnerable to the same memory waste problem that shies developers away from arrays in the first place. Also, partial-unrolling offers a neat optimization for rapid indexing that we should talk about now.

Indexing

All linked lists are not random access collections anymore. Random access requires contiguous storage, and links add flexibility at the expense of contiguous storage. For simple lists, this means traversal through the list requires dereferencing a pointer just to move to each next node. While this should be handled for you by an iterator/enumerator/cursor, it's still happening, and you pay for that. This also means that moving to the 500th element requires dereferencing every pointer up to that point. That's a lot! For this reason, various techniques including but not limited to partial-unrolling have been developed to speed this up. With partial unrolling, random access is now possible inside of the chunk, and moving to the next chunk advances the equivalent of the chunk size in pointer dereferences as a single dereference. For a chunk size of 32, this means moving to the 500th element in 15 dereferences instead of 500. Much faster!.

Skip Lists

Another strategy for optimizing linked lists is the skip list. As far as I can tell, this first showed up with Skip lists: a probabilistic alternative to balanced trees back in 1990. This thing is as old as I am, and similarly to partial-unrolling I never seem to see it anywhere.

I haven't implemented this one yet, but I need it, so it's happening.

Skip lists work off the idea that you're still going to hold one element per node, but you are now going to have additional linkage in the nodes. Unlike what was done for the doubly-linked list however, these linkages all point in the same direction. Instead what we're now doing is linking ahead more than 1 element. This is the skip. We're skipping x elements ahead. Exactly how this is done is up for the implementer to decide. You could keep track of the skip amount inside the node. You could keep it a fixed amount and update it with every operation that effects it. There's assorted options, but it always skips ahead. This offers superior indexing capabilities compared to simple lists, while also not introducing the possibility of unused space like with partial-unrolling. However, you do pay for those extra linkages. As always, benchmark/profile before making decisions, but from my experiences I generally switch to a skip-list when working with lists above a certain large size.

Jump lists

Not to be confused with the jump list feature introduced with Windows 7!

A jump list is a list with two internal lists, because yo dawg I heard you like lists, so I got lists for your lists. (I'm gonna go end my life now for saying that)

Seriously though, that's what it is. The idea is that you have two simple lists inside of the jump list. One list is the actual linked elements. The other is the true jump list. This list doesn't hold elements. Rather, its element is actually just another reference to a node. Only this time around, the node reference isn't a reference to a node in itself, but rather the other list. To facilitate knowing where you even are, this needs to additionally store either an index, or a skip amount similar to the skip list. In either case, it's another approach to rapid indexing.

As far as I can tell, I independently arrived to this solution back in 2013. If you've got research showing otherwise, please send it my way.

S-Lists

Gonna be straight up. I discovered this one about 5 minutes before starting this article so I really don't feel comfortable talking about it just yet. It was published as The S-Linked List – A Variant Of The Linked List Data Structure and seems to be useful for embedded scenarios.

Advanced Arrays

Patrick Kelly — Sun, 27 Sep 2020 13:14:23 +0000

Liquid syntax error: 'raw' tag was never closed

Collectathon

Patrick Kelly — Sat, 26 Sep 2020 12:25:12 +0000

Typically, when I talk about work I'm doing, I talk about Stringier because I mostly deal with text processing now, and that set of libraries serves the foundation for a lot of the work I do. Over the two years of developing Stringier, I've been increasingly implementing specialized data structures, or even just data structures that I think should be in the standard library, but aren't. Sometimes, there's even the issue of the implementations just being bad, whether problematic API's or just less efficient or performant than they could be. Whenever you're doing a lot of the same thing, you've got a pattern, and you want to start looking into frameworks that aide with that pattern.

So is there a framework for collections? Not really. .NET has CollectionBase that makes all sorts of assumptions about how your collection works and what features it supports. It's a leaky abstraction that forces your collection to behave how it says, and that's just not realistic. This may be a major factor behind why .NET doesn't have a rich tree or graph API. It may even be behind the issues with ISet<T>. There's also C5, which isn't a bad option, but I think falls into many of the same traps that collections libraries fall into (and I've fallen for in the past, let's learn from my mistakes).

This is where I starting thinking about Collectathon again. Collectathon was originally an attempt at designing a better collections API based on separation of Abstract Data Type and Data Structure, as well as dependency injecting certain features that were implicit whether you wanted or could even use them, like filters. There was a major goal of trying to get as much code sharing as possible, and for a while was successful at this. But then I hit a wall. A hard wall. And this was the wake up I needed, and the eureka on why all collection libraries seem to have the same fundamental issue: They all make assumptions about collections that have nothing to do with that ADT because they all derive from the same core types, which by their very nature make those exact assumptions. See, collections don't form a taxonomy. One only needs to try to implement an unsorted list, self-sorting list, and unique list ("set") from the same base type to see the issue.

It wasn't until deep into the v4.0 audit and rollout of Stringier that the solution hit me, and it hit me like a swift kick in the ass that's been allowing me to quite literally pump out several efficient collection implementations a day, even though they are drastically different ADT's, without leaking implementing details (in fact, as of this writing, IResizable is the only abstraction leak). It turns out, my discovery of real traits in C# was critical for doing this, allowing moving sharable code outside of the types entirely, so that the hierarchy could be squashed, with no actual base type at all. In fact, the only hierarchies at all are within specific ADTs and even then they get broken when appropriate. But none of this is obvious using the trait based API.

What all this means is that Collectathon is two things. First, is a framework for the creation of custom collections. Second, is implementations of various collections using that framework. So, not only is it easier to provide generic collections within Collectathon, but it's also easier to provide specialized collections within Stringier. Fantastic! This, by implication, means that development on Collectathon is development on Stringier, especially since the end goal is to simplify Stringier immensely.

Since the work on Stringier is going to take quite a while, and most of the functions I'd like to talk about are in Core which requires the most work, I really can't talk about them yet. But, what I can do is talk about data structures as I implement them. This isn't just a "hey here's some basic data structures I learned about in a 30 minute data structures video" kinda series though. No. I'm gonna talk about thinks like what partial-unrolling means to a linked-list. How skip-lists can be superior to binary-trees when you know you have ordered data. What a trie or in-tree is. How a proper set is implemented and works. And more!

ISet Considered Harmful

Patrick Kelly — Thu, 24 Sep 2020 17:03:37 +0000

ISet<T> is a disaster waiting to happen, should be considered a code smell, and considered harmful. But why?

Nanos gigantum humeris insidentes

If I have seen further it is by standing on the shoulders of Giants. -- Isaac Newton

I say with Didacus Stella, a dwarf standing on the shoulders of a giant may see farther than a giant himself. -- Diego de Estella

If we reuse an existing idea, we can build upon the entire corpus of knowlege built upon it. We can stand on giants, and see further.

So is there an existing idea and corpus we can stand upon? Yes, and it's Set Theory and Set Algebra. In reusing these ideas, we can build upon ever pitfall, every mistake, every advancement, and every solution people before us have found. Does ISet<T> do this? No.

Where `ISet<T>` goes wrong

Before anything else, I should probably clarify what a set is. A set is a collection where each element only exists once, and does not care about the order of the elements, nor how the internals are structured. It only cares about what is in the set. Evaluating against this alone, ISet<T> seems fine. But this isn't the whole picture.

Sets are inherently immutable. Consider the set of all even numbers. There's no reason to add a new number to the set, for the set always contained all even numbers. So why does ISet<T> provide Add()? Is this problematic? Consider:

ISet<Int32> evens = new HashSet<Int32>(new Int32[] { 2, 4, 6, 8...});
Assert.False(evens.Contains(1)); // passes
_ = evens.Add(1);
Assert.False(evens.Contains(1)); // fails

Whoa, wait, why is this allowable? We just violated the semantics of the set!

But this isn't the only place where we can violate set semantics. Oh no.

ISet<Color> primaryColors = new HashSet<Color>(new Color[] { Color.Red, Color.Yellow, Color.Blue });
ISet<Color> printerColors = new HashSet<Color>(new Color[] { Color.Cyan, Color.Magenta, Color.Yellow, Color.Black });
primaryColors.UnionWith(printerColors);
Assert.False(primaryColors.Contains(Color.Magenta)) // fails

Magenta isn't a primary color! Why did this happen? One only needs to look at the signature and summary of UnionWith() to see why.

public void UnionWith(IEnumerable<T> other);

Modifies the current set so that it contains all elements that are present in the current set, in the specified collection, or in both.

This isn't even the end of the story though. Set Algebra, much like the Abstract Algebra you're familiar with from Algebraic Number Theory has the concept of identities that are very important for its operation. These are empty set (Ø) and universe set (U). Trying to do set algebra without identities is like trying to do abstract algebra without 0 and 1!

Furthermore, ISet<T> is a leaky abstraction, and this isn't just a case of a code smell where it makes it difficult to do refactorings later on, although that is a problem in and of itself. Because of the implementation details leaking through, we know ISet<T> is a collection like any other. What's wrong with that? The problem is immediately apparent with the compliment operation. Consider the compliment of all primary colors. This is a set that has to contain every color that is not one of the three primary colors. You're guaranteed to run out of memory! There's infinite colors! Even if we were to just go with 24-bit colors that computers can represent, even though some advanced color spaces use even larger amounts, this means allocating 16,777,216 - 3 color structures, at 32-bits each, for 536,870,816 bits or 67,108,852 bytes of memory! I don't know about you, but I don't have a computer that can hold that.

What `ISet<T>` should be

ISet<T>'s problems stem from deriving from ICollection<T> which itself is problematic because it makes incorrect assumptions about what is common amongst all collections. Sets are only one of the areas where those assumptions are violated.

Instead, sets should adhere as closely to the established Set Theory and Set Algebra as possible. This not only ensures that basic semantics of a set are as they should be, but also that discovered and published solutions which utilize Set Theory and Set Algebra can be readily adopted by programmers facing difficult problems, rather than working out new solutions using an ad-hoc theory and ad-hoc algebra likely rife with undiscovered problems.

I've been doing exactly this inside of Collectathon, a project I revived earlier this month (Sept, 2020). As of this article the resulting code hasn't been committed just yet, as I'm fleshing out expected algebraic operations, but the implementation and interface have been delightful, and actually rather simple. Furthermore, as I talked about in a previous article, Category was conceptually a set as well, and in implementing a generalized set base, the implementation of Category can be simplified, with the entirety of set algebra automatically provided, by simply deriving from Set. That is a fantastic example of code reuse.

Again:

If I have seen further it is by standing on the shoulders of Giants. -- Isaac Newton

DEV Community: Patrick Kelly

C#'s Generic Math from F#

Getting Started

Cranking to 11

Real World F# Interop

Numbersome

Collectathon

Stringier

Closing

Pattern Combinators

Designing Around F# Interop

The Past

Traits

Null tollerance

Refined F# Bindings / Putting It All Together

Summary

Going Further

The (non) Monorepo Mistake

Theoretical monorepo benefits...

Easier collaboration...

Single build...

Code refactors...

Unique monorepo downsides

Tight coupling...

VCS scalability

Other arguments.

Dependencies

Documentation

Testing

Summary

Avoiding Nulls with Extension Methods

Functional Collections

Proper Sets

Linked Lists

SinglyLinkedList<TElement> and SinglyLinkedList<TIndex, TElement>

Linkage

Nodes

How it works?

DoublyLinkedList<TElement> and DoublyLinkedList<TIndex, TElement>

Partial Unrolling

Indexing

Skip Lists

Jump lists

S-Lists

Advanced Arrays

Collectathon

ISet Considered Harmful

Where ISet<T> goes wrong

What ISet<T> should be

`SinglyLinkedList<TElement>` and `SinglyLinkedList<TIndex, TElement>`

`DoublyLinkedList<TElement>` and `DoublyLinkedList<TIndex, TElement>`

Where `ISet<T>` goes wrong

What `ISet<T>` should be