Higher Logics

In any system with mutable entities saved in an object store, it's inevitable that you'll want to audit the changes made to a particular entity. Explicitly versioning your entities solves this problem, and it's often pretty useful to end users of a sophisticated application, say for undo purposes. However, it's not always so clear how to transform a mutable entity into an versioned entity. There are also a number of complications to versioning mutable objects: Handling parent-child relations such that a child change does not propagate to every parent Supporting efficient queries on history Supporting efficient queries for the newest version Space complexity of data representation Concurrent changes Some of the above properties also have a natural tension, ie. supporting efficient queries often require storing more data so their space complexity is worse. I'm going to provide an overview here of a very simple schema for versioned entities with the following...

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

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 posted awhile ago about a pattern for ad-hoc extensions in .NET using generics. Unfortunately, like every "design pattern", you had to manually ensure that your abstraction properly implements the pattern. There was no way to have the compiler enforce it, like conforming to an interface. It's common wisdom that "design patterns" are simply a crutch for languages with insufficient abstractive power. Fortunately, .NET's multicast delegates provides the abstractive power we need to eliminate the design pattern for ad-hoc extensions: /// <summary> /// Dispatch cases to handlers. /// </summary> /// <typeparam name="T">The type of the handler.</typeparam> public static class Pattern<T> { static Dispatcher<T> dispatch; static Action<T, object> any; delegate void Dispatcher<T>(T func, object value, Type type, ref bool found); /// <summary> //...

A recent discussion on LtU brought up a common limitation of modern languages and runtimes. Consider some set of abstractions A, B, ..., Z that we wish supported some custom operation Foo(). Languages like C# give only two straightforward possibilities: inheritance and runtime type tests and casts. Inheritance is straightforward: we simply inherit from each A, B, ..., Z to make A_Foo, B_Foo, ..., Z_Foo, with a custom Foo() method. Unfortunately, inheritance is sometimes forbidden in C#, and furthermore, it sometimes prevents us from integrating with existing code. For instance, say we want to integrate with callback-style code, where the existing code hands our program an object of type A. We can't call Foo() on this A, because it's not an A_Foo, which is what we really wanted. This leaves us with the undesirable option of using a large set of runtime type tests. Now type tests and casts are actually pretty fast , faster than virtual dispatch in fact, but the danger is i...

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

My day job is has stuck me with C#, but I try to make the best of it, as evidenced by my FP# and Sasa C# libraries. One thing that still gets in my way more than it should is O/R mapping. No other mapper I've come across encourages a true object-oriented application structure. Granted, I've only really used NHibernate, and I had built my own mapper before that was even available, but I've read up quite a bit on the the other mappers. By true OO structure, I mean that all application objects are only constructed from other application objects, which doesn't involve dependencies on environment-specific code (ie. if you're running under ASP.NET, Windows forms, Swing, etc.). A pure structure encourages a proper separation between core application code, and display and controller code, which allows more flexible application evolution. Instead, controller logic often manually constructs application objects, passing in default arguments to properly initialize the required ...

There's a long-running debate on the power of functional languages over object-oriented languages. In truth, now that C# has full generics, aka parametric polymorphism, it's almost equivalent in typing power to most typical statically typed functional languages. In fact, in terms of typing power, generic objects are universal and existential types, and can be used for all the fancy static typing trickery that those entail (see my previous reference to the GADTs in C# to see what I mean). As a prior post explained, C#'s type system still lacks some of the flexible constraint refinement available in more powerful functional type systems, but in general C# is powerful enough to encode most interesting functional abstractions. And I started a new project to demonstrate this: FP# . It provides a number of widely used functional abstractions, like the option type, a lazy type, lists, lazy lists, etc. and map, filter, and fold over all the collection types, including the sta...

My previous definition of IVisitor hard-coded the return value as a type of Val, but one can generalize a visitor to any kind pattern-matching function by adding a generic type parameter to the interface: //the pattern matching visitor public interface IVisitor<T> { //return type is now parameterized T App(Exp e0, Exp e1); } This of course requires a modification to the class variants as well: //the type representing an expression application public sealed class App : Exp { Exp e0; Exp e1; public App(Exp e0, Exp e1) { this.e0 = e0; this.e1 = e1; } //add a generic constraint to the Visit method, so the client can //specify the return type public override T Visit<T>(IVisitor<T> v) { return v.App(e0, e1); } } So instead of IVisitor being hard-coded as an evaluator, I can now write an IVisitor that performs transformations on the expression tree (such as rewriting optimizations), or a visitor that implements some arbitrary predica...

To kick off my first post, I thought I'd cover a post on another blog that I found interesting . Basically, the gist of the post is that object oriented visitor pattern does not lend itself to the problem of walking trees, and general symbolic manipulation, despite that being its claim to fame. In general, algebraic data types and pattern matching are much simpler, and more concise. I agree, however I think that post goes a bit too far in saying that visitors simply can't do this elegantly, because in fact there's a straightforward translation of a pattern matching function into a visitor, as long as you keep your objects "functional", ie. treat them as variants. For instance, let's say we are constructing an evaluator: //the Expression type public abstract class Exp { public abstract Val Visit(IVisitor v); } //the type of Values public abstract class Val : Exp { } //the type representing an application public sealed class App : Exp { Exp e0; Exp e1; ...