tags:

views:

685

answers:

5

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#
+3  A: 

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.

Brian
Right, I think this is called `higher-kinded polymorphism`, something I really miss from Haskell. OCaml does not have this, but I have seen OCaml libraries (JaneStreet Core) that offer monads through functors. I will need to investigate this further to see how can this play with F# - I do not know functors well enough either..
toyvo
+1  A: 

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

toyvo
Right. The ways to fake it are to "pass a dictionary of functions" that serves as a witness to the instance of the monad (maybe-typical Haskell under-the-hood implementation), or to use static member constraints and "inline" in F# (in which case the monad must be expressed via static methods on a type).
Brian
At the end of the day, all of these options come off as "too painful" in my experience, so you just abandon it and say ok, this is something I cannot express typesafely in .Net.
Brian
My experience is similar so far, but I have not quite given up yet.
toyvo
There seems to be a solution that pass function dictionaries nor uses `inline` - see the link above if you are interested.
toyvo
+2  A: 

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/

RD1
Thank you for the link!
toyvo
+5  A: 

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.

naasking
Thank you for explaining! I have seen your posts but did not realise the essence of the technique before. I do enjoy your blog, although I am not quite up to understanding the Symantics yet - will do some weekend reading. I played with expressing the monad example in F# using the encoding you suggest. It does look practical - only a few downcasts. http://gist.github.com/192353
toyvo
Symantics just describes an interpreter for a language; basically, the functions that implement the semantics of the language. For example, the "language" in the above post permits declaring constants ints, and adding two ints.I'm not quite used to F# syntax yet as compared to OCaml, so I'll have to brush up on that to parse your translation to F#.
naasking
A: 

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.

naasking
It's nice, yes - I'd agree the best you do, and workable in some situations. But, sharing is really not going to fit into this. It doesn't even fit well into Haskell. It can be emulated in Haskell, but not in a practical way for the kinds of sharing I'm used to working with in SML/OCaml programs specifications.
RD1