Skip to main content

Objects are Existential Packages

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.

Comments

Popular posts from this blog

async.h - asynchronous, stackless subroutines in C

The async/await idiom is becoming increasingly popular. The first widely used language to include it was C#, and it has now spread into JavaScript and Rust. Now C/C++ programmers don't have to feel left out, because async.h is a header-only library that brings async/await to C! Features: It's 100% portable C. It requires very little state (2 bytes). It's not dependent on an OS. It's a bit simpler to understand than protothreads because the async state is caller-saved rather than callee-saved. #include "async.h" struct async pt; struct timer timer; async example(struct async *pt) { async_begin(pt); while(1) { if(initiate_io()) { timer_start(&timer); await(io_completed() || timer_expired(&timer)); read_data(); } } async_end; } This library is basically a modified version of the idioms found in the Protothreads library by Adam Dunkels, so it's not truly ground bre

Building a Query DSL in C#

I recently built a REST API prototype where one of the endpoints accepted a string representing a filter to apply to a set of results. For instance, for entities with named properties "Foo" and "Bar", a string like "(Foo = 'some string') or (Bar > 99)" would filter out the results where either Bar is less than or equal to 99, or Foo is not "some string". This would translate pretty straightforwardly into a SQL query, but as a masochist I was set on using Google Datastore as the backend, which unfortunately has a limited filtering API : It does not support disjunctions, ie. "OR" clauses. It does not support filtering using inequalities on more than one property. It does not support a not-equal operation. So in this post, I will describe the design which achieves the following goals: A backend-agnostic querying API supporting arbitrary clauses, conjunctions ("AND"), and disjunctions ("OR"). Implemen

Easy Automatic Differentiation in C#

I've recently been researching optimization and automatic differentiation (AD) , and decided to take a crack at distilling its essence in C#. Note that automatic differentiation (AD) is different than numerical differentiation . Math.NET already provides excellent support for numerical differentiation . C# doesn't seem to have many options for automatic differentiation, consisting mainly of an F# library with an interop layer, or paid libraries . Neither of these are suitable for learning how AD works. So here's a simple C# implementation of AD that relies on only two things: C#'s operator overloading, and arrays to represent the derivatives, which I think makes it pretty easy to understand. It's not particularly efficient, but it's simple! See the "Optimizations" section at the end if you want a very efficient specialization of this technique. What is Automatic Differentiation? Simply put, automatic differentiation is a technique for calcu