I funtori ML possono essere completamente codificati in .NET (C#/F#)?

Question

I funtori ML possono essere praticamente espressi con interfacce e generici .NET?Esiste un esempio di utilizzo di un funtore ML avanzato che sfida tali codifiche?

Riepilogo delle risposte:

Nel caso generale la risposta è NO.I moduli ML forniscono funzionalità (come la condivisione delle specifiche tramite firme [1]) che non si associano direttamente ai concetti .NET.

Tuttavia, per alcuni casi d'uso gli idiomi ML possono essere tradotti.Questi casi includono non solo quelli di base Set funtore [2], ma anche la codifica funtoriale delle monadi [3], e usi ancora più avanzati di Haskell, come finalmente gli interpreti senza tag [4, 5].

Le codifiche pratiche richiedono compromessi come i downcast semi-sicuri.Il tuo chilometraggio sarà diffidente.

Blog e codice:

1. blog.matthewdoig.com
2. highlogics.blogspot.com
3. funtore monade in Fa#

Answer 1

Una delle caratteristiche principali dei moduli ML è la condivisione delle specifiche. Non esiste alcun meccanismo in .NET che sia in grado di emularli - il macchinario richiesto è semplicemente troppo diverso.

Puoi provare a farlo trasformando i tipi condivisi in parametri, ma ciò non può emulare fedelmente la capacità di definire una firma, e quindi applicare la condivisione ad essa, forse in diversi modi.

Secondo me, .NET trarrebbe beneficio da qualcosa che aveva questo tipo di macchinario - si avvicinerebbe quindi al supporto reale della diversità dei linguaggi moderni. Speriamo che includa i progressi più recenti nei sistemi di moduli come quelli in MixML, che secondo me è il futuro dei sistemi di moduli.        http://www.mpi-sws.org/~rossberg/mixml/

Answer 2

HigherLogics è il mio blog e ho dedicato molto tempo a indagare su questa domanda. La limitazione è in effetti l'astrazione sui costruttori di tipi, ovvero & Quot; generici su generici & Quot ;. Sembra il meglio che puoi fare per imitare i moduli ML e i funzioni richiedono almeno un cast (semi-sicuro).

Fondamentalmente si tratta di definire un tipo astratto e un'interfaccia che corrisponde alla firma del modulo che opera su quel tipo. Il tipo astratto e l'interfaccia condividono un parametro di tipo B che io chiamo a & Quot; marca & Quot ;; il marchio è generalmente solo il sottotipo che implementa l'interfaccia del modulo. Il marchio assicura che il tipo passato sia il sottotipo corretto previsto dal modulo.

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

Come puoi vedere, il cast è per lo più sicuro, poiché il sistema dei tipi assicura che il marchio del tipo di espressione corrisponda al marchio dell'interprete. L'unico modo per rovinare tutto è se il cliente crea la propria classe Exp e specifica il marchio Interpreter. C'è una codifica più sicura che evita anche questo problema, ma è troppo ingombrante per la normale programmazione.

In seguito ho usato questa codifica e tradotto gli esempi da uno degli articoli di Oleg scritti in MetaOCaml, per usare C # e Linq. L'interprete può eseguire in modo trasparente programmi scritti utilizzando questo lato server incorporato in ASP.NET o lato client come JavaScript.

Questa astrazione sugli interpreti è una caratteristica della codifica finale senza tag di Oleg. I collegamenti al suo documento sono forniti nel post del blog.

Le interfacce sono di prima classe in .NET e poiché usiamo le interfacce per codificare le firme dei moduli, anche i moduli e le firme dei moduli sono di prima classe in questa codifica. Pertanto, i funzioni utilizzano semplicemente l'interfaccia direttamente al posto delle firme dei moduli, ad es. accetterebbero un'istanza di ISymantics < B > e delegare qualsiasi chiamata ad esso.

Answer 3

Non conosco i funzioni ML abbastanza bene per rispondere davvero alla tua domanda. Ma dirò che l'unico fattore limitante di .Net che trovo sempre con la programmazione monadica è l'incapacità di astrarre su "M" nel senso di & Quot; per tutti M. qualche tipo espressione con M < T > " (ad es. dove M è un costruttore di tipi (tipo che accetta uno o più argomenti generici)). Quindi, se è qualcosa che a volte ti serve / usi con i funzioni, allora sono abbastanza sicuro che non c'è un buon modo per esprimerlo su .Net.

Answer 4

Ora ho pubblicato una descrizione dettagliata della mia traduzione per moduli, firme e funtori ML in una codifica C# equivalente.Spero che qualcuno lo trovi utile.

Answer 5

Il commento di Brian è perfetto. Ecco il codice OCaml che utilizza i funzioni per fornire un'implementazione (rigorosa) di Haskell sequence :: (Monad m) => [m a] -> m [a] parametrizzata sulla monade in questione:

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

Sembra difficile esprimere in .NET.

Aggiorna :

Usando una tecnica di naasking sono stato in grado di codificare la funzione riutilizzabile sequence in F # in un modo prevalentemente sicuro (usa i downcast).

http://gist.github.com/192353