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

Question

I funtori ML possono essere praticamente espressi con interfacce .NET e generici? Esiste un esempio di utilizzo del functor ML avanzato che sfugge a tali codifiche?

Risposte sintesi:

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

Tuttavia, per alcuni casi d'uso gli idiomi ML possono essere tradotti. Questi casi includono non solo il funtore di base Set [2], ma anche la codifica funzionale di monadi [3] e anche usi più avanzati di Haskell, come ad esempio 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. higherlogics.blogspot.com
3. monad functor in F#

Answer 1

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

Si può provare a farlo trasformando i parametri condivisi in parametri, ma questo non può emulare fedelmente la possibilità di definire una firma, e successivamente applicare la condivisione ad esso, forse in più modi diversi.

A mio parere, .NET trarrebbe vantaggio da qualcosa che ha questo tipo di macchinario - si avvicinerebbe quindi a sostenere veramente la diversità delle lingue moderne.Speriamo di includere più recenti progressi nei sistemi di moduli come quelli in MixML, che a mio parere è il futuro dei sistemi di moduli. http://www.mpi-sws.org/~rossberg/mixml/

Answer 2

Non so ML funtori abbastanza bene per rispondere davvero alla tua domanda. Ma dirò che il fattore limitante di .Net trovo sempre con monadica la programmazione è l'impossibilità di astrarre su "M" nel senso di "forall M. qualche espressione di tipo con M < T>" (es. M è un costruttore di tipi (tipo che accetta uno o più argomenti generici)). Quindi, se è qualcosa che a volte è necessario/utilizzare con i funtori, allora mi sento abbastanza sicuro che non c'è un buon modo per esprimerlo su .Net.

Answer 3

Il commento di Brian è perfetto. Ecco il codice OCaml che utilizza funtori a dare un (rigida) l'attuazione di Haskell sequence :: (Monad m) => [m a] -> m [a] parametrizzato sopra la 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 

Questo sembra difficile da esprimere in .NET.

UPDATE:

Utilizzando una tecnica da naasking sono stato in grado di codificare la funzione di sequence riutilizzabile in F # in modo per lo più type-safe (usa downcasts).

http://gist.github.com/192353

Answer 4

HigherLogics è il mio blog e ho dedicato molto tempo a indagare su questa domanda. La limitazione è in realtà astrazione rispetto ai costruttori di tipi, ovvero "generici rispetto ai generici". Sembra il meglio che puoi fare per imitare i moduli ML ei funtori 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 definisco una "marca"; il marchio è generalmente solo il sottotipo che implementa l'interfaccia del modulo. Il marchio garantisce che il tipo passato è 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 si può vedere, il cast è in gran parte al sicuro, dal momento che il sistema di tipo assicura la marca del tipo espressione corrisponde al marchio dell'interprete. L'unico modo per rovinare tutto questo è 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 programmazione ordinaria.

Successivamente, used this encoding and translated the examples da uno degli articoli di Oleg scritti in MetaOCaml, per utilizzare C# e Linq. L'interprete può eseguire in modo trasparente programmi scritti utilizzando questo linguaggio 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 articolo sono forniti nel post del blog.

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

Answer 5

Ora ho pubblicato a detailed description della mia traduzione per moduli ML, firme e funtori con una codifica C# equivalente. Spero che qualcuno lo trovi utile.