¿Los funtores ML pueden codificarse completamente en .NET (C#/F #)?

Question

¿Los funcionantes ML pueden expresarse prácticamente con interfaces .NET y genéricos? ¿Existe un ejemplo de uso avanzado de un agente ML que desafíe tales codificaciones?

Respuestas Resumen:

En el caso general, la respuesta es NO. Los módulos ML proporcionan características (como el intercambio de especificaciones a través de las firmas [1]) que no se correlacionan directamente con los conceptos de .NET.

Sin embargo, para ciertos casos de uso, los idiomas ML pueden traducirse. Estos casos incluyen no solo el functor básico Set [2], sino también la codificación funcional de mónadas [3], e incluso usos más avanzados de Haskell, como finalmente intérpretes sin etiquetas [4, 5].

Las codificaciones prácticas requieren compromisos tales como downcasts semi-seguros. Su kilometraje será cauteloso.

blogs y el código:

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

Answer 1

Una de las características clave de los módulos ML es compartir especificaciones. No hay ningún mecanismo en .NET que pueda emularlos: la maquinaria requerida es demasiado diferente.

Puede intentar hacerlo convirtiendo los tipos compartidos en parámetros, pero esto no puede emular fielmente la capacidad de definir una firma, y ​​luego aplicarle el uso compartido, quizás de múltiples maneras diferentes.

En mi opinión, .NET se beneficiaría de algo que sí tenía este tipo de maquinaria, entonces se acercaría más al verdadero soporte de la diversidad de idiomas modernos.Esperemos que incluya avances más recientes en sistemas de módulos como los de MixML, que en mi opinión es el futuro de los sistemas de módulos. http://www.mpi-sws.org/~rossberg/mixml/

Answer 2

No sé funtores ML suficientemente bien como para responder realmente a su pregunta. Pero diré que el factor limitante de .Net siempre encuentro con monadic programación es la incapacidad de abstraer sobre 'M' en el sentido de "forall M. algún tipo de expresión con M < T>" (por ejemplo, donde M es un constructor de tipos (tipo que toma uno o más argumentos genéricos)). Entonces, si eso es algo que a veces necesitas/usas con los funtores, entonces me siento bastante seguro de que no hay una buena forma de expresarlo en .Net.

Answer 3

El comentario de Brian es perfecto. Aquí está el código que utiliza OCaml funtores para dar un (estricto) la implementación de Haskell sequence :: (Monad m) => [m a] -> m [a] parametrizado sobre la mónada en cuestión:

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 

Esto parece difícil de expresar en .NET.

ACTUALIZACIÓN:

Usando una técnica por naasking I fue capaz de codificar el sequence función reutilizable en F # de una forma mayormente de tipo seguro (utiliza downcasts).

http://gist.github.com/192353

Answer 4

HigherLogics es mi blog, y he pasado mucho tiempo investigando esta cuestión. La limitación es, de hecho, la abstracción sobre los constructores de tipo, también conocidos como "genéricos sobre genéricos". Parece que lo mejor que puedes hacer para imitar los módulos ML y los funtores requiere al menos un lanzamiento (semi seguro).

Básicamente se trata de definir un tipo abstracto y una interfaz que corresponde a la firma del módulo que opera en ese tipo. El tipo abstracto y la interfaz comparten un parámetro de tipo B que denomino "marca"; la marca generalmente es solo el subtipo que implementa la interfaz del módulo. La marca asegura que el tipo pasado es el subtipo correcto esperado por el módulo.

// 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; }; } 
    } 
} 

Como se puede ver, el reparto es sobre todo seguro, ya que el sistema de tipos asegura la marca del tipo de expresión coincide con la marca del intérprete. La única forma de arruinar esto es si el cliente crea su propia clase Exp y especifica la marca de Intérprete. Existe una codificación más segura que también evita este problema, pero es demasiado difícil de manejar para la programación ordinaria.

Más tarde used this encoding and translated the examples de uno de los documentos de Oleg escritos en MetaOCAMl, para usar C# y Linq. El intérprete puede ejecutar de forma transparente programas escritos usando este lenguaje incrustado en el lado del servidor en ASP.NET o en el lado del cliente como JavaScript.

Esta abstracción sobre los intérpretes es una característica de la codificación final sin etiquetas de Oleg. Los enlaces a su documento se proporcionan en la publicación del blog.

Las interfaces son de primera clase en .NET, y como utilizamos interfaces para codificar firmas de módulos, los módulos y las firmas de los módulos también son de primera clase en esta codificación. Por lo tanto, los funtores simplemente usan la interfaz directamente en lugar de las firmas de los módulos, es decir. Aceptarían una instancia de ISymantics <B> y le delegarían cualquier llamada.

Answer 5

He publicado a detailed description de mi traducción para módulos ML, firmas y funtores con una codificación C# equivalente. Espero que alguien lo encuentre útil.