Higher Logics

Diff for IEnumerable

2012-02-02T21:10:00.000-05:00

I've just added a simple diff algorithm under Sasa.Linq. The signature is as follows:

/// <summary>
/// Compute the set of differences between two sequences.
/// </summary>
/// <typeparam name="T">The type of sequence items.</typeparam>
/// <param name="original">The original sequence.</param>
/// <param name="updated">The updated sequence to compare to.</param>
/// <returns>
/// The smallest sequence of changes to transform
/// <paramref name="original"/> into <paramref name="updated"/>.
/// </returns>
public static IEnumerable<Change<T>> Difference<T>(
  this IEnumerable<T> original,
  IEnumerable<T>      updated);
/// <summary>
/// Compute the set of differences between two sequences.
/// </summary>
/// <typeparam name="T">The type of sequence items.</typeparam>
/// <param name="original">The original sequence.</param>
/// <param name="updated">The updated sequence to compare to.</param>
/// <param name="eq">The equality comparer to use.</param>
/// <returns>The smallest sequence of changes to transform
/// <paramref name="original"/> into <paramref name="updated"/>.
/// </returns>
public static IEnumerable<Change<T>> Difference<T>(
  this IEnumerable<T>  original,
  IEnumerable<T>       updated,
  IEqualityComparer<T> eq);

The extension methods depend only on the following enum and struct:

/// <summary>
/// Describes the type of change that was made.
/// </summary>
public enum ChangeType
{
    /// <summary>
    /// An item was added at the given position.
    /// </summary>
    Add,
    /// <summary>
    /// An item was removed at the given position.
    /// </summary>
    Remove,
}
/// <summary>
/// Describes a change to a collection.
/// </summary>
/// <typeparam name="T">The collection item type.</typeparam>
public struct Change<T>
{
    /// <summary>
    /// The change made at the given position.
    /// </summary>
    public ChangeType ChangeType { get; internal set; }
    /// <summary>
    /// The set of values added or removed from the given position.
    /// </summary>
    public IEnumerable<T> Values { get; internal set; }
    /// <summary>
    /// The position in the sequence where the change took place.
    /// </summary>
    public int Position { get; internal set; }
}

This is a simple and general interface with which you can perform all sorts of computations on the differences between two sequences. The code as provided will work out of the box for any type T that implements equality. Some simple examples:

Console.WriteLine( "miller".Difference("myers").Format("\r\n") );
// prints out:
// +1:y
// -1:i,l,l
// +6:s

var original = new int[] { 2, 5, 99 };
var updated = new int[] { 2, 4, 4, 8 };
Console.WriteLine( original.Difference(updated).Format("\r\n") );
// prints out:
// +1:4,4,8
// -1:5,99

"Format" is a simple extension method also under Sasa.Linq with generates a formatted string when given an IEnumerable

At the moment, I simply implemented the naive algorithm that takes N*M space and time. I plan to eventually implement some linear space optimizations, as described in An O(ND) Difference Algorithm and Its Variations.

There are many applications for a general difference algorithm like this. Consider a reactive property of type IEnumerable<T>, like as used in a drop down for a user interface. If the UI is remote, as you find in X11 or a web browser, sending the entire list over and over again is bandwidth-intensive, and trashes the latency of the UI. It's much more efficient to just send the changes, which can be accomplished by taking the diff of the original and the new list.

Clavis - A Web Security Microframework

2012-01-08T09:32:00.000-05:00

Web programming has been a pretty big deal for over 10 years now, but in some ways the tools web developers use haven't really progressed that much, particularly when it comes to security. For instance, CSRF and clickjacking are instances of the Confused Deputy problem, a security problem known since at least 1988.

Since these are both instances of the same underlying problem, in principle they should have the same or very similar solutions. However, the current solutions to these pervasive vulnerabilities are designed to solve only the specific problem at hand, and not the general problem of Confused Deputies. This means that if another HTML or Flash enhancement comes along that introduces another Confused Deputy, these solutions will not necessarily prevent exploitation of that vulnerability.

However, if we solve the underlying Confused Deputy problem, then that solution will address all present and future Confused Deputies, assuming any new features don't violate the constraints the solution specifies. Fortunately, the solution to the Confused Deputy has been known since it was first recognized: capabilities.

Capabilities

Capabilities are in fact a very simple and general framework for representing and reasoning about the flow of authority in a program. You've used capabilities many times without even knowing it. For instance, if you've ever received an activation e-mail with a long, unguessable URL, or if you've ever received a link to a Google Docs document.

There was no login requirement to load these links, no account information you had to input or password you had to provide. These types of links just bring you to the resource you want to access and whatever loads in your browser lets you know what you can do. Sometimes you can only read that resource, and sometimes there are some fields via which you can update the resource you're viewing, or other possibly update other resources. These types of URLs are capabilities.

The Confused Deputy problem inherently relies on references to resources being forgeable, like a file path, and the permissions for that resource being separate from the reference itself. The latter criterion is called "ambient authority" in capability parlance.

Capabilities solve the Confused Deputy because references are inherently unforgeable and include the permissions on that object. So if you have a capability, you have necessary and sufficient permission to operate on that object, period, full stop. I won't go into capabilities and Confused Deputies any further since there are plenty of online references describing them, but if there's enough interest I will write something up for a future post.

The quintessential capability web framework is Waterken, and its capabilities are called "web-keys".

Capabilities are not a panacea though. In the past, I found the Waterken programming model somewhat unintuitive. In my experience, most programming proceeds by designing a model that reflects the problem domain, which you then compose with models that cover other, often orthogonal, problem domains.

Example problem domains are data persistence, web request handling, and the usual models a programmer might have to write himself, like an order processing system. Most of these models are orthogonal, so each problem a developer needs to tackle can often be tackled independently, with a little glue to compose them into a final program.

Part of the problem with Waterken-style capabilities is that the data model of a program is more tightly coupled to the authorities as viewed by the user. These often take the form of capability patterns like "facets", which are used for attenuation, revocation and delegation of authority.

However, in traditional programming, security is most often modelled separately like every other concern, and evolves independently. This orthogonal thinking doesn't work with capabilities as they are currently provided. In Waterken, you have to compose the capability model and your data model in your head before you can even write any code, and this is why it's a little more difficult than necessary in my opinion. Combined with the fact that Waterken already has a built-in notion of persistence, and it's not exactly a drop-in solution.

However, it's undeniable that capabilities provide a natural framework for preventing Confused Deputies, so a good web framework will probably look a bit like capabilities.

Continuations

In my opinion, the biggest advance on the server-side was the development of continuations to model web interactions. If used correctly, they provide a natural framework for specifying and reasoning about the state needed by a request, and how that request can flow into other requests.

Every web program is unequivocally continuation-based, simply due to the stateless nature of HTTP and the various browser features, eg. back buttons. However, there have been many extensions to HTTP to try and mimic statefulness. Most of these extensions are still expressible as abstractions on top of continuations, although when these abstractions are used to carry credentials of various types, as is often done with cookies, a web program is susceptible to Confused Deputies [1].

Continuations are particularly advantageous in a statically typed language. A web framework in a typed language can define continuation abstractions specifying the static types of the parameters the continuation needs to satisfy a request. The framework itself can then guarantee that any requests for that resource have precisely the right types, and even the right names. This eliminates quite a bit of duplicate sanity checking code.

A good web framework will make the continuations inherent to web development somewhat obvious to maximize simplicity and flexibility.

Summary of Problems

Fundamentally, the problems with typical web frameworks are simple:

Pervasive statefulness, ie. sessions and cookies.
No standard, reliable way to protect parameters from tampering.
Authorization context is ambient, leading to confused deputies like CSRF and clickjacking.
No way to know at a glance which parameters require sanity checking, and which can be relied on.

Clavis

Taking the above lessons to heart, I present here a simplistic web security microframework. It trivially integrates with ASP.NET, but does not inherently depend on the page model. System.Web.Page already naturally satisfies Clavis' requirements though, so you can get right to developing your program.

What Clavis provides, addressing some of the failings of typical approaches:

A session-free, ambient authority-free state model via continuations.
A standard parameter protection semantics that prevents tampering, ie. parameters are unforgeable by default.
Authorization context is explicit as a parameter. Combined with unforgeability, this automatically prevents Confused Deputies like CSRF and clickjacking.
A parameter's forgeability is specified in the type and enforced by the compiler, so the need for sanity checking is obvious at a glance.

State Model - Continuations

The core concept is that of a set of interfaces defining continuations with various parameters required to load the page:

public interface IContinuation : ...
{
}
public interface IContinuation<T> : ...
{
}
public interface IContinuation<T0, T1> : ...
{
}
public interface IContinuation<T0, T1, T2> : ...
{
}
public interface IContinuation<T0, T1, T2, T3> : ...
{
}
...

A page class you define will then simply declare that it implements a certain continuation interface, and specify the types of the parameters the page requires to load:

public class Foo : System.Web.Page, IContinuation<User, SalesOrder>
{
  ...
}

The requirements on IContinuation are already satisfied by System.Web.Page, so there is nothing to implement. A page can also implement multiple continuation types, However, implementing the IContinuation interface gets you access to extension methods that allow you to name and parse parameters:

public class Foo : System.Web.Page, IContinuation<User, SalesOrder>
{
  User user;
  SalesOrder order;
  protected void Page_Load(object sender, EventArgs e)
  {
    if (!this.TryParse0(out user, userId => LoadUser(userId)))
      throw ArgumentException("Invalid request!");

    if (!this.TryParse1(out order, orderId => LoadOrder(orderId)))
      throw ArgumentException("Invalid request!");
  }
}

You can generate URLs from a continuation based on the page's fully qualified type name:

var link = Continuation.ToUrl<Foo, User, SalesOrder>(
                        user.AsParam(), order.AsParam());

If you just want to redirect to a continuation:

Continuation.Display<Foo, User, SalesOrder>(
             user.AsParam(), order.AsParam());

For simplicity, Clavis requires that the fully qualified names of the continuations map to the URL path. So a continuation class Company.Warehouse.Foo, will map to ~/Company/Warehouse/Foo/. If the continuation is a System.Web.Page, you can simply place it under that directory and name it Default.aspx, and IIS will load it.

You can also customize the name used for a parameter if you really want to, although you must then keep the names used when generating the URL and the name used when parsing the parameter in sync.

Unforgeable Parameters

Each of a continuation's arguments are unforgeable, meaning that a URL constructed from a program is guaranteed to be free from tampering. A URL constructed for Foo above, might look something like this:

http://host.com/Foo/?!User=123&!SalesOrder=456&clavis=6dc8ca2b

Every query parameter prefixed with ! is guaranteed to be tamper proof, which means they can be used as unforgeable references. The unforgeability is guaranteed by the "clavis" query parameter, which is an HMAC of the URL path and the parameters prefixed by !.

By default, continuation arguments generate tamper-proof query parameters, with no further work on the developer's part. The developer simply needs to provide the functions to convert a type to and from a string that designates that type, ie. a UserId, a SalesOrderId, etc.

The query parameters are named according to the type of object that parameter is supposed to represent as specified in the IContinuation type definition. You should avoid using "int" or "string" since those aren't very meaningful. Foo from above generated "User" and "SalesOrder" parameters, but if I were instead write a class like this:

public class Meaningless : System.Web.Page, IContinuation<int, string>
{
  ...
}

you'd end up with a URL that isn't very meaningful:

http://host.com/Meaningless/?!int=123&!string=456&clavis=0a1a15d0

So instead of specifying that your continuation accepts integers or strings that represent an object in your data model, just specify the data model objects in your continuation as I did with Foo above.

Generating a URL for Foo from above is probably a little more complicated than I showed before, since you will often need to specify a string conversion:

var link = Continuation.ToUrl<Foo, User, SalesOrder>(
                        user.AsParam(u => u.UserId),
                        order.AsParam(o => o.OrderId));

Loading the parameter on the receiving end depends on the position in the continuation argument list. The first parameter is loaded via TryParse0, the second via TryParse1, and so on.

In general, the AsParam() extension methods are used to generate URL parameters with string conversions, and TryParseX() extension methods are to load data model objects from the continuation arguments via conversion from string. You could also add your own extension methods for AsParam() so you don't have to specify the string conversion every time. It's not quite so easy for TryParseX since you need to provide an overload for each possible argument index.

Explicit Authorization

Since all state is intended to be passed via continuation arguments, this includes any user identification or other authorization information, like a UserId:

http://host.com/Foo/?!User=123&!SalesOrder=456&clavis=6dc8ca2b

Because the User parameter is unforgeable, this means the explicit authorization information needed to operate on SalesOrder 456 is guaranteed to be reliable. No attacker will be able to generate the correct "clavis" parameter to forge such a request.

With plain continuations and unforgeable references discussed so far, all URLs are straightforward capabilities. This means if someone ever accidentally finds a legitimate URL, they can access the content at that URL.

Consider being on the above page for Foo, and it contains an external link. If you click that link, the server receiving the request will get the above URL in its entirety, as do any HTTP caches along the way if the connection isn't encrypted. It's a hideous security leak. There are plenty of techniques to mitigate this problem, but it's a general symptom of capabilities. For instance, capability URLs are also susceptible to shoulder-surfing attacks.

Clavis addresses this by providing a mechanism for tying its intrinsic capability URLs to "sessions". A session is basically just like an authentication cookie you would use on a typical website, except it need not carry any meaningful credentials. It's merely another random token that is included in the MAC so resulting URL is unique and tied to the lifetime of that token, and all such capability "leaks" are automatically plugged so long as the token is not also leaked.

The URL generated for a session-limited continuation will look like:

http://host.com/Foo/?!User=123&!SalesOrder=456&clavis-auth=faee8ce2

Notice that the "clavis" parameter is now called "clavis-auth", so Clavis knows that this request should include a session token in the MAC.

Clavis is agnostic about how this token is generated and stored on the server. You don't even have to store it at all, technically. The token can technically be anything, and you can even just use ASP.NET's FormsAuthentication cookies, or the ASP.NET session id for the token. This configuration happens on application load:

Continuation.Init(Convert.FromBase64String(clavisKey), () =>
{
    var x = HttpContext.Current.Session;
    return x == null ? "" : x.SessionID;
});

"clavisKey" in the above is a 64-bit random byte array used as the private key for generating the MAC. Storing it as a parameter in the web.config file would do for most purposes. If you ever change this key, all previous URLs MAC'd with that key will break, but sometimes that's what you need. For instance, if this key is ever disclosed, you want to change it immediately to eliminate the threat.

Sanity Checked Parameters

By default, continuation arguments are unforgeable, so they don't require any sanity checking. This is unnecessarily restrictive however, since there are many HTTP patterns where we want the client to provide or modify some URL parameters. Ideally, we could easily identify such parameters so we can tell at a glance which ones need sanity checking.

In Clavis, this is achieved via Data<T>. A continuation whose argument type is wrapped in Data<T> will generate a forgeable query parameter, not an unforgeable one:

public class Foo2 : System.Web.Page,
                    IContinuation<User, Data<SalesOrder>>
{
  ...
}

This indicates that the second argument of type SalesOrder is pure data, and not unforgeable, and so it requires strict sanity checking before being used. Foo2 will generate URL that looks like:

http://host.com/Foo2/!User=123&SalesOrder=456&clavis=8def944e

The SalesOrder parameter is no longer prefixed by !, and so it is not included in the MAC that prevents tampering. This is mostly useful in GET submissions like search forms, and allows a developer to see at a glance which arguments require sanity checking.

The Data<T> type itself is fairly straightforward wrapper:

public struct Data<T> : IRef<T>, IPureData, IEquatable<Data<T>>
{
  /// 
  /// The encapsulated value.
  /// 

  public T Value { get; set; }
  ...
}

Using Clavis

You can obtain the Clavis binaries here. The Clavis API docs are here.

Simply link the Clavis and Sasa assemblies into your project, and put "using Clavis;" at the top of every file that's implementing or using continuations. I'm slowly migrating an old ASP.NET app to Clavis, demonstrating that it can be used incrementally in existing programs.

A few simple rules when using Clavis will maintain strong security at this layer of the stack:

All state should preferably be transmitted via continuation parameters, ie. no use of the session or cookies. If you're careful, you can store credentials in the session token used by Clavis and remain safe, but only do this if you understand the serious dangers.
Forgeable parameters should be used with extreme care, ie. Data<T>. In particular, don't use them to carry the authorization context or you are vulnerable to Confused Deputies, ie. a userId used to make access decisions should never be specified via Data<User>. Sanitize these parameters thoroughly.
Use frameworks like Linq2Sql to ensure you're free of code injection vulnerabilities.

If you never use cookies or session state, your program will also automatically be RESTful. You still need to exercise care when sending content to clients to prevent XSS, but this happens at another layer that Clavis can't really help with.

Future Work

Clavis is a fairly simplistic approach to solving the issues I raised in this post, but this simplicity makes it reliable and easy to integrate with the existing ASP.NET stack. There are a few small limitations to Clavis as currently devised, some of which will be addressed shortly:

The way type names are mapped to URLs might be changed to exploit ASP.NET's new and more flexible URL routing framework.
There are only continuation types for up to 4 parameters. I intend to at least double that.
Clavis currently depends minimally on the last stable release of Sasa. I will either eliminate this dependency, or update it when the new Sasa version is released shortly.

I welcome any comments or suggestions.

Footnotes

[1] Credentials in cookies are bundled separately from the URL to the resource being operated on, and URLs are typically forgeable -- classic Confused Deputy.

Software Transactional Memory in Pure C#

2011-12-23T17:18:00.000-05:00

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> is actually a collection of all values pushed to that observable in some undefined order. If you were to create an IObservable that retains only the "last" pushed value, and thus now retains an identity, you then have the same problems as above, namely that this update must always be consistent with other updates at any given instant in time. For instance:

var plusOne = intObservable.Select(i => i+1);

At every instant in the program's execution, plusOne should always observably equal intObservable + 1, and the ability to observe a violation of this constraint is known in reactive literature as a 'glitch'.

Similarly, in database programming where transactions rule, this is known as a 'dirty read'. Essentially, an update to intObservable is executing in a transaction, but other transactions are able to view those changes before that transaction has committed.

Generally speaking, glitches and dirty reads are undesirable, because they require the developer to manually synchronize state, which defeats the whole purpose of going with FRP or transactions to begin with. From what I've seen so far, Rx.NET gets around this by not providing abstractions that expose identity in this way. The programs you write must work with collections of values, and the program must specify the ordering via Observable.OrderBy.

When I added the Property<T> IObservable to Sasa, I added a limited form of transactions to prevent glitches, because a property has identity. This implementation uses a global 'clock', which is really just a global uint64 counter to properly sequence updates and prevent glitches.

Overview

I'm going to focus here on implementing STM directly, but to keep it simple, I've gone with the simplest STM that is expressible using .NET primitives. In fact, the resulting STM is probably not good if you're after scaling, it does a good job of ensuring concurrency safety for arbitrary composition.

The STM I committed to Sasa is a very simple, perhaps even simplistic, STM employing encounter-time locking with deadlock detection on transactional variables. Any read or write acquires the lock on a transactional variable. Whenever two transactions would block to wait for each other, the transaction that is not already blocked is aborted and retried.

This design has advantages and disadvantages. The disadvantages are the limited concurrency even when reads and writes would not conflict. Two transactions that only read a transactional variable Y, would still block each other despite the fact that concurrent reads can't cause problems. Furthermore, the use of encounter-time locking means that locks can be held for a long time. Finally, the naive deadlock detection combined with encounter time locking means that some programs will have higher abort rates than they would in other STMs.

There are significant advantages to this approach though. For one, a transaction doesn't require elaborate read/write/undo logs. In fact, this STM requires only a single allocation for the transaction object itself at transaction start. By contrast, most other STM designs require at least one allocation for every object that is read or written. These allocation costs are generally amortized, but they still add up.

The STM is also conceptually simple at 450 lines of code, including elaborate comments (127 lines counting only semicolons). This STM consists of only 3 classes, and 1 exception, and uses only System.Monitor for locking. This means that the STM isn't really fair, but it's rather simple to replace standard locks with a fair locking once the core STM algorithm is understood.

There is also preliminary support for integration with System.Transactions.

Transactional Programming

Any sort of transactional programming requires a transaction:

public sealed class MemoryTransaction : IEnlistmentNotification,
                                        IDisposable
{
  public static MemoryTransaction Begin();
  public static void Run(Action body);
  public static MemoryTransaction Current { get; }
  public void Complete();
}

This class is closely modeled on the design of TransactionScope from System.Transactions. Programs will generally concern themselves mostly with transactional variables, which in Sasa.TM is called Transacted<T>:

public class Transacted<T> : Participant, IRef<T>
{
  public T Value { get; set; }
  public void Write(T value, MemoryTransaction transaction);
  public T Read(MemoryTransaction transaction);
}

Any reads and writes to Transacted<T> occur within the lifetime of a MemoryTransaction, and the set of all such reads and writes are committed atomically. A simple program demonstrating the use of these abstractions:

Transacted<int> accountBalance = new Transacted<int>();
MemoryTransaction.Run(() =>
{
  accountBalance.Value += 100;
});

MemoryTransaction.Run will handle all the commits, rollbacks and retries for you. You can do this manually as well if you catch RetryException, and call Complete and Dispose methods on the transaction manually, but for most purposes the Run method suffices. You can nest calls to Run as many times as you like, but only one top-level transaction will ever be created.

No matter how many concurrent threads are executing the above code, it will always be updated atomically, and you can compose the above program with any other transactional program, and the result will also be free of concurrency hazards. The one caveat is that you should not cause non-transactional side-effects from within a transaction.

Please refer to the API docs under Sasa.TM for further details.

Internals

The internals of this STM design is pretty straightforward. Structurally, it looks something like this:

+---------------+   +---------------+    +----------------+
|Tx0            |   |Transacted0    |    |Transcated1     |
|  participants---->|  value = 2    | +->|  value = true  |
|  waitingFor   |   |  undo  = 1    | |  |  undo  = false |
+-----|---------+   |  next-----------+  |  next  = null  |
      |       ^     |  owner        |    |  owner         |
      |       |     +---|-----------+    +---|------------+
      |       |         |                    |
      |       +------------------------------+
      |
      +--------------------+
                           |
                           v
+------------------+     +------------------+
|Tx1               |     |Transacted2       |
|  participants--------->|  value = null    |
|  waitingFor=null |     |  undo  = "Foo"   |
+------------------+<-------owner           |
                         +------------------+

There's quite a bit going on here, so here are some quick highlights:

Each Transacted<T> is a member of a linked list rooted in the "participants" field of the MemoryTransaction. The list consists of Transacted<T> which have been read or written during the current transaction.
Each Transacted<T> points to the current transaction that owns its lock.
Each MemoryTransaction that attempts to acquire a lock on a Transacted<T>, stores the Transacted<T> in a local field called "waitingFor".
Transacted<T> stores the original value before any changes are made, so we can rollback if the transaction aborts.

From the above graph, we can see that there are two running transactions, Tx0 and Tx1, and that Tx0 has read or written Transacted0 and Transacted1, and it has tried to read/write Transacted2. However, Tx1 currently owns the lock on Transacted2, so Tx0 is effectively blocked waiting for Tx1 to complete.

This dependency graph is acyclic so there is no deadlock. If Tx1 were to then try to acquire the lock on Transacted0 or Transacted1, we would create a cycle in the waits-for graph, and we would have to abort one of the transactions.

On commit, a transaction's participant list is walked, unlinking elements as it goes, and all the undo fields are cleared and the locks are released. The next transaction blocked on any of the participants, acquires the lock it's been waiting for, sets the owner field, and proceeds.

Rollback is much the same, except the Transacted<T>'s value field is first overwritten with the value from the undo field.

Future Work

Fair STM

To those that have read my previous posts, note that the structure of the MemoryTransaction is exactly the structure of MetaThread from a previous post. By simply adding a WaitHandle to MemoryTransaction with a FIFO locking protocol, we have a fair STM.

Lock Stealing

STM research so far has shown that most transactions are short enough that they can execute in a single timeslice, and throughput suffers if a thread is descheduled while it's holding locks. This would only be exacerbated in an encounter-time locking design like I've described here, since locks are held for longer.

Instead of blocking on a variable that is already owned, we can instead steal the lock under certain conditions. For instance, if Tx0 and Tx1 are merely reading from a variable, they can repeatedly steal the lock from each other without concern.

A transaction that writes a variable that has only been locked for reading, can steal that lock too, but if the original owner tries to read the variable again, it must abort.

If Tx0 and Tx1 both try to write the same variable, blocking is unavoidable.

Obviously, all of these performance improvements impact the simplicity of the original design, so I'm leaving them for future work if the need arises.

Type Unification Forbidden - More C#/CLR Irritations

2011-11-12T16:57:00.001-05:00

I've written about quite a few irritations of C#/CLR, including asymmetries in CIL, oddly unverifiable CIL instructions, certain type constraints are forbidden for no reason, delegate creation bugs, the lack of higher-kinded types, equality asymmetries between events and IObservable, generics/type parameter problems, lack of usable control over object layouts, and just overall limitations of the CLR VM.

I've just smack into yet another annoying problem: type parameter unification is forbidden. The Microsoft Connect bug filed in 2004 was closed as By Design.

Here's a simple code fragment demonstrating the problem:

class ObserveTwo<T0, T1> : IObservable<T0>, IObservable<T1>
{
}

This will fail with the error:

'ObserveTwo<T0,T1>' cannot implement both 'System.IObservable<T0>' and 'System.IObservable<T1>' because they may unify for some type parameter substitutions

This is frankly nonsense. What's the problem if T0 and T1 unify? If T0=T1, ObserveTwo just implements IObservable<T0>, and the methods are all unified as well [2]. If T0!=T1, then the usual semantics apply.

The MS Connect bug implies that a type safety issue, but there's no problem that I can see [1].

This is incredibly frustrating, because interfaces are the only way to design certain extension methods (mixin-style). For instance, suppose we have a set of simple interfaces:

// marks a class as containing a parseable parameter of type T
public interface IParseable<T>
{
   HttpRequest Request { get; }
}
// continuation parameters are parseable
public interface IContinuation<T> : IParseable<T> { }
public interface IContinuation<T0, T1> : IParseable<T0>, IParseable<T1> { }
...

This is a perfectly sensible set of type definitions, and there is no ambiguity or type safety problem here, even if a class were to implement IContinuation<int, int>.

If anyone has any suggestions for workarounds, I'm all ears. Options that don't work:

Can't turn IParseable into a struct/class with an implicit conversion, because implicit conversions don't work on interfaces.
Can't define MxN overloads of the extension methods defined on IParseable, where N=number of IContinuation type definitions, and M=number of type parameters (although this actually has a shot of working, the code duplication is just ludicrous).

A Partial Solution

The best solution I have involves N overloads of the extension methods by implementing interfaces that designate type parameter positions:

// type param at index 0
public interface IParam0<T> { }
// type param at index 1
public interface IParam1<T> { }
// type param at index 2
public interface IParam2<T> { }
...
// continuations  have indexed type parameters
public interface IContinuation<T> : IParam0<T> { }
public interface IContinuation<T0, T1> : IParam0<T0>, IParam1<T1> { }
...

Now instead of defining extension methods on IParseable, I define an overload per IParamX interface (N overloads, 1 per type parameter).

This necessarily causes an ambiguity when two type parameters unify, since the compiler won't know whether you wanted to call the extension on IParam0<int> or IParam2<int>, but this ambiguity happens at the call site/at type instantiation, instead of type definition. This is a much better default [1], because you can actually do something about it by disambiguating manually. I've eliminated ambiguity entirely in my library by appending the type parameter index to the extension method name.

Of course, none of this boilerplate would have been necessary if type unification were supported.

[1] If the CLR supported type inequalities, instead of just type equalities, then we could just forbid this at the point ObserveTwo is created.

[2] EDIT 2011-11-13T11:45 AM: there's been some confusion about this statement. Doug McClean rightly points out that there's no guarantee that the two implementations are confluent, so unifying is not an "automatic" thing, so please don't take this to mean that I'm saying the compiler should be able to automatically "merge" methods somehow, or magically know which implementation to dispatch to based on context. This is undecidable in general.

Also, even if the interfaces require no implementation, the error still occurs, despite reduction being Church-Rosser. Finally, plenty of nice properties are violated on the CLR, so I'm not sure why also sacrificing confluence is such a big deal here. A sensible dynamic semantics, like always dispatching to the implementation for T0 in case of type parameter unification, restores most of the desirable properties without sacrificing expressiveness, and without going whole-hog and ensuring confluence via type inequalities [1].

Ad-hoc Extensions in .NET

2011-11-01T16:34:00.000-04:00

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 in missing a case and thus triggering a runtime exception, a danger inheritance does not have.

Furthermore, we'd have to repeat the large set of runtime type tests for each operation we want to add to A, B, ... Z, which means every time we want to add an operation we have to do a large copy-paste, and every time we add a new class we have to update every place we test types, and the compiler doesn't warn us when we're missing a case.

A Solution

Fortunately, there's a straightforward way to address at least part of this problem. We can collect all the type tests we have to do in one place, and we can ensure that we have properly handled all cases that we are aware of. To do this, we combine the standard visitor pattern with the CLR's open instance delegates and its unique design for generics.

Here are the types:

// the interface encapsulating the operation to implement, ie. Foo()
public interface IOperation
{
  void A(A obj);
  void B(B obj);
  ...
  void Z(Z obj);
  void Unknown(object obj);
}
// the static dispatcher where runtime tests occur
public static class Dispatcher<T>
{
  static Action<IOperation, T> cached;
  public static Action<IOperation, T> Dispatch
  {
    get { return cached ?? (cached = Load()); }
  }
  static Action<IOperation, T> Load()
  {
    var type = typeof(T);
    var mName = type == typeof(A) ? "A":
                type == typeof(B) ? "B":
                        ...
                                  ? "Unknown";
    var method = typeof(IOperation).GetMethod(method);
    return Delegate.CreateDelegate(typeof(Action<IOperation, T>), null, method)
             as Action<IOperation, T>;
  }
}

If you want to extend A, B, ... Z, with any operation, you simply create a class that implements IOperation and the compiler will ensure you handle all known cases. If you want to add a class to the set of handled cases, you simply extend IOperation and add a case to the runtime type tests (or if you use a naming convention, you can just use the class name as the method name).

The dynamic type test runs once, and then a delegate that directly calls into the IOperation is cached, so the type tests are not run again.

If you try to dispatch on an unknown type, IOperation.Unknown is invoked. I could have made this a generic method, but the CLR currently has a bug creating open instance delegates to generic interface methods, so that would require some code generation to do properly.

There is a caveat though: if any of the cases are subtypes of each other, and you dispatch on the static base type, it will dispatch to the base type and not the super type handler. For instance, if A:B, and you call Dispatcher<B>.Dispatch(new A()), IOperation.B is called, not IOperation.A. This can be handled in various ways, but it's beyond the scope of this article. I may post a follow-up discussing the various options.

Extensions

Type Constraints on T

If all types to handle are subtypes of type X, then it's simple to constrain the type parameter T on Dispatcher<T>:

 public static class Dispatcher<T>
  where T : X
{
  ...
}

Operation Return Type

You could extend IOperation with a return type, but this requires propagating the return type parameter into Dispatcher and the cached delegate type, and thus requires more runtime state for more static fields. This is because the CLR doesn't support GADTs, so following this paper, I prefer to keep the return type encapsulated in IOperation and expose it as a public field for the caller to extract the value:

public sealed class Foo : IOperation
{
  // the return value
  public Bar ReturnValue { get; set; }
  public void A(A obj) { ... }
  ...
}

This requires fewer type parameters, and keeps the implementation simple.

Per-Class Overrides

Suppose some of the classes you are handling are your own, or are already aware of your code such that they have already implemented your custom operations. In that case, you can specify a companion interface to indicate this, and modify the dispatch code to invoke the interface instead:

public interface ICompanion<T>
{
  // your custom operations that are implemented via subclassing
  void Foo(IOperation operation, T self);
  ...
}

The dispatch code is then modified like so:

static Action<IOperation, T> Load()
{
  var type = typeof(T);
  // if companion interface is implemented, then dispatch directly into it
  if (typeof(ICompanion<T>).IsAssignableFrom(type))
  {
    var method = type.GetMethod("Foo");
    return Delegate.CreateDelegate(typeof(Action<IOperation, T>), null, method)
             as Action<IOperation, T>;
  }
  // the usual dispatch code
  ...

Useful Applications

This pattern simulates the usefulness of type classes in Haskell, because these are essentially ad-hoc extensions added after the fact. I use this exact pattern in Sasa.Dynamics to implement safe type case and reflection patterns over the CLR primitive types, ie. ints, strings, delegates, etc., with the per-class override extension described above via the IReflected interface.

The Most General Concurrent API

2011-10-24T17:06:00.000-04:00

Concurrent programming is hard, and many abstractions have been developed over the years to properly manage concurrent resources. The .NET base class libraries have mutexes, spinlocks, semaphores, compare-and-set (CAS) instructions, and more.

The Problem

Unfortunately, many of these standard abstractions are rather opaque, so predicting their behaviour is difficult, and enforcing a particular thread schedule is nearly impossible. For example, consider the issue of "fairness". Many abstractions to deal with threads are not fair, which is to say that they are not guaranteed to release threads in FIFO order, so a thread could starve.

Furthermore, these opaque abstractions do not allow the application to easily specify domain-specific scheduling behaviour. Suppose threads T0, T1, and T2 are blocked on a resource X, in that order. X becomes available, and according to FIFO order, T0 should acquire control next. However, a domain-specific requirement may state that T2 should be processed first, but there is no way to check the wait queue for the presence of T2 when using any of .NET's thread abstractions. We'd have to build some auxiliary data structures to log the fact that T2 is waiting for X, and force T0 and T1 to relinquish their control voluntarily, but these data structures already exist as the locking queue, so we're duplicating work. Furthermore, both T0 and T1 must run before T2 to relinquish control, so we're wasting valuable CPU time. It's rather wasteful all around.

What I want to cover here is a pattern consisting of a few simple primitives which forms a general concurrent API. Using this API, we can easily implement all of the above threading abstractions, while still allowing arbitrary scheduling policies. I devised this approach while developing a software transactional memory (STM) library for C#, since STM requires deadlock detection and is rather sensitive to scheduling policies. None of this is achievable using the standard concurrent abstractions on the CLR, without modifying the VM.

The paper entitled Light-weight Locks really crystallized the path I was on, and gelled the final components I was missing into an elegant, general solution. The solution I present here is merely one of the abstractions found in that paper.

The Solution

The fundamental primitives needed for a more flexible concurrent API are few: Interlocked.CompareExchange, AutoResetEvent, and ThreadStaticAttribute.

The approach is simple, and consists of only three fundamental concepts:

A lock-free list is associated with each resource being accessed concurrently. If structured as I describe below, managing this list requires no memory allocation.
An AutoResetEvent is associated with each Thread via thread-static data. Each time the thread must block, it calls WaitOne on its own AutoResetEvent after pushing itself onto the resource's lock-free list.
A thread releasing its control of a resource walks the list of waiting threads, and wakes up the ones that should assume control next by calling Set on that Thread's AutoResetEvent.

AutoResetEvent is fundamentally thread-safe, and serves as a combined signal and mutex, and the only other point of contention is the lock-free list. The list requires only one CAS to push a waiter on the front, and occasionally a CAS to pop the front element [1].

Using only the above, we can construct a mutex abstraction, like Monitor, that allows exclusive access to a resource, but permits arbitrary scheduling policy, such as FIFO, LIFO, or something custom (like priorities that don't suffer from inversion). Even more, this requires no allocation at runtime. Here's all we need [2]:

// the thread-static data
class MetaThread
{
  // the kernel signal+mutex to wait on
  public AutoResetEvent Signal { get; private set; }
  // the next MetaThread in whatever list this
  // MetaThread happens to be on at the time
  public MetaThread Next { get; private set; }
  [ThreadStatic]
  public static MetaThread Current { get; private set; }
}
// some resource T that requires mutually
// exclusive access
class Locked<T>
{
  T value;
  MetaThread owner;
  MetaThread blocked;
}

What makes this work is the property that a thread can only be on one blocked list at any given time. This means we need only one piece of thread-static data to track which list it's on, and one AutoResetEvent to block and unblock the thread. Now suppose Locked has two public operations: Enter and Exit, which mimic the behaviour of Monitor.Enter and Monitor.Exit [3]:

class Locked<T>
{
  ...
  public void Enter()
  {
    var thread = MetaThread.Current;
    // push current thread onto wait list
    do thread.Next = blocked;
    while (thread.Next != Interlocked.CompareExchange(ref blocked, thread, thread.Next));
    // if owner is null, then try to acquire lock; if that fails, block
    if (owner != null || null != Interlocked.CompareExchange(ref owner, thread, null))
    {
      next.Signal.WaitOne();
    }
    Unblock(thread); // remove from blocked list
  }
  public void Exit()
  {
    // retry if no candidate acquired the lock, but the
    // blocked list has since become not empty
    MetaThread next;
    do {
      next = SelectNext();
      Interlocked.Exchange(ref owner, next);
    } while (next == null && blocked != null);
    if (next != null) next.Signal.Set(); // resume the thread
  }
  protected virtual MetaThread SelectNext()
  {
    ...
  }
}

The SelectNext method can provide a variety of domain-specific selection behaviour, such as LIFO, FIFO, etc. to dequeue the next lock owner. All that's required is that the thread releasing the resource select the candidate from the list and assign the lock to it, and then signal it to continue via AutoResetEvent. Unblock is not shown for brevity, but it's not too complicated.

The paper I linked to above uses this pattern to implement all the common concurrency abstractions, using very compact structures (2 bytes per mutex, 4 bytes per rw-lock, 4-bytes per condition variable).

I use it in my STM library to dynamically detect deadlocks and abort transactions, and I will soon extend this to implement reader-writer lock semantics similar to a pessimistic version of TLRW.

Regardless, associating a kernel AutoResetEvent, or pthread signal+mutex on Linux, permits far more flexible and compact concurrency primitives. I recommend this "MetaThread" API be exposed in any language's standard threading library.

The Future

This design can also inform the design of concurrency abstractions in kernels. Consider a reader-writer lock where a writer currently has exclusive access to the resource, and a list of N readers is waiting for the release of the lock. The writer must then invoke AutoResetEvent.Set N times, once for each waiting reader. That's N user-kernel transitions, which can be quite expensive for large N [4].

The ideal solution would be to group a number of individual AutoResetEvents so we only need to make one user-kernel transition to signal the whole group, sort of like a multicast for EventWaitHandles. This would provide efficient single thread and multithread suspend/resume semantics.

Footnotes

[1] A CAS may be needed to remove elements further in the list if more than one thread can operate on a resource at a time.
[2] I'm skipping a few steps to simplify the presentation. MetaThread.Current must actually be lazily-initialized. If I were starting a new programming language, this structure would be part of the standard Thread abstraction. Furthermore, when implementing abstractions which allow multiple threads through, you will probably need more synchronization. For instance, a reader-writer lock requires an atomically incremented/decremented read counter. See the paper linked above for more details.
[3] I'm again simplifying here for presentation, so I apologize for any errors. This code is adapted from my STM library, so I haven't tested this version thoroughly, but it's at least derived from correct code. There are many optimizations to avoid redundant CAS operations, but this is the simplest presentation.
[4] N here is the number of threads, which in general are probably less than a hundred, even for heavily threaded workloads. Still, user-kernel transitions can cost upwards of 1,000 cycles, so wasting 100,000 cycles is nothing to scoff at.

ThreadScoped The Next Generation

2011-09-28T00:07:00.000-04:00

Jeroen Frijters helpfully pointed out that the CLR implements some hard limits on nesting generics, which is 99 for .NET 4 based on my tests. My previous implementation of ThreadScoped<T> was thus limited to 99 instances. Not very useful!

The solution is actually quite simple, which I briefly outlined on Jeroen's blog: add more type parameters and use a simple base-99 counting scheme to generate new instances. Each additional type parameters thus increases the permutations 99 fold. One type index parameter yields 99¹ instances, two type index parameters yields 99² instances, three type index parameters yields 99³, and so on.

No one in the foreseeable future will require more than 99³, which is almost a million thread-local variables, so I've added two more type index parameters to make Ref<T0, T1, T2>. The instance allocation function is now:

internal override ThreadScoped<T> Allocate()
{
    // If 'next' is null, we are at the end of the list of free refs,
    // so allocate a new one and enqueue it, then return 'this'
    var x = next;
    if (x != null) return this;
    // The CLR has some fundamental limits on generic nesting depths, so we circumvent
    // this by using two generic parameters, and nesting them via counting.
    x = Interlocked.CompareExchange(ref next, CreateNext(), null);
    // atomic swap failure doesn't matter, since the caller of Acquire()
    // accesses whatever instance is at this.next
    return this;
}

and CreateNext is:

ThreadScoped<T> CreateNext()
{
    var x = allocCount + 1;
    if (x % (99 * 99) == 0) return new Ref<T, T, Ref<T2>> { allocCount = x };
    if (x % 99 == 0)        return new Ref<T, Ref<T1>, T2> { allocCount = x };
    return new Ref<Ref<T0>, T1, T2> { allocCount = x };
}

This is simple base-99 arithmetic. Anyone familiar with arithmetic should recognize the pattern here: when we get to certain multiples of 99, we reset the previous digits and carry the 1 to the next slot. Normally, humans deal in base-10, so a carry happens at 10¹, 10², 10³, and so on.

In this case, we are dealing with base-99, so carries happen at 99¹, 99² and 99³, and the "carry" operation consists of nesting a generic type parameter. Simple!

This scheme is also trivially extensible to as many additional parameters as is needed, so if someone somewhere really does need more than a million fast thread-local variables, I have you covered.

These changes don't seem to have impacted the performance of ThreadScoped<T>, so I'm still over 250% faster than the ThreadLocal<T> provided in .NET 4's base class libraries.

Faster Thread-Local Data with ThreadScoped

2011-09-27T00:18:00.000-04:00

Awhile ago, Jeroen Frijters blogged about .NET 4's new ThreadLocal<T>, and how it was implemented. It was based on a neat generics trick exploiting the fact that the CLR does not erase types. Indexing a generic type X with a type T, means X<string> has distinct static and thread-local fields from say, X<int>.

I've actually used this trick before to implement a type of safe reflection.

Jeroen's sample implementation exploiting this trick for thread-local instance variables seemed far too complicated however, and it suffered from a number of limitations that he notes in his post. If Microsoft's implementation was even more complicated as was claimed, I wasn't confident it would perform very well at all. I decided to do my own implementation, without conforming the ThreadLocal<T>'s interface since I have very specific applications in mind.

ThreadScoped<T>

As I suspected, my implementation was considerably simpler, coming in at less than 90 lines of code, and it doesn't suffer from the problems that Jeroen identifies, save for the fact generated types are not reclaimed until the AppDomain exits. However, ThreadScoped instances are aggressively reused, so I don't anticipate this to be a huge problem.

Conceptually, the implementation is quite simple. We have four views to keep in mind here:

Thread-global static data: ordinary static fields that are thus visible by all threads.
Thread-global instance data: ordinary object fields visible to all threads with access to that instance.
Thread-local static data: static fields marked with [ThreadStatic], giving a thread-specific view of that field.
Thread-local instance data: not provided natively by the CLR, but simulated by ThreadLocal<T> and ThreadScoped<T> via thread-local static data + generics.

Our thread-global static data consists of a lock-free linked list of unallocated ThreadScoped instances. Our thread-global instance data is a version number, and a 'next' pointer that points to the next available ThreadScoped<T>. This is used when freeing an instance by pushing it on the global list. Accessing the global and instance data are all done via Interlocked.CompareExchange, so all updates are lock-free.

Now comes the tricky part: the private type ThreadScoped<T>.Ref<TIndex> has two static fields, one for the value T and one for a version number (more on this later):

sealed class Ref<TIndex> : ThreadScoped<T>
{
  [ThreadStatic]
  static T scoped;     // the unique thread-local slot
  [ThreadStatic]
  static uint version; // the version number of the thread-local data
}

The type parameter TIndex is not actually used in a static or instance field, it's merely used here as a "phantom type". Basically, if we keep substituting new types for TIndex, we'll keep forcing the CLR to generate new thread local static fields for us that we can use to simulate thread-local instance fields!

This is done in the Ref<TIndex>.Allocate() method. The global instance list always contains at least one unallocated instance. Whenever we try to allocate a new ThreadScoped<T>, we check whether we're down to the last instance in the list. If so, this last instance will generate a Ref<Ref<TIndex>> and enqueue that on the end:


internal override ThreadScoped<T> Allocate()
{
    // if 'next' is null, we are at the end of the list of free refs,
    // so allocate a new one and enqueue it, then return 'this'
    var x = next;
    if (x != null) return this;
    x = Interlocked.CompareExchange(ref next, new Ref<Ref<TIndex>>(), null);
    // atomic swap failure doesn't matter, since the caller of Acquire()
    // accesses whatever instance is at this.next
    return this;
}

ThreadScoped.Create then pops the front of the list to obtain the next to last instance, and we're back to only having one unallocated instance.

There's an important invariant here: there is always at least one item in the global list, and the last item on the global list is always the most deeply nested generic type that has been generated so far for ThreadScoped<T>. This means when we get to the last remaining unallocated instance, we can always safely generate a new instance without interfering with other threads.

The version numbers also bear some explanation. Basically, even if Thread0 disposes of an ThreadScoped instance, Thread1 may have data sitting in that instance. Suppose that the ThreadScoped instance is then pushed on the free list, and then allocated again. If Thread1 participates in that second computation, it will already find data sitting in its supposedly fresh thread-local instance from the last computation where it was supposed to have been disposed!

Obviously this is not what we want, but while Thread0 is disposing of the instance, it can't access Thread1's thread-local fields to clear them. This is the purpose of the instance and the thread-local version numbers. During dispose, we increment the instance's version number. If the thread-local version number and the instance version number don't match, it means the instance was disposed in the intervening time, so we should reinitialize it before proceeding:

public override T Value
{
    get { return current == version ? scoped : Update(); }
    set { scoped = value; }
}
T Update()
{
    if (next != this) throw new ObjectDisposedException("Transacted<T> has been disposed.");
    version = current;
    return scoped = default(T);
}

And that's it! There are a few other minor details related to book keeping that aren't really important. I think that's pretty much as simple as you can get, and since this results in effectively a direct pointer to thread-local data, it should be quite fast. There are also no intrinsic allocation limits, as it will just keep allocating or reusing instances as needed.

Benchmarks

Here is the source for the benchmarks I used. The main loop runs 10,000,000 iterations of a simple calculation that performs one read and one write to the thread-local instance per iteration. I ran this test 20 times in a loop, logging the number of iterations per second on each run. Then I used Peirce's Criterion to filter out the outliers, and used the resulting data set.

The numbers are iterations/second, benchmarks were run on .NET 4 and Windows 7. The results are fairly compelling:

	*ThreadLocal<T>*	*ThreadScoped<T>*	*ThreadStatic*
	5022000	16260000	22396000
	5042000	14378000	18484000
	4972000	16514000	20790000
	5002000	15722000	22470000
	5070000	14244000	19860000
	5098000	13946000	16570000
	5076000	16474000	22246000
	5102000	13994000	20532000
	5012000	13494000	14482000
	5108000	16090000	21598000
	5074000	16778000	20000000
	5104000	15408000	21620000
	5076000	12762000	16312000
	5054000	16792000	21008000
	5064000	16380000	21856000
	5108000	16154000	15910000
	5066000	16750000	22988000
	5108000	16076000	18778000
	5012000	15986000	23094000

*MIN*	4972000	12762000	14482000
*MAX*	5108000	16792000	23094000
*AVG*	5061579	15484316	20052316
% Overhead relative to ThreadStatic	296%	29%	0%

Microsoft's implementation takes a real beating in this simple benchmark with almost 300% overhead over raw ThreadStatic fields. I'm not sure what could be going on in there to cause such a significant slowdown

By contrast, ThreadScoped has a modest 30% overhead, which is far more reasonable. I suspect this overhead is due to two factors: 1. virtual dispatch overhead because ThreadScoped.Value is a virtual property, and 2. the encapsulated instance for Ref <TIndex> may require a bit of pointer-chasing to resolve the right thread-local static field. I can't think of a way to eliminate this overhead, so this is as good as it's going to get for now.

I will note that I've had a few programs where ThreadLocal<T> did not perform as badly as demonstrated above, so it may be that reads or writes are more penalized. However, no benchmark or program I tested had ThreadLocal outperforming ThreadScoped, so I can say with confidence that ThreadScoped is much faster than ThreadLocal.

Jeroen's post also implied that he had tested a ThreadLocal version that used arrays for the backing store, and that it was faster. I also implemented a version of ThreadScoped using arrays, but haven't tested it enough. It did seem quite a bit faster with some code I had been playing with, but there were many uncontrolled variables, so I can't reach any conclusion with any confidence. The array-backed version is commited to the Sasa repository for the adventurous though. There are serious limitations with using arrays as a backing store however, namely that you're stuck with a fixed number of instances defined at compile-time, and allocating large enough arrays to avoid falling back on slow thread-local data wastes quite a bit of memory.

Still, I will run some benchmarks at some future date, so stay tuned! As for ThreadScoped<T>, it will probably be in the next Sasa release coming in a month or two, or you can just grab it from the Mercurial repo.

Idioms in C# with LINQ

2011-09-25T11:46:00.000-04:00

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 = SomeFoo.SelectMany(x => x.Values, (x, y) => y);

This is a purely syntactic transformation, meaning that the C# compiler simply takes the text from above, and naively translates each 'from', 'where', 'select', etc. into calls to instance or extension methods, SelectMany, Where, Select, etc. Type inference must then be able to infer the types used in your query, and everything must type check.

The fact that we're dealing with a purely syntactic transform means that we can be sneaky and alter the signatures of these LINQ functions and the C# compiler would be none the wiser. The resulting calls to the LINQ methods would still need to compile, but we can ensure that they only compile following the rules we want, in this case, of the rules of idioms.

LINQ Methods

The core LINQ methods are as follows, using Formlet<T> as the LINQ type:

Formlet<R> Select<T, R>(this Formlet<T> f, Func<T, R> selector);
Formlet<R> SelectMany<R>(this Formlet<T> f,
                              Func<T, Formlet<R>> collector);
Formlet<R> SelectMany<U, R>(this Formlet<T> f,
                                 Func<T, Formlet<U>>
                                 Func<T, U, R> selector);

The problematic methods for idioms are the two SelectMany calls, specifically, the parameter I've called 'collector'. You can see that the LINQ type is unwrapped and the value extracted on each SelectMany, and passed to the rest of the query. Accessing the previous values like this is forbidden in idioms.

Fortunately, the signatures for SelectMany don't have to have this exact signature, they must only have a similar structure. You must have two SelectMany overloads with one and two delegate parameters, and the first delegate parameter must return your LINQ type, in this case Formlet<T>, as this allows you to chain query clauses one after another. You can also modify the second delegate parameter in various ways, but I haven't found much use for that myself.

To implement idioms, we will simply alter the first delegate parameter so instead of unwrapping the value encapsulated by the Formlet<T>, we simply pass the Formlet<T> itself:

Formlet<R> Select<T, R>(this Formlet<T> f, Func<T, R> selector);
Formlet<R> SelectMany<R>(this Formlet<T> f,
                              Func<Formlet<T>, Formlet<R>> collector);
Formlet<R> SelectMany<U, R>(this Formlet<T> f,
                                 Func<Formlet<T>, Formlet<U>> collector,
                                 Func<T, U, R> selector);

Our query above:

var foo = from x in SomeFoo
          from y in foo.Values
          select y;

would then no longer compile, because 'x' is now not a Foo, but is in fact a Formlet<Foo>, and the formlet type does not have a "Values" property. Of course, you shouldn't provide a property to extract the encapsulated value, or this is all for naught.

The Downsides

Simple queries work great, but longer queries may run into some problems if you alter the LINQ signatures. In this case, if you try to access previous values by mistake, as in our example query above, you will get a complicated error message:

Error 1       Could not find an implementation of the query pattern for source type 'Formlet.Formlet<AnonymousType#1>'. '<>h__TransparentIdentifier0' not found.

Basically, your incorrect program was naively translated to use the LINQ methods, but because it does not properly match the type signatures you've hijacked, type inference fails. So you can't break your idioms by hijacking the query pattern this way, but depending on your target audience, perhaps you will render them unusable.

Still, it's a neat trick that should be in every type wizard's toolbox.

IObservable and Delegate Equality

2011-09-17T13:34:00.000-04:00

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:
// Observable Equality: False

This is unfortunate, because it means that by default we cannot implement previous event handling patterns using IObservable without significantly restructuring the code to propagate the IDisposable returned by IObservable.Subscribe. By this, I mean code that properly managed event registration and unregistration has no easy transition to using IObservable, it must be completely rewritten.

Like event equality, the equality of IObservers created from delegates should be structural, not based on identity. Thus, manually managing subscriptions would be possible via an explicit "Unsubscribe" operation.

This decision has a real consequence that I just hit: I can implement IObservable given an object implementing INotifyPropertyChanged, but could not do the reverse using the built-in abstractions. You'd either have to define your own IObservers that implement structural equality, or you'd have to store the actual event locally and trigger it manually when a new value is available, as I have done with NamedProperty<T> in Sasa.

On a slightly related note, I've switched Sasa over to use Mercurial on Sourceforge, and have closed the old subversion repo.

Open Instance Delegate for Generic Interface Methods

2011-08-21T14:59:00.000-04:00

Ran into a snag when developing the latest abstraction for Sasa. The problem is distilled to its simplest form in this Stack Overflow question.

In summary, while the CLR supports open instance delegates to interface methods, and supports delegates to generic interface methods, it does not seem to support the composition of the two, ie. an open instance delegate to a generic interface method.

The following trivial example fails when creating the delegate with a NotSupportedException:

interface IFoo
{
  void Bar<T>(T j);
}
class Foo : IFoo
{
  public void Bar<T>(T j)
  {
  }
}
static void Main(string[] args)
{
  var bar = typeof(IFoo).GetMethod("Bar").MakeGenericMethod(typeof(int));
  var x = Delegate.CreateDelegate(typeof(Action<IFoo, int>), null, bar);
}

However, the CLR does support open instance delegates to generic class methods. For some reason interfaces are singled out here, and it's not clear why.

If I'm doing something wrong, please let me know!

Edit: I submitted a bug to Microsoft Connect, since this now looks like a legit bug.

Edit 2: MS acknowledged the limitation, but said it wouldn't be solved in the current version of .NET. As I explain in that bug, this limitation just doesn't seem to make sense, but it must be due to the internals that don't reuse the existing CLR dispatching logic.

Sasa v0.9.3 Released!

2010-12-05T21:59:00.001-05:00

I recently realized that it's been over a year since I last put out a stable Sasa release. Sasa is in production use in a number of applications, but the stable releases on Sourceforge have lagged somewhat, and a number of fixes and enhancements have been added since v0.9.2.

So I decided to simply exclude the experimental and broken abstractions and push out a new release so others could benefit from everything Sasa v0.9.3 has to offer.

The changelog contains a full list of changes, too numerous to count. I'll list here a few of the highlights.

IL Rewriter

C# unfortunately forbids certain types from being used as generic type constraints, even though these constraints are available to CIL. For instance, the following is legal CIL but illegal in C#:

public void Foo<T>(T value)
 where T : Delegate
{
 ...
}

Sasa now provides a solution for this using its ilrewrite tool. The above simply uses the Sasa.TypeConstraint<T> in the type constraint and the rewriter will erase all references to TypeConstraint leaving the desired constraints in place:

public void Foo<T>(T value)
 where T : TypeConstraint<Delegate>
{
 ...
}

The Sasa library itself makes pervasive use of these type constraints to provide generic versions of static functions on System.Enum, thread-safe delegates add/remove, null-safe delegate calls, and more.
Simply call ilrewrite like so:

ilrewrite /verify /dll:[your dll] /[Debug | Release]

The /verify option runs peverify to ensure the rewrite produced verifiable IL. Pass /Debug if you're rewriting a debug build, and /Release if you're rewriting a release build. I have it set up as a Visual Studio post-build event, so I call it with /$(ConfigurationName) for this parameter.

Thread-safe and Null-Safe Event Handling

The CLR provides first-class functions in the form of delegates, but there are various problems that commonly creep up which Sasa.Events is designed to fix:

Invoking delegates is not null-safe

Before invoking a delegate, you must explicitly check whether the delegate is null. If the delegate is in a field instead of a local, you must first copy the field value to a local or you leave yourself open to a concurrency bug, where another thread may make the field null between the time you checked and the time you call it (this is commonly known as a TOCTTOU bug, ie. Time-Of-Check-To-Time-Of-Use).

This involves laborious and tedious code duplication that the C# compiler could have easily generated for us. The Sasa.Events.Raise overloads solve both of the above problems. Instead of:

var dlg = someDelegate;
if (dlg != null) dlg(x, y, z);

you can simply call:

someDelegate.Raise(x, y, z);

This is null-safe, and thread-safe.

Event add/remove is not thread-safe

Events are a pretty useful idiom common to .NET programs, but concurrency adds a number of hazards for which the C# designers provided less than satisfactory solutions.

For instance, declaring a publicly accessible event creates a hidden "lock object" that the add/remove handlers first lock before modifying the event property. This is not only wasteful in memory, it's also expensive in highly concurrent scenarios. Furthermore, this auto-locking behaviour is completely different for code residing inside the class as compared to code outside the class. Needless to say, this unnecessarily subtle semantics was constantly surprising C# developers.

Enter Sasa.Events.Add/Remove. These overloads accept a ref to a delegate field, and perform an atomic compare and exchange on the field directly, eliminating the need for lock objects, and providing more scalable event registration/unregistration. Code that looked like this:

event Action fooEvent;
...
fooEvent += newHandler;

or like this:

event Action fooEvent;
...
lock (this) fooEvent += newHandler;

can now both be replaced by this:

Action fooEvent;
...
Events.Add(ref fooEvent, newHandler);

This code has less overhead than the standard event registration code currently generated by any C# compiler, in both concurrent and non-concurrent settings.

Safe, Statically-Typed and Blazingly-Fast Reflection

Reflection is incredibly useful, and incredibly dangerous. You are forced to work with your objects as untyped data which makes it difficult to write correct programs, and the compiler can't help you.

Most operations using reflection are functions operating over the structure of types. To make reflection safe, we only need a single reflective function that breaks apart an object into a stream of field values. The client then provides a stream processing function (the reflection function) that handles all the type cases that it might encounter.

Sasa.Dynamics is here to help. Type<T>.Reflect is a static reflection function for type T which breaks up instances of type T into its fields (use DynamicType.Reflect if you're not sure of the concrete type).

The client need only provide an implementation of IReflector, which defines a callback-style interface completely describing the CLR's primitive types and providing you with an efficient ref pointer to the field's value for get/set purposes, and a FieldInfo instance providing access to the field's metadata:

public interface IReflector
{
    void Bool(ref bool field, FieldInfo info);
    void Int16(ref short field, FieldInfo info);
    ...
    void Object<T>(ref T field, FieldInfo info);
}

The compiler ensures that you handle every case in IReflector. You handle non-primitive objects in IReflector.Object<T>, by recursively calling DynamicType.Reflect(field, this, fieldInfo).

Type<T> and DynamicType use lightweight code generation to implement a super-fast dispatch stub that invokes IReflector on each field of the object. These stubs are cached, so over time the overhead of reflection is near-zero. Contrast to the typical reflection overheads, and not only is this technique safer, it's significantly faster as well.

Extensible, Statically-Typed Turing-Complete Parsing

I covered the implementation of the Pratt parser before, and the interface has changed only a little since then. Pratt parsing is intrinsically Turing complete, so you can parse literally any grammar. The predefined combinators are for context-free grammars, but you can easily inject custom parsing functions.

What's more, each grammar you define is extensible in that you can inherit from and extend it in the way you would any other class. Here is a grammar from the unit tests for a simple calculator:

abstract class MathSemantics<T> : Grammar<T>
{
   public MathSemantics()
   {
       Infix("+", 10, Add);   Infix("-", 10, Sub);
       Infix("*", 20, Mul);   Infix("/", 20, Div);
       InfixR("^", 30, Pow);  Postfix("!", 30, Fact);
       Prefix("-", 100, Neg); Prefix("+", 100, Pos);

       Group("(", ")", int.MaxValue);
       Match("(digit)", char.IsDigit, 1, Int);
       SkipWhile(char.IsWhiteSpace);
   }

   protected abstract T Int(string lit);
   protected abstract T Add(T lhs, T rhs);
   protected abstract T Sub(T lhs, T rhs);
   protected abstract T Mul(T lhs, T rhs);
   protected abstract T Div(T lhs, T rhs);
   protected abstract T Pow(T lhs, T rhs);
   protected abstract T Neg(T arg);
   protected abstract T Pos(T arg);
   protected abstract T Fact(T arg);
}

The unit tests then contain an implementation of the grammar which is an interpreter:

sealed class MathInterpreter : MathSemantics<int>
{
   protected override int Int(string lit) { return int.Parse(lit); }
   protected override int Add(int lhs, int rhs) { return lhs + rhs; }
   protected override int Sub(int lhs, int rhs) { return lhs - rhs; }
   protected override int Mul(int lhs, int rhs) { return lhs * rhs; }
   protected override int Div(int lhs, int rhs) { return lhs / rhs; }
   protected override int Pow(int lhs, int rhs) { return (int)Math.Pow(lhs, rhs); }
   protected override int Neg(int arg) { return -arg; }
   protected override int Pos(int arg) { return arg; }
   protected override int Fact(int arg)
   {
       return arg == 0 || arg == 1 ? 1 : arg * Fact(arg - 1);
   }
}

Instead of interpreting directly, you could just as easily have created a parse tree.

The tests also contain an extended grammar that inherits from MathSemantics and adds lexically-scoped variables (see EquationParser at the link):


sealed class EquationParser : MathSemantics<Exp>
{
   public EquationParser()
   {
       Match("(ident)", char.IsLetter, 0, name => new Var { Name = name });
       TernaryPrefix("let", "=", "in", 90, Let);
   }
...
}

MIME Parsing

Sasa contains a simple stand-alone assembly devoted to MIME types, file extensions, and functions mapping between the two (Sasa.Mime).

The Sasa.Net.Mail namespace in the Sasa.Net assembly, contains functions for parsing instances of System.Net.Mail.MailMessage from strings, including attachments in every encoding I've come across in the past few years. This code has been in production use in an autonomous e-mail processing program which has processed tens of thousands of e-mails over many years, with very few bugs encountered.

It can also format MailMessage instances into string form suitable for transmission over texty Internet protocols.

Miscellaneous

The library is also better factored than before, and has numerous handy extensions to IEnumerable/LINQ, strings, numbers, tuples, endian encoding, url-safe binary encoding, some purely functional collections, easy file system manipulation (first described here), Stream extensions (including stream-to-stream copying), endian-aware binary encoding, non-blocking futures, atomic exchange extensions, non-nullable types, lazy types, statically typed weak refs, code generation utilities (first described here), statistical functions, and much more.

The full docs for this release are available online.

Deprecated

Unfortunately, the efficient, compact binary serializers from the last release have been deprecated, and the replacements based on Sasa.Dynamics are not yet ready. The ASP.NET page class that is immune to CSRF and clickjacking attacks first released in v0.9 has been removed for now as well, since it depended on the compact binary serializer.

I have plenty of new developments in the pipeline too. 2010 saw many interesting safety enhancement added to Sasa as outlined above, and 2011 will be an even more exciting year I assure you!

Edit: the original download on sourceforge was missing the ilrewrite tool. That oversight has now been addressed.

Abstracting Computation: Arrows in C#

2010-11-26T21:43:00.000-05:00

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.

Factoring Out Common Patterns in Libraries

2010-11-06T10:36:00.000-04:00

A well designed core library is essential for building concise, maintainable programs in any programming language. There are many common, recurrent patterns when writing code, and ideally, these recurring uses should be factored into their own abstractions that are distributed as widely as possible throughout the core library.

Consider for instance, an "encapsulated value" pattern:

/// <summary>
/// A read-only reference to a value.
/// </summary>
/// <typeparam name="T">The type of the encapsulated value.</typeparam>
public interface IValue<T>
{
 /// <summary>
 /// A read-only reference to a value.
 /// </summary>
 T Value { get; }
}

This shows up everywhere, like Nullable<T>, Lazy<T>, and Task<T> (property called "Result"), IEnumerator<T> (property called "Current"), and many many more.

However, the common interface of a value encapsulated in an object has not been factored out into a common interface in the .NET Base Class Library (BCL). This means one cannot write programs that are agnostic over the type of a value's container, resulting in unnecessary code duplication.

A legitimate argument against this approach is that the containers each have different semantics. For instance, accessing Lazy.Value will block until the value becomes available, but Nullable.Value always returns immediately.

Fortunately, this is not an argument against factoring out the "encapsulated value" pattern, but an argument for another interface that exposes these semantics. In this case, the new pattern is an "optional value":

/// <summary>
/// A volatile value.
/// </summary>
/// <typeparam name="T">The type of value held in the reference.</typeparam>
public interface IVolatile<T>
{
 /// <summary>
 /// Attempt to extract the value.
 /// </summary>
 /// <param name="value">The value contained in the reference.</param<
 /// <returns>True if the value was successfully retrieved, false otherwise.</returns>
 bool TryGetValue(out T value);
}
public interface IOptional<T> : IValue<T>, IVolatile<T>
{
 /// <summary>
 /// Returns true if a value is available.
 /// </summary>
 bool HasValue { get; }
}

Lazy, Nullable and Task all exhibit these exact semantics. Programs can then be written that are agnostic over how optional values are encapsulated and processed, and the common interfaces ensure the different behaviours are overloaded in a consistent, familiar way.

We can extend this even further to "mutable encapsulated values, aka, references":

/// <summary>
/// A mutable reference.
/// </summary>
/// <typeparam name="T">The type of value the reference contains.</typeparam>
public interface IRef<T> : IValue<T>
{
 /// <summary>
 /// The value in the reference.
 /// </summary>
 new T Value { get; set; }
}

This pattern is less common, but still quite prevalent. For instance, see ThreadLocal<T> (which could also implement IOptional and IVolatile incidentally).

These interfaces have been in the Sasa library for quite some time, and are used consistently throughout the entire library. The consistency has helped considerably in guiding the design of new abstractions, and clarifying their use, since developers can simply understand any new abstraction in terms of the familiar interfaces it implements.

I suppose the lesson to take from all this is to hunt down common patterns, and aggressively factor them out into reusable abstractions. This helps the library's consistency, thus helping clients learn your API by reducing the number of unnecessary new properties and methods.

High-level constructs for low-level C: exception handling, RAII, sum types and pattern matching

2010-09-23T21:06:00.000-04:00

There are numerous high-level abstractions available in other languages that simply make programming easier and less error prone. For instance, automatic memory management, pattern matching, exceptions, higher order functions, and so on. Each of these features enable the developer to reason about program behaviour at a higher level, and factor out common behaviour into separate but composable units.

For fun, I've create a few small macro headers that enable some of these patterns in pure C. If anyone sees any portability issues, please let me know!

libex: Exception Handling and RAII

RAII in C is definitely possible via a well-known pattern used everywhere in the Linux kernel. It's a great way to organize code, but the program logic and finalization and error logic are not syntactically apparent. You have to interpret the surrounding context to identify the error conditions, and when and how finalization is triggered.

To address this, I encapsulated this RAII pattern in a macro library called libex, with extensions to support arbitrary local exceptions, and a small set of pre-defined exception types. Currently, this just consists of more readable versions of the error codes in errno.h.

No setjmp/longjmp is used, and libex provides little beyond case checking and finalization, because I wanted to provide a zero overhead exception handling and RAII that can supplant all uses of the undecorated pattern. Replacing all instances of the RAII pattern in Linux with these macro calls would incur little to no additional overhead, as it compiles down to a small number of direct branches.

There are also some convenience macros for performing common checks, like MAYBE which checks for NULL, ERROR which checks for a non-zero value, etc.

Example:

exc_type test(int i) {
  THROWS(EUnrecoverable)
  TRY(char *foo) {
    MAYBE(foo = (char*)malloc(123), errno);
  } IN {
    // ... no exception was raised, so compute something with foo
    // if EUnrecoverable thrown, it will propagate to caller
    if (some_condition()) THROW(EUnrecoverable)
  } HANDLE CATCH (EOutOfMemory) {
    // ... handle error for foo
  } CATCHANY {
    // ... other errors?
  } FINALLY {
   // ... finalize any state that has already been allocated
  }
  DONE
}

There are a few small restrictions required for the full exception semantics to work, so please see the main page of libex for further details.

libsum: Pattern matching and sum types, aka disjoint/tagged/discriminated unions, aka variants

Functional languages have long enjoyed the succinct and natural construction and deconstruction of data structures via sum types and pattern matching. Now you can have some of that power in via a few simple macros:

/* declare a sum type and its constructor tags */
SUM(foo) {
  foo_one,
  foo_two,
};
/* declare each sum case */
CASE(foo, foo_one) { int i; char c; };
CASE(foo, foo_two) { double d; };

void do_bar(foo f) {
  MATCH(f) {
    AS(foo_one, y) printf("foo_one: %d, %c\n", y->i, y->c);
    AS(foo_two, y) printf("foo_two: %d\n", y->d);
    MATCHANY 
      fprintf(stderr, "No such case!");
      exit(1);
  }
}

int main(int argc, char** argv) {
  foo f;
  LET(f, foo_one, (3, 'g')); /* (3,'g') is an initializer */
  do_bar(f);
}

There are a few small requirements and caveats, eg. LET performs dynamic memory allocation. Please see the main libsum page for further details.

License

My default license is LGPL, but since these are macro libraries that's probably not appropriate choice, given there is no binary that can be replaced at runtime (one of the requirements of the LGPL). I like the freedoms afforded by the LGPL though, so I'm open to alternate suggestions with similar terms. I will also consider the MIT license if there are no viable alternatives.

CLR: Verification for Runtime Code Generation

2010-05-31T12:04:00.000-04:00

The CLR's lightweight code generation via DynamicMethod is pretty useful, but it's sometimes difficult to debug the generated code and ensure that it verifies. In order to verify generated code, you must save the dynamic assembly to disk and run the peverify.exe tool on it, but DynamicMethod does not have any means to do so. In order to save the assembly, there's a more laborious process of creating dynamic assemblies, modules and types, and then finally adding a method to said type.

This is further complicated by the fact that a MethodBuilder and DynamicMethod don't share any common interfaces or base types for generating IL, despite both of them supporting a GetILGenerator() method.

This difficulty in switching between saved codegen and pure runtime codegen led me to add a CodeGen class to Sasa, which can generate code for either case based on a bool parameter. Since no common interface is available for code generation, it also accepts a delegate to which it dispatches for generating the code:

/// <summary>
/// Create a dynamic method.
/// </summary>
/// <typeparam name="T">The type of the dynamic method to create.</typeparam>
/// <param name="type">The type to which this delegate should be a member.</param>
/// <param name="methodName">The name of the delegate's method.</param>
/// <param name="attributes">The method attributes.</param>
/// <param name="saveAssembly">Flag indicating whether the generated code should be saved to a dll.</param>
/// <param name="generate">A call back that performs the code generation.</param>
/// <returns>An dynamically created instance of the given delegate type.</returns>
public static T Function<T>(
  Type type,
  string methodName,
  MethodAttributes attributes,
  bool saveAssembly,
  Action<ILGenerator> generate)
         where T : TypeConstraint<Delegate>;

You can also see Sasa's ilrewrite tool at work here with the T : TypeConstraint<Delegate>. This function will generate either a DynamicMethod or a dynamic assembly and save that assembly to disk, based on the 'saveAssembly' parameter. The assembly name is generated based on the type and methodName parameters.

In debugging the Sasa.Dynamics reflection code, I also came across a strange error which was not adequately explained anywhere that I could find. peverify.exe spit out an error to the effect of:

[X.dll : Y/Z][offset 0x0000001D] Unable to resolve token

Where X is the name of the generated dll, Y the namespace path, and Z is the class name. In my case, this occurred when the dynamically generated code was referencing a private class, which should not be possible from a separate dll.

Peirce's Criterion: command-line tool

2010-05-20T23:48:00.000-04:00

I've written a simple command-line tool filter out statistical outliers using the rigourous Peirce's Criterion.

The algorithm has been available in Sasa for awhile, and will be in the forthcoming v0.9.3 release.

I've also packaged the command-line tool binary for running Peirce's Criterion over multi-column CSV files (LGPL source available here).

The Cost of Type.GetType()

2010-05-20T23:06:00.000-04:00

Most framework-style software spends an appreciable amount of time dynamically loading code. Some of this code is executed quite frequently. I've recently been working on a web framework where URLs map to type names and methods, so I've been digging into these sort of patterns a great deal lately.

The canonical means to map a type name to a System.Type instance is via System.Type.GetType(string). In a framework which performs a significant number of these lookups, it's not clear what sort of performance characteristics one can expect from this static framework function.

Here's the source for a simple test pitting Type.GetType() against a cache backed by a Dictionary<string, Type>. All tests were run on a Core 2 Duo 2.2 GHz, .NET CLR 3.5, and all numbers indicate the elapsed CPU ticks.

Type.GetType()	Dictionary<string, Type>
6236070640	51351056
6236193856	51440360
6237466224	51463192
6238210488	51583336
6240645816	51599480
6242089400	51687448
6244450392	51719808
6245201664	51757472
6248327048	51793696
6249253736	51800056
6250640672	51859704
6251133912	51885992
6253544768	51897264
6254336632	51946408
6255117872	52046512
6256060648	52106936
6256159176	52140984
6259453568	52391000
Average
6247464250.67	51803928

Each program was run 20 times, and the resulting timing statistics were run through Peirce's Criterion to filter out statistical outliers.

You can plainly see that using a static dictionary cache is over two orders of magnitude faster than going through GetType(). This is a huge savings when the number of lookups being performed is very high.

Edit: Type.GetType is thread-safe, so I updated the test to verify that these performance numbers hold even when locking the dictionary. The dictionary is still two orders of magnitude faster. There would have to be significant lock contention in a concurrent program to justify using Type.GetType instead of a dictionary cache.

LINQ Transpose Extension Method

2010-05-20T20:05:00.000-04:00

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 IEnumerable<T>;
}

It simply numbers the columns in each row, flattens the sequence of cells, and groups the entries by number. If the table has entries that are missing, this algorithm has the side-effect of compacting all entries so that only the last row or column will be missing the elements. This may or may not be suitable for your application.

This extension method will be available in the forthcoming Sasa 0.9.3 release.

Asymmetries in CIL

2010-05-17T22:17:00.001-04:00

Most abstractions of interest have a natural dual, for instance, IEnumerable and IObservable, induction and co-induction, algebra and co-algebra, objects and algebraic data types, message-passing and pattern matching, etc.

Programs are more concise and simpler when using the proper abstraction, be that some abstraction X or its dual. For instance, reactive programs written using the pull-based processing semantics of IEnumerable are far more unwieldy than those using the natural push-based semantics of IObsevable. As a further example, symbolic problems are more naturally expressed via pattern matching than via message-passing.

This implies that any system is most useful when we ensure that every abstraction provided is accompanied by its dual. This also applies to virtual machine instruction sets like CIL, as I recently discovered while refining my safe reflection abstraction for the CLR.

A CIL instruction stream embeds some necessary metadata required for the CLR's correct operation. Usually this metadata is type information of some sort, such as the type of a local or the name and/or signature of a target method. For instance, here's a Hello World! example:

ldstr "Hello World!"
call  void [mscorlib]System.Console::WriteLine(string)

Unfortunately, the CIL instruction set suffers from some asymmetries which make some types of programming difficult.

For example, the ldtoken instruction takes an embedded metadata token and pushes the corresponding runtime type handle onto the evaluation stack; this is the instruction executed when using the typeof() operator in C#.

While this operation is useful, we sometimes want its dual, which is to say, we want the metadata used in a subsequent instruction to depend on the object or type handle at the top of the evaluation stack. A related operation is supported on the CLR, namely virtual dispatch, which depends on the concrete type, but dispatch is not general enough to support all of these scenarios because the vtable is immutable.

Consider a scenario where you have an untyped object, like a reference to System.Object "obj", and you want to call into some generic code, like a method Foo<T>(T value), but pass the concrete type of obj for T, instead of System.Object. Currently, you must go through a laborious process where you call GetType() on the object to obtain it's type handle, then obtain the method handle via reflection or some clever CIL hackery, then call MethodInfo.MakeGenericMethod in order to instantiate the type argument on Foo<T>, and finally, you must perform a dynamic invocation via reflection or allocate a custom delegate of type Action<T> and perform a virtual call, even though the call is statically known.

Each step of this process is expensive, and it makes typeful programming on the CLR painful when working on the boundary between typed and untyped code. Many reflection problems, like serialization, become simpler once we're dealing with fully typeful code.

Consider a dual instruction to ldtoken called "bind" which takes a type handle obtained via GetType() and then binds the resulting type handle into the executing instruction stream for the subsequent generic call to Foo<T>. This instruction could be easily and efficiently supported by any VM. Some restrictions are clearly needed for this instruction to remain verifiable, namely that the type constraints required by the target method are a subset of the type constraints of the statically known type, but the verifier already performs this analysis, and all of the information needed is available at the call site.

Fully polymorphic functions like Foo<T> trivially satisfy this condition since it has no constraints whatsoever. Serialize<T>/Deserialize<T> operations are duals, and in fact exhibit exactly the same sort of fully polymorphic type signature as Foo<T>.

There are many more programs that exhibit this structure, but they are unnecessarily difficult to write due to these asymmetries in CIL. This unfortunately requires developers to write a lot of ad-hoc code to get the results they want, and more code results in more bugs, more time, and more headaches.

CIL Verification and Safety

2010-05-17T17:10:00.000-04:00

I've lamented here and elsewhere some unfortunate inconveniences and asymmetries in the CLR -- for example, we have nullable structs but lack non-nullable reference types, an issue I address in my Sasa class library.

I've recently completed some Sasa abstractions for safe reflection, and an IL rewriter based on Mono.Cecil which allows C# source code to specify type constraints that are supported by the CLR but unnecessarily restricted in C#. In the process, I came across another unjustified decision regarding verification: the jmp instruction.

The jmp instruction strikes me as potentially incredibly useful for alternative dispatch techniques, and yet I recently discovered that it's classified as unverifiable. This seems very odd, since the instruction is fully statically typed, and I can't think of a way its use could corrupt the VM.

In short, the instruction performs a control transfer to a named method with a signature matching exactly the current method's signature, as long as the evaluation stack is empty and you are not currently in a try-catch block (see section 3.37 of the ECMA specification).

This seems eminently verifiable given a simple control-flow analysis, an analysis which the verifier already performs to verify control-flow safety of some other verifiable instructions. If anyone can shed some light on this I would appreciate it.

Purely Functional Collections vs. Mutable Collections

2009-12-10T13:39:00.000-05:00

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.

This is particularly annoying for data types where null is in fact a valid value, as it is in linked lists, where null denotes the empty list. The idea I had was to make the data type a struct, wrapping an inner reference that would hold the actual collection contents, basically moving the null into a non-nullable type that I control:

public struct Stack<T> : IEnumerable<T> {
  Node top;

  sealed class Node {
    internal T value;
    internal Node next;
  }
  public bool IsEmpty { get { return top == null; } }
  public override string ToString() {
    return IsEmpty ? "<empty>" : this.Format(" & ");
  }
  ...
}

A struct type can never be null, so I can overload Equals and ToString behaviour, but still handle null as a valid value -- a null inner reference indicates an empty list, for example.

I copied over the Sasa Seq type, implemented a struct-based version of it, and similarly implemented two persistent versions of a queue type. I then ran some quick benchmarks against the system collection classes, List<T>, Stack<T> and Queue<T> using a random sequence of 10,000,000 enqueues and dequeues. This test was repeated 10 times in each run, and the average runtime and memory use was taken.

This process was then repeated 13 times for each collection type, and I threw away the top and bottom two values. The results follow, where all values are in CPU ticks measured by System.Diagnostics.StopWatch. The results are displayed in sorted order, with the fastest at the top, and slowest at the bottom.

Queue Operations

Legend:

PQueue<T>: persistent class-based queue.

LinkedList<T>: System.Collections.Generic.LinkedList.

PQueue2<T>: persistent struct-based queue.

Queue<T>: System.Collections.Generic.Queue.

PQueue<T>	LinkedList<T>	PQueue2<T>	Queue<T>
7699324462.55	7890322380.36	7679249692.36	7761780264
7718837154.91	7983445563.64	7687912510.55	7803131562.18
7740207043.64	8023998067.64	7703769050.18	7810452602.91
7828445642.91	8032055720.73	7800245839.27	7811040914.91
8451346377.45	8201663652.36	7834188839.27	7850104080
8589153123.64	8282536765.09	7955433135.27	7935923176
8707905445.82	8484668378.91	8178008811.64	8118527255.27
8764140750.55	8742958103.27	8323106361.45	8348756291.64
8979406774.55	8752582049.45	8327369725.09	8350023904
Averages
8275418530.67	8266025631.27	7943253773.9	7976637783.43

Stack Operations

Legend:

Seq<T>: persistent class-based stack.

List<T>: System.Collections.Generic.List.

Seq2<T>: persistent struct-based stack.

Stack<T>: System.Collections.Generic.Stack.

List<T>	Seq<T>	Stack<T>	Seq2<T>
7710263064	7826307262.55	7802069434.91	7690359998.55
7762791045.82	7870793184	7808408813.82	7770721440.73
7849427981.09	8035572504.73	7840059360	7989185347.64
7905690538.18	8099787029.09	7883823349.09	8201203589.82
7912993893.82	8315915441.45	7907107597.82	8208994094.55
7947893535.27	8349995466.18	7914102997.82	8239609125.82
7952697770.18	8396224841.45	7927640684.36	8352575028.36
8131449759.27	8694619845.82	8155345951.27	8376635294.55
8388583725.09	8738260760	8294985193.45	8540294446.55
Averages
7951310145.86	8258608481.7	7948171486.95	8152175374.06

Analysis

The persistent collections perform rather well, generally within 5% of their mutable counterparts given this set of test data. While I didn't calculate it, you can see from the variance in the runs that there's a wider standard deviation from the mean for persistent collections, so their performance is ever so slightly less predictable, though not drastically so.

Interestingly enough, the struct-based persistent collections outperformed the class-based versions. I expected the reverse considering struct operations are not always properly optimized by the JIT. Even though the entire struct would fit into a register, the JIT may still allocate a stack slot for it, which would be more expensive than the guaranteed register-sized operations of a class type. Upon further thought, I suspected that perhaps the struct versions are faster simply because the VM doesn't need to perform a null check on dispatch, but the class-based versions use all-static method calls which don't perform null checks as far as I know.

I don't yet have a good explanation for this, but given the results, I believe I will move all Sasa collections to struct implementations as it simply provides more flexibility, immunity from null errors, and no appreciable runtime overhead.

If I had more time I would make these tests a little more rigourous by varying the test vectors in a more controlled fashion instead of just random, ie. use stepped, random, and other types of enqueue/dequeue sequences, to determine exactly how persistent and mutable collections behave based on inputs. I suspect the performance profiles will differ more drastically in such different scenarios.

This test was enough to demonstrate to me that persistent collections are sufficiently performant to be used in daily code, particularly given their numerous other advantages.

All source code and raw timing/memory tables can be downloaded here.

Easy File System Path Manipulation in C#

2009-11-18T22:39:00.000-05:00

I came across this type-safe module for handling file paths in the Haskell subreddit this week, and thought it looked kind of neat. Handling paths as strings, even with System.IO.Path always bugged me.

So I created a close C# equivalent of the Haskell type and added it to the Sasa library, to be available in the upcoming v0.9.3 release:

public struct FsPath : IEnumerable<string>, IEnumerable
{
 public FsPath(IEnumerable<string> parts);
 public FsPath(string path);

 public static FsPath operator /(FsPath path1, FsPath path2);
 public static FsPath operator /(FsPath path, IEnumerable<string> parts);
 public static FsPath operator /(FsPath path, string part);
 public static FsPath operator /(FsPath path, string[] parts);
 public static FsPath operator /(IEnumerable<string> parts, FsPath path);
 public static FsPath operator /(string part, FsPath path);
 public static FsPath operator /(string[] parts, FsPath path);
 public static implicit operator FsPath(string path);

 public FsPath Combine(FsPath file);
 public IEnumerator<string> GetEnumerator();
 public static FsPath Root(string root);
 public override string ToString();
}

The above is just the interface, minus the comments which you can see at the above svn link. This struct tracks path components for you and C#'s operator overloading lets you specify paths declaratively without worrying about combining paths with proper separator characters, etc.:

FsPath root = "/foo/bar";
var baz = root / "blam" / "baz";
var etc = FsPath.Root("/etc/");
var passwd = etc / "passwd";

The library will generate path strings using the platform's directory separator.

One significant departure from the Haskell library is the lack of phantom types used to distinguish the various combinations of relative/absolute and file/directory paths. C# can express these same constraints, but I intentionally left them out for two reasons:

The type safety provided by the file/directory phantom type is rather limited, since it's only an alleged file/directory path; you have to consult the file system to determine whether the alleged type is actually true. The only minor advantage to specifying this in a path type, is as a form of documentation to users of your library that you expect a file path in a particular method, and not a directory path. I could be convinced to add it for this reason.

The relative/absolute phantom type seems a bit useless to me, though the reason may be less obvious to others. IMO, the set of file and directory info classes should not have GetParent() or support ".." directory navigation operations, nor should they support static privilege escalation operations like File.GetAbsolutePath() which ambiently converts a string into an authority on a file/directory, since this inhibits subsystem isolation; without GetParent() or privilege escalation functions, any subsystem you hand a directory object is automatically chroot jailed to operate only in that directory. This has long been known to the capability-security community, and is how they structure all of their IO libraries (see Joe-E and the E programming language). Thus, in a capability-secure file system library, all paths are relative paths interpreted relative to a given directory object. As a result, FsPath also strips all "." and resolve all ".." to within the provided path to supply this isolation.

It goes without saying that .NET does not currently handle files and directories this way, but I plan to handle this eventually as well. FsPath will play a significant role in ensuring that paths cannot escape the chroot jail.

As an interim step along that path, the FsPath interface is a good first step.

[Edit: the reddit thread for this post has some good discussion.]

Extensible, Statically Typed Pratt Parser in C#

2009-11-16T09:41:00.000-05:00

I just completed a statically typed Pratt-style single-state extensible lexer+parser, otherwise known as a top-down operator precedence parser, for the Sasa library. The implementation is available in the Sasa.Parsing dll, under Sasa.Parsing.Pratt. Two simple arithmetic calculators are available in the unit tests.

This implementation is novel in two ways:

Aside from an alleged implementation in Ada, this is the only statically typed Pratt parser I'm aware of.

Pratt parsers typically require a pre-tokenized input before parsing semantic tokens, but I've eliminated this step by using the symbol definitions to drive a longest-match priority-based lexer.

Symbols by default match themselves, but you can optionally provide a scanning function used to match arbitrary string patterns. The symbol selected for the current position of the input is the symbol that matches the longest substring. If two symbols match equally, then the symbol with higher precedence is selected.

The design was heavily influenced by this Python implementation, though numerous departures were made to restore static typing and integrate lexing. In particular, symbols and semantic tokens are separate, where symbols are used primarily during lexing, and construct the appropriate semantic tokens on match.

Here is a simple arithmetic calculator:

class Calculator : PrattParser<int>
{
 public Calculator()
 {
     Infix("+", 10, Add);   Infix("-", 10, Sub);
     Infix("*", 20, Mul);   Infix("/", 20, Div);
     InfixR("^", 30, Pow);  Postfix("!", 30, Fact);
     Prefix("-", 100, Neg); Prefix("+", 100, Pos);

     // grouping symbols, ie. "(_)"
     Group("(", ")", int.MaxValue);

     // provide a predicate to identify valid literals
     Match("(digit)", char.IsDigit, 1, Int);

     // ignore whitespace
     SkipWhile(char.IsWhiteSpace);
 }

 int Int(string lit) { return int.Parse(lit); }
 int Add(int lhs, int rhs) { return lhs + rhs; }
 int Sub(int lhs, int rhs) { return lhs - rhs; }
 int Mul(int lhs, int rhs) { return lhs * rhs; }
 int Div(int lhs, int rhs) { return lhs / rhs; }
 int Pow(int lhs, int rhs) { return (int)Math.Pow(lhs, rhs); }
 int Neg(int arg) { return -arg; }
 int Pos(int arg) { return arg; }
 int Fact(int arg)
 {
     return arg == 0 || arg == 1 ? 1 : arg * Fact(arg - 1);
 }
}

The above is a simplified version of the calculators used in the unit tests. You can clearly see the definition of left and right-associative infix operators, and postfix operators. The numbers are precedence levels, and the delegates are the semantic actions associated with each token type.

There are pre-defined functions for creating left and right-associative infix, prefix, postfix, and both prefix and infix ternary operators -- prefix ternary is a simple "if _ then _ else _", infix ternary is like C's ternary operation, "_ ? _ : _". You are not constrained to these symbol types however, as you can define arbitrary character sequences as symbols and parse the results at your whim.

Adding variable binding to the above calculator requires a few extensions to support lexically scoped environments, but the parser requires only the following two extensions:

// symbol for identifiers, ie. variable names
Match("(ident)", char.IsLetter, 0,
        name => new Var { Name = name });
// let binding, ie. "let x = 1 in x", is a
// prefix-ternary operator
TernaryPrefix("let", "=", "in", 90, Let);

"let" is not matched as an identifier because the "let" symbol has a higher precedence. Parser definitions with ambiguous parses thus require some care to resolve the ambiguity either via match length or precedence relationships.

There are two popular choices when it comes to parsing: parser generator tools and parser combinator libraries. I've never liked generators personally, as they require a separate language and entirely separate tools to define and process the grammar thus increasing the learning and maintenance curve.

I actually like parser combinators, and there are now good techniques for supporting arbitrary left recursion in grammars (see Packrat parsing in OMeta). However, handling operator precedence often involves a series of complex extensions to the otherwise simple recursive descent, or it requires the parsed results to maintain all operator and grouping information so a post-processing phase can readjust the parse tree to reflect the proper priorities. The post-processing phase typically uses a shunting yard or Pratt-style operator precedence algorithm to resolve precedence, so why not just build the parser itself directly on Pratt parsing?

Unlike parser-combinator libraries, of which I've built a few, Pratt parsers natively support arbitrary operator precedence and are efficient as they require no backtracking. Pratt parsers are also Turing-complete, because the semantic actions can perform arbitrary computations on the parser input. Turing completeness carries both benefits and costs of course, but the single-state nature of Pratt parsers keeps it manageable. The "single state" of the parser is simply the current token matched from the input.

For example, if prefix-ternary operators weren't already available, you could simply define one like so:

// "let" is a prefix symbol on a name
var let = Prefix("let", 90, x =>
{
    // lexer matched "let" prefix operator on x
    // argument, a variable name
    Advance("=");          // advance past the "="
    var xValue = Parse(0); // parse the value to bind to x
    Advance("in");         // advance past the "in"
    var body = Parse(0);   // parse the let expression body
    // return a Let expression node
    return new Let{ Variable = x, Value = xValue, Body = body};
});
// declare the other symbols involved for the lexer
// but they have no associated semantic action
Symbol("=");
Symbol("in");

The above builds on "Prefix", but you could break this down even further as in Pratt's original paper and define arbitrary symbol behaviour by providing a scanning function, "left denotation", and "null denotation", and so on.

To define a parser, you need only inherit from Sasa.Parsing.Pratt.PrattParser, provide the semantic type T, and override the constructor for your parser to define your symbol table. The only downside is that each parser instance is monolithic and not thread-safe, so it can only parse one input at a time. There is no limit to how many parsers you can create however.

Pratt parsing is simple, compact, and efficient, so I hope it finds more widespread use, particularly now that there is a statically typed implementation for a popular language.

[Edit: the PrattParser will be available in the upcoming v0.9.3 release of the Sasa class library.]

Abstracting over Type Constructors using Dynamics in C#

2009-10-01T11:50:00.000-04:00

I've written quite a few times about my experiments with the CLR type system [1, 2, 3]. After much exploration and reflection, I had devised a pretty good approach to encoding ML-style modules and abstracting over type constructors in C#.

A recent question on Stack Overflow made me realize that I never actually explained this technique in plain English.

The best encoding of ML modules and type constructor polymorphism requires the use of partly safe casting.

An ML signature maps to a C# interface with a generic type parameter called a "brand". The brand names the class that implements the interface, ie. the module implementation.

An ML module maps to a C# class. If the module implements a signature, then it implements the corresponding interface and specifies itself as the signature's brand.

Since classes and interfaces are first-class values, an ML functor also maps to a class.

An ML type component maps to an abstract class that shares the same brand as the module. This effectively ties the the module data representation and the module implementation together at the interface boundary, and makes the necessary casting partly safe.

I'll use the tagless interpreter from Fig. 2 of tagless staged interpreters as a concrete example:

(* Fig. 2 *)
module type Symantics = sig
  type ('c, 'dv) repr
  val int : int -> ('c, int) repr
  val bool: bool -> ('c, bool) repr
  val lam : (('c, 'da) repr -> ('c, 'db) repr) ->
            ('c, 'da -> 'db) repr
  val app : ('c, 'da -> 'db) repr -> ('c, 'da) repr ->
            ('c, 'db) repr
  val fix : ('x -> 'x) -> (('c, 'da -> 'db) repr as 'x)
  val add : ('c, int) repr -> ('c, int) repr ->
            ('c, int) repr
  val mul : ('c, int) repr -> ('c, int) repr ->
            ('c, int) repr
  val leq : ('c, int) repr -> ('c, int) repr ->
            ('c, bool) repr
  val if_ : ('c, bool) repr ->
            (unit -> 'x) -> (unit -> 'x) ->
            (('c, 'da) repr as 'x)
end

In the translation, I omit the 'c type parameter used in OCaml. The type of the expression representation, 'dv, becomes T in C#:

module type Symantics = sig

maps to

interface ISymantics<B> where B : ISymantics<B>

(B is the module's Brand)

type ('c, 'dv) repr

maps to

abstract class Repr<T, B> where B : ISymantics<B>

(B is the module's Brand)

Each signature function maps to a method on ISymantics, ie.
```
val int : int -> ('c, int) repr
```
maps to
```
Repr<int, B> Int(int value)
```

The final translation will look something like:

// type component
abstract class Repr<T, B> where B : ISymantics<B> { }
// module signature
interface ISymantics<B> where B : ISymantics<B>
{
  Repr<int, B> Int(int i);
  Repr<int, B> Add(Repr<int, B> left, Repr<int, B> right);
  ...
}

The implementation undergoes a similar translation:

```
module R = struct
```
maps to
```
sealed class R : ISymantics<R>
```
(R implements ISymantics and provides itself as the type brand)

```
type ('c,'dv) repr = 'dv
```
maps to
```
sealed class ReprR<T> : Repr<T, R>
```
(the concrete representation is a sealed class that inherits from Repr, and supplies R as the brand, effectively typing it to the R implementation)

The final mapping looks like:

(* Section 2.2 *)
module R = struct
  type ('c,'dv) repr = 'dv (* no wrappers *)
  let int (x:int) = x
  let add e1 e2 = e1 + e2
  ...
end

maps to:

// concrete type component for the interpreter
// representation
sealed class ReprR<T> : Repr<T, R>
{
  internal T value;
}
sealed class R : ISymantics<R>
{
  public Repr<int, R> Int(int i)
  {
    return new ReprR<int> { value = i };
  }
  public Repr<int, R> Add(Repr<int, R> left,
                         Repr<int, R> right)
  {
    var l = left as ReprR<int>; // semi-safe cast
    var r = right as ReprR<int>;// semi-safe cast
    return new ReprR<int> { value = l.value + r.value; }; }
  }
}

Programs written against tagless interpreters are wrapped in functors in order to properly abstract over the interpreter implementation. As mentioned before, modules and signatures are effectively first-class values in this encoding, so a functor simply becomes a function:

(* Fig. 3 *)
module EX(S: Symantics) = struct
  open S
  let test1 () = app (lam (fun x -> x)) (bool true)
  ...
end

maps to:

public static class EX
{
  public static Repr<bool, B> Test1<B>(ISymantics<B> s)
  {
    return s.App(s.Lam(x => x), s.Bool(true));
  }
}

The brand/ISymantics type could also be lifted to be a generic class parameter to make it syntactically closer to how it looks in the paper, but the difference is not important.

You can now run EX.Test1 with any conforming implementation of ISymantics, and the type system will prevent you from mixing representations of different implementations just as it would in ML, because the brands will not match. The only way to trigger a type error due to the downcast, is if the client implements his own Repr<T, B> supplying R for the brand, then passing the custom Repr type in to a method on ISymantics<R>. In such cases the client deserves an error.

I think this is a fairly reasonable trade off all things considered. Of course, it would be preferable if the CLR could just support type constructor polymorphism natively. And while all my wishes are coming true, can I have all of these changes too?

Disabling EDGE/3G on iPhone OS 3.0

2009-09-16T15:17:00.000-04:00

After much struggle and dead ends, this fix worked like a charm. I don't think it's been publicized very much, and there are many people in need of such fixes.

Sasa v0.9.2 Released

2009-09-15T15:36:00.000-04:00

The newest Sasa release contains a number of bugfixes and increased compliance with MIME standards, including proper MIME MailMessage subject decoding. Perhaps of wider interest to the .NET community, there are a number of extension methods for thread safe and null-safe event raising; safe event raising is a major bane of the .NET developer's existence.

There are specific overloads for all System.Action delegate types. A general RaiseAny extension method is also provided that isn't very efficient, but which should match the signature of any event in the class libraries. More overloads can be provided for more efficient execution if needed.

Here is the complete list of changes from the changelog:

= v0.9.2 =

* fixed bug where quoted printable encoding failed when = was the last
  character.
* added Pop3Session.Reset method.
* compact serializer no longer uses stream positions to track cached
  objects, so non-indexable streams, like DeflateStream, are now
  usable.
* ISerializing interface generalized to support serializing non-primitive
  field values.
* added e-mail subject decoding.
* fixed boundary condition on QuotedPrintableEncoding.
* added extension methods to support safely raising events.
* added an extension method to safely generate field and property names
  as strings.
* added parameter to Compact serializer to indicate whether
  SerializableAttribute should be respected.
* added a boundary check for SliceEquals.
* added a event Raise overload for any event handlers whose arg
  inherits from EventArgs, which enables safe event raising within
  an object.
* MailAddressCollection already handles parsing comma-delimited e-mail
  address strings, so don't attempt to split them manually.
* added a test for an e-mail address that contains a comma.
* default to us-ascii charset if none provided.
* NonNull now throws a ArgumentNullException with a proper
  description.
* many FxCop-related fixes and CLS compliance improvements.
* added usage restrictions on Sasa.CodeContracts attributes.

[Edit: generating HTML docs from the XML files used to be such a chore, though Sandcastle at least makes it possible, if convoluted. Mono's mdoc util is barely any help here, as it can only process one Visual Studio generated XML file at a time. I just found ImmDoc.Net which made this process ridiculously easy and stupendously fast, easily an order of magnitude faster than Sandcastle, but it looks like there's a bug handling method ref and out parameters.

In any case, here is some preliminary HTML API documentation for your perusal (CHM file here). Unfortunately, Sandcastle doesn't produce a handy index.html, but hopefully the ImmDoc.Net dev will fix the above bug soon, and I can use that to generate documentation.]

[Edit 2: The ImmDoc.Net dev fixed the bug, so here is a clearer set of docs with a proper index. The previous link will still work for now.]

SlimTimer Timesheet Processing Utility

2009-08-16T15:32:00.001-04:00

I use the very respectable SlimTimer to help me track my hours. Unfortunately, while they display a consistent total across all reports, the entries in each report do not necessarily add up to that total due to the fractional time units and the rounding involved.

Unfortunately, the accounting department tends to frown upon inconsistencies like this, no matter the reason. My process thus far has been to simply export a full timesheet with the report settings specifying time units as precisely as possible, and then performing the sum myself on the resulting chart.

This got a bit tedious, so I wrote a program to compile the necessary tallies over however many timesheet files I wanted to process. The source and binaries are available for download. Simply drag and drop any number of timesheets generated from SlimTimer, and the utility will generate a new csv file for each timesheet, with an extension "-out.csv".

The format of the output csv file is formatted for my invoice structure, but adjusting it for other formats is fairly trivial for anyone familiar with C#.

Mobile Code in C# via Finally Tagless Interpreters

2009-06-23T15:36:00.000-04:00

Awhile back I described an idea to transparently execute code server-side or client-side given the same program. I've finally gotten around to implementing this using my encoding for type constructor polymorphism in C#.

Here is an example you can run from the original paper showcasing exponentiation which can execute transparently either server-side or client-side. The server-side code is intentionally limited to bases less than 100 and exponents less than 20.

Here is some simplified code that defines an exponentiation function:

void Build<B, R>(B _)
    where B : ISymantics<B>, new()
{
    var e = _.Lambda<int, Func<int, int>>(
            x => _.Fix<int, int>(self => _.Lambda<int, int>(n =>
                 _.If(_.Lte(n, _.Int(0)), () => _.Int(1),
                                          () => _.Mul(x, _.Apply(self, _.Add(n, _.Int(-1))))))));
}

The parameter "_" is the tagless interpeter and it's type is ISymantics<B>, which defines the semantics of the language being interpreted:

/// <summary>
/// The abstract base class of a typed expression.
/// </summary>
/// <typeparam name="T">The type of the encapsulated expression.</typeparam>
/// <typeparam name="B">The brand of the interpreter that can interpret this expression.</typeparam>
public abstract class E<T, B> where B : ISymantics<B>, new() { }

/// <summary>
/// The interface for interpreters.
/// </summary>
/// <typeparam name="B">The brand of the interpreter. This should be unique for each interpreter.</typeparam>
public interface ISymantics<B>
    where B : ISymantics<B>, new()
{
    /// <summary>
    /// Construct an integer.
    /// </summary>
    /// <param name="i">The integer value.</param>
    /// <returns>An expression encapsulating the value.</returns>
    E<int, B> Int(int i);

    /// <summary>
    /// Add two expressions.
    /// </summary>
    /// <param name="left">The left expression.</param>
    /// <param name="right">The right expression.</param>
    /// <returns>The sum of the two expressions</returns>
    E<int, B> Add(E<int, B> left, E<int, B> right);

    ...
}

The code-behind for the .aspx page interprets this code twice, once with a LINQ-based compiler for server-side execution, and once with a JavaScript backend to generate the client-side program.

The client-side program depends only one utility function to compute the fixed point of a given function:

function fix(f) {
    return function self(x) { return f(self)(x); };
}

Clearly any programs written this way are fairly verbose, but it's fairly straightforward to define wrapper structs around E<T, B>, such as Eint, Ebool, etc., to provide overloaded operators such that embedded programs look almost like ordinary C#. The current ISymantics interface is also limited to single-arg functions, but it's possible to add more overloads to support multi-arg functions.

Of course, it's already possible to translate C# expressions to JavaScript if we write a LINQ expression visitor. However, LINQ expressions are in a sense more limited than operating on this lifted data type. For instance, it's not possible to translate a static function to JavaScript using LINQ expressions, but it is possible using the final tagless representation.

It's an open question whether such final tagless interpreters can be made usable enough for real programming. However, the techniques employed here, in particular the structure which enables semi-safe type constructor polymorphism, are definitely useful for other projects that require retargetable abstractions.

The full source code is available, and includes a simple C# evaluator, LINQ-based compiler, a JavaScript backend, and an interpreter that computes the depth of the expression tree, which was also an example in the tagless paper. Also included is a partially working partial evaluator. This proved the trickiest to implement, and the only remaining problem appears to be recursive partial evaluation.

As future work, the partial evaluator can be parameterized by the type of compiler, so it can partially evaluate managed code and JavaScript programs; it is currently needlessly tied to the managed code interpreter. I also plan to implement the aforementioned wrapper structs and other enhancements to improve the clarity of embedded programs, hopefully to the point where they are usable for real programming.

[Edit 2009-08-16: it just came to my attention that the JS failed on the first run, but succeeded after a server-side execution was performed. This was a DOM manipulation bug, and the source and server code have been updated to fix this.]

Sasa v0.9 Released

2009-05-22T11:13:00.000-04:00

Sasa v0.9 has been released. See the changelog for a detailed description of the changes. Here is the original release description for Sasa v0.8. This post will describe only changes from v0.8.

Backwards-incompatible changes:

Renamed Sasa.Collections.List to Sasa.Collections.Seq to avoid clashes with System.Collections.Generic.List

Restructured the list operators to better support chaining

Useful additions include:

Sasa.Weak<T> which wraps WeakReference

Additional string processing functions, like StringExt.SliceEquals

Array-processing combinators under Sasa.Collections.Arrays (Slice, Dup, etc.)

Stream functions under Sasa.IO (CopyTo, ToArray)

Support for MIME decoding and encoding for MailMessage parsing

Bugfixes:

Better conformance to RFCs for Pop3Client and MailMessage parsing

Concurrency bugfix in Sasa.Lazy.

MIME MailMessage parsing and the Pop3Client are already in use in production code, and conformance appears adequate after hundreds of processed messages.

Experimental Additions

There are a few components of this release that I would deem "experimental".

Sasa.Dynamics is intended as a "safe reflection" facility. Basically, this is a "type-case" construct as found in the "intensional type analysis" literature. Any reflective algorithm should be implementable via ITypeFunc<R>, and you cannot forget to handle a particular case. This interface basically factors out object traversal from the actual reflection algorithm.

Under Sasa.Web and Sasa.Web.Asp, I've included a URL-safe Base64 encoder/decoder, Sasa.Web.Url64, and a generic ASP.NET Page base class that is immune to clickjacking and CSRF.

I first proposed this idea on the capability security mailing list. I'm not completely satisfied with the current incarnation, but it's an interesting idea I'm still toying with.

Garbage Collection Representations Continued II

2009-03-22T23:56:00.000-04:00

The tagged pointer representation described in Xavier Leroy's ZINC paper is compelling in its simplicity. Most data manipulated in typical programs is integer or pointer-based in some way, so using a 1-bit tagged representation allows unboxed integers, resulting in an efficient representation of the most common data types.

I've never been satisfied with the size header in heap-allocated types though, and the two bits reserved for GC pretty much forces you to use some mark-sweep variant. Integrating something like age-oriented collection with reference counting for the old generation would require an entirely new word for every block of memory. This is a prohibitive cost in functional programs.

Removing the Size Header

Reading about BIBOP techniques used in the Streamflow allocator gave me the idea of using page masking to determine the block size.

As in Streamflow, consider an allocator where each page obtained from the OS was partitioned into a list of equally-sized blocks. Each of these blocks does not need its size stored in an object header, since the size of the block is a property of the page it was allocated from, and we can easily obtain the page address by simply masking the pointer to the block. So the first block of every page is dedicated to storing the size, and all subsequent blocks are placed in the free list.

This works for structured data allocated in fixed-sized blocks, but unstructured data is dynamic in extent and can span pages. Unstructured data must also carry the GC header in the first word, even when spanning pages. However, we know that arrays and strings are the only primitive unstructured data described in ZINC, and they must now both carry their size information as part of the structure. We can thus easily identify "small" strings and arrays that could fit into a fixed-sized block.

As a possible space optimization, such "small" arrays and strings don't need to be accompanied by a size field. We can perform a simple test to distinguish "small" arrays: if the array pointer is more than one word off from a page-aligned address, it is structured data, since unstructured data that spans pages always starts on a page address + GC header size.

We now have a full 24 free bits in the block header, which we can reserve for use by the GC. 24 bits is enough to employ reference counting, or a hybrid mark-sweep for the nursery, reference counting for the old generation as in age-oriented collection. The GC to employ is now completely at the discretion of the runtime, and can even be changed while the program is running.

The Problem

There is a downside of course. Streamflow allocates fixed-sized blocks for sizes ranging from 4 bytes up to 2kB. Considering the above approach uses the first block to store the block size, we would waste up to 2kB on the larger block sizes. We could amortize this cost by allocating more pages and spreading the cost across them, but then we lose the simple page masking. We could avoid large fixed-sized blocks, maybe cutting them off at 512 bytes, but then we would still need some way to store the size for these "medium-sized" blocks.

We can't simply use a single word of the page to store the size, as we would then have an odd number of bytes to divide into fixed size blocks. Again, it's only a problem for larger block sizes. You can't split 4092 bytes into two 2kB blocks.

Another Approach

As a general solution to these problems, we can eliminate the size tag on the page entirely by maintaining a sorted array of address ranges and the block size of the range. When we need to discover the size of a block, we perform a binary search to find the address range the address falls in, and extract the size. This operation is O(log n), where n is the number of distinct address ranges, ie. sequences of consecutive pages allocated to the same block size. I would expect the number of such page regions to be under 50, so the logarithmic cost should be very low in practice, though the additional indirections accessing the array can be costly due to cache misses.

Summary

A block header representation that provides for GC independence would be compelling. The page-level size header is promising, but clearly has problems. Hopefully, some clever person will devise a general way to handle the larger fixed sized blocks without wasting too much space.

The solution to the problems with the page-level size header using a binary search is a mixed blessing. The additional runtime cost in discovering block size may be prohibitive, since it must be performed during GC traversal, and on every free operation. The costs of free might possibly be amortized somehow when done in bulk, but the cost incurred by GC traversal seems much more challenging to eliminate.

Sasa Reborn!

2009-02-24T10:08:00.001-05:00

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, I figured variously sized sum types might also find some uses. Time will well.

Lazy type, for lazily computed values.

An immutable list.

Various Ruby-like extensions to core types, like generators for int.UpTo, int.DownTo, string.IsNullOrEmpty, string.Slice, etc.

Useful extensions to IEnumerable.

"Zip" functions from Haskell for anonymous types and tuple types.

A NonNull type which decorates method parameters and ensures those parameters are not null; if NonNull is used pervasively, you can ensure that your program is free of NullReferenceExceptions.

An Option type indicating values which may be null. Unlike System.Nullable, this works for class types.

Function currying extensions, and extensions to lift multi-parameter functions to single-parameter tupled functions

Some convenience extensions to IDictionary.

Sasa.Linq

A stand-alone assembly for Linq development.

Default IQueryProvider and IQueryable implementations

Generic ExpressionVisitor base class.

IdentityVisitor which provides default implementations for all NodeTypes and performs no modifications to the expression, just returning it as-is.

ErrorVisitor which which throws NotSupportedException for all NodeTypes.

Sasa.Serialization

A stand-alone assembly with serialization classes.

Provides a compact serializer which requires only ReflectionPermission, and not SecurityPermission like the System classes do; this serializer can therefore be used in medium trust environments. The serializer currently requires a little more discipline from the developer to use correctly, but space savings of 100-200% are typical.

An experimental unsafe, highly compact binary serializer.

Sasa.Net

A library providing missing functionality under System.Net.

A Pop3Client class.

MailMessage parsing.

Sasa.CodeContracts

Microsoft Research is developing a design by contract library which they hope to release with .NET 4.0. It's a fairly sophisticated piece of software, that integrates with a static verification tool called Pex. The analysis tools can detect contract violations at compile-time, and even generate test cases for each violation.

Unfortunately, their license forbids commercial application of the pre-release library, even if you just want to utilize runtime contract checking.

Sasa.CodeContracts is a Microsoft API-compatible implementation of the CodeContracts library. This is only a runtime library, and does not provide the Pex integration with static analysis and automated test generation.

Precondition checking is enabled, but postconditions and object invariants require CIL re-writing, so they are not currently supported. I will be looking into using Mono.Cecil to rewrite the IL to support post-conditions and invariants in the future.

TODO for v1.0

There are a few items remaining before v1.0 is released, but the library is usable as-is. Notably missing is MIME parsing for MailMessage, which will be added for v1.0. Also serialization will get improved safety almost on-par with standard framework serialization, and the compaction will be user-customizable for even more space savings in any given program.

Future Work

The Sasa API is fully documented with accompanying XML for code completion. Comments on the clarity of the API and documentation are welcome! Some tutorials on using these features safely are coming as well.

I'm dissatisfied with a few other approaches being pursued on the CLR, including:

Current approaches to parallel and concurrent programming, even Microsoft's Parallel Extensions and the Concurrency and Coordination Runtime.

CLR security is far too coarse-grained and pretty much unusable.

Efficient async I/O is too difficult to reason about (though the CCR does make it easier).

In lieu of a Pex static analysis, there is the possibility of QuickCheck-like test suites derived from CodeContract annotations.

Keep an eye on this space for what I come up with.

The cost of type tests and casts in C#

2009-02-03T19:07:00.000-05:00

Awhile back I ran some tests comparing the dispatching performance of runtime tests+casts against double dispatch. Turned out runtime type tests and casting were noticeably faster than dispatching, probably because they avoid more pipeline stalls.

Unfortunately, there is a "common wisdom" in the .NET world that an "is" test followed by an "as" cast is performing two casts, and in fact one should simply perform the "as" cast then check the result against null:

// prefer this form
string a = o as string;
if (a != null)
{
  Console.WriteLine(a);
}

// to this form:
if (o is string)
{
  string a = o as string;
  Console.WriteLine(a);
}

In fact, that's not the case, as any compiler worth its salt will coalesce the two tests into a single cast and branch operation. I took the tests from the above dispatching and altered them to perform the cast-and-null check, then I ran the tests again with the original is-then-as form. The latter form was about 6% faster on every timing run.

There's obviously some optimization being done here, but the lesson is: don't try to outsmart the compiler. In general, just write code the safe way and let the compiler optimize it for you. It's safer to perform a test then cast within a delimited scope like an if-statement, than to let the possibly null variable float around in the outer scope where you might use it inadvertently later in the method or during refactoring.

If performance turns out to be an issue, profile before trying these sorts of low-level "optimizations", because you might be surprised at the results.

Embedded Stack Language for .NET - Redux

2009-01-29T21:41:00.000-05:00

Awhile ago, I had posted about an embedding of a stack language in C#. The type signatures of the functions and the stack object encoded the consumption and production of stack values, so if your program compiled, it ran correctly.

Unfortunately, the prior structure had a safety problem when generating code which I noted, but didn't have time to address.

The new structure provided below does not have the safety problem, and any functions that compile are guaranteed to execute correctly. I have also altered the style to emphasize the row variable representing the "rest of the record" which the operation knows nothing about. The row variable is denoted by "_".

This is still a fairly limited embedding, but I have added a few convenience functions, and may yet add more. Here is a sample program:

var d = new DynamicMethod("test", typeof(void), null);
var s =
  1.Load()                   // load constant: { int }
   .Int(2)                   // load constant: { int, int }
   .Add()                    // add: { int, int } -> { int }
   .Do(Console.WriteLine)    // output top: { int } -> { }
   .String("Test out")       // load string: { } -> { string }
   .Do(Console.WriteLine);   // output top: { string } -> { }
s.Compile(d.GetILGenerator());// only compile empty stacks: { }
d.Invoke(null, null);

Thankfully, C# can infer the types used so we can avoid any superfluous type annotations. The code generation functions are a little more involved however:

/// <summary>
/// Abstracts the stack structure used to hold locals, etc.
/// </summary>
/// <typeparam name="_">The rest of the stack.</typeparam>
/// <typeparam name="T">The top of the stack.</typeparam>
public sealed class Stack<_, T>
{
    /// <summary>
    /// Defer the code generation by enclosing the opcodes
    /// in a closure.
    /// </summary>
    internal Action<ILGenerator> gen;
    public Stack(Action<ILGenerator> gen)
    {
        this.gen = gen;
    }
}

/// <summary>
/// An empty value aka void.
/// </summary>
public struct Unit
{
}

/// <summary>
/// Statically typed stack operations.
/// </summary>
public static class Stack
{
    /// <summary>
    /// Load an int on a new stack.
    /// </summary>
    public static Stack<Unit, int> Load(this int value)
    {
        return new Stack<Unit, int>(il =>
                   il.Emit(OpCodes.Ldc_I4, value));
    }

    /// <summary>
    /// Load a string on a new stack.
    /// </summary>
    public static Stack<Unit, string> Load(this string value)
    {
        return new Stack<Unit, string>(il =>
                   il.Emit(OpCodes.Ldstr, value));
    }

    /// <summary>
    /// Load a string on an existing stack.
    /// </summary>
    public static Stack<Stack<_, T>, string> String<_, T>(
                  this Stack<_, T> stack, string value)
    {
        return new Stack<Stack<_, T>, string>(il =>
        {
            stack.gen(il);
            il.Emit(OpCodes.Ldstr, value);
        });
    }

    /// <summary>
    /// Duplicate the top of the stack.
    /// </summary>
    public static Stack<Stack<_, T>, T> Dup<_, T>(
                  this Stack<_, T> stack)
    {
        return new Stack<Stack<_, T>, T>(il =>
                   il.Emit(OpCodes.Dup));
    }

    /// <summary>
    /// Apply a function to the top of the stack, replacing
    /// the top element with the return value of the function.
    /// </summary>
    public static Stack<_, R> Apply<_, T, R>(
                  this Stack<_, T> stack, Func<T, R> target)
    {
        return new Stack<_, R>(il =>
        {
            stack.gen(il);
            il.EmitCall(OpCodes.Call, target.Method, null);
        });
    }

    /// <summary>
    /// Apply an action to the top of the stack consuming
    /// the top value.
    /// </summary>
    public static Stack<_, Unit> Do<_, T>(
                  this Stack<_, T> stack,
                  Action<T> target)
    {
        return new Stack<_, Unit>(il =>
        {
            stack.gen(il);
            il.EmitCall(OpCodes.Call, target.Method, null);
        });
    }

    /// <summary>
    /// Load the value at the given array's index on to the stack.
    /// </summary>
    public static Stack<_, T> LoadArrayIndex<_, T>(
                  this Stack<_, Stack<T[], int>> stack)
    {
        return new Stack<_, T>(il =>
                   il.Emit(OpCodes.Ldelem, typeof(T)));
    }

    /// <summary>
    /// Check that the top element is of type U.
    /// </summary>
    public static Stack<_, U> IsInstance<_, T, U>(
                  this Stack<_, T> stack)
        where T : class
    {
        return new Stack<_, U>(il =>
        {
            stack.gen(il);
            il.Emit(OpCodes.Isinst, typeof(U));
        });
    }

    /// <summary>
    /// Load an int onto an existing stack.
    /// </summary>
    public static Stack<Stack<_, T>, int> Int<_, T>(
                  this Stack<_, T> stack, int i)
    {
        return new Stack<Stack<_, T>, int>(il =>
        {
            stack.gen(il);
            il.Emit(OpCodes.Ldc_I4, i);
        });
    }

    /// <summary>
    /// Add the two elements at the top of the stack.
    /// WARNING: T must overloead the addition operator.
    /// </summary>
    public static Stack<_, T> Add<_, T>(
                  this Stack<Stack<_, T>, T> stack)
    {
        return new Stack<_, T>(il =>
        {
            stack.gen(il);
            il.Emit(OpCodes.Add);
        });
    }

    /// <summary>
    /// Return from a function.
    /// </summary>
    public static void Return<_, T>(this Stack<_, T> stack,
                                    ILGenerator il)
    {
        stack.gen(il);
        il.Emit(OpCodes.Ret);
    }

    /// <summary>
    /// Compile the code so long as the top of the stack
    /// has type Unit.
    /// </summary>
    public static void Compile<_>(this Stack<_, Unit> stack,
                                  ILGenerator il)
    {
        stack.Return(il);
    }
}

Compact, Declarative Serialization

2008-11-27T22:41:00.000-05:00

A few posts back, I hinted at using parameterization as an alternative to metadata. I've just written a serialization interface using this technique, and a binary serializer/deserializer to demonstrate the inherent tradeoffs.

You can inspect the pair of interfaces required, and I implemented a binary serializer/deserializer pair as an example. ICompactSerializable is implemented for each serializable object. It's essentially a declarative method, which describes the sequential, internal structure of the object. It's simple and fast, since it provides native speed access to an object's fields without reflection, and no need for metadata.

Of course, the obvious downside is that clients must describe the internal structure themselves via ICompactSerializer, and refactoring must be careful about reordering the sequence of calls. The upshot is that serialization and deserialization is insanely fast as compared to ordinary reflection-driven serialization, the binary is far more compact, and clients have full control over versioning and schema upgrade without additional, complicated infrastructure (surrogates, surrogate selectors, binders, deserialization callbacks, etc.).

These serializers are very basic, but the principle is sound. My intention here is only to demonstrate that parameterization can often substitute for the typical approach of relying heavily on metadata and reflection. This is only one possible design of course, and other tradeoffs are possible.

For instance, each method in ICompactSerializer could also accept a string naming the field, which could make the Serialize call invariant to the ordering of fields, and thus more robust against refactoring; this brings the technique much closer to the rich structural information available via reflection, but without the heavy metadata infrastructure of the .NET framework.

The Serialize method of ICompactSerializable can also easily be derived by a compiler, just as the Haskell compiler can automatically derive some type class instances.

This application is so basic, that the user wouldn't even need to specify the field names manually, as the compiler could insert them all automatically. Consider how much metadata, and how much slow, reflection-based code can be replaced by fast compiler-derived methods using such techniques. Projects like NHibernate wouldn't need to generate code to efficiently get and set object properties, since full native speed methods are provided by the compiler.

The Chicken and the Egg - Redux

2008-11-15T12:44:00.000-05:00

There is still considerable skepticism regarding my conclusion that the chicken comes first. Many of the objections are simply due to different interpretations of the question, interpretations which I consider unfaithful to the original purpose of the chicken-egg dilemma.

Fundamentally, this question is supposed to represent a causality dilemma. When there is a causal dependency between any two objects, A and B, we can ask ourselves, "which came first, A or B?" An object C could have caused B, and thus triggered the recursive relation C→B→A→B→A... Of course, it could just as easily have been A that was caused first.

To properly answer this question, we must reduce the abstract objects A and B to concrete objects and apply our scientific knowledge to ground the recursion. Using chickens and eggs as our objects, we have to precisely define what chickens and what eggs to consider.

The question "which came first, chickens or any type of egg?" is not a causal dilemma at all, and further is not faithful to the original purpose of the question. The ancient Greeks that first posed this question had no concept of evolution and no inkling that chickens could have any relationship to other egg types, so they would not have asked, "which came first, the chicken or the fish egg?" To the ancient Greeks, such a question isn't a dilemma, it's complete nonsense. Thus, the paper linked in my last post is invalid.

The more precise and faithful phrasing of the dilemma is, "which came first, the chicken or the chicken egg?", or more generally, "which came first, species S_n or it's reproductive mechanism R_n?"

S_n and R_n are in the appropriate recursive relation to form a causal dilemma, and we can ground it in biology and chemistry. The very first single-celled organism did not form by mitosis, thus the first single-celled organism, S_∅ preceded its own reproduction mechanism, R_∅. Thus, the dominoes fall, ie. the first egg-laying species was not hatched from an egg, thus it too preceded its own reproductive mechanism, and so on, ad infinitum.

Eventually, we reach chickens and chicken eggs, and the conclusion is simply, that the chicken necessarily came before its egg.

Embedded Stack Language for .NET

2008-11-07T12:28:00.000-05:00

Parametric polymorphism is a powerful tool for constructing and composing safe programs. To demonstrate this, I've constructed a tiny embedded stack language in C#, and I exploited C# generics, aka parametric polymorphism, to ensure that any embedded programs are type-safe, and thus, "can't go wrong".
Moreover, this language is jitted, since I use ILGenerator of System.Reflection.Emit, and the complexity of doing this was no higher than creating an interpreter. This is mainly because the CLR is itself a stack-based VM, and so jitting a stack-based program to a stack-based IL is fairly natural.

Here is the type-safe representation of the stack:

public struct Stack<R, T> : IDisposable
{
    internal ILGenerator gen;
    public Stack(ILGenerator gen)
    {
        this.gen = gen;
    }
    public void Dispose()
    {
        this.Return();
    }
}

This type encapsulates the IL output stream and uses two phantom type variables to encode the values at the top of the execution stack. The T parameter represents the top of the stack, and the R parameter represents the rest of the stack.

A few more types are needed to safely represent other reflected objects used during code generation:

// Represents the 'void' type used in some functions
public struct Unit
{
}
// Represents a named function with a known type structure T→R.
// This could be a void→void, an int→string, etc.
public struct Function<T, R>
{
    internal MethodInfo method;
    public Function(Action<T> f)
    {
        this.method = f.Method;
    }
}

Here's a test program demonstrating the use:


class Program
{
    static void Main(string[] args)
    {
        var d = new DynamicMethod("test", typeof(void), null);
        using (var s = new Stack<Unit, Unit>(d.GetILGenerator()))
        {   // equivalent to: () => Console.WriteLine(1 + 2);
            s.Int(1)
            .Int(2)
            .Add()
            .Apply(new Function<int, Unit>(Console.WriteLine));
        }
        d.Invoke(null, null);
        Console.ReadLine();
    }
}

Next I define a set of extension methods operating on typed stack objects, all parameterized by the underlying types. You can see how the top elements of the stack are specified, and how each operation consumes these elements or otherwise modifies the stack:

public static class CodeGen
{
    // Apply a function to its arguments; note that function args and arity
    // is checked at compile-time
    public static Stack<R, R0>
      Apply<R, T, R0>(this Stack<R, T> stack, Function<T, R0> target)
    {
        stack.gen.EmitCall(OpCodes.Call, target.method, null);
        return new Stack<R, R0>(stack.gen);
    }
    // Embed an literal integer in the IL stream
    public static Stack<Stack<R, T>, int>
      Int<R, T>(this Stack<R, T> stack, int i)
    {
        stack.gen.Emit(OpCodes.Ldc_I4, i);
        return new Stack<Stack<R, T>, int>(stack.gen);
    }
    // Add the two integers at the top of the execution stack
    public static Stack<R, T>
      Add<R, T>(this Stack<Stack<R, T>, T> stack)
    {
        stack.gen.Emit(OpCodes.Add);
        return new Stack<R, T>(stack.gen);
    }
    // Return from the current function
    public static Stack<R, T>
      Return<R, T>(this Stack<R, T> stack)
    {
        stack.gen.Emit(OpCodes.Ret);
        return new Stack<R, T>(stack.gen);
    }
}

This is obviously a fairly limited set of functionality, and it would require a great deal more work and thought to properly abstract the full execution of CIL (especially exceptions!), but it just might be possible. A large subset is certainly possible.

It might serve as an interesting alternative to System.Linq.Expressions for some code generation applications, since Linq expressions are largely untyped. Here are a few more opcode examples for reference purposes:


    // Duplicate the top element
    public static Stack<Stack<R, T>, T>
      Dup<R, T>(this Stack<R, T> stack)
    {
        stack.gen.Emit(OpCodes.Dup);
        return new Stack<Stack<R, T>, T>(stack.gen);
    }    // index into an array
    public static Stack<R, T>
      LoadArrayIndex<R, T>(this Stack<R, Stack<T[], int>> stack)
    {
        stack.gen.Emit(OpCodes.Ldelem, typeof(T));
        return new Stack<R, T>(stack.gen);
    }
    // runtime type test
    public static Stack<R, T>
      IsOfType<R, T, T>(this Stack<R, T> stack)
        where T : class
    {
        stack.gen.Emit(OpCodes.Isinst, typeof(T));
        return new Stack<R, T>(stack.gen);
    }

Pasting all of the code in this post into a file and compiling it should just work.

Wrapping all CIL opcodes this way could be quite useful, since you're guaranteed to have a working program if your code type checks. If you have a language, embedded or otherwise, using this sort of technique might be a good way to achieve a type-safe JIT for .NET, assuming you can assign a stack-based execution semantics. Since you're compiling to .NET, it will need exactly such a stack semantics anyway!

Reflection, Attributes and Parameterization

2008-11-04T10:26:00.000-05:00

I used to be a big fan of reflection, and C#'s attributes also looked like a significant enhancement. Attributes provide a declarative way to attach metadata to fields, methods, and classes, and this metadata is often used during reflection.

The more I learned about functional programming, type systems, and so on, the more I came to realize that reflection isn't all it's cracked up to be. Consider .NET serialization. You can annotate fields you don't want serialized with the attribute [field:NonSerialized].

However, metadata is just data, and every usage of attributes can be replaced with a pair of interfaces. Using [field:NonSerialized] as an example, we can translate this class:

class Foo {
  [field:NonSerialized]
  object bar;
}

Into one like this:

// these two interfaces take the place of a NonSerializableAttribute declaration
interface INonSerialized {
  void Field<T>(ref T field);
}
interface IUnserializableMembers {
  void Unserializable(INonSerialized s);
}
class Foo : IUnserializableMembers {
  object bar;
  void Unserializabe(INonSerializable s) {
    s.Field(ref bar);
  }
}

Essentially, we are replacing reflection and metadata with parameterization, which is always safer. This structure is also much more efficient than reflection and attribute checking.

Consider another example, the pinnacle of reflection, O/R mapping. Mapping declarations are often specified in separate files and even in a whole other language (often XML or attributes), which means they don't benefit from static typing. However, using the translation from above, we can obtain the following strongly type-checked mapping specification:

// specifies the relationships of objects fields to table fields
interface IRelation
{
    // 'name' specifies the field name in the table
    void Key<T>(ref T id, string name);
    void Field<T>(ref T value, string name);
    void Foreign<T>(ref T fk, string name);
    void ForeignInverse<T>(ref T fk, string foreignName);
    void List<T>(ref IList<T> list);
    void List<T>(ref IList<T> list, string orderBy);
    void Map<K, T>(ref IDictionary<K, T> dict);
}
// declares an object as having a mapping to an underlying table
interface IPersistent
{
    void Map(IRelation f);
}
// how to use the above two interfaces
class Bar: IPersistent
{
    int id;
    string foo;
    public void Map(IRelation f)
    {
        f.Key(ref id, "Id");
        f.Field(ref foo, "Foo");
    }
    public string Foo
    {
        get { return foo; }
    }
}

There are in general two implementors of IRelation: hydration, when the object is loaded from the database and the object's fields are populated, and write-back, when the object is being written back to the database. The IRelation interface is general enough to support both use-cases because IRelation accepts references to the object's fields.

This specification of the mappings is more concise than XML mappings, and is strongly type-checked at compile-time. The disadvantage is obviously that the domain objects are exposed to mapping, but this would be the case with attributes anyway.

Using XML allows one to cleanly separate mappings from domain objects, but I'm coming to believe that this isn't necessarily a good thing. I think it's more important to ensure that the mapping specification is concise and declarative.

Ultimately, any use of attributes in C# for reflection purposes can be replaced by the use of a pair of interfaces without losing the declarative benefits.

Garbage Collection Representations Continued

2008-11-03T16:36:00.000-05:00

In a previous post, I discussed representations used for polymorphic parameters. These special data representations are a contract between the language and the runtime which enables the runtime to traverse data structures to collect garbage.

64-Bit Polymorphic Representation

I had neglected to mention this interesting variant of tagged representations that I had come across at one point, but which I believe is not in widespread use. This representation uses full 64-bit floating point representations for all polymorphic values, and encodes non-floating point data in the unused bits of NaN values. IEEE 754 floating point numbers reserve 12 of the 64 bits for flagging NaN values, so the remaining bits are free to use for encoding integers, pointers, and so on.

I haven't found very much empirical data on this approach, but it looks promising. The polymorphic representation is doubled in size, but the structure is unboxed, so the polymorphic function call overhead may be slightly higher, but garbage collector pressure is reduced since less boxing is needed. Also, this representation can be used to ensure that all values are properly 8-byte aligned, which is often an efficiency gain in modern memory systems. This also has the advantage of permitting unboxed floating point values, which is a significant slowdown for the other tagged representations.

Natural Representations with Bitmasks

A new representation I recently came across is being used in the SML# language. Consider a typical tagged representation where 1-bit is co-opted to distinguish integers from pointers. Each polymorphic parameter must carry this 1 bit.

But there is no reason for this 1 bit to be contained within the parameter itself. Consider lifting this 1 bit to an extra function parameter, so:

val f: 'a → 'b → 'c

becomes:

val f: 'a * Bool → 'b * Bool → 'c * Bool

The Bool is the flag indicating whether the parameter is a pointer or an integer. But using a full function parameter to hold a single bit is a waste, so let's coalesce all the Bool parameters into a single Bitmask:

val f: Bitmask → 'a → 'b → 'c

Bitmask can be an arbitrarily long sequence of bits, and each bit in the mask corresponds to the bit that would normally be in the pointer/integer representation of the corresponding parameter in a typical tagged representation. By lifting the tag bit to an external parameter, we can now use full natural representations for all parameters.

Calling a polymorphic function now consists of masking and shifting to extract the bit for the given parameter, or assigning one if calling from a monomorphic function.

Bitmasks must also accompany polymorphic data structures. The presence of any polymorphic type variable implies the requirement for a bitmask. It's also not clear how expensive this shifting is in relation to inline tag bits. SML# does not yet have a native code compiler, so any comparisons to other SML compilers aren't representative.

However, the bitmask representation does not unbox floating point numbers, but a hybrid scheme with the above 64-bit representation is possible.

Consider the lifted 1-bit to indicate whether the parameter is word-sized (1), or larger (0). Larger parameters require a full 64-bit representation, while word-sized parameters do not. The garbage collector thus skips any parameters of bitmask tag value 1 (since they are unboxed integers), and analyzes any values of bitmask tag value 0 as a 64-bit value. If the 64-bit is a NaN, the value is further analyzed to extract a single distinguished bit indicating whether it is a pointer. If it is not a pointer, it is skipped (since it is an unboxed floating point value). If it is a pointer, the structure pointed to is traversed.

This last scheme provides natural representations for integers and floating point numbers, and expands the representation of pointers in polymorphic functions by one word. Other tradeoffs are certainly possible.

SysCache build for NHibernate 2.0.1GA

2008-10-21T13:12:00.000-04:00

NHibernate 2.0.1GA is the latest binary download available, but it seems the NHibernate.Caches.SysCache binary release is lagging behind, as the download at Sourceforge was built against NHibernate 2.0.0. Here's a version of NHibernate.Caches.SysCache built against 2.0.1GA.

Dispatching: VTables vs. Runtime Tests and Casts

2008-10-20T14:22:00.000-04:00

Object oriented languages like C# and Java use method dispatching techniques to select a concrete method to invoke when given a polymorphic type. By far the most common technique is the virtual method table, or vtable for short.

Long ago I had updated the above Wikipedia page with information regarding alternative dispatch techniques. Research published a few years back indicated that dispatching through a vtable incurred astonishing overheads, as high as 50% of total execution time. Alternative dispatch techniques based on runtime tests, such as a linear sequence of if statements checking for the various concrete class types, or a sequence of nested if statements forming a binary search, were often more efficient on a variety of hardware.

Vtables are rather flexible however, and the composition of a number of vtables can encode a variety of advanced dispatching behaviour. The .NET CLR utilizes vtables, and I've sketched out rough encodings of first-class functions, algebraic data types and pattern matching, higher-ranked polymorphism, and even a form of first-class messages, all by encoding them as virtual method dispatches.

Unfortunately, research indicated that vtable dispatch is quite expensive, and many of these idioms require at least one and often two virtual dispatches. Runtime tests and casts might be usable here instead, but a call site compiled for a fixed hierarchy of classes cannot be extended as easily as vtable-based dispatching. The only exception is a JIT using a technique called "polymorphic inline caches", which neither the CLR nor JVM utilize.

So I set about to measure the dispatch overhead on the CLR. Here's the source for my test, which consists of 3 classes in a hierarchy, each of which provide a visitor for double-dispatching, and a single method for the single virtual dispatch test. The driver code performs the runtime tests and casts at the dispatch site for the last case.

The numbers are total CPU ticks for the entire test, so lower numbers are better. It's a purely CPU-bound test, and I ran it on a Core 2 Duo 2.13GHz. I used .NET's high resolution timer, and I threw away the highest and lowest numbers:

Double Dispatch	Runtime Test	Single Dispatch
1658222872	1092469328	1136358792
1659474960	1092917368	1136520160
1659485472	1093638752	1136745536
1659866480	1094546584	1136985448
1660287768	1094639088	1137321136
1660488312	1094689040	1137526400
1660662648	1094856216	1137994576
1662110088	1095503256	1138300032
1666248296	1095734848	1138461264
1667377456	1095989528	1138609112
1672127744	1097126880	1141472360
Avg:
1662395645.09	1094737353.45	1137844983.27

As you can see, runtime tests and casts are surprisingly efficient, beating out even single dispatch. Any functional language targeting the CLR will definitely want to use runtime tests to implement pattern matching. I might try a deeper hierarchy at some point, but research has shown that up to 95% of algebraic types have 3 cases or less.

Unfortunately, when the complete set of concrete types is not known, a vtable dispatch is unavoidable, unless one resorts to runtime code generation to recompile the dispatch site. This is essentially a polymorphic inline cache, and it requires more sophisticated runtime infrastructure than the CLR natively supports, though it is possible if the language abstracts program execution away from how the CLR natively works.

So in summary, vtables are nice and simple, but rather inefficient on current hardware.

Tagless Interpreters in C#

2008-09-12T10:50:00.000-04:00

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 by checking the tags, then evaluates the result by dispatching to the appropriate handler.

let eval exp env = match exp with
  | Int(i) -> i
  | Sub(e1,e2) -> (eval e1) - (eval e2)
  | Add(e1,e2) -> (eval e1) + (eval e2);;

This is fine for simple languages, but it's not very efficient since tag decode and dispatch can expensive. Eliminating tags via program analysis, like partial evaluation, yields a simple compiler of sorts, thus yielding efficient DSLs.

Furthermore, we would like to exploit the type checking of the host language to ensure the type safety of the embedded language's interpreter, and type safety of any expressions of the embedded language. Unfortunately, more sophisticated languages written using this structure make it difficult to ensure that all the cases in the language are properly handled, which then requires the use of runtime errors.

By far the simplest solution to all of these problems that I've come across, is a paper by Jacques Carette, Oleg Kiselyov, and Chung-chieh Shan, Finally Tagless, Partially Evaluated, Tagless Staged Interpreters for Simpler Typed Languages.

If I understand the terminology correctly, they use a final algebra instead of an initial algebra to describe a language. In other words, instead of using data types to describe language expressions, they use functions. The language above is described using four functions provided by a module:

module type L = sig
  type exp
  val Int : int -> exp
  val Add : exp -> exp -> exp
  val Sub : exp -> exp -> exp
end;;

An interpreter for this language is trivial:

module I : L = struct
  let Int i = i
  let Add i1 i2 = i1 + i2
  let Sub i1 i2 = i1 -i2
end;;

Constructing an expression of this little language from within the host language is simple:

let test l:L = 
  let i = l.Int 1 in
    let sum = l.Add i (l.Int 2);; (* sum is now 3 *)

This embedded program abstracts over the type of the "interpreter" used to evaluate it. In other words, if we build a compiler backend for the module type L, we can use it to evaluate this term. A compiler is overkill for this simple language, but the more sophisticated the embedded language, the more attractive a compiler looks.

This toy arithmetic language just illustrates the main ideas, but the language described in the paper is actually a full-fledged programming language, with if-statements, first-class functions, etc. The authors then extend their tagless interpreter into a full fledged compiler using MetaOCaml's staging facilities, and then further extend the compiler into a partial evaluator. There are also more sections on abstracting evaluation order of the embedded language, ie. making the embedded language lazy even if the host language is strict, and self-interpretation (ie. metacircular interpretation).

It's a very exciting result, but as Oleg describes in the LtU thread linked to above, the abstraction over "interpreter" types L, requires the host language to abstract over type constructors. As I explained before, C# cannot do this. In order to implement a program which abstracts over type constructors in some way, we have to resort to dynamics. In other words, we have to use casts.

I have devised three techniques to structure these interpreters to be mostly safe. The tradeoffs are slightly different in each, but in all cases, the interpreter and all embedded language terms are type-safe as long as the client doesn't try any hijinks. If they do, the resulting runtime errors are a perfectly acceptable compromise IMO. The embedded language I describe is also a full-fledged programming language with if-statements, lambdas, and so on, and all examples are written in C#.

The first implementation uses a ML-module-to-C# translation I described in a previous post on this blog. It's actually rather complicated, and you should probably skip over it unless you're masochistic enough to want to delve into nitty gritty details. This encoding is the safest of the three however, as I believe there is no way to trigger a runtime exception except by resorting to reflection.

The second implementation uses a much more natural functional-style encoding, where the language is described by an interface, and an expression is an extensible data type Exp that must be implemented by an interpreter. All Exp types are "branded" by the type of the interpreter, so it's not possible to accidentally mix expressions from different interpreters.

However, because Exp is extensible, this leaves the interpreter open to client injections, where a client can trigger a runtime exception if they subclass Exp themselves, and inject such an Exp value into a program term. This is only a problem if a trusted component evaluates program terms built by untrusted clients. The trusted component must still be aware that runtime errors are possible if clients can be malicious, which seems like a perfectly acceptable compromise for the simplicity of this solution.

The third implementation is a more object-oriented style encoding, reminiscent of Smalltalk. Each core type is now its own class, and operations on those types are methods on that class. For instance, an if-statement is the If method on the Bool class.

The language interface consists only of constructors for the core language types. This approach is more verbose than the functional-style implementation, but it permits a more natural embedding of program terms in C#, because we can now use operators and ordinary method calls to operate on program terms. Like the second implementation, this too can throw runtime errors based on client-injected Exp types, so the same caveats apply.

It's not yet clear which of the last two implementations is preferable, but I prefer the functional-style for its brevity if you're writing a real interpreter and/or compiler for a language. Functional-style programs excel at symbol manipulation. If you're constructing embedded programs from within C# only, then the last implementation is probably preferable, since the availability of operators can make program terms less verbose.

All three implementations abstract over the type of "interpreter" for program terms. It could be a straight-laced interpreter, or it could be a code generator backend (like System.Runtime.Emit). For instance, in the post for the third implementation, I briefly describe a JavaScript-generating backend for an embedded language I'm playing with. It would allow an embedded program to transparently execute server-side via an interpreter or client-side via JavaScript depending on a client's capabilities.

Consider the possible uses for transparently displaying AJAX pages server-side for thin HTML-only clients, and client side for real browsers. In other words, you write this code only once. Witness the power of DSLs.

Mobile Continuations for the Web

2008-08-18T10:36:00.000-04:00

A continuation is basically the state of a program at the time the continuation was captured. For a common example, consider a blocking system call for any operating system. If the system call blocks the process, the continuation of that process is placed on a blocked queue until the system call completes. When the operation completes, the continuation is removed from the queue and resumed with the result of the system call.

There has been plenty of well-deserved hoopla around continuations for web interaction. Navigating a website is a great deal like operating on a program's continuations. A page generated from a server-side program contains references to a number of program continuations in its links and forms. Clicking a link or submitting a form invokes the captured continuation which the server then executes. The result is yet another set of continuations on the resulting page, ad infinitum.

Unfortunately, most continuation frameworks are designed around server-side continuations, where the continuations are saved on the server, and the client receives only a secure token naming the continuation. The Waterken server is a particularly beautiful example of this for Java. Awhile ago I ported an older version of the Waterken server to ASP.NET. Here is a public continuation for the comments page, and embedded in the comments page is the editing authority, which is an unguessable capability URL for the continuation to edit the comments page.

The Waterken "web-calculus" is actually a full blown persistent, distributed object system with a binding for the web.

However, maintaining persistent server-side state significantly complicates many aspects of web systems. It makes load balancing servers difficult, and persistent continuations are single threaded so only one invocation can proceed at a time which hurts scalability. Furthermore, if the continuations are persistent, as they are in Waterken which provides orthogonal persistence, then we must also contend with schema upgrade.

Two recent articles prompted me to re-examine these issues and devise a solution. First, Tommy McGuire posted a link to his "Infernal Device" paper on LtU. His paper describes a set of structures which can be used to develop an application by reifying the application's states as transitions in a finite state machine. The Transition objects are essentially application-specific partial continuations. The paper also details all of the different storage available in a browser, and how it can be exploited by a server to save state on the client.

For page-local state, the browser URL can hold up to 2kB on IE (other browsers can store more), and we have embedded form fields for POST requests. For site-local state, we have cookies which can be in the multi-kB size.

Then I came across this blog post about scaling Seaside by reducing the need to capture server-side state. The best way to optimize expensive operations is by avoiding them completely!

However, much program state does not need to reside on the server. We can capture a limited set of program state in the browser itself. In essence, we serialize the program continuation in the browser's URL or in its form fields. We also encrypt the serialized form to maintain integrity.

And so our program continuations have become mobile objects that migrate between client and server and can survive server restarts as long as any server state the continuations access also survives restart. A set of load balanced machines need only share the encryption keys, and user requests seamlessly migrate between them.

I've created a small library for mobile continuations written in C#. I also provide an IHttpHandler for use with ASP.NET. A web application using this library doesn't need to use any web controls or .aspx pages. An application is structured as a set of continuations which implement two operations: Show, and Apply. Show outputs the continuation via display-independent set of interfaces. Apply is invoked when a continuation receives a POST request. It takes a NameValueCollection containing all of the form's fields. This takes the place of a continuation's named arguments. I could implement a more elaborate system as found in the Waterken server where the fields are implicitly typed and named, but I felt a more limited scope is preferable for the time being.

By convention, continuations in the research literature are generally named "k", so the continuation interface is named K. This simple HelloWorld class implements the K interface and it embeds a continuation to an Adder object in its display:

    public struct HelloWorld : K
    {
        public void Show(IWindow v)
        {
            v.Title("Hello world!");
            v.Body(this);
        }

        public void Show(IBody v)
        {
            v.Const("Hello", "Hello world!");
            v.Promise("Adder", new Adder());
        }

        public void Show(IInput v)
        {
        }

        public K Apply(NameValueCollection args)
        {
            return this;
        }
    }

The Adder class is equally simple, consisting of a text input and a submit button. This continuation builds a form which submits to itself. When applying the continuation, it adds its currently stored value to the value specified in the form and returns a new instance of Adder with the stored value.

    public struct Adder : K
    {
        int n;
        string e;
        public Adder(int n)
        {
            this.n = n;
            this.e = "";
        }

        public void Show(IWindow v)
        {
            v.Title("Adder!");
            v.Body(this);
        }

        public void Show(IBody v)
        {
            if (!string.IsNullOrEmpty(e))
            {
                v.Const("error", "Error: " + e);
            }
            v.Literal(n);
            v.Literal(" + ");
            v.K("y", "add", this);
        }

        public void Show(IInput v)
        {
            v.Text("x", "", "");
        }

        public K Apply(NameValueCollection args)
        {
            try
            {
                return new Adder(this.n + int.Parse(args["x"]));
            }
            catch
            {
                this.e = "Invalid number specified.";
                return this;
            }
        }
    }

The library also provides a compact object serializer. HelloWorld serializes to 48 bytes. Adding some simple fields barely increases the size at all. You probably won't be entering any of these URLs by hand of course. There are a few more optimizations that can be made to the serializer as well. CrystalTech hosts ASP.NET in a medium trust environment, so the library also works for shared hosts. Some contortions were necessary, and fully general object serialization is not yet available (for instance, serializing delegates will fail).

By default, the library assumes all continuation objects can be migrated to clients. This encourages more scalable program structures. If some object needs to remain server-side, simply implement the ILocal interface. There are no operations, but the interface marks the class as non-mobile. The default behaviour in this case is to generate a random 64-bit token, and migrate this token instead. When the token migrates back to the server, it re-connects to the original object. If the server restarts, this state is lost, but a state server as found in ASP.NET can be built which will allow the state to survive restarts and be shared between machines.

Schema upgrade can still pose a problem unfortunately, and unlike with server-side state where the continuations are stored centrally, you can't use a tool to upgrade them. Altering method implementations does not pose an upgrade problem. Adding and removing fields is problematic however.

Fortunately, applications using the library are already structured for easy upgrade and permit a configurable policy for deprecation. Basically, don't touch existing classes, and only create new classes. Replace the use of old classes in the program with the new classes, then whenever you judge it appropriate, remove the old class entirely. On any serialization errors, the library will invoke an application-specific handler which returns a continuation. I think any conceivable upgrade policy is feasible given these primitives.

The current source for the library is available here. I plan to improve the mechanism for displaying continuations in a medium-independent fashion. Ideally, I'd like to be able to create a binding for Windows.Forms, and for JSON requests, so that the same continuation-structured application can be reused unmodified in different environments.

Garbage Collection Representations

2008-07-28T13:26:00.000-04:00

I have yet to find a comprehensive description of the various data representations used for garbage collection. This isn't an overview of garbage collection algorithms, but an overview of how to distinguish pointers from other values and how to traverse the data structures, which has seemingly gotten only a short riff in the literature. I aim to give an in-depth overview of the techniques I've come across or managed to puzzle out on my own.

Boxing: all values are allocated on the heap, so basically everything is a pointer, thus, there is no ambiguity between pointers and values.

Tagged pointers: pointers are distinguished from ordinary values by some sort of tag. This information is often encoded in the pointer or value itself for a very compact representation.

Type-passing: each parameter of a function is associated with a set of operations, usually referred to as a "dictionary", which is similar to an interface in object-oriented languages. This dictionary defines a collect() operation for each type, which will traverse the structure looking for garbage. This dictionary can be passed into every function, or it can be reconstructed from the stack.

Why Are Special Representations Needed?

One might first ask why special representations are even needed. At compile-time, it's generally perfectly clear what types are being used, as well as the types of the various data structures.

While this is true of simple C-like languages, it isn't true of polymorphic languages. C is what's known as monomorphic, meaning all parameters have a fixed, known type at compile-time.

By contrast, polymorphic languages can have function parameters that can accept any type, and this type is not fixed at any time. A simple example is the identity function:

val id: 'a -> 'a

This function accepts a parameter of any type, and returns a value of the same type. But since you can't know this type ahead of time, you need some way to encode the type in a running program so the garbage collector has enough information to traverse it in its search for garbage.

This problem only really crops up with the combination of polymorphism and separate compilation, meaning you compile a program to a single machine code file which can then be distributed without prior knowledge of how it will be instantiated and used. The .NET CLR is an example of a platform which supports polymorphism, but not separate compilation, since it uses the JIT to specialize methods that use generics. A specialized method is GC'd differently depending on whether it's instantiated with a reference type or a value type. In separately compiled languages, this is not true, hence the need for a special representation.

Boxing

All boxed values are allocated in the heap, including integers and floats. This is the most straightforward representation, and the least efficient of the options both in terms of space and time.

The extra space use comes from the additional pointer needed to indirect to an int, and the additional allocator headers required to track it.

The additional runtime overhead is incurred when repeatedly indirecting the pointers to access the values, and the additional garbage collector pressure from having so many small values.

Allocating many small types like this could also lead to significant memory fragmentation, which balloons memory use, and induces poor locality of reference.

A boxed version of the identity function would look like this:

void * id(void * v) {
  return v;
}

Basically, we don't know anything about the value involved, and the void pointer just points to a heap location where the value is stored.

There is a single flag stored in the allocator headers to indicate whether this is a compound structure or a value. An int is a value, and a (int,int) pair is a compound. All compounds consist of pointers, so the collector just recursively traverses all of the pointers in the structure, and halts when it reaches values. For compounds, the size of the structure must also be encoded in the header.

Tagged Pointers

Tagged pointers have a long tradition in functional languages. Typically, all of the tag bits are encoded within pointers and values themselves, so the representation is very compact. This is important for functional languages in particular, since they encourage the allocation of many small objects.

Modern memory allocation algorithms generally segregate free space in variously sized buckets. The smallest bucket is generally the size of a pointer, or perhaps twice the size of a pointer. This is generally 4 bytes on a 32-bit machine, so at the very least, the pointer will always point to an address aligned on a 4-byte boundary.

However, most pointers are byte-addressable, meaning they can point to addresses that are aligned on a single byte boundary. This means that the lowest two bits of a pointer are generally wasted space, since they will always be 0. So let's use that wasted space for something!

Let's say we use the lowest bit to differentiate between pointers and integers on the stack and in data structures. This means an int will no longer be 32-bits, but 31-bits, with 1 bit going to this flag. If the lowest bit is 0, it's an int, and if the low order bit is 1, it's a pointer. This means we can scan a stack frame or a data structure one word at a time and easily distinguish integers from pointers by just checking the lowest bit.

So now we can have fully unboxed integers, which saves a lot of time and space in programs since we no longer need to allocate them on the heap. Anything larger than a word must still be heap-allocated.

Field offset calculations now require us to omit the lowest bit, which involves subtracting 1 from any offset. Since most offsets are statically known, this costs nothing at runtime.

There is one remaining problem with the above representation, namely, we still don't know the size of a structure! When the GC traverses a structure, it will iterate right off of the end since it doesn't know when to stop.

The paper I linked to above places the size in a header word present in every structure. This header word is split into multiple fields. On a 32-bit machine, the lowest 22 bits are used for the size of the structure in words, the next two bits are used by the garbage collector (typically a mark-sweep), and the last 8 bits are used for the constructor tag, ie. Nil or Cons. The constructor tag is typically present in every data structure, but using a whole word for it is somewhat wasteful, so this more compact representation is quite useful.

This representation may also permit some interesting optimizations. Since word-sized values are unboxed, all heap allocated structures will be at least 8-bytes in size, consisting of the header word followed by a number of data words (a commenter pointed out that this doesn't necessarily imply 8-byte alignment however; while true, as mentioned above allocators segregate memory into variously sized buckets, and so we need to simply ensure that these buckets are multiples of 8-bytes). This means the third lowest order bit is also unused, giving us two free bits in every pointer.

Consider the following type declaration:

type 'a Foo = Foo1 | Foo2 of int | Foo3 of 'a | Foo4 of 'a * 'a

Since Foo1 does not contain any embedded values or pointers, we don't need a pointer for it at all and it can just be represented by a simple unboxed integer.

Foo2 contains an integer, so we must allocate a heap structure to contain this case.

Foo3 and Foo4 are the interesting cases. 'a is a polymorphic value, and if instantiated with a pointer type, we don't need to allocate a heap structure for it. Basically, we can use the two free bits to encode up to 3 constructors for such values, and remove a level of indirection. Pattern matching on such structures is broken down into 3 cases:

If it's an int, then it's one of the empty constructors.

If it's a pointer, and the second and third lowest order bits are clear, extract the constructor tag from the header, and the value is just after the header.

Else, extract the constructor tag from the pointer, and the pointer is a pointer to the value.

However, to maintain separate compilation, we cannot assume that 'a is a pointer type, as it could be an int. Therefore only Foo4 can benefit from this inlining optimization in this particular case.

Coming back to the question of identifying structure sizes, an alternative representation which I have not seen described anywhere, is to use the unused third lowest bit as a mark bit to terminate GC scanning, and use the second lowest bit to distinguish structures with nested pointers, and those that are pointer-free.

A '1' in the second lowest order bit position flags a "value structure" which contains no pointers. In other words, it consists entirely of integer-sized data, so the GC does not need to scan this structure. Alternately, a '0' in this position indicates a "compound structure" which contains pointers, and which must be scanned by the GC.

A '1' in the third lowest order bit position flags the last pointer in a data structure. This bit is only set in pointers within data structures, and is clear everywhere else.

Note that only the last pointer is used for the halt condition, since the collector cares only about pointers and ignores unboxed values. The compiler can optimize garbage collection by placing all pointers at the beginning of a structure. Also, when extracting a pointer from a structure or writing one into a structure, it should be masked to clear or set the appropriate bits.

Using this representation, we free the 22-bits used for the structure size in the header. We can thus reserve a full 24 bits for the GC, which expands our choice of GC algorithms considerably. Even ref-counting becomes feasible with 24-bits in the header.

One possible downside of this representation is that the size header was also used for array lengths. The length must now be stored in its own field in the structure, so we've effectively grown the array type by one word. Considering the size of arrays compared to a single word, this seems like an acceptable overhead for this representation's uniformity and flexibility.

Type-Passing

Type-passing, aka tagless GC, is the most sophisticated GC technique. There are two approaches that I'm aware of:

Dictionary-passing: a dictionary consisting of functions specific to the type is passed along with all values of that type. These functions know how to collect values of that type.

Type Reconstruction: basically, the concrete type of a polymorphic function is reconstructed at runtime by inferring the type from previous activation frames. Monomorphic functions have all the type information needed to fully specify any polymorphic parameters, so we just search the stack for the type information stored there.

The benefits are that pointers are just pointers, integers are full-sized integers, and no special meaning is assigned to their values or any bits contained within the word.

To my knowledge, only two languages have used this technique, Id and Mercury, and only Mercury is still available as far as I know. The .NET CLR's technique can also be considered a form of type-passing.

The downsides of dictionary-passing are that every polymorphic parameter is paired with a dictionary parameter, thus increasing the parameter lists of all polymorphic functions. The additional pushing and popping can outweigh any advantages that might be gained from dictionary-passing.

Type-reconstruction can remove the need to pass this parameter at the expense of additional runtime overhead. Basically, we don't need to pass this dictionary to every function call, we just need to get it paired with the parameter in the monomorphic function which calls the first polymorphic function. As we walk the stack we can then extract the dictionary for a given parameter from the last monomorphic function. This becomes more complicated with closures, since the dictionaries for polymorphic parameters must now be saved in the closure environment as well.

This process is essentially a form of type inference performed at runtime. Unfortunately, type inference often has pathological corner cases with exponential running time. These cases are unlikely, but inference in general has substantial overhead (see the Id paper).

Acknowledgments

Many thanks to Andreas Rossberg, of Alice ML fame, for patiently wading through my sometimes confused ramblings. :-)

[Edit: GHC's recent pointer tagging paper actually discusses the constructor inlining optimization I describe above, along with some hard numbers to quantify how many constructors can be eliminated. Turns out that >95% of constructors contain 3 cases or less, so the technique could amount to a substantial savings. Theoretically, it seems that every second nested data type could be unboxed in this fashion.]

Coroutines in C Redux

2008-07-18T10:38:00.000-04:00

My last post generated a bit of discussion here and on Reddit, where after further testing, I discovered that stack management didn't work properly on Windows. It would seem that embedded frame pointers on the stack are used to ensure that we are on the same stack, at least in DEBUG mode, and so growing or shrinking the stack generated cryptic errors.

These problems motivated me to explore alternate methods of implementing coroutines. Fundamentally, the current state of a computation is encapsulated in the stack. So switching between two concurrent computations means modifying the stack, either by swapping out the old stack for an entirely new one, or by copying the relevant portion of the stack to a save area, and restoring it when switching back. Coroutines and threads typically use stack switching, and continuations have traditionally used some sort of copying.

The initial coroutine implementation used stack switching, which is fairly efficient incurring only a register save, a pointer update, and a register restore. Stack copying involves a register save, a copy to save area, a copy from a save area, and a register restore. The additional copies incur a certain overhead.

The benefits of copying are that it's virtually guaranteed to work across all platforms, and that all stack data are restored to their original locations so the full semantics of C are available. Stack switching restricts certain C operations, such as taking the address of a local variable.

My naive copying implementation was about two orders of magnitude slower than stack switching. It performed about 300,000 context switches/sec on my Core 2 Duo, vs stack switching at ~12,500,000 context switches/sec. I reduced this overhead by an order of magnitude by caching stacks (~1,500,000 context switches/sec), so part of the stack save area is wasted, but at least we're not allocating and freeing on each context switch.

The copying implementation can be optimized further using lazy stack copying. Basically, only a portion of the stack is restored, and an underflow handler is set up as the return address of the last stack frame. The underflow handler then restores the next portion of the stack and resumes the computation. If the underflow handler is never invoked, then we only need to copy that small portion of the stack back to the save area, so this ends up being a huge win.

Unfortunately, while establishing an underflow handler is trivial to do in assembly, I haven't been able to figure out how to accomplish this in C. It would be a neat trick though, and I'd estimate that it would bring the performance of a copying implementation very close to a stack switching implementation.

I've also started playing with an implementation of delimited continuations for C, since this has the potential to reduce the amount of copying needed. It's tricky to do in C though, so I don't have anything solid yet.

For expediency, I have also implemented coroutines using Windows Fibers. Unfortunately, Fibers don't support any sort of copy or clone operation, so I had to retire coro_clone for the time being. This means my coroutine library can no longer be used to implement multishot continuations. Of course, this capability is trivial in a stack copying implementation. Hopefully I'll be able to figure out a way to improve the performance of copying coroutines/continuations in a portable way.

Coroutines in C

2008-07-16T20:00:00.001-04:00

I've just uploaded a functional coroutine library for C, called libconcurrency. It's available under the LGPL. I think it's the most complete, flexible and simplest coroutine implementation I've seen, so hopefully it will find some use.

Next on the todo list are some more rigourous tests of the corner cases, and then extending libconcurrency to scale across CPUs. This will make it the C equivalent of Manticore for ML.

There is a rich opportunity for scalable concurrency in C. Of course, I only built this library to serve as a core component of a virtual machine I'm building, and that's all I'm going to say about that. ;-)

The Chicken and the Egg - An Inductive Analysis

2008-05-26T19:18:00.000-04:00

In a slight departure from my usual computer science focused musings, I'm going to analyze another logical conundrum that has raged for centuries. Which came first, the chicken or the egg?

One of my many online debates clued me into the fact that there is a widespread belief that the egg came first. I even found a "paper" providing an in-depth analysis concluding the same. Unfortunately, the analysis appears flawed. An e-mail to the author bounced, so I figured I might as well post my brief analysis here.

A simple inductive analysis suffices to conclusively determine the causal chain.

Base case: single celled organism, asexual reproduction via mitosis (given our current knowledge)
n implies n+1: species n produces, by its own reproduction mechanism R_n, an offspring n+1 with a slightly different reproduction mechanism, R_n+1.
Conclusion: the "chicken" came first.

In this case, our "chickens" were not hatched from "chicken eggs", but were instead hatched from the "chicken's" progenitor's egg type. The authors of the paper attempted to disregard this semantic interpretation under "Chicken Precision", but as this is a metaphor, a "chicken" is merely a stand-in for a particular species to be substituted at will.

Thus, the only universally quantifiable proposition is that the "chicken" came first, since the first egg-bearing species, S_n+1 and R_n+1, was produced from some non-egg-based reproduction mechanism, R_n. The contrary proposition that the egg came first contradicts the base case of the above inductive argument where we know reproduction was based on asexual mitosis.

Unless our understanding of early biology changes radically, metaphorically and literally speaking, "chickens" came first.

[Edit: I posted an update to elaborate on why I believe my interpretation is more faithful to the original intent of the question, as first formulated in ancient Greece.]

Object/Relational Mapping and Factories

2008-04-17T15:07:00.000-04:00

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 fields. This means constructor and initialization code must be duplicated when running in another environment, or tedious refactoring is needed when changing the constructor interface. Further, the defaults are hardcoded in the code, which means changes in defaults require an application upgrade.

Instead, O/R mappers should promote a factory pattern for constructing application objects. Factories themselves are constructed when the application is initialized, and are henceforth singletons within a given application instance. O/R mappers don't support or encourage factories or singletons in this manner however, as they always map a key/identifier, to an object instance. Factories are slightly different as they are generally singletons.

For example, let's assume we have a simple Product class:

public abstract class Product
{
  int productId;
  decimal price;
  protected Product()
  {
  }
}

Now we have here a public constructor which requires a Quote object to initialize the base Product object. You can't sell 'abstract' products, so we need a concrete product, like a Table:

public class Table : Product
{
  int length;
  int width;
  public Table(int length, int width) : base()
  {
    this.length = length;
    this.width = width;
  }
}

Of course, a Table with dimensions of 0'x0' is invalid, so we need to ensure that a Table is initialized with a proper length and width. We can pass in a pair of default dimensions when constructing a Table instance in a controller, but chances are the default values will be the same everytime you construct an instance of Table. So why duplicate all that code?

For instance, suppose we have another class "DiningSet" which consists of a Table and a set of Chairs. Do we call the Table constructor with the same default values within the DiningSet constructor?

Of course, many of you might now be thinking, "just create an empty constructor which invokes the parameterized constructor with the default values; done". All well and good because your language likely supports the int type very well. Now suppose that constructor needs an object that cannot be just constructed at will from within application code, such as an existing object in the database.

Enter factories:

public interface IProductFactory
{
  Product Make();
}
public sealed class TableFactory : IProductFactory
{
  int defaultLength;
  int defaultWidth;
  public Product Make()
  {
    return new Table(defaultLength, defaultWidth);
  }
}

The IProductFactory abstract all factories which construct products. Any parameters that the base Product class accepts in its constructor are passed in to the Make() method, as this is shared across all Product Factories. TableFactory is mapped to a table with a single record containing the default length and width values. If the constructor requires an existing database object, this can be referenced via a foreign key constraint, and the O/R mapper will load the object reference and its dependencies for you.

Since factories are generally singletons, it would be nice if O/R mappers provided special loading functions:

public interface ISession
{
  T Load<T>(object id);
  T Singleton<T>();
}

This models and O/R mapper session interface after the one in NHibernate. Note that a special Singleton() method simply loads the singleton of the given type without needing an object identifier.

Our controller code is thus reduced to:

...
Product table = session.Singleton<TableFactory>().Make();
...

Which encapsulates all the constructor details in application objects, does not hardcode any default values since they live in the database and can be upgraded on the fly, isolates refactorings which alter the Table constructor interface to the TableFactory alone, and simplifies controller code as we don't need to load any objects. This is a "pure" object-oriented design, in that the application can almost bootstrap itself, instead of relying on its environment to properly endow it with "god-given" defaults.

This approach also enables another useful application pattern which I may describe in a future post.

[Edit: I've just realized that the above is misleading in some parts, so I'll amend soon. Singletons aren't needed as much as I suggest above.]

Permutations with Duplicates in C

2008-04-01T13:02:00.000-04:00

Calculating permutations has some fairly nifty algorithms out there. I recently ran into a permutation problem for which I couldn't find an existing algorithm. I admit that I didn't look too hard though. Basically, I needed the permutations of the elements of a set of size N over K slots. However, the permutations should include duplicate elements from the set, as K > N is valid configuration. This corresponds to N^K permutations. Most algorithms I found did not permit duplicate elements.

As an example of an application for such a permutation algorithm, imagine the set of all function signatures of arity K-1 over N types. This corresponds to K slots with N possible choices for each slot.

I devised a fairly simple implementation of such a permutation algorithm. Essentially, N forms the base of an arbitrary-precision integer of size K. In other words, we have an array of elements with a maximum of N which index our set. To permute, we simply increment the first element and propagate any overflow across the rest of the array. If the carry is 1 when we're done iterating over the whole array, then we're done generating permutations.

Calculating permutations has been reduced to counting! Here is the C code:

#include <stdio.h>

void print(const unsigned *slots, const unsigned K)
{
  unsigned i;
  for (i = 0; i < K; ++i) {
    printf("%4d", slots[i] );
  }
  printf("\n");
}

unsigned incr(unsigned *slots, const unsigned K, const unsigned N) {
  unsigned i, carry;
  print(slots, K);
  for (i=0, carry=1; i < K; ++i) {
    unsigned b = slots[i] + carry;
    carry = b/N;
    slots[i] = b % N;
  }
  return !carry;
}

void count(const unsigned N, const unsigned K) {
  unsigned i;
  unsigned *slots = calloc(K, sizeof(unsigned));
  while(incr(slots, K, N)) {
  }
}

//output:
//   0   0   0
//   1   0   0
//   0   1   0
//   1   1   0
//   0   0   1
//   1   0   1
//   0   1   1
//   1   1   1
int main(int argc, char ** argv) {
  count(2, 3);
  getchar();
}

The only assumption is that N is less than UINT_MAX. Also, for some insane reason that I cannot fathom, I can't get the slots to print in reverse order. The trivial reversal of the print loop induces an access violation under Windows:

void print(const unsigned *slots, const unsigned K)
{
  unsigned i;
  for (i = K-1; i >= 0; --i) {
    printf("%4d", slots[i] );
  }
  printf("\n");
}

The mind boggles.

[Edit: a commenter pointed out the problem, so the solution can be found in the comments.]

Blue-eyed Islander Puzzle - an analysis

2008-02-11T13:53:00.000-05:00

Many people find themselves stumped by the so-called Blue-Eyed Islanders puzzle. There is also much controversy over its supposed solution. I'm going to analyze the problem and the solution, and in the process, explain why the solution works.

To begin, let's modify the problem slightly and say that there's only 1 blue-eyed islander. When the foreigner makes his pronouncement, the blue-eyed islander looks around and sees no other blue eyes, and being logical, correctly deduces that his own eyes must be blue in order for the foreigner's statement to make sense. The lone blue-eyed islander thus commits suicide the following day at noon.

Now comes the tricky part, and the source of much confusion. Let's say there are 2 blue-eyed islanders, Mort and Bob. When the foreigner makes his pronouncement, Mort and Bob look around and see only each other. Mort and Bob thus both temporarily assume that the other will commit suicide the following day at noon. Imagine their chagrin when they gather in the village square at noon the next day, and Mort and Bob both look at each other in surprise because Mort thought Bob was going to commit suicide, and Bob thought the same of Mort! Now both Mort AND Bob know their own eye colour is blue, and they will both commit suicide on day 2.

The very same argument can be extended to 3 blue-eyed islanders, Mort, Bob and Sue, who will commit suicide on the third day at noon. The day of the pronouncement, the three of them see each other, and Sue assumes Mort and Bob see only each other. Being logical, she thus deduces that they will commit suicide on the second day, by the above argument. Mort and Bob each see the same number of blue eyes as Sue, and thus reach the very same conclusions.

Imagine Sue's chagrin, when she gathers in the village square on the second day, and Mort and Bob are both surprised that she's not committing suicide! She now knows that her eye colour is also blue, and all three of them will kill themselves on the third day.

This inductive argument can be generalized to N blue eyed islanders, where all N of them will suicide on the Nth day after the pronouncement. QED.

An Almost Type-Safe General Monad in C#, aka how to Abstract over Type Constructors using Dynamics

2008-01-19T14:27:00.000-05:00

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 the monad's encapsulated state,
   // and the binding function f.
   Monad<M, R> Bind<T, R>(
     object state,
     Fun<T, Monad<M, R>> f,
     Fun<Monad<M, R>, object> from,
     Fun<object, Monad<M, R>> to);
}

Looks a bit complicated, I know, but every piece is well-motivated. IMonadOps is fortunately the only interface that new monads must implement. Note the type constraints. The interface and the general monad both have a "phantom" or "witness" type M, constraining the type of the monad operations to the same IMonadOps type that created the monad. This means that the monad is entirely closed to extension and inspection.

Each IMonadOps is effectively a stateless singleton. The constraint to a struct is merely an optimization. Every IMonadOps implementor is actually very similar to the body of an ML module. If I want to invoke Identity.Zero, I can do it thusly:

default(Identity).Zero<int>();

This reveals the magic I used to define the Monad type. Whenever the Monad<M,T> type needs to invoke the underlying monad operations, it invokes the operation on the corresponding singleton M just like the above. Indexing the Monad by an IMonadOps implementation M, is like a linking step between Monad and M.

public sealed class Monad<M, T>
    where M : struct, IMonadOps<M>
{
    object state;

    Monad(object state)
    {
        this.state = state;
    }

    // The projection function.
    static object get<R>(Monad<M, R> m)
    {
        return m.state;
    }

    // The injection function.
    static Monad<M, R> ctor<R>(object state)
    {
        return new Monad<M, R>(state);
    }

    // The standard 'bind' operation. It dispatches to the
    // type-indexed 'bind', defined by M.
    public Monad<M, R> Bind<R>(Fun<T, Monad<M, R>> f)
    {
        return default(M).Bind<T, R>(state, f, get<R>, ctor<R>);
    }

    // The standard 'unit' operation, injecting a value into
    // the monad. It dispatches to the type-indexed unit
    // function defined by M.
    public static Monad<M, T> Unit(T t)
    {
        return new Monad<M, T>(default(M).Unit<T>(t));
    }

    public static Monad<M, T> Zero()
    {
        return new Monad<M, T>(default(M).Zero<T>());
    }
}

You can see the dispatching at work here. All monad operations are dispatched to the "linked" methods of M. In a sense, we have succeeded in abstracting over the concrete implementation of Monad.

Now comes the catch: it's not fully type-safe, because the encapsulated state of the monad must be stored as 'object'. This means that each monad body must ensure it properly casts to and from the appropriate type. This is again due to the type constructor abstraction limitation.

Your first thought might be, why can't the encapsulated state simply be 'T'? Well, if all you wanted was an Identity monad, then that would be fine. But consider the Maybe monad:

public struct Maybe : IMonadOps<Maybe>
{
    public object Unit<T>(T t)
    {
        return new Option<T>(t);
    }

    public object Zero<T>()
    {
        return new Option<T>();
    }

    public Monad<Maybe, R> Bind<T, R>(
      object state,
      Fun<T, Monad<Maybe, R>> f,
      Fun<Monad<Maybe, R>, object> from,
      Fun<object, Monad<Maybe, R>> to)
    {
        Option<T> value = (Option<T>)state;
        return (value.HasValue) ? f(value.Value) : Fail<R>();
    }

    public static Monad<Maybe, T> Fail<T>()
    {
        return Monad<Maybe, T>.Zero();
    }
}

The encapsulated state is an Option of type T, not a T. As another example, the List monad encapsulates a list of T's. Since we can't abstract over the type constructor for the encapsulated state, we thus need to resort to dynamic typing.

Now comes a slightly bizarre part: what are the injection and projection functions for? Well, despite the fact that IMonadOps is the "internal implementation" of Monad, it doesn't have direct access to the monad's internals. Unfortunately, sometimes that access is needed. Consider the List monad:

public struct ListM : IMonadOps<ListM>
{
    public object Unit<T>(T t)
    {
        return List.Cons<T>(t, List.Nil<T>());
    }

    public object Zero<T>()
    {
        return List.Nil<T>();
    }

    public Monad<ListM, R> Bind<T, R>(
      object state,
      Fun<T, Monad<ListM, R>> f,
      Fun<Monad<ListM, R>, object> from,
      Fun<object, Monad<ListM, R>> to)
    {
        return to(
            List.MapFlat<T, R>(
                state as List.t<T>, delegate(T t)
                {
                    return from(f(t)) as List.t<R>;
                }));
    }
}

ListM needs access to the private state of the returned list of Monads in order to flatten the list, but that access is not permitted since Monad is a separate, encapsulated type. There is no way to make this state available using inheritance or access modifiers, without also permitting the state to escape inadvertently.

Instead, the Monad provides an injection/projection pair, which are used to construct monad instances when given private state, or read out the private state of a monad instance, respectively. Note that encapsulation is maintained since this ability is granted only to the implementor of a given monad, which is already trusted with its own state.

I suspect there's a more efficient way to share the monad's state, but I'm a little tired from standing on my head all day for C#, so if anyone has any ideas, I welcome them. :-)

While this encoding is less efficient than the one described in my previous post, it's safer in some ways for users monad implementors alike, and I proved to myself that C#'s type system is powerful enough to encode the monad interface if you contort yourself appropriately. This technique for abstracting over type constructors might even be usable in my tagless Orc implementation.

The Worst Monad Tutorial... Except For All Those Others.

2008-01-18T19:33:00.000-05:00

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 converts an instance of that monad into another instance of a monad by passing its private state to the provided function. For instance, meet Haskell's Identity monad:

instance Monad Identity where
    return a           = Identity a   -- i.e. return = id 
    (Identity x) >>= f = f x          -- i.e. x >>= f = f x

Looks simple enough. Now meet Haskell's List monad:

instance Monad [] where
    bind m f  = concatMap f m
    return x = [x]
    fail s   = []

What's not at all obvious from any of the above signatures, or any of the existing tutorials, is that the monad that the function f returns, must be the same monad type. If you're in the list monad, f must return a new instance of the list monad. If you're in the identity monad, f must return a new instance of the identity monad. This simple fact eluded me for quite some time, and explains why the monad interface cannot be expressed in C#. We can still program using monads, but the interface can't be enforced by the type system.

So without further ado, here is the Identity monad in C#:

public class Identity<T> : Monad<T>
{
  T value;

  public Identity(T t)
  {
    value = t;
  }
  public Identity<B> Bind<B>(Fun<T, Identity<B>> f)
  {
    return f(value);
  }
}

The Monad<T> base class is actually empty, so it's just a marker interface. For those of you unfamiliar with the "Fun" delegate, it's just one of the many standard delegates I use for function signatures in my FP# library. Here is the List monad in C#:

public class ListMonad<T> : Monad<T>
{
    protected List.t<T> l;

    public ListMonad(T t)
    {
        l = t;
    }

    public ListMonad()
    {
        l = List.Nil<T>();
    }

    public ListMonad<B> Bind<B>(Fun<T, ListMonad<B>> f)
    {
        return new ListMonad<B>(
            List.MapFlat<T, B>(
                l, delegate(T t) { return f(t).l; }));
    }
}

Note that all of these monads in C# share a common structure. They have at least one constructor used to wrap a value (called 'return' earlier), and they all have a Bind method which operates on the value encapsulated in the monad, and maps it to a new instance of the monad. Since we have such a similar structure, is there a way to declare an interface or an abstract base class declaring the signature for the Bind method?

Unfortunately not, because C# cannot abstract over type constructors. If it could, the abstract monad class and the Identity monad would look something like:

public abstract class Monad<M,T> where M : Monad
{
  public abstract M<M, R> Bind<R>(Fun<T, M<M, R>> f);
}
public sealed class Identity<T> : Monad<Identity,T>
{
  ...
  public override Identity<R> Bind<R>(Fun<T, Identity<R>> f)
  ...
}

Note the two emphasized sections: the class constraint on Monad, and the type parameter Identity provides to Monad when inheriting from it. They are both used without a type argument. This is illegal in C#/.NET, but it's perfectly legal in languages with more powerful type systems, such as those with "kinds". Identity<int> has kind *, while Identity without a type argument has type *⇒*, ie. a function that constructs a type of kind * when given a type of kind *. This is why monads are not so easily translated into languages like C#.

Coming soon, a real example of using monads in C#?

Towards the best collection API... in C#. And some partial applications too.

2008-01-16T19:09:00.000-05:00

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 source file that I derived FoldLeftDerived from SuperFold. Deriving FoldRight is a bit trickier, so I have to think about it. The simple, inefficient, answer is to simply reverse the list.

I've also enhanced the FP# library with:

A number of tuple types (up to 10),
Tuple inference,just call: Tuple._(a,b,c,...)
streamed versions of Map/Filter/FoldRight over IEnumerable which don't build intermediate lists,
FoldLeft over IEnumerable including support for early termination,
FoldLeft over my purely functional list including support for early termination,
Option type now looks more like System.Nullable, with an overload for the | operator to choose between an empty option, or a default value [1],
Partial application for almost all defined function types

I'll probably remove SuperFold from my purely functional list, since I don't think it will end up being useful in C#. The iterated FoldLeft I defined is more efficient due to the lack of tail recursion, and the iterated version also supports early termination.

[1] It's very frustrating to see how close MS gets to a truly general and useful abstraction, only to lock it down for no apparent reason. What good reason is there for Nullable to be restricted to struct types? If you give it more than a second's thought, I think you'll realize that there is no good reason. Nullable is the option type if it weren't for this restriction!

ML Modules in C# - Sorely Missing Polymorphic Type Constructors

2008-01-08T11:43:00.000-05:00

As Chung-chieh Shan pointed out, my encoding of modules in C# is somewhat limited. In particular, I cannot abstract over type constructors, which is to say, C# is missing generics over generics. Consider the Orc.NET interpreter:

class Orc {
  class Exp<T> { ... }

  public Exp<U> Seq<T,U>(Exp<T> e1, <U>) { ... }
  public Exp<T> Par<T>(Exp<T> e1, Exp<T>) { ... }
  public Exp<T> Where<T>(Exp<T> e1, Exp<Promise<T>>) { ... }
}

This is the result of my translation, which was necessitated by the "Where" method. Where introduces a dependency which currently cannot be expressed with ordinary C# constraints, so the module encoding is necessary.

The above interface is a direct, faithful implementation of the Orc semantics. The implementation I currently have is an interpreter for those semantics. What if I want to provide a compiler instead? The interface should remain the same, but the implementation should differ. This is a classic abstraction problem.

It's clear that the implementations can be changed at compile-time, but providing a different Orc implementation at runtime, something very natural for OO languages, does not seem possible. The reason is that C# lacks the requisite polymorphism.

A generic type is a type constructor, which means that from an abstract type definition, Exp<T>, you can construct a concrete type by providing a concrete type T, such as Exp<int>. But, if Exp<T> is not a concrete type until you provide it a concrete type T, what is the type of the abstract definition Exp<T>?

Reasoning about type constructors requires the introduction of something called "kinds". As types classify values, so kinds classify types. The set of values, or concrete types, is of kind *. The set of type constructors is of kind *⇒*, which is to say they are "compile-time functions" accepting a concrete type and producing a concrete type.

Now consider that we have multiple Exp<T> implementations, say Interpreter.Orc.Exp and Compiler.Orc.Exp, all with different innards, and all define the same operations and thus are theoretically interchangeable. We would somehow like to abstract over the different implementations of Exp<T> so that we can use whichever one is most appropriate. In other words, we want to make our code polymorphic over a set of generic types Exp<T>.

This necessitates type constructor constructors, the kind *⇒*⇒*, which accepts a type such as Orc.Compiler.Exp, and produces a type constructor Exp<T>.

At the moment, I can't think of a way to encode such polymorphism in C#. Functional languages provide this level of polymorphism, and some even provide higher-order kinds, meaning type constructors can be arguments to other type constructors, thus achieving entirely new levels of expressiveness.

ML Modules in C#

2007-12-28T10:53:00.000-05:00

I've written about the limitations of C#'s equational constraints before. Truth is, I now believe that any such limits can be circumvented by a relatively simple translation. The result is less "object-oriented", as it requires a set of cooperating objects instead of being encapsulated in a single object.

Let's take a simple, unsafe list flattening operation described in Generalized Algebraic Data Types and Object-Oriented Programming (GADTOOP). This can be expressed in OCaml as:

let List = struct 
  type 'a t = Nil | Cons of 'a * 'a t
  let append l a = Cons(a, l)
  let flatten la =
      Cons(a, l) -> append a (flatten l)
    | Nil -> Nil
end

The argument to flatten, la, is a list of lists of type 'a. However, there is no way to express this in C# without unrestricted equational constraints as I described earlier. Here is the translation to C# from GADTOOP:

public abstract class List<T> {...
  public abstract List<T> Append(List<T> that);
  public abstract List<U> Flatten<U>();
}
public class Nil<A> : List<A> {...
  public override List<U> Flatten<U>()
  { return new Nil<U>(); }
}
public class Cons<A> : List<A> {...
  A head; List<A> tail;
  public override List<U> Flatten<U>()
  { Cons<List<U>> This = (Cons<List<U>>) (object) this;
    return This.head.Append(This.tail.Flatten<U>()); }
}

Note how Flatten requires an unsafe, ugly cast to and from object to get around C#'s type limitations. However, there is a safe way. Here is the translation:

static class List
{
  public abstract class t<A> {}
  public sealed class Nil<A> : t<A> {}
  public sealed class Cons<A> : t<A> {
    internal A head; internal t<A> tail;
  }
  public static t<A> Append(t<A> l, A a)
  {  return new Cons<A>(a, l);  }
  public static t<A> Flatten<A>(t<List<A>> l)
  { return l.head is Nil ? new Nil<A>() : Append<A>(Flatten<A>(l.tail), l.head); }
}

Basically, the step-wise translation I propose:

move the generic class I into a nested generic class O.I
```
class I<T> {}
```
becomes
```
class O {
  class I<T> {}
}
```

move the instance methods of that generic class into generic methods of the enclosing class, I.m -> O.m
```
class I<T> {
  I<T> m<U>(U u) { ... }
}
```
becomes
```
class O {
  class I<T> {}
  I<T> m<T, U>(I<T> i, U u) { ... }
}
```

mark all relevant state of I "internal", so the outer class O can access it.

class I<T> {
  private T value;
  public T get() { return value; }
}

becomes

class O {
  class I<T> { internal T value; }
  public T get(I<T> i) { return i.value; }
}

now you can express arbitrary constraints on the type structure in the methods of O.
```
class O {
  class I<T> {}
  I<T> m2<T, U>(I<I<T>> i, I<I<U>> u) { ... }
  ...
}
```

Because the external methods do not depend on an implicit 'this' argument, we no longer need equational constraint refinements to express the required type structure. Ordinary C# types suffice!

If you squint a little more closely, you'll also note a much closer symmetry in this version of the code and the OCaml code. In fact, this translation essentially builds ML modules in C#!

Like all widely-used module systems, it's pretty clear that these modules are "second-class". Only rebinding the name is possible, via C#'s "using" directive, and everything is resolved and fixed at compile-time. By this, I mean that you can import different list implementations and it will compile cleanly as long as the other list implementation defines the same operations with the same type signatures:

using L = List;
...
L.Flatten(l);
...

Or:

using L = AnotherList;
...
L.Flatten(l);
...

The compile-time restriction is primarily due to the declaration as a static class. Making the class non-static permits runtime binding of concrete implementations to signatures, so it's a little more flexible, and just as safe. Loosening this restriction may also make runtime "functors" possible.

I've used this pattern to complete Orc.NET, because the 'where' combinator required an inexpressible dependency. You can see my use in the Orc interpreter. The "Orc" object in Interp.cs is essentially an "expression builder", and I suspect that all such "builder" implementations are really ML modules at their core.

An open question is the interaction of inheritance with such modules. Seems like inheritance is a particular type of functor from structure S to S.

In any case, if you need type constraints which are inexpressible in C#, then make them ML modules using the above translation, and add object-orientedness back in incrementally. On a final note, I find it amusing that OO languages must resort to functional techniques to resolve fundamental OO limitations. I'd much prefer if we could just use functional languages instead and forgo all the hassle. ;-)

Generalizing C# Generics

2007-11-12T11:40:00.000-05:00

In previous posts, I had commented on certain non-sensical limitations in the C# type system, particularly with regard to equational constraints on generic type parameters; these unfortunate limitations significantly reduce the expressiveness of well-typed solutions.

Microsoft Research had actually already tackled the problem in their 2006 paper Variance and Generalized Constraints for C# Generics. Taking inspiration from Scala, they generalize class and method parameter constraints with arbitrary subtyping relations, and they further add use-constraints on generic methods. This increased expressiveness should address the problems I alluded to in my previous posts; if only the changes were integrated into the .NET VM and C#... :-)

[Edit: figures that LTU already covered this paper]

On the Importance of Purity

2007-10-24T09:00:00.000-04:00

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're given, and the only effect functions may have, is to return a value.

This may not sound very significant, but permitting functions which are not
RT is literally a nightmare for software developers. This fact is simply not obvious because most mainstream languages are not referentially transparent.

Consider a fairly benign scenario where you're in a loop and you call a function, but the function suddenly changes your loop index variable even though you didn't pass it to the function! This generally doesn't happen, but it could happen in languages like C/C++. The only reason it's not prevalent is because functions are RT regarding local variables allocated on the stack, and most languages other than C/C++ enforce this property.

I'm sure it's not difficult to imagine the horrors if any function you call could modify any of your local variables: you could no longer rely on the variables holding correct values at any time. How could you rely on anything? Global variables are a good example of this mess. It's common wisdom that one should avoid globals. Why? Because they're not RT, and since their values could change at any time, they're unreliable.

If a client calls you with a problem in your program written in a RT language, you immediately know that the problem is exactly in module B providing that feature, and perhaps even the particular function B.F performing the given operation. Instead, in non-RT languages a completely different module C could be interfering with module B by changing its state behind the scenes. Debugging is thus much easier with RT.

Consider a more malicious scenario, where a function does some useful computation, but also deletes all of your files behind your back. You download this library because it seems useful, only to lose your entire machine. Even worse, it may only deletes files when deployed to a server. Or perhaps it installs some adware. This situation is only possible because the function is not referentially transparent. If it were, the only way it could have deleted your files is if you had given it a handle to a directory.

Those of you well-versed in the security field might recognize this constraint: it is the same authority propagation constraint underlying capability security.

However, the properties of full referential transparency are stronger than those of capability security: where the latter permits non-determinism as long as the facility providing it is accessed via a capability, full referential transparency requires "pure functions", which are fully deterministic.

The Benefits of Determinism

So why is determinism important? It's important that everything in your program is reproducible, and thus testable. No arguments with that statement I'm sure.

Consider a particular function, that whenever called with the same parameters, it returns a completely different value. How could you ever produce a useful program if every function were like that? How could you even test it?

Most developers have experienced the problems of non-determinism when a client calls in with a problem, but the problem is not reproducible even by retracing the exact same steps. If the program was deterministic, then retracing those exact steps would always produce the error, no exception. I can't understate how essential reproducibility is for testing and quality assurance purposes.

However, non-deterministic functions do exist. We've all used such functions at one time or another. Consider a function that returns the value of the clock, or consider the random() function. If we want to use a RT, deterministic language, we need some way to use non-deterministic functions. How do we reconcile these two conflicting ends? There are a number of different ways, but all of them involve controlling and isolating non-determinism in some way.

For instance, most capability languages permit non-determinism, but the source of non-determinism can only be accessed via a capability which must be explicitly granted. Thus, you know that only the modules that were granted access to a source of non-determinism can behave non-deterministically and every other module in the program is completely deterministic. What a relief when debugging!

Essentially, this means that any source of non-determinism cannot be globally accessible, or ambient. So for you C/C++ programmers, rand() and getTime() are not global functions, they are function pointers that must be passed explicitly to the modules that need them. Only main() has access to all sources of non-determinism, and main() will pass on the appropriate pointers to the authorized modules.

Purely functional languages like Haskell take a similar approach to capability languages. RT is absolutely essential to purely functional languages, and any source of non-determinism violates RT. Such languages have a construct which was mathematically proven to isolate and control non-determinism: monads. It's not important what a monad is, just consider it as a design pattern for purely functional languages that preserves RT in the presence of non-determinism.

I would say that determinism is strictly more important than RT, but that RT is currently the best known method of achieving determinism. Now if your client calls you with an irreproducible problem, at least you've narrowed the field to only the modules that use sources of non-determinism.

The Benefits of Totality

What is a total function? A function is total if it is defined for all possible values of its inputs, no exception. Integer addition is a total function: regardless of the values of the two input integers, adding them produces a valid result.

By contrast, many functions are partial functions. Here, "partial" means that not all values passed to the function are valid. For instance, integer division is defined for all integers except zero. Dividing by zero is considered an error and its behaviour is undefined. Division is thus a partial function.

Using total functions always results in defined behaviour. Using partial functions sometimes results in undefined behaviour, if they are applied to invalid values. Thus, the more total functions you use, the more likely your program will run without generating errors.

If a language forces all of your functions to be total, then your program will have no undefined behaviour at all. You are forced to consider and handle all possible error conditions and edge cases, in addition to the program' expected normal operating mode. No undefined or unknown behaviour is possible.

As you can imagine, totality inevitably produces more reliable software. In C you are free to ignore errors and segfault your program, but with total functions you can't ignore those errors.

Unfortunately, totality can be a serious burden on the developer, which is why partial programming is more prevalent. Exceptions were invented to help deal with invalid inputs to partial functions: don't segfault, throw an exception! They do permit more modular code to be written, since errors can propagate and be handled at higher levels. Unfortunately, unchecked exceptions, where the exceptions a function can throw are not defined in the function's signature, just bring us back to square one: uncaught exceptions result in undefined behaviour, but the language doesn't help us by telling us what exceptions we need to catch.

Correct software inevitably requires totality of some sort. How do we transform a partial function into a total function? Here's how we can make division total:

fun divide(n,d) : int * int -> int

This snippet is the signature for the division function. It takes two integers, n and d, and returns an integer. No mention is made of the error condition in the signature when d=0. To make divide total, we transform it to the following:

data Result = Defined(x) | Undefined
fun divide(n,d) : int * int -> Result = 
 if d == 0 then
   return Undefined
 else
   return Defined( n/d )

So now, any code that calls divide must deconstruct the return value of divide into either a Defined result x, or an Undefined result indicating an invalid input:

fun half(x) =
  match divide(x,2) with
    Undefined -> print "divide by zero!"
  | Defined(y) -> print "x/2=" + y

As you can see, a total divide function forces you to handle all possible cases, and so any program using it will never have undefined behaviour when dividing by zero. It will have whatever behaviour you specify on the Undefined branch. No efficiency is lost as any decent compiler will inline the above code, so the cost is just an integer compare against 0.

A similar strategy can be used for errors that come from outside the program as well. Consider the file open() function. It's a partial function:

fun open(name) : string -> FILE

It can be transformed it into a total function as follows:

data FileOpenResult = File f | PermissionDenied | FileNotFound | ...
fun open(name) : string -> FileOpenResult

If all partial functions are made total using the above technique, then all of your software will have fully defined behaviour. No more surprises! To a certain extent, totality even mitigates some problems with non-determinism: after all, who cares if the output is not reproducible since you are forced to handle every possible case anyway.

At first glance, totality is not appealing to the lazy programmer. But if you've ever had to develop and maintain complex software, you'll soon appreciate your language forcing you to deal with all possible cases at development time, instead of dealing with irate customers after deployment.

For all the lazy programmers out there, consider this: totality almost eliminates the need for testing. As a lazy programmer myself, that's a selling point I can support. ;-)

The Benefits of Strong Static Typing

What is strong static typing? Static typing is an analysis a compiler performs to ensure that all the uses of data and functions in a program are consistent. In other words, you're not saying X in one place, and then saying Y which contradicts X in another place.

I take strong static typing to mean a static type analysis that the developer cannot circumvent. C/C++ are statically typed, but their static type systems are not strong because you can freely cast between types, even when doing so will generate an error. C#, Java, and similar languages are statically typed, but they are on the border line of strong typing: there is no way to defeat the type system, but the static analysis is weak since you can still cast. Casting just introduces dynamic runtime checks and runtime errors.

There are many arguments for and against strong static typing, but in combination with the previously discussed features, static typing enables developers to write software that is "almost correct by construction". By this I mean that if your program compiles, it will run without errors, and it has a high probability of actually being correct.

The reason for this is some computer science black magic called the Curry-Howard isomorphism. What that is exactly isn't important. Just consider a static type system to be a built-in logic machine: when you declare and use types this logic machine is making sure that everything you're telling it is logically consistent. If you give it a contradiction, it will produce a type error. Thus, if your whole program type checks, it is logically consistent: it contains no contradictions or logical errors in the statements the logic machine understands, and the logic machine constructed a proof of this fact.

The power of the static type system dictates how intelligent the logic machine is: the more powerful the type system, the more of your program the machine can test for consistency, and the closer your program is to being correct. Your program essentially becomes a logical specification of the problem you are solving. You can still make errors in the specification, but those errors must not contradict anything else in the specification for it to type check.

The downside of strong static typing is that the analysis is necessarily conservative, meaning some legitimate programs will produce a type error even though they would not generate an error at runtime.

Such is the price to pay for the additional safety gained from static typing. As a lazy programmer I'm willing to pay that price.

Conclusion

These are some of the less common idioms found in advanced programming languages. Other idioms are either more well known and have already been adopted into other languages (algebraic datatypes, higher-order functions), or are simply less relevant for constructing reliable software (laziness).

Absolute purity may ultimately prove to be unachievable, but its pursuit has given us a number of powerful tools which significantly aid in the development and maintenance of reliable, secure software.

[Edit: clarified some statements based on some feedback from LTU]

Reading PDFs on the iPhone the moderately difficult way

2007-10-08T15:29:00.000-04:00

Taking a break from my programming language blogging, I thought I'd describe a recent adventure with my new iPhone: reading PDFs. The iPhone can read PDFs, but insists on doing so only when reading the PDF from the network in some way, ie. via the mail client or Safari.

Being the programming language enthusiast I am, I have plenty of papers stored locally on my machine which I'd like to read on the go, and network access is less than desirable for obvious reasons. Unfortunately, Apple disabled the obvious answer to local browsing: using the "file://" URI scheme. Very stupid of them IMO.

Fortunately, I'm an "unscrupulous" person, because I jailbroke my iPhone so I could install third-party apps. So if network access is required to view PDFs in Safari, then I'll just have to access local files over the network! The way that's been done for over 20 years is available on the iPhone: a web server.

Both Apache and LightTPD are available in Installer.app, and I chose the latter; I just find the configuration less obtuse than Apache's. You will need OpenSSH installed as well. I also recommend UICtl so you can load/unload the web server only when you need it.

Once everything is installed, I ssh'd to the iPhone, opened the lighttpd config file at /usr/local/etc/lighttpd.conf, changed the root directory to point to /var/root/PDFs (or place it wherever you like), and added:
dir-listing.activate = "enable"
config line to enable directory browsing. Then using UICtl, I unloaded and reloaded lighttpd.

Finally, I opened up Safari on the iPhone and bookmarked http://127.0.0.1/

Voila! I have access to all my local PDFs via Safari. :-)

Browsing and viewing PDFs is very easy, unlike other schemes using the "data:" URI scheme. Of course, the setup is moderately difficult for anybody who isn't versed in the basics of unix and the command shell.

Naturally, I'd much prefer a native app, or at the very least, local browsing via the file:// URI scheme in Safari. I'm keeping my fingers crossed. :-)

Visitor Pattern Deprecated: First-Class Messages Are All You Need!

2007-09-28T21:35:00.000-04:00

In previous posts [1,2], I argued that the visitor pattern was a verbose, object-oriented equivalent of a pattern matching function. The verbosity stems from the need to add the dispatching code to each data class in the hierarchy, and because the encapsulation inherent to objects is awkward when dealing with pure data.

A single addition to an OOP language could completely do away with the need for the dispatching code and make OO pattern matching simple and concise: first-class messages (FCM). By this I mean, messages sent to an object are themselves 'objects' that can be passed around as parameters.

To recap, functional languages reify the structure of data (algebraic data types), and they abstract operations (functions). OOP languages reify operations (interfaces), but they abstract the structure of data (encapsulation). They are duals of one another.

All the Exp data classes created in [1,2] shouldn't be classes at all, they should be messages that are sent to the IVisitor object implementing the pattern matching:


data Exp = App(e,e) | Int(i) | ...

IVisitor iv = ...

//the expression: 1 + 2
Exp e = App(Plus(Int(1), Int(2)));

//'e' is now the "App" operation placed in a variable
iv.e  //send "App" to visitor

FCM removes the inefficient double-dispatch inherent to the visitor pattern, while retaining object encapsulation for when you really need it; the best of both worlds.

Note also how the above message declaration looks a great deal like a variant in OCaml? This is because first-class messages are variants, and pattern-matching functions are objects. I'm actually implementing the DV language in that paper, first as an interpreter, then hopefully as a compiler for .NET. To be actually useful as a real language, DV will require some extensions though, so stay tuned. :-)

[Edit: made some clarifications to avoid confusion]

Objects are Existential Packages

2007-06-15T20:07:00.000-04:00

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 standard .NET collections API. Each of these abstractions will be available as a separate DLL, so instead of linking to a large library, you can just pick those abstractions you're interested in using.

Besides more flexible typing as in GADTs, expressiveness is the only advantage functional languages still have over C#. Compare the verbosity of the C# option type:

//T is the type variable
public abstract class Option<T> { }
public sealed class None<T> : Option<T> { }
public sealed class Some<T> : Option<T>
{
  T value;
  public Some(T v) { value = v; }

  public T Value
  {
    get { return value; }
  }
}

as compared to an O'Caml definition:

type 'a option = None | Some of 'a    (* 'a is the type variable *)

This contrast highlights my previous argument in favour of expressiveness; just think of it as 1 line of O'Caml generating 12 lines of C#, since the efficiency of both definitions is equivalent.

To demonstrate the power of existential packages and universal types in C#, I'll be including a number of statically typed abstractions that have only been found in O'Caml and Haskell to date; types like statically sized lists and arrays, number-parameterized types, and other type wizardry resulting in strong partial correctness properties (see: Lightweight Static Capabilities).

It will be particularly interesting to compare the efficiency of a sized type, like a list, to its unsized counterpart, because .NET does not erase types like Java and O'Caml do.

Expressiveness: what's all the fuss?

2007-05-28T12:16:00.000-04:00

I just read a blog post recommending that developers broaden their language horizons, with a particular emphasis on Ruby. The author attempts to explain why expressiveness is an important metric for a language:

What is this obssesion[sic] with "expressiveness"? Go write poertry [sic] if you want to be expressvive.[sic]
Remember that ultimately our jobs are (usually) to solve some kind of business problem. We're aiming for a finish line, a goal. The programmer's job is translate the language of the business person to the language of the computer.

The whole point of compilers, interpreters, layers of abstraction and what-not are to shorten the semantic distance between our intent and the way the computer thinks of things.

To be honest, this is not very convincing; the moment you mention "semantics", is the moment many developers will close your blog and go do something "productive".

The argument for expressiveness is ultimately quite simple: the more expressive the language, the more you can do in fewer lines of code. This means that 3 lines of Ruby code might take 12 lines in C#, and 15 lines of C# could be compressed to 2 lines of Ruby while retaining readability and maintainability [1].

Consider viewing Ruby as a C# code generator, where 2 lines of Ruby code can generate 12 lines of C#. That actually sounds like a pretty good idea doesn't it? You would never write a generator to go the other way around though would you?

More expressive languages also tend to be simpler and more coherent. There are all sorts of little ad-hoc rules to Java and C# that you would not find in most functional languages.

You can readily see the differences in expressiveness at the Alioth language shootout. Set the metrics to CPU:0, memory:0, GZIP:1, which means we only care about the GZIP'd size of the source code. You'll see that functional languages tend to come out on top. Ironically, Ruby is first lending weight to the above blog post on Ruby's expressiveness.

Expressiveness is the whole driving force behind DSLs: a DSL is more expressive in solving the problems it was designed for. For instance, a relational database DSL specific to managing blogs could generate perhaps 100 lines of SQL per single line of DSL code. It would take you far more code to emulate that 1 DSL line in C#.

So the expressiveness argument is quite compelling if you simply view it as a code generation metric: the more expressive the language, the more code it can generate for you for the same number of characters typed. That means you do your job faster, and more importantly, with fewer errors.

Why fewer errors? Studies have shown that developers generally write about 20-30 correct lines of code per day. That means 20 lines of correct C# code or 20 lines of correct Ruby code. It just so happens that those 20 lines of correct Ruby can generate 100 lines of correct C#, which means you're now 5x more productive than your C#-only developer next door. Do you see the advantages now?

[1] These numbers are completely bogus and are used purely for illustrative purposes.

GEXL Lives!! Solving the Expression Problem in C#

2007-05-09T21:56:00.000-04:00

GEXL is a general expression library providing core primitives for building and processing expression trees. I had abandoned it awhile ago because I quickly ran into a serious, well-known issue: The Expression Problem.

Basically, the expression problem boils down to the fact that typical programming solutions are extensible in only a single direction: either the data types or the operations defined on them, but not both, can be extended without modifying existing code. It takes some sophisticated type machinery to safely solve the expression problem, and various languages, including OCaml, Haskell, Beta/gBeta, and Scala, have acceptable solutions. Languages supporting multimethods support less type safe extension, so I exclude them here (although Nice might do it properly).

So GEXL, which aims to provide both data and their operations as data and visitors respectively, runs smack into the expression problem. Fortunately, Mads Torgersen's paper, The Expression Problem Revisited, provides 4 new solutions by exploiting the generics of C# and Java. The first 3 solutions are still biased towards data-centric or operation-centric extensions, but the last solution provides full extensibility in both directions in ordinary C# with generics. GEXL is saved! There's just one catch: it's not type safe since it requires 2 casts. Fortunately, these casts are encapsulated in the core data and visitor classes, which are parameterized by the types they must check and cast to. The developer extending the core will also need to be a bit careful to make sure he's parameterizing the visitor and expression types at the same level as the extension he's writing.

These core classes are now implemented in GEXL, together with two interpreters and pretty printers written for the untyped lambda calculus, one implemented as data-centric extension of the core library, and the other as an operation-centric extension; the two total about 300 lines of excessively verbose C#, including comments. The paper provides a mixed example of data and operation extensions if you're interested in extending in both directions.

There is a disadvantage of this solution however: visitors can no longer return the results of their computation, due to a type dependency between the Data and Op; if we were to parameterize IVisitor with a return type, IVisitor<R>, as I described earlier, Op must also be parameterized by R, which forces Data to also be parameterized by R since Data's type is constrained by IVisitor.

This means that the entire expression tree will be parameterized by the return type of the operation that we wish to perform, R, which means it can only be traversed by operations that return R! No more typechecking returning bools and tree transforms returning new trees on the same expression tree. Type safety has backed us into a corner; this is in fact a GADT problem, and as covered previously, C# generics fall just short of GADTs. If C# were to be augmented by full equational constraints, instead of the limited form they have now, this problem would be solvable, since we could simply parameterize the methods themselves with the appropriate constraints.

In fact, full equational constraints aren't needed; there are only two limitations of C#'s type system impeding this solution:

Limitations of type constraints to derivations: a constraint placed on a generic parameter must be a non-sealed class or an interface, so a constraint limiting a type parameter to a string is not possible. This should be relaxed so that the type constraint is a full subtype relation. The current design is simply a consequence of #2.
Lack of type constraint refinements: a constraint cannot be refined to a more specific type when subtyping. For instance, the declaration "class Foo where T : S", cannot be refined to "class Bar : Foo where T : U" where U is a subtype of S.

As it stands, the least offensive solution is for each visitor to retain its computed value as a private field.

So now that GEXL lives, perhaps we'll also see the eventual revival of Orc.NET. In the meantime, I'll try porting the interpreter for my language to GEXL and see how painful it turns out to be. :-)

P.S. There's a further interesting post in the above LTU thread: it provides a solution to the expression problem using just sum and recursive types; it requires significant boilerplate, but the extensions are still possible, which is impressive.

What's wrong with .NET

2007-05-03T22:55:00.000-04:00

I work with .NET everyday, and it's a decent virtual machine from the developer's perspective, and a slight overall improvement over Java in a number of respects.

But for a language implementor, .NET continues a tradition of mistakes that began with Java, which inhibit it from achieving its much touted goal as the Common Language Runtime (CLR). These issues are divided into two categories: blatant mistakes, and nice to haves. The former requires no cutting edge features or research to implement, and the CLR should have had them from the get-go. The latter might have required some research to get right (like they did with generics), but which are ultimately required for a truly secure and flexible virtual machine.

Blatant Mistakes

Insufficiently powerful primitives for execution and control flow. The most glaring of these omissions are first class function pointers and verifiable indirect calls. On .NET a function pointer is reified as an IntPtr, which is an opaque struct representing a native pointer reified as a native integer. calli is the VM instruction that indirectly invokes a function via such an IntPtr. Because an IntPtr is opaque, the VM can't really know whether it's pointing to a function, or a data blob held outside the VM heap, and calli is consequently an unverifiable instruction. calli is thus available only under full trust since the VM will crash if it calli's into a data blob. Many truly interesting languages would require calli for efficient execution, and the full trust requirement means that partial trust environments, such as cheap web hosts, won't be able to run assemblies generated from these languages. Microsoft consulted with a number of language researchers in the design for .NET and they responded enthusiastically with a "verifiable calli" proposal for just the above reasons. Unfortunately, MS ignored them.
Stack walking was a huge mistake inherited from Java. Stack walking prevents a number of useful optimizations, such as efficient tail calls, and alternative security architectures and execution models from being implemented. As it is, we're stuck with the horrible Code Access Security (CAS), when a far simpler model was already built into the VM. MS's new Silverlight supposedly introduces a new security framework based solely on named "trusted" assemblies, so perhaps we can expect this to be partly fixed. Efficient tail calls in particular are essential for functional languages.
Continuations. I was never sold on continuations until I started considering scheduling and scalability issues, and subsequently read a number of papers on concurrency; in summary, continuations are essential for scalable, schedulable execution subject to configurable user-level policies. Actually, continuations are not strictly necessary, as an expensive global CPS-transform of a program coupled with efficient tail calls can achieve the same effect; however, CPS has a number of performance side-effects that may not be acceptable for certain languages. Thus, continuations or something equally expressive, like delimited continuations, are essential for a true CLR. Coupled with efficient tail calls, we can easily achieve highly scalability architectures with low memory use, as SEDA and Erlang have shown. Many people believe that threads subsume continuations, and some believe the contrary, but in fact, both abstractions are necessary; a thread is a "virtual processor", and a continuation is the processor context. If .NET had continuations, we could build operating system-like execution models that, in theory, can achieve optimal CPU utilization and parallelism with minimal resource use via non-blocking I/O, dataflow variables, and a number of threads equal to the number of real CPUs on the machine. This is achievable only with continuations or the equivalent as a global CPS transform.
Poor security architecture. CAS is a hack bolted on to a VM that had it omitted a single feature and tweaked another feature, wouldn't have needed any security architecture at all. If static class fields were not available, then the native execution model of the .NET VM reduces to capability-based security. It's possible to include static fields if the fields have certain properties (transitive immutability for instance), but conceptually, just imagine a VM whereby the only way to obtain access to an object is being given access to it such as in a method call. There is a further condition to satisfy capability security that has consequences for P/Invoke: all functionality accessible via P/Invoke must be reified as a reference (ie. an object). This means that static, globally accessible operations such as "FileInfo File.Open(string name)" would not be permitted since they subvert the security model by calling out to the OS to convert a string into authority to a File; instead, at the very least File.Open would be reified as a FileOpener object, and this object is "closely held" by trusted code. In effect, this forces all P/Invoke functions to be minimally capability secure. There is also an alternative approach to security with which we can have our fully mutable static fields, and have our isolation and security too; in fact, it's a widely used abstraction invented decades ago which provides full fault isolation and a number of other useful properties: lightweight language process; like OS processes they provide full isolation, but it's a process that exists only in the VM; in effect, it's similar to processes as found in the pi-calculus. Static fields are thus scoped to the lightweight process. Processes and their properties are explained further under "nice to haves".

Nice to Haves

Lightweight process model. Yes, I'm aware that .NET has the AppDomain which is sort of like a lightweight process, but it's isolation properties are inadequate. Microsoft's Singularity operating system takes the base AppDomain abstraction, and extends it into a full "software isolated process" (SIP). Processes should be single-threaded, and should additionally permit fault handling and resumption via Keepers. Like in OSs, portions of a process can potentially be paged in and out, serialized, persisted, or otherwise manipulated, all transparently. Call them Vats as in E, processes as in Erlang, or SIPs as in Singularity, but the process abstraction is critical for full VM isolation. AppDomains are fairly good start however, and I'm researching ways to exploit AppDomains to enhance .NET's security.
Resource accounting. Resource accounting includes managing memory, scheduling concurrent execution, etc. Without properly reifying these abstractions as explicit objects subject to configurable policies, the VM is vulnerable to denial of service (DoS) attacks from malicious code. As it stands, .NET cannot load and run potentially malicious code in the same VM as benign code. For instance, it should be possible to set a quota for memory use, and to schedule and interleave execution so that code cannot exhaust VM memory and "steal the CPU". However, you can imagine that passing around quotas in code would be quite unwieldy; fortunately, this requirement interacts nicely with another abstraction we already need: processes. Thus, the process is also the unit of resource accounting, and spawning a new process starts a new heap, potentially with a quota. Processes can then be scheduled via a VM-level scheduler, and each VM can also schedule its own execution as it sees fit (threaded, event-loops, etc.). Interprocess communication (IPC) can be managed with an exchange heap as in Singularity, or via copying as is done in most microkernels.
Concurrency model. This has more of an effect on the class library than the base VM design, but plan interference is a huge source of bugs in concurrent code, and it should be tackled by every language. VM processes provide a minimal, tried and tested concurrency and isolation abstraction, but within a process there are a wide range of options available, including event-loop concurrency, or language enforced concurrency models. Controlled sharing of state between processes needs to be tackled, such as the exchange heap in Singularity, though my current inclination is to prefer copying for safety reasons.

As you can see, .NET doesn't need much to turn it into a flexible, industrial strength, high security VM. I'm going to follow this post with a detailed description of what the ideal minimal VM should have, and I will even describe how I believe it can be implemented safely and efficiently.

General Pattern Matching with Visitors

2007-04-07T14:10:00.000-04:00

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 predicate over the expression tree (such as type-checking, type inference, etc.).

Like pattern matching functions over ordinary parameterized algebraic data types, the return value of the visitor must be T or a subtype of T.

In fact, this visitor pattern, minus the decomposition as in pattern matching, is featured in Generalized Algebraic Data Types and Object-Oriented Programming; see also the LTU discussion.

According to the paper, generics as in C# are almost capable of encoding GADTs. Unfortunately, they lack some flexibility in declaring type dependencies between class type parameters, and method type parameters. The paper provides some very interesting C# examples of type-safe type checking, evaluation, phantom types, and representation types. This generics black magic warrants further study for the advanced C# student.

Visitor pattern considered harmful (unless functionalized)

2007-04-03T21:38:00.000-04:00

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;

   public App(Exp e0, Exp e1)
   {
       this.e0 = e0;
       this.e1 = e1;
   }

   public override Val Visit(IVisitor v)
   {
       return v.App(e0, e1);
   }
}

//the pattern matching visitor
public interface IVisitor
{
 Val App(Exp e0, Exp e1);
 //...
}

This is slightly different from the typical visitor pattern you see in books, where the object itself would be passed in to IVisitor.App(). In fact, this looks almost exactly like a pattern matching function in a language like OCaml:

type Exp = App of Exp * Exp | Val   (* | ... *)

let rec eval exp =
  match exp with
   App e0 e1 ->   (* ... evaluate the application *);;

Thus, properly designed, a visitor is simply a pattern matching function. By convention, we use the class name as the visitor's method, so it matches with the convention in functional language's (ie. the constructor name). The visitor method's parameters are the object's private fields, just like a variant. I'm using this approach for an interpreter I'm implementing and it works quite well (unfortunately no source is publicly available at the moment).

In terms of efficiency, the pattern matching function is probably faster. After all, it's simply a tag check plus a branch, whereas the visitor must perform a double dispatch (two method lookups incurring two indirections and two indirect branches).

Clearly, the visitor is also far more verbose, as you must create the "variant classes", manually add a "Visit" method to each, and since there is no "default" case as in pattern matching, like the "default" case in a switch statement, you have to exhaustively handle each variant explicitly in each visitor, even if the case isn't relevant. You can mitigate the latter problem by implementing a "Default" abstract base class with dummy implementations on all cases, and then override only the cases you are interested in:

public abstract class Default : IVisitor
{
 //overridden in my Interpreter visitor
 public virtual Val App(Exp e0, Exp e1)
 {
   throw new NotSupportedException();
 }
}

As a potentially interesting extension, the variant classes may not even have to be in the same inheritance hierarchy, they only have to implement a marker interface with the appropriate Visit() method. This may increase extensibility along similar lines to polymorphic variants; only the visitor has to be kept up to date with all the relevant cases, and it can evolve separately from the core.

Summary:

So if you're doing symbolic manipulation, and are forced to operate in a OO language like C# above, you can still approximate the elegance of algebraic data types and pattern matching, it just takes a little more work on your part. Pretty much par for the course in the OO world. :-)