Tenue type générique sans η expansion

Question

Qu'est-ce que je fais: J'écris un petit système d'interprétation qui peut analyser un fichier, la transformer en une séquence d'opérations, puis alimenter des milliers d'ensembles de données dans cette séquence pour extraire une valeur finale de chacun. Un interpréteur compilé est constitué d'une liste de fonctions pures qui prennent deux arguments: un ensemble de données, et un contexte d'exécution. Chaque fonction retourne le contexte d'exécution modifié:

  

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

Le compilateur est essentiellement un tokenizer avec un dernier jeton à instruction étape de mappage qui utilise une description de la carte définie comme suit:

  

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

Utilisation d'un interprète typique ressemble à ceci:

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

Le problème: Je voudrais mon interprète pocket_calc de travailler avec une classe qui prend en charge les méthodes add, sub et mul, et le type de data correspondant (peut être des entiers pour une classe de contexte et FLOATING- nombre de points pour l'autre).

Cependant, pocket_calc est définie comme une valeur et non une fonction, de sorte que le système de type ne fait pas son type générique: la première fois qu'il est utilisé, les types de 'data et 'context sont liés aux types de toutes les données et le contexte je suis fournir, et l'interprète devient toujours incompatible avec tout autre type de données et le contexte.

Une solution viable est de êta élargir la définition de l'interprète pour permettre d'être générique ses paramètres de type:

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

Cependant, cette solution est inacceptable pour plusieurs raisons:

• re-compile l'interprète à chaque fois qu'il est appelé, ce qui dégrade considérablement les performances. Même l'étape de la cartographie (tourner une liste de jetons dans un interpréteur en utilisant la liste de la carte) provoque un ralentissement notable.

• Ma conception repose sur tous les interprètes sont chargés au moment de l'initialisation, car le compilateur émet des avertissements à chaque fois qu'un jeton dans le fichier chargé ne correspond pas à une ligne dans la liste de la carte, et je veux voir tous ces avertissements lorsque le lancements de logiciels (pas quand les interprètes individuels sont finalement exécutés).

• Je veux parfois réutiliser une liste de carte donnée dans plusieurs interprètes, que ce soit seul ou en préfixant instructions supplémentaires (par exemple, "div").

Les questions: est-il un moyen de faire le type paramétrique autre que eta expansion? Peut-être une astuce impliquant des signatures du module ou héritage? Si cela est impossible, est-il un moyen d'alléger les trois questions que j'ai mentionnées ci-dessus afin de rendre eta expansion une solution acceptable? Merci!

Answer 1

  

Une solution viable est de êta étendre   définition de l'interprète pour permettre   ses paramètres de type à être générique:

 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

  

Cependant, cette solution est inacceptable   pour plusieurs raisons:

     

  
• re-compile l'interprète à chaque fois qu'il est appelé, qui   dégrade considérablement les performances.   Même l'étape de mise en correspondance (en tournant un jeton   la liste dans un interpréteur en utilisant la carte   liste) provoque un ralentissement notable.
  

Il recompile l'interprète chaque fois que vous faites mal. La bonne forme est plus quelque chose comme ça (et techniquement, si l'interprétation partielle de Interpreter.run à interpreter peut faire des calculs, vous devez la déplacer de la fun aussi).

 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

Je pense que votre problème réside dans un manque de polymorphisme dans vos opérations, que vous aimeriez avoir un type paramétrique fermé (fonctionne pour toutes les données supportant les primitives arithmétiques suivantes) au lieu d'avoir un paramètre de type représentant un type de données fixe. Cependant, il est un peu difficile à assurer qu'il est exactement cela, parce que votre code n'est pas assez autonome pour le tester.

En supposant que le type donné pour les primitives:

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

Vous pouvez utiliser le polymorphisme de premier ordre fourni par des structures et des objets:

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

Vous revenez l'agnostique données type:

 val map : (string * op) list

Edit: au sujet de vos commentaires sur les différents types d'opérations, je ne suis pas sûr quel niveau de flexibilité que vous voulez. Je ne pense pas que vous pouvez mélanger les opérations sur différentes primitives dans la même liste, et encore bénéficier des spécifités de chacun: au mieux, on ne pouvait transformer une « opération sur add / sous / mul » dans une « opération plus ajouter / sous / mul / div »(comme nous sommes contravariant dans le type de primitives), mais certainement pas grand-chose.

Sur un plan plus pragmatique, il est vrai que, avec cette conception, vous avez besoin d'un type « opération » différent pour chaque type de primitives. Vous pouvez facilement, cependant, construire un foncteur paramétrées par le type de primitives et renvoyer le type d'opération.

Je ne sais pas comment on pourrait exposer une relation de sous-typage directe entre les différents types primitifs. Le problème est que cela aurait besoin d'une relation de sous-typage au niveau foncteur, que je ne pense pas que nous avons en Caml. Vous pouvez, cependant, en utilisant une forme plus simple de sous-typage explicite (au lieu de coulée a :> b, utilisez une fonction a -> b), construire un deuxième foncteur, contravariant, que, étant donné une carte d'un type primitif à l'autre, construirait une carte d'une opération de type à l'autre.

Il est tout à fait possible que, avec une représentation différente et intelligente du type évolué, est possible une solution beaucoup plus simple. Les modules de première classe de 3,12 pourrait aussi venir en jeu, mais ils ont tendance à être utile pour la première classe des types existentiels, alors qu'ici nous utilisons rhater types universels.

frais généraux et d'interprétation réifications opération

En plus de votre problème de frappe locale, je ne suis pas sûr que vous vous dirigez dans le bon sens. Vous essayez d'éliminer les frais généraux d'interprétation par la construction, « à l'avance » (avant d'utiliser les opérations), une fermeture correspondant à une représentation de votre opération en langue.

Dans mon expérience, cette approche ne soit pas généralement débarrasser des frais généraux d'interprétation, plutôt déplace à une autre couche. Si vous créez vos fermetures ingénument, vous aurez le flux d'analyse syntaxique de contrôle reproduit sur la couche de fermeture: la fermeture appellera autres dispositifs de fermeture, etc., comme votre code d'analyse syntaxique « interprété » l'entrée lors de la création de la fermeture. Vous avez éliminé le coût de l'analyse syntaxique, mais le débit peut-être sous-optimale du contrôle est toujours le même. Additionnaly, les fermetures ont tendance à être une douleur à manipuler directement: il faut être très prudent au sujet des opérations de comparaison par exemple, sérialisation, etc

.

Je pense que vous pouvez être intéressé par le long terme dans une langue intermédiaire « réifié » représentant vos opérations: un type de données simple algébrique pour les opérations arithmétiques, que vous construire à partir de votre représentation textuelle. Vous pouvez toujours essayer de construire des fermetures « à l'avance » de lui, mais je ne suis pas sûr que les performances sont beaucoup mieux que directement interpréter, si la représentation en mémoire est bonne. De plus, il sera beaucoup plus facile de brancher des analyseurs / transformateurs intermédiaires pour optimiser vos opérations, par exemple passer d'un modèle « opérations binaires associatives » à un modèle « opérations n-aire », qui pourrait être plus efficacement évaluée.