Can ML functors be fully encoded in .NET (C#/F#)?

Question

Can ML functors be practically expressed with .NET interfaces and generics? Is there an advanced ML functor use example that defies such encodings?

Answers summary:

In the general case, the answer is NO. ML modules provide features (such as specification sharing via signatures [1]) that do not directly map to .NET concepts.

However, for certain use cases the ML idioms can be translated. These cases include not only the basic Set functor [2], but also the functorial encoding of monads [3], and even more advanced uses of Haskell, such as finally tagless interpreters [4, 5].

Practical encodings require compromises such as semi-safe downcasts. Your mileage will wary.

Blogs and code:

1. blog.matthewdoig.com
2. higherlogics.blogspot.com
3. monad functor in F#

Answer 1

I don't know ML functors well enough to really answer your question. But I will say the one limiting factor of .Net I always find with monadic programming is the inability to abstract over 'M' in the sense of "forall M. some type expression with M<T>" (e.g. where M is a type constructor (type that takes one or more generic arguments)). So if that's something you sometimes need/use with functors, then I feel pretty confident that there's no good way to express it on .Net.

Answer 2

Brian's comment is spot on. Here is OCaml code that uses functors to give a (strict) implementation of Haskell sequence :: (Monad m) => [m a] -> m [a] parameterised over the monad in question:

module type Monad = 
sig
  type 'a t (*'*)
  val map : ('a -> 'b) -> ('a t -> 'b t)
  val return : 'a -> 'a t
  val bind : 'a t -> ('a -> 'b t) -> 'b t
end

module type MonadUtils =
sig
  type 'a t (*'*)
  val sequence : ('a t) list -> ('a list) t
end

module MakeMonad (M : Monad) : MonadUtils =
struct
  type 'a t = 'a M.t
  let rec sequence = function
    | [] -> 
        M.return []
    | x :: xs ->
        let f x = 
          M.map (fun xs -> x :: xs) (sequence xs)
        in 
          M.bind x f
end

This looks challenging to express in .NET.

UPDATE:

Using a technique by naasking I was able to encode the reusable sequence function in F# in a mostly type-safe way (uses downcasts).

http://gist.github.com/192353

Answer 3

One of the key features of ML modules is sharing specifications. There's no mechanism in .NET that would be able to emulate them - the required machinery is just too different.

You can try to do it by turning the shared types into parameters, but this can't faithfully emulate the ability to define a signature, and then later apply sharing to it, perhaps in multiple different ways.

In my opinion, .NET would benefit from something that did have this kind of machinery - it would then come closer to truly supporting the diversity of modern languages. Hopefully including more recent advances in modules systems like those in MixML, which in my opinion is the future of module systems. http://www.mpi-sws.org/~rossberg/mixml/

Answer 4

HigherLogics is my blog, and I've spent a lot of time investigating this question. The limitation is indeed abstraction over type constructors, aka "generics over generics". It seems the best you can do to mimic ML modules and functors requires at least one (semi-safe) cast.

It basically comes down to defining an abstract type, and an interface which corresponds to the module signature that operates on that type. The abstract type and the interface share a type parameter B which I term a "brand"; the brand is generally just the subtype that implements the module interface. The brand ensures that the type passed in is the proper subtype expected by the module.

// signature
abstract class Exp<T, B> where B : ISymantics<B> { }
interface ISymantics<B> where B : ISymantics<B>
{
  Exp<int, B> Int(int i);
  Exp<int, B> Add(Exp<int, B> left, Exp<int, B> right);
}
// implementation
sealed class InterpreterExp<T> : Exp<T, Interpreter>
{
  internal T value;
}
sealed class Interpreter : ISymantics<Interpreter>
{
  Exp<int, Interpreter> Int(int i) { return new InterpreterExp<int> { value = i }; }
  Exp<int, Interpreter> Add(Exp<int, Interpreter> left, Exp<int, Interpreter> right)
  {
    var l = left as InterpreterExp<int>; //semi-safe cast
    var r = right as InterpreterExp<int>;//semi-safe cast
    return new InterpreterExp<int> { value = l.value + r.value; }; }
  }
}

As you can see, the cast is mostly safe, since the type system ensures the brand of the expression type matches the brand of the interpreter. The only way to screw this up, is if the client creates his own Exp class and specifies the Interpreter brand. There is a safer encoding which avoids this problem too, but it's far too unwieldy for ordinary programming.

I later used this encoding and translated the examples from one of Oleg's papers written in MetaOCaml, to use C# and Linq. The interpreter can transparently run programs written using this embedded language server-side in ASP.NET or client-side as JavaScript.

This abstraction over interpreters is a feature of Oleg's final tagless encoding. Links to his paper are provided in the blog post.

Interfaces are first-class in .NET, and since we use interfaces to encode module signatures, modules and module signatures are also first-class in this encoding. Thus, functors simply use the interface directly in place of module signatures, ie. they would accept an instance of ISymantics<B> and delegate any calls to it.

Answer 5

I've now posted a detailed description of my translation for ML modules, signatures and functors to an equivalent C# encoding. I hope someone finds it useful.