Higher Logics

Concurrent programming is a very difficult problem to tackle. The fundamental issue is that manual locking is not composable , which is to say that if you have two concurrent programs P0 and P1 free of deadlocks, livelocks and other concurrency hazards, and you try to compose P0 and P1 to create a program P2, P2 may not be free of concurrency hazards. For instance, if P0 and P1 take two locks in different orders, then P2 will deadlock. Needless to say, this is a serious problem because composition is the cornerstone of all programming. I've been toying with some ideas for software transactional memory (STM) in C# ever since I started playing with FRP and reactive programming in general. The problem in all of these domains is fundamentally about how to handle concurrent updates to shared state, and how to reconcile multiple, possibly conflicting updates to said state. Rx.NET handles concurrency essentially by removing the identity inherent to shared state. An IObservable<T...

Equality and identity are often intermingled in the .NET framework. .NET delegates correctly implement a straightforward structural equality , where if two delegates are equal if they designate the same method and the same object, regardless of whether the delegate is a unique instance: class Bar { public void Foo(int i) { } } var bar = new Bar(); Action<int> a1 = bar.Foo; Action<int> a2 = bar.Foo; Console.WriteLine("Delegate Equality: {0}", a1 == a2); // prints: // Delegate Equality: True However, an IObservable<T> created from delegates does not respect structural equality, and reverts to an identity criterion: // use a1 and a2 from previous code sample var o1 = Observer.Create<int>(a1); var o2 = Observer.Create<int>(a2); Console.WriteLine("Observable Equality: {0}", o1 == o2 || o1.Equals(o2) || EqualityComparer<IObserver<int>>.Default.Equals(o1, o2)); //prints: // Obs...

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 i...