Mantenere tipo generico senza η-espansione

Question

Quello che sto facendo: che sto scrivendo un piccolo sistema interprete in grado di analizzare un file, trasformarlo in una sequenza di operazioni, e poi migliaia di sfamare set di dati in quella sequenza per l'estratto qualche valore finale da ciascuno. Un interprete compilato costituito da un elenco di funzioni pure che prendono due argomenti: un insieme di dati, e un contesto di esecuzione. Ogni funzione restituisce il contesto di esecuzione modificata:

  

type ('data, 'context) interpreter = ('data -> 'context -> 'context) list

Il compilatore è essenzialmente un tokenizer con una fase finale di token da istruzioni mappatura che utilizza una mappa Descrizione definito come segue:

  

type ('data, 'context) map = (string * ('data -> 'context -> 'context)) list

sguardi di utilizzo interprete tipici come questo:

let pocket_calc = 
  let map = [ "add", (fun d c -> c # add d) ;
              "sub", (fun d c -> c # sub d) ;
              "mul", (fun d c -> c # mul d) ]
  in 
  Interpreter.parse map "path/to/file.txt"

let new_context = Interpreter.run pocket_calc data old_context

Il problema: Vorrei che il mio pocket_calc interprete per funzionare con qualsiasi classe che supporta add, sub e mul metodi, e il tipo data corrispondente (potrebbero essere numeri interi per una classe contesto e floating numeri in virgola per un altro).

Tuttavia, pocket_calc è definito come un valore e non una funzione, in modo che il sistema di tipo non fa il suo tipo generico: la prima volta che viene utilizzato, i tipi 'data e 'context sono legati ai tipi di qualsiasi dato e contesto ho fornire, e l'interprete diventa sempre incompatibile con qualsiasi altro tipo di dati e di contesto.

Una soluzione praticabile è quella di ETA-espandere la definizione di interprete per consentire ai propri parametri di tipo ad essere generico:

let pocket_calc data context = 
  let map = [ "add", (fun d c -> c # add d) ;
              "sub", (fun d c -> c # sub d) ;
              "mul", (fun d c -> c # mul d) ]
  in 
  let interpreter = Interpreter.parse map "path/to/file.txt" in
  Interpreter.run interpreter data context

Tuttavia, questa soluzione è inaccettabile per diverse ragioni:

• E 'ri-compila l'interprete ogni volta che si chiama, che degrada in modo significativo le prestazioni. Anche la fase di mappatura (trasformare una lista di token in un interprete utilizzando l'elenco mappa) provoca un rallentamento evidente.

• Il mio progetto si basa su tutti gli interpreti corso di caricamento in fase di inizializzazione, perché le questioni compilatore avvertenze ogni volta che un token nel file caricato non corrisponde a una linea nella lista delle mappe, e voglio vedere tutti quegli avvertimenti quando il lanci di software (non quando i singoli interpreti sono infine eseguiti).

• A volte mi vuole riutilizzare una data lista mappa in diversi interpreti, sia da solo o anteponendo istruzioni aggiuntive (per esempio, "div").

Le domande: non v'è alcun modo per rendere il tipo parametrico diversa eta-espansione? Forse qualche trucco intelligente che coinvolge le firme dei moduli o eredità? Se questo è impossibile, c'è qualche modo per alleviare le tre questioni che ho menzionato in precedenza al fine di rendere eta-espansione una soluzione accettabile? Grazie!

Answer 1

  

Una soluzione praticabile è quella di ETA-espandere la   definizione del interprete per permettere   i suoi parametri di tipo ad essere generico:

 let pocket_calc data context = 
   let map = [ "add", (fun d c -> c # add d) ;
               "sub", (fun d c -> c # sub d) ;
               "mul", (fun d c -> c # mul d) ]
   in 
   let interpreter = Interpreter.parse map "path/to/file.txt" in
   Interpreter.run interpreter data context

  

Tuttavia, questa soluzione è inaccettabile   per diversi motivi:

     

  
• E 'ri-compila l'interprete ogni volta che si chiama, che   degrada in modo significativo le prestazioni.   Anche la fase di mappatura (girando un gettone   elenco in un interprete utilizzando la mappa   lista) provoca un rallentamento evidente.
  

Si ricompila l'interprete ogni volta perché si sta facendo male. La forma corretta è più qualcosa di simile (e tecnicamente, se l'interpretazione parziale di Interpreter.run a interpreter può fare alcuni calcoli, si dovrebbe spostare fuori dalla fun troppo).

 let pocket_calc = 
   let map = [ "add", (fun d c -> c # add d) ;
               "sub", (fun d c -> c # sub d) ;
               "mul", (fun d c -> c # mul d) ]
   in 
   let interpreter = Interpreter.parse map "path/to/file.txt" in
   fun data context -> Interpreter.run interpreter data context

Answer 2

Credo che le tue bugie problema in una mancanza di polimorfismo nelle vostre operazioni, che si desidera avere un tipo parametrico chiuso (opere per tutti i dati che supportano i seguenti primitive aritmetiche) invece di avere un parametro di tipo che rappresenta un tipo di dati fissa. Tuttavia, è un po 'difficile per assicurarsi che sia esattamente questo, perché il codice non è a sé stante sufficiente per testarlo.

Supponendo che il tipo di dato per primitive:

type 'a primitives = <
  add : 'a -> 'a;
  mul : 'a -> 'a; 
  sub : 'a -> 'a;
>

È possibile utilizzare il polimorfismo del primo ordine fornito da strutture e oggetti:

type op = { op : 'a . 'a -> 'a primitives -> 'a }

let map = [ "add", { op = fun d c -> c # add d } ;
            "sub", { op = fun d c -> c # sub d } ;
            "mul", { op = fun d c -> c # mul d } ];;

È possibile ottenere indietro i seguenti dati-agnostic tipo:

 val map : (string * op) list

Modifica: per quanto riguarda i suoi commenti su diversi tipi di operazione, non sono sicuro che il livello di flessibilità che si desidera. Non credo che si possa mescolare le operazioni su diversi primitive nella stessa lista, e ancora beneficiare delle specificità di ciascuna: nella migliore delle ipotesi, si potrebbe trasformare solo un "intervento nell'arco di add / sub / mul" in un "intervento nell'arco di add / sub / mul / div"(come siamo controvarianti nel tipo primitivi), ma certamente non molto.

Ad un livello più pragmatico, è vero che, con quel disegno, è necessario un tipo diverso "operazione" per ogni tipo di primitive. Si potrebbe facilmente, tuttavia, costruire un funtore parametrizzata tipo primitive e restituire il tipo di operazione.

Non so come si potrebbe esporre una relazione di sottotipo diretta tra i diversi tipi primitivi. Il problema è che questo avrebbe bisogno di una relazione sottotipizzazione a livello funtore, che non credo che abbiamo in Caml. Si potrebbe, tuttavia, utilizzando una forma più semplice di subtyping esplicita (invece di lanciare a :> b, utilizzare una funzione a -> b), costruire secondo funtore, contravariant, che, data una mappa da un tipo primitivo verso l'altro, avrebbero costruito una mappa da una sola operazione tipo all'altro.

E 'del tutto possibile che, con una diversa rappresentazione e intelligente di tipo evoluto, una soluzione molto più semplice è possibile. I moduli di prima classe di 3.12 potrebbe anche entrare in gioco, ma tendono ad essere utile per prima classe tipi esistenziali, mentre qui abbiamo rhater utilizzare i tipi universali.

interpretativi generali e di funzionamento reificazioni

Oltre al vostro problema di battitura locali, non sto sicuro che siete diretti nel modo giusto. Si sta cercando di eliminare spese generali interpretativa da costruzione, "prima del tempo" (prima di utilizzare le operazioni), una chiusura che corrisponde ad una rappresentazione in lingua del funzionamento.

Nella mia esperienza, questo approccio non generalmente sbarazzarsi di testa interpretativa, piuttosto lo sposta su un altro livello. Se si creano le chiusure ingenuamente, si avrà il flusso di analisi di controllo riprodotta a livello di chiusura: la chiusura chiamerà altri dispositivi di chiusura, ecc, come il tuo codice di analisi "interpretato" l'ingresso durante la creazione della chiusura. È eliminato il costo di parsing, ma il flusso possibilmente subottimale di controllo è sempre lo stesso. Additionnaly, chiusure tendono ad essere un dolore per manipolare direttamente:. Bisogna stare molto attenti a operazioni di confronto, ad esempio, la serializzazione, ecc

Penso che si può essere interessati a lungo termine in un intermedio "reificata" linguaggio che rappresenta le operazioni: un semplice tipo di dati algebrico per le operazioni aritmetiche, che si dovrebbe costruire dal vostro rappresentazione testuale. Si può ancora provare a costruire chiusure "prima del tempo" da esso, anche se non sono sicuro che le prestazioni sono molto meglio di interpretare direttamente, se la rappresentazione in memoria è decente. Inoltre, sarà molto più facile da collegare analizzatori intermediario / trasformatori per ottimizzare le operazioni, ad esempio passando da un modello "operazioni binarie associative" ad un modello di "operazioni di n-ary", che potrebbe essere valutata in modo più efficiente.