Mantener tipo genérico sin η-expansión

Question

Lo que estoy haciendo: Estoy escribiendo un sistema de intérprete pequeña que puede analizar un archivo, convertirlo en una secuencia de operaciones, y luego alimentar a miles de conjuntos de datos en esa secuencia de extracto algunos valor final de cada uno. Un intérprete compilado consiste en una lista de funciones puras que toman dos argumentos: un conjunto de datos, y un contexto de ejecución. Cada función devuelve el contexto de ejecución modificado:

  

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

El compilador es esencialmente un tokenizer con un paso final token--a la instrucción de asignación que utiliza un mapa descripción define como sigue:

  

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

Uso típico intérprete es similar al siguiente:

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

El problema: Me gustaría que mi pocket_calc intérprete para trabajar con cualquier clase que add soportes, métodos y sub mul, y el correspondiente tipo data (podrían ser números enteros para una clase de contexto y flotante números de punto para otro).

Sin embargo, pocket_calc se define como un valor y no una función, por lo que el sistema de tipo no hace que su tipo genérico: la primera vez que se usa, los tipos 'data y 'context están ligados a los tipos de cuantos datos y el contexto lo primero proporcionar, y el intérprete se convierte siempre incompatible con cualquier otro tipo de datos y el contexto.

Una solución viable es eta-ampliar la definición del intérprete para permitir a sus parámetros de tipo para ser genérico:

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

Sin embargo, esta solución es inaceptable por varias razones:

• re-compila el intérprete cada vez que se llama, que se degrada significativamente el rendimiento. Incluso el paso de asignación (convertir una lista de símbolos en un intérprete utilizando la lista de mapas) provoca una desaceleración notable.

• Mi diseño se basa en todos los intérpretes que se cargan en tiempo de inicialización, debido a que los emite advertencias del compilador siempre que un token en el archivo cargado no concuerda con una línea en la lista de mapas, y yo quiero ver todas esas advertencias cuando el lanzamientos de software (no cuando los intérpretes individuales son finalmente RUN).

• A veces desea volver a utilizar una lista mapa dado en varios intérpretes, ya sea por sí mismo o anteponiendo instrucciones adicionales (por ejemplo, "div").

Las preguntas: ¿hay alguna manera de hacer que el tipo paramétrico que no sea eta-expansión? Tal vez algún truco inteligente que implica la firma de módulo o herencia? Si eso es imposible, ¿hay alguna manera de aliviar las tres cuestiones que he mencionado anteriormente con el fin de hacer eta-expansión de una solución aceptable? Gracias!

Answer 1

  

Una solución viable es eta ampliar el   definición del intérprete para permitir   sus parámetros de tipo para ser genérico:

 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

  

Sin embargo, esta solución es inaceptable   por varias razones:

     

  
• Se re-compila el intérprete cada vez que se llama, el cual   degrada significativamente el rendimiento.   Incluso el paso de mapeo (girando un contador   lista en un intérprete utilizando el mapa   lista) provoca una desaceleración notable.
  

Se vuelve a compilar el intérprete cada vez porque lo está haciendo mal. La forma correcta es más o menos así (y técnicamente, si la interpretación parcial de Interpreter.run a interpreter puede hacer algunos cálculos, se debe moverlo fuera de la fun también).

 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

creo que sus mentiras problema en una falta de polimorfismo en sus operaciones, lo que le gustaría tener un tipo paramétrico cerrado (obras de todos los datos que apoyan las siguientes primitivas aritméticas) en lugar de tener un parámetro de tipo representa un tipo de datos fija. Sin embargo, es un poco difícil asegurar que es exactamente esto, debido a que su código no es autónomo suficiente para probarlo.

Suponiendo que el tipo dado de primitivas:

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

Se puede usar el polimorfismo de primer orden proporcionado por estructuras y objetos:

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

volver la siguiente independiente del tipo de datos:

 val map : (string * op) list

Editar: con respecto a su comentario sobre diferentes tipos de operación, no estoy seguro de qué nivel de flexibilidad que desea. Yo no creo que se podría mezclar las operaciones más primitivas diferentes en la misma lista, y todavía beneficiarse de las especificidades de cada uno: a lo sumo, sólo se podía transformar una "operación sobre add / sub / mul" en una "operación sobre add / sub / mul / div"(ya que estamos en el tipo contravariant primitivas), pero ciertamente no mucho.

En un nivel más pragmático, es cierto que, con ese diseño, se necesita un tipo diferente "operación" para cada tipo de primitivas. Desde aquí se puede, sin embargo, construir un funtor parametrizada por el tipo primitivas y devolver el tipo de operación.

No sé cómo se podría exponer una relación directa entre subtipos diferentes tipos primitivos. El problema es que esto tendría una relación subtipificación a nivel funtor, que no creo que tenemos en Caml. Se podría, sin embargo, el uso de una forma más simple de los subtipos explícita (en lugar de echar a :> b, use un a -> b función), construcción de segunda funtor, contravariant, que, dado un mapa de un tipo primitivo a la otra, sería construir un mapa de una operación tipo a otro.

Es muy posible que, con una representación diferente e inteligente del tipo evolucionado, una solución mucho más simple posible. módulos de primera clase de 3.12 también podrían entrar en juego, pero tienden a ser útil para este tipo existencial de primera clase, mientras que aquí nos rhater utilizar tipos universales.

interpretativos generales y operación reificaciones

Además de su problema de escribir locales, no estoy seguro de que está al frente de la manera correcta. Usted está tratando de eliminar la sobrecarga interpretativa de la construcción, "antes de tiempo" (antes de utilizar las operaciones), un cierre que corresponde a una representación en el lenguaje de su operación.

En mi experiencia, este enfoque no en general, deshacerse de los gastos generales de interpretación, más bien lo mueve a otra capa. Si crea sus cierres ingenuamente, tendrá que analizar el flujo del control reproducido en la capa de cierre: el cierre llamará demás dispositivos de cierre, etc., como su código de análisis "interpreta" la entrada al crear el cierre. Usted eliminó el costo de análisis, pero el flujo posiblemente subóptima de control es todavía la misma. Additionnaly, cierres tienden a ser un dolor de manipular directamente:. Usted tiene que tener mucho cuidado con las operaciones de comparación, por ejemplo, la serialización, etc.

creo que puede estar interesado en el largo plazo en un intermedio "cosificado" lenguaje de representación de sus operaciones: un tipo de dato simple algebraica para operaciones aritméticas, que se construiría a partir de su representación textual. Todavía se puede tratar de construir el cierre de "anticipación" de ella, aunque no estoy seguro de las actuaciones son mucho mejor que interpretar directamente, si la representación en memoria es decente. Por otra parte, será mucho más fácil de conectar intermediarios analizadores / transformadores para optimizar sus operaciones, por ejemplo, al pasar de un modelo de "operaciones binarias asociativas" a un modelo de "operaciones de n-arias", lo que podría ser evaluado de manera más eficiente.