Manter o tipo genérico sem η-expansão

Question

O que eu estou fazendo: Estou escrevendo um sistema pequeno de intérprete que pode analisar um arquivo, transformá -lo em uma sequência de operações e, em seguida, alimentar milhares de conjuntos de dados nessa sequência para extrair algum valor final de cada um. Um intérprete compilado consiste em uma lista de funções puras que recebem dois argumentos: um conjunto de dados e um contexto de execução. Cada função retorna o contexto de execução modificado:

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

O compilador é essencialmente um tokenizer com uma etapa final de mapeamento de token-to-instruction que usa uma descrição do mapa definida da seguinte forma:

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

O uso típico de intérprete se parece com o seguinte:

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

O problema: Eu gostaria do meu pocket_calc intérprete para trabalhar com qualquer classe que suporta add, sub e mul métodos e os correspondentes data Tipo (pode ser números inteiros para uma classe de contexto e números de ponto flutuante para outro).

No entanto, pocket_calc é definido como um valor e não uma função; portanto, o sistema de tipos não torna seu tipo genérico: a primeira vez que é usada, o 'data e 'context Os tipos estão vinculados aos tipos de quaisquer dados e contexto que eu forneço primeiro, e o intérprete se torna para sempre incompatível com outros dados e tipos de contexto.

Uma solução viável é expandir a definição do intérprete para permitir que seus parâmetros de tipo sejam genéricos:

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

No entanto, esta solução é inaceitável por vários motivos:

• Ele recorrente ao intérprete toda vez que se chama, o que degrada significativamente o desempenho. Até a etapa de mapeamento (transformando uma lista de token em um intérprete usando a lista de mapas) causa uma desaceleração notável.

• Meu design depende de todos os intérpretes que estão sendo carregados no tempo de inicialização, porque o compilador emite avisos sempre que um token no arquivo carregado não corresponde a uma linha na lista de mapas, e quero ver todos esses avisos quando o software é lançado (não quando individual Os intérpretes são eventualmente executados).

• Às vezes, quero reutilizar uma determinada lista de mapas em vários intérpretes, seja por conta própria ou precendendo instruções adicionais (por exemplo, "div").

As questões: Existe alguma maneira de tornar o tipo paramétrico que não seja a expansão do ETA? Talvez algum truque inteligente envolvendo assinaturas ou herança do módulo? Se isso é impossível, existe alguma maneira de aliviar as três questões que mencionei acima, a fim de tornar a expansão do ETA uma solução aceitável? Obrigada!

Answer 1

Uma solução viável é expandir a definição do intérprete para permitir que seus parâmetros de tipo sejam genéricos:

 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

No entanto, esta solução é inaceitável por vários motivos:

• Ele recorrente ao intérprete toda vez que se chama, o que degrada significativamente o desempenho. Até a etapa de mapeamento (transformando uma lista de token em um intérprete usando a lista de mapas) causa uma desaceleração notável.

Ele recompila o intérprete sempre porque você está fazendo errado. A forma adequada é mais algo assim (e tecnicamente, se a interpretação parcial de Interpreter.run para interpreter pode fazer alguns cálculos, você deve movê -lo para fora do fun também).

 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

Eu acho que seu problema está na falta de polimorfismo em suas operações, que você gostaria de ter um tipo paramétrico fechado (funciona para todos os dados que suportam as seguintes primitivas aritméticas) em vez de ter um parâmetro de tipo que representa um tipo de dados fixo. No entanto, é um pouco difícil garantir que seja exatamente isso, porque seu código não é independente o suficiente para testá-lo.

Assumindo o tipo dado para primitivas:

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

Você pode usar o polimorfismo de primeira ordem fornecido por estruturas e 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 } ];;

Você recebe o seguinte tipo de dados agnóstico de dados:

 val map : (string * op) list

Editar: Em relação ao seu comentário sobre diferentes tipos de operação, não tenho certeza de qual nível de flexibilidade você deseja. Eu não acho que você possa misturar operações sobre diferentes primitivas na mesma lista e ainda se beneficiar das especificações de cada uma: na melhor das hipóteses, você só pode transformar uma "operação em add/sub/mul" em uma operação sobre add/add/ sub/mul/div "(como somos contravariantes no tipo primitivos), mas certamente não muito.

Em um nível mais pragmático, é verdade que, com esse design, você precisa de um tipo de "operação" diferente para cada tipo de primitiva. Você pode facilmente, no entanto, criar um functor parametizado pelo tipo de primitivos e retornar o tipo de operação.

Não sei como alguém exporia uma relação de subtipagem direta entre diferentes tipos primitivos. O problema é que isso precisaria de uma relação de subtipagem no nível do functor, que eu acho que não temos no CAML. Você pode, no entanto, usar uma forma mais simples de subtipagem explícita (em vez de fundir a :> b, use uma função a -> b), construa o segundo functor, contravariante, que, dado um mapa de um tipo primitivo para o outro, construiria um mapa de um tipo de operação para o outro.

É inteiramente possível que, com uma representação diferente e inteligente do tipo evoluído, seja possível uma solução muito mais simples. Os módulos de primeira classe de 3,12 também podem entrar em jogo, mas eles tendem a ser úteis para os tipos existenciais de primeira classe, enquanto aqui nós usamos tipos universais.

Reificações de sobrecarga e operação interpretativas

Além do seu problema de digitação local, não tenho certeza se você está indo do caminho certo. Você está tentando eliminar a sobrecarga interpretativa pela construção, "Antes do tempo" (antes de usar as operações), um fechamento correspondente a uma representação interna da sua operação.

Na minha experiência, essa abordagem geralmente não se livra da sobrecarga interpretativa, mas a move para outra camada. Se você criar seu fechamento ingenuamente, terá o fluxo de controle de controle reproduzido na camada de fechamento: o fechamento chamará outros fechamentos, etc., como seu código de análise "interpretou" a entrada ao criar o fechamento. Você eliminou o custo da análise, mas o fluxo de controle possivelmente subótimo ainda é o mesmo. Além disso, os fechamentos tendem a ser uma dor de manipular diretamente: você deve ter muito cuidado com as operações de comparação, por exemplo, serialização etc.

Eu acho que você pode estar interessado a longo prazo em um idioma intermediário "reificado" que representa suas operações: um tipo de dados algébrica simples para operações aritméticas, que você construiria a partir de sua representação textual. Você ainda pode tentar criar fechamentos "antes do tempo", embora não tenha certeza de que as performances sejam muito melhores do que interpretá-lo diretamente, se a representação na memória for decente. Além disso, será muito mais fácil conectar analisadores/transformadores intermediários para otimizar suas operações, por exemplo, passando de um modelo de "operações binárias associativas" para um modelo de "operações n-yar", que pode ser avaliado com mais eficiência.