Higher Logics

I've had numerous posts here describing instances where C# has come so close to getting it right, and yet misses the mark by an inch. The original C# enums have a simple semantics: enum SomeEnum { First, // compiler implicitly assigns 0 Second, // compiler implicitly assigns 1 Third, // compiler implicitly assigns 2 Fourth, // compiler implicitly assigns 3 } This worked nicely as a concise expression of a need for a set of distinct of values, but without caring what they are. C# later introduced the [Flags] attribute, which signals to the compiler that a particular enum isn't actually a set of disjoint values, but a set of bit flags. However, the compiler doesn't actually change its behaviour given this change of semantics. For instance, the following enum is completely unchanged, despite the semantically meaningful change to a set of bitwise flags: [Flags] enum SomeEnum { First, // compiler implicitly assigns 0 Second, // compiler implicitly assign...

.NET's delegates are a powerful and convenient abstraction available since .NET 1.1. They encapsulate a method pointer and the object the method belongs to in a single callable "function object". Multicast delegates are an extension of plain delegates, in that they encompass multiple single delegates. Invoking a multicast delegate invokes every encapsulated delegate, in the order they were added. Multicast delegates are key to event handling patterns that were a core part of the CLR nearly since its inception. If you're curious about virtual machines or CLR internals, you've perhaps wondered how multicast delegates actually work. These are the key properties of multicast delegates: They encapsulate a list of delegates of the same delegate type. Adding a delegate returns a new multicast delegate containing the new addition at the end of the list (the original is unchanged). Removing a delegate returns a new multicast delegate without the specified delegate (...

References in C# are second-class citizens, which is to say, that you cannot pass them around as values. They can appear in function parameter position, but that's it: public static void DoFoo(ref int value) { Action captureRef = () => value = 3; // ERROR: ref can't escape scope } This makes it easy to verify their safety statically, and makes them very efficient, but it somewhat limits their expressiveness. First-class citizens can be passed around as values, and otherwise used in any way that you'd use any other object. The above capture would work, for instance. To make references first-class citizens means constructing an object that exposes get and set operations, and that can reference the internals of any .NET type. IRef<T> Sasa has had the IRef<T> type for quite some time, but its full potential as a first-class reference hasn't been realized. There was only a single implementation, and that was a simple mutable slot as found in ML. I...

I recently came across Vance Morrison's blog post on the relative costs of dynamic type tests on the CLR, and I was struck by how much my experience differed from the results he received. In past tests, I had concluded that operations and comparisons using System.Type were just as fast as operations on System.RuntimeTypeHandle . This struck me as a little odd at the time, but numbers don't lie. Vance helpfully provided the code he used for his benchmarks, so I decided to see if perhaps I was mistaken. Lo and behold, the numbers I received from running his code matched my past results, ie. RuntimeTypeHandle provided no advantage. This seemed extremely odd, and after digging a little deeper, it turns out that Vance and I are both right. I've been doing most of my development on 64-bit x64 machines, and I suspect Vance was running x86 at the time. It turns out that the x64 runtime for the CLR is woefully underperforming when compared to x86, at least for this type of code...

The CLR's value types are incredibly useful for reducing memory usage of programs, but they have a severe limitation in concurrent scenarios: structs larger than the atomic type on a given machine can suffer from torn reads . Most typical applications won't encounter this because their concurrent accesses, both reads and writes, are protected by locks. However, there are some scenarios where locks just aren't viable for various reasons. For instance, if a few shared variables are read an order of magnitude more often than they're written, then all the lock contention is 90% wasted work among readers that aren't performing any updates. In principle, the lock is really there to permit only one writer to modify the variable at a time. This means we can possibly use some other signalling mechanism to notify readers that a write is taking place, or has taken place. Ideally, this mechanism shouldn't cause contention among readers thus permitting more read parallel...

Awhile back I had written about a a type unification nuisance I had run into. In a nutshell, the problem occurs when a class with two type parameters tries to implement the same interface twice, once for each type parameter: // compiler error: // 'Foo<T0,T1>' cannot implement both 'IEnumerable<T0>' and // 'IEnumerable&;lt;T1>' because they may unify for some type // parameter substitutions public class Foo<T0, T1> : IEnumerable<T0>, IEnumerable<T1> { } As Doug McClean pointed out in the comments, the reason behind this error is because the two implementations of the interfaces may not be confluent, ie. behaviourally identical, in which case there's no legitimate way to choose between the two. The application I had in mind at the time used marker interfaces, ie. interfaces with no methods or properties, so they were guaranteed to be confluent. I also had a sneaking suspicion that C# already permitted this structure el...

A bit of departure from my usual practical posts in C#, I decided to try my hand at an abstract computer science topic. I've become interested in concatenative programming, and combinator calculi are right up this alley. The quintessential combinator calculus is the well-known SKI calculus , which features two core combinators, S and K, and one optional combinator I. SKI is quite simple, and it's pretty straightforward to implement as an EDSL. I suspect the key stumbling block for most programmers unfamiliar with functional programming will be the pervasive partial application inherent to combinators. Partial Application Partial application is a pretty simple concept for anyone whose done even a little programming with LINQ. C#/.NET features first-class functions called "delegates" with types like: public delegate T2 Func<T0, T1, T2>(T0 arg0, T1 arg1); That's the type declaration for a delegate that accepts two arguments of types T0 and T1, and retu...

Since I recently finished documenting the core Sasa assembly , I decided to upload -RC4. Of course, then I ran into an issue with Nuget, which forced me to update my version number to -RC5 in order to overwrite an improperly uploaded package. So here is Sasa 0.9.4-RC5: Sourceforge : download all assemblies and ilrewrite in one package. CHM documentation file available as a separate download. Documentation available online here . Sasa on Nuget : the core Sasa.dll (no dependencies) Sasa.Arrow on Nuget: arrows for .NET (depends on Sasa.dll) Sasa.Binary on Nuget: low-level functions on bitdata (no dependencies) Sasa.Collections on Nuget: purely functional lists, trees, stacks (depends on Sasa.dll, Sasa.Binary.dll) Sasa.Concurreny on Nuget: concurrent abstractions including faster thread-local data and software transactional memory (depends on Sasa.dll) Sasa.Contracts on Nuget: a simple reimplementation of Microsoft's code contracts (no dependencies) Sasa.FP on Nuget: mor...

This is the twenty second post in my ongoing series covering the abstractions in Sasa . Previous posts: Sasa.Parsing - type-safe, extensible lexing and parsing framework Sasa.Dynamics - type-safe polytypic/reflective programming Sasa.Func - Type-Safe Delegate Combinators Sasa.Option - Handling Optional Values Sasa.Result - Handling Exceptional Values Sasa.Numbers - Generic Number Extensions Sasa.Strings - General String Extensions Sasa.Types - Runtime Types And CLR Metadata Sasa.Weak - Typed Weak References Sasa's Tuples Sasa's Core Interfaces Sasa.Events - Type-Safe, Null-Safe, Thread-Safe Events Sasa.Web.Url64 - URL-Safe Base64 Encoding Sasa.Operators<T> - Generic Arithmetic and Logical Operators Sasa.IO.FilePath - Easy and Safe Path Manipulations Sasa.IO.Streams - Convenient Stream Extensions Sasa.Linq.Enumerables - Extensions on IEnumerable<T> Sasa.Either - Simple Sums for .NET Sasa.Atomics - Simpler, More Scalable Atomic Operations Sasa.Col...

It's been awhile since I posted about Sasa's new immutable hash-array mapped trie (HAMT) , and I've only just gotten around to running some benchmarks and profiling the code. I just pushed a new project under the "Sasa/Bench" in the repo where I will place all Sasa benchmarks going forward. Initially the benchmarks were disappointing, but 2 minutes with the profiler revealed the problem was the Tree.Add method, which was using a very simple but poor implementation. Basically, it was checking if the key was already in the tree before attempting to update, thus performing the traversal twice for every addition. I refactored this to share the same implementation as Tree.Update which performs only a single traversal, and the results are now more reasonable. The benchmarks were run on an FX-8120 performing 200,000 individual inserts and 200,000 individual membership checks on a set of unique integers, ie. treating the dictionaries and trees as a set. The inserts we...

Sasa.Operators<T> was covered in a previous post , and was useful in its own right, but was still somewhat limited in the operators it could expose. Since it abstracted only over a single type parameter T, it exposed those operators defined only on T. For instance, addition has signature "T add(T, T)", negation is "T negate(T)", and so on. But not all operators are defined on only a single type. For instance, System.Decimal provides addition operators that work on integers, both signed and unsigned. Sasa.Operators<T> couldn't handle that. It can now. Sasa.Operators is now a fully generic operator framework, exposing static generic class types Operators<T> as before, Operators<T0, T1> which exposes operators defined over two type parameters, like equals whose signature is "bool equals(T0, T1)", and finally, Operators<T0,T1,T2> for operators defined over three possible types, like addition "T2 add(T0, T1)". Fur...

It's well known that C# doesn't permit certain types to appear as constraints, like System.Enum or System.Delegate, and that C# further prevents sealed classes from appearing as constraints . However, the example in the above article serves to point to an interesting circumvention of C#'s limitations on constraints. Suppose we wish to provide a statically typed enum interface, similar to what I provide in my Sasa class library , but without having to resort to IL rewriting as I do. We can implement this by exploiting the fact that type constraints are inherited. Consider the following general base class: public abstract class Constrained<TArg0, TReturn> { public abstract T1 Apply<T0, T1>(T0 arg0) where T0 : TArg0 where T1 : TReturn; } Notice how all the type parameters at the class level are fully abstract, so the C# compiler can't complain about using Enum or Delegate at this level. The class then constrains the type parameters at t...

This is the seventeenth post in my ongoing series covering the abstractions in Sasa . Previous posts: Sasa.Parsing - type-safe, extensible lexing and parsing framework Sasa.Dynamics - type-safe polytypic/reflective programming Sasa.Func - Type-Safe Delegate Combinators Sasa.Option - Handling Optional Values Sasa.Result - Handling Exceptional Values Sasa.Numbers - Generic Number Extensions Sasa.Strings - General String Extensions Sasa.Types - Runtime Types And CLR Metadata Sasa.Weak - Typed Weak References Sasa's Tuples Sasa's Core Interfaces Sasa.Events - Type-Safe, Null-Safe, Thread-Safe Events Sasa.Web.Url64 - URL-Safe Base64 Encoding Sasa.Operators<T> - Generic Arithmetic and Logical Operators Sasa.IO.FilePath - Easy and Safe Path Manipulations Sasa.IO.Streams - Convenient Stream Extensions In my opinion, the release of .NET 3.5 and LINQ to Objects was one of the greatest productivity and safety enhancements to .NET since its inception. It enabled th...

This is the sixteenth post in my ongoing series covering the abstractions in Sasa . Previous posts: Sasa.Parsing - type-safe, extensible lexing and parsing framework Sasa.Dynamics - type-safe polytypic/reflective programming Sasa.Func - Type-Safe Delegate Combinators Sasa.Option - Handling Optional Values Sasa.Result - Handling Exceptional Values Sasa.Numbers - Generic Number Extensions Sasa.Strings - General String Extensions Sasa.Types - Runtime Types And CLR Metadata Sasa.Weak - Typed Weak References Sasa's Tuples Sasa's Core Interfaces Sasa.Events - Type-Safe, Null-Safe, Thread-Safe Events Sasa.Web.Url64 - URL-Safe Base64 Encoding Sasa.Operators<T> - Generic Arithmetic and Logical Operators Sasa.IO.FilePath - Easy and Safe Path Manipulations Streams are a pervasive component of .NET I/O, but the standard stream interface is missing a few convenient extensions, if only needed for testing and debugging purposes. Sasa.IO.Streams provides a few simple e...

This is the fifteenth post in my ongoing series covering the abstractions in Sasa . Previous posts: Sasa.Parsing - type-safe, extensible lexing and parsing framework Sasa.Dynamics - type-safe polytypic/reflective programming Sasa.Func - Type-Safe Delegate Combinators Sasa.Option - Handling Optional Values Sasa.Result - Handling Exceptional Values Sasa.Numbers - Generic Number Extensions Sasa.Strings - General String Extensions Sasa.Types - Runtime Types And CLR Metadata Sasa.Weak - Typed Weak References Sasa's Tuples Sasa's Core Interfaces Sasa.Events - Type-Safe, Null-Safe, Thread-Safe Events Sasa.Web.Url64 - URL-Safe Base64 Encoding Sasa.Operators<T> - Generic Arithmetic and Logical Operators One persistent difficulty in dealing with IO in .NET is path handling. .NET exposes a platform's directory separator characters, but really this sort of thing should be automated. Furthermore, paths are considered simple strings and so concatenating fragments c...