Higher Logics

Scala and Haskell both have very useful type-directed concepts for resolving implicit function parameters, called "implicits" and "type classes" respectively. To illustrate the impact of this, consider a generic sorting function like Enumerable.OrderBy . It must define two overloads, one that takes a custom comparer, and one that does not and so should use a default comparison for type TKey: public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>( this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IComparer<TKey> comparer ) public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>( this IEnumerable<TSource> source, Func<TSource, TKey> keySelector ) While it's simple to define the second overload as calling the first with Comparer<TKey>.Default for the custom comparer, in general, for N overridable parameters, you would need to define something like f...

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

An interesting question was posed to /r/Haskell today: is there a quick intro to C# from Haskell programmers? Well there are plenty of explanations of C#'s basic syntax, classes, structs, etc., but nothing that specifically addresses the functional mindset a Haskell programmer would be starting with, so I wrote a reply providing links to the various familiar concepts from functional programming found in C#, and described various caveats that might be surprising to a Haskell user. I'll reproduce the post here for posterity: I think there's a reasonable C# subset for functional programming, so if you stick to that you should be able to pick it up relatively quickly. Read up on: LINQ -- you can use the query comprehension syntax, or the regular first-class function syntax. The former is sugar for the latter. Tuples Lambdas and delegates (delegates are first-class functions) Parametric polymorphism is known as generics . You can place generic parameters on methods...

I just committed the core of a simple dependency injection container to a standalone assembly, Sasa.IoC . The interface is pretty straightforward: public static class Dependency { // static, type-indexed operations public static T Resolve<T>(); public static void Register<T>(Func<T> create) public static void Register<TInterface, TRegistrant>() where TRegistrant : TInterface, new() // dynamic, runtime type operations public static object Resolve(Type registrant); public static void Register(Type publicInterface, Type registrant, params Type[] dependencies) } If you were ever curious about IoC, the Dependency class is only about 100 lines of code. You can even skip the dynamic operations and it's only ~50 lines of code. The dynamic operations then just use reflection to invoke the typed operations. Dependency uses static generic fields, so resolution is pretty much just a field access + invoking a ...

I finally got around to finishing the immutable HAMT implementation I wrote about in my last post. The only missing features were tree merging and hash collision handling. Both features are now implemented with unit tests, and the whole branch has been merged back into "default" . It now also conforms to Sasa's standard collection semantics, namely the publicly exported type is a struct, so null reference errors are impossible, and it provides an atomic swap operation for concurrent use. Here's the API: /// <summary> /// An immutable hash-array mapped trie. /// </summary> /// <typeparam name="K">The type of keys.</typeparam> /// <typeparam name="T">The type of values.</typeparam> public struct Tree<K, T> : IEnumerable<KeyValuePair<K, T>>, IAtomic<Tree<K, T>> { /// <summary> /// The empty tree. /// </summary> public static Tre...

I just completed an implementation of an immutable hash array mapped trie (HAMT) in C#. The HAMT is an ingenious hash tree first described by Phil Bagwell . It's used in many different domains because of its time and space efficiency, although only some languages use the immutable variant. For instance, Clojure uses immutable HAMTs to implement arrays/vectors which are essential to its concurrency. The linked implementation is pretty much the bare minimum supporting add, remove and lookup operations, so if you're interested in learning more about it, it's a good starting point. Many thanks also to krukow's fine article which helped me quickly grasp the bit-twiddling needed for the HAMT. The tree interface is basically this: /// <summary> /// An immutable hash-array mapped trie. /// </summary> /// <typeparam name="K">The type of keys.</typeparam> /// <typeparam name="T">The type of values.</typeparam> public cl...

There's a great post on implementing idioms with LINQ, and the example application was to implement formlets, as WebSharper does for F#. Tomas's post is well written, so if you're unclear on the above concepts I recommend reading it first before proceeding with this article. The claim in that post is that idioms can only be encoded via LINQ's 'join' operators. While strictly true if you stick to all the LINQ rules, because LINQ queries are just naive syntactic transforms you don't have to follow the rules. You can thus exploit this to hijack the signatures for the SelectMany overloads to yield idiom signatures. It's not all sunshine and roses though, as there are consequences. Overview LINQ is a standard set of methods one can implement that the C# compiler can use to provide "query patterns". This query: var foo = from x in SomeFoo from y in foo.Values select y; is translated by the C# compiler to: var foo = Some...

I had recent need for a transpose operation which could swap the columns and rows of a nested IEnumerable sequence, it's simple enough to express in LINQ but after a quick search, all the solutions posted online are rather ugly. Here's a concise and elegant version expressed using LINQ query syntax: /// <summary> /// Swaps the rows and columns of a nested sequence. /// </summary> /// <typeparam name="T">The type of elements in the sequence.</typeparam> /// <param name="source">The source sequence.</param> /// <returns>A sequence whose rows and columns are swapped.</returns> public static IEnumerable<IEnumerable<T>> Transpose<T>( this IEnumerable<IEnumerable<T>> source) { return from row in source from col in row.Select( (x, i) => new KeyValuePair<int, T>(i, x)) group col.Value by col.Key into c select c as IEnume...

I've been experimenting with some purely functional collections, also known as persistent collections, and began to wonder precisely how much overhead they incur as compared to the standard framework collections on a VM platform such as .NET. My open source Sasa library has long had a persistent stack type , considered a list in functional languages, and I was considering adding some additional persistent collections. I therefore wanted a better understanding of the various costs involved. I had also wanted to test an interesting design alternative to standard class-based collections. One of the consistent nuisances on widely deployed VM platforms is the widespread presence of null values. C#'s extension methods somewhat mitigate this problem since you can call extension methods on null values and properly handle it, but calling instance methods on a null value throws a NullReferenceException. Therefore, you cannot invoke ToString or Equals without first checking for null. Thi...

My .NET Sasa library has fallen by the wayside as I experimented with translating various functional idioms in my FP# library. Reading up on what a few other generic class libraries have been experimenting with, like Mono Rocks, spurred me to putting those experiments to use and updating Sasa. I significantly simplified a lot of the code, documented every class and method, and generalized as much as possible. The license is LGPL v2, and you can download the source via svn: svn co https://sasa.svn.sourceforge.net/svnroot/sasa/tags/v0.8 sasa Sasa Core v0.8 A set of useful extensions to core System classes and some useful classes for high assurance development. Named tuple types: Pair, Triple, Quad. Either types, representing one of many possible values. There are Either types for 2, 3, and 4 parameters, mimicking the Pair, Triple, and Quad structure. Tuples are "product" types, while Either is a "sum" type, and products and sums are duals. Since products are useful,...

Creating DSLs is all the rage these days, and for good reason. Most abstractions are actually a little language struggling to get out. Design consists of creating abstractions with maximum power, and minimum restrictions, and reusing this abstraction as much as possible. Small domain-specific languages are the ticket. However, language implementations are often written in fairly ad-hoc ways, and most interpreters are difficult to extend to compilers and partial evaluators. Languages are usually described by an "initial algebra", which basically just means that language terms are described by data types. Here's a simple definition of a language with integers, variables and addition: (* * Expressions := [0-9]* | e1 + e2 | e1 - e2 *) type expression = Int of int | Add of expression * expression | Sub of expression * expression So a program in this language can consist of integers, subtraction or addition expressions. The interpreter for this language unpacks the expression...

Extending the work in my last post , I've developed a way to express an almost type-safe, general monad in C# . Similar to my module translation, the single monad object becomes a pair of co-operating objects, only one of which the monad implementor must define. Since C# cannot abstract over type constructors, I had to exploit the only feature that could accomodate the flexibility I needed: C#'s dynamic typing. // The Monad object, indexed by a singleton type that implements the // monad operations. public sealed class Monad<M, T> where M : struct, IMonadOps<M> { ... } // An object that implements operations on the monad's encapsulated // state. public interface IMonadOps<M> where M : struct, IMonadOps<M> { /// Return the encapsulated state for the monad's zero value. object Zero<T>(); // Return the encapsulated state for the 'unit' operation. object Unit<T>(T t); // Perform a bind operation given th...

I've found other monad tutorials very frustrating. They are typically written in expressive languages with type inference, which permits concise descriptions, but obscures the underlying type structure. I've been struggling with writing something close to a monad in C# for quite some time, simply because none of these tutorials give a sufficiently complete description of a monad's structure. Suprisingly, the Wikipedia page on monads helped clarify what I was missing. Here is the general structure of a monad all these tutorials use : -- the type of monad m type m a = ... -- return is a type constructor that creates monad instances return :: a → m a -- bind is a function that combines a monad instance m a with a -- computation that produces another monad instance m b from a's -- to produce a new monad instance m b bind :: m a → (a → m b) → m b So the monad type 'm', has a function 'return' that constructs instances of that type, and 'bind' which c...

The venerable Oleg Kiselyov once posted about the "best" collection traversal API . Let's call this ideal iterator a "SuperFold". LTU also covered his article . Essentially, a SuperFold is a left fold with early termination support. Any cursor can then be automatically derived from the SuperFold. The converse is not true. Additional arguments are made in the above paper and in the LTU thread, so I won't repeat them here. Without further ado, I present the SuperFold for my purely functional list in C# : //OCaml signature: ((T → B → bool * B) → B → B) → (T → B → bool * B) → B → B B SuperFold<B>( Fun<Fun<T, B, Pair<bool, B>>, B, B> self, Fun<T, B, Pair<bool, B>> proc, B seed) { bool cont; proc(head, seed).Bind(out cont, out seed); return cont ? self(proc, seed) : seed; } While quite simple, it's not as efficient as it should be since C#/.NET doesn't support proper tail calls. You can see in that so...

The benefits of advanced programmings languages are sometimes difficult to grasp for everyday programmers. The features of such languages and how they relate to industrial software development are sometimes hard to understand, especially since the arguments are couched in terms such as "referential transparency", "totality", "side-effect-free", "monads", "non-determinism", "strong static typing", "algebraic data types", "higher-order functions", "laziness/call-by-need", and so on. Many of these features are attributed to "pure" languages, but purity is also a nebulous concept. I will explain the importance of a number of these features and how they impact the everyday programmer's life. The Benefits of Referential Transparency Referential transparency (RT) is a simple principle with profound consequences. Essentially, RT dictates that functions may access only the parameters they...