Skip to main content

Abstracting Computation: Arrows in C#

I just committed an implementation of Arrows to my open source Sasa library. It's in its own dll and namespace, Sasa.Arrow, so it doesn't pollute the other production quality code.

The implementation is pretty straightforward, and it also supports C#'s monadic query pattern, also known as LINQ. It basically boils down to implementing combinators on delegates, like Func<T, R>. It's not possible to implement the query pattern as extension methods for Func<T, R> because type inference fails for even the simplest of cases. So instead I wrapped Func<T, R> in a struct Arrow<T, R>, and implemented the query pattern as instance methods instead of extension methods. This removes a number of explicit type parameters that the inference engine struggles with, and type inference now succeeds.

Of course, type inference still fails when calling Arrow.Return() on a static method, but this is a common and annoying failure of C#'s type inference [1].

What is this madness?


Some might question my sanity at this point, since arrows in C# are bound to be rather cumbersome. I have a specific application in mind however, and experimenting with that led naturally to arrows. Basically, while trying to use Rx.NET in a highly configurable and dynamic user interface library, I became dissatisfied with the state management required.

In short, Rx.NET supports first-class signals, which does not play well with garbage collection. They solve this by reifying subscriptions in IDisposable objects that ensure proper cleanup if a signal is no longer required. So every time-varying value in my UI controls now requires me to keep track of two objects, the signal itself, and the IDisposable subscription to prevent it from being garbage collected.

Now consider all the elements of a text box or data grid that may be changing over time, including the text font, the margins, the position, the background, and so on, and you quickly see the state management problem grow.

Arrows can simplify this situation considerably, because instead of programming directly with signals, the user instead programs with signal functions. Since signals are no longer first-class values, there is no garbage collection problem and no need to juggle subscriptions.

There are further advantages in sharing, particularly for this UI library, so there's a great deal of incentive to use arrows. I'm hoping I can hide the use of arrows behind the user interface abstractions so the user has minimal interaction with it.

[1] Consider:
static int Id(int t)
{
return i;
}
static Func<T, R> Return<T, R>(Func<T, R> f)
{
return f;
}
If you call Return(Id), type inference will fail.

Comments

Popular posts from this blog

async.h - asynchronous, stackless subroutines in C

The async/await idiom is becoming increasingly popular. The first widely used language to include it was C#, and it has now spread into JavaScript and Rust. Now C/C++ programmers don't have to feel left out, because async.h is a header-only library that brings async/await to C! Features: It's 100% portable C. It requires very little state (2 bytes). It's not dependent on an OS. It's a bit simpler to understand than protothreads because the async state is caller-saved rather than callee-saved. #include "async.h" struct async pt; struct timer timer; async example(struct async *pt) { async_begin(pt); while(1) { if(initiate_io()) { timer_start(&timer); await(io_completed() || timer_expired(&timer)); read_data(); } } async_end; } This library is basically a modified version of the idioms found in the Protothreads library by Adam Dunkels, so it's not truly ground bre

Building a Query DSL in C#

I recently built a REST API prototype where one of the endpoints accepted a string representing a filter to apply to a set of results. For instance, for entities with named properties "Foo" and "Bar", a string like "(Foo = 'some string') or (Bar > 99)" would filter out the results where either Bar is less than or equal to 99, or Foo is not "some string". This would translate pretty straightforwardly into a SQL query, but as a masochist I was set on using Google Datastore as the backend, which unfortunately has a limited filtering API : It does not support disjunctions, ie. "OR" clauses. It does not support filtering using inequalities on more than one property. It does not support a not-equal operation. So in this post, I will describe the design which achieves the following goals: A backend-agnostic querying API supporting arbitrary clauses, conjunctions ("AND"), and disjunctions ("OR"). Implemen

Easy Automatic Differentiation in C#

I've recently been researching optimization and automatic differentiation (AD) , and decided to take a crack at distilling its essence in C#. Note that automatic differentiation (AD) is different than numerical differentiation . Math.NET already provides excellent support for numerical differentiation . C# doesn't seem to have many options for automatic differentiation, consisting mainly of an F# library with an interop layer, or paid libraries . Neither of these are suitable for learning how AD works. So here's a simple C# implementation of AD that relies on only two things: C#'s operator overloading, and arrays to represent the derivatives, which I think makes it pretty easy to understand. It's not particularly efficient, but it's simple! See the "Optimizations" section at the end if you want a very efficient specialization of this technique. What is Automatic Differentiation? Simply put, automatic differentiation is a technique for calcu