保持类型通用而不使用 η-扩展

Question

我正在做的事情：我正在编写一个小型解释器系统，它可以解析文件，将其转换为一系列操作，然后将数千个数据集输入到该序列中以提取一些最终值来自每一个。已编译的解释器由一系列纯函数组成，这些函数带有两个参数：数据集和执行上下文。每个函数返回修改后的执行上下文：

type('data,'context)解释器=('data -> 'context -> 'context)列表

编译器本质上是一个分词器，具有最终的分词到指令映射步骤，该步骤使用地图描述定义如下：

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

典型的解释器用法如下：

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

问题：< /strong> 我希望我的 pocket_calc 解释器能够处理任何支持 add、sub 和 mul 的类方法，以及相应的数据类型（一个上下文类可以是整数，另一个上下文类可以是浮点数）。

但是，pocket_calc 被定义为值而不是函数，因此类型系统不会使其类型通用：第一次使用时，'data 和 'context 类型绑定到我首先提供的任何数据和上下文的类型，并且解释器将永远与任何其他数据和上下文类型不兼容。

一个可行的解决方案是对解释器的定义进行 eta 扩展，以允许其类型参数是通用的：

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

但是，由于以下几个原因，该解决方案是不可接受的：

• 它每次调用时都会重新编译解释器，这会显着降低性能。即使是映射步骤（使用映射列表将标记列表转换为解释器）也会导致明显的速度减慢。

• 我的设计依赖于在初始化时加载的所有解释器，因为只要加载文件中的标记与映射列表中的行不匹配，编译器就会发出警告，并且我希望在软件启动时看到所有这些警告（不是当单个解释器最终运行时）。

• 我有时想在多个解释器中重用给定的地图列表，无论是单独使用还是通过预先添加其他指令（例如，“div”）。

问题：除了 eta 扩展之外，还有其他方法可以使类型参数化吗？也许有一些涉及模块签名或继承的聪明技巧？如果这是不可能的，有没有什么方法可以缓解我上面提到的三个问题，使 eta 扩展成为一个可接受的解决方案？谢谢你！

Answer 1

一个可行的解决方案是 eta 扩展
解释器的定义允许
它的类型参数是通用的：

 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

但是，这个解决方案是不可接受的
有几个原因：

• 每次调用时都会重新编译解释器，这
  显着降低性能。
  甚至映射步骤（将令牌
  使用地图将列表放入解释器中
  列表）导致明显的速度减慢。

它每次都会重新编译解释器，因为你做错了。正确的形式更像是这样（从技术上讲，如果 Interpreter.run 到 interpreter 的部分解释可以进行一些计算，您应该将其移出 也很有趣）。

 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

我认为你的问题在于你的操作缺乏多态性，你希望有一个封闭的参数类型（适用于支持以下算术基元的所有数据），而不是有一个代表固定数据类型的类型参数。
但是，要确保确实如此有点困难，因为您的代码不够独立，无法对其进行测试。

假设给定的基元类型：

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

您可以使用结构和对象提供的一阶多态性：

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

您将得到以下与数据无关的类型：

 val map : (string * op) list

编辑：关于您对不同操作类型的评论，我'我不确定您想要哪种级别的灵活性。我认为您不能在同一列表中混合对不同原语的操作，并且仍然受益于每个原语的特殊性：充其量，您只能将“对 add/sub/mul 的操作”转换为“对 add/ 的操作” sub/mul/div”（因为我们在原语类型中是逆变的），但肯定不多。

在更务实的层面上，确实，通过这种设计，您需要为每个基元类型使用不同的“操作”类型。然而，您可以轻松地构建一个由基元类型参数化的函子并返回操作类型。

我不知道如何公开不同原始类型之间的直接子类型关系。问题是这需要函子级别的子类型关系，我认为 Caml 中没有这种关系。但是，您可以使用更简单的显式子类型（而不是转换 a :> b，而是使用函数 a -> b），构建第二个函子，逆变，即给定从一种基本类型到另一种类型的映射，将构建从一种操作类型到另一种操作类型的映射。

完全有可能的是，通过进化出不同且巧妙的类型表示，可以得到更简单的解决方案。 3.12 的一流模块也可能发挥作用，但它们往往对一流的存在类型有帮助，而在这里我们不愿使用通用类型。

解释开销和操作具体化

除了您本地的打字问题之外，我不确定您的方向是否正确。您试图通过“提前”（在使用操作之前）构建与操作的语言表示相对应的闭包来消除解释开销。

根据我的经验，这种方法通常不会消除解释开销，而是将其移动到另一层。如果您天真地创建闭包，您将在闭包层重现控制的解析流程：闭包将调用其他闭包等，因为您的解析代码在创建闭包时“解释”了输入。您消除了解析成本，但可能次优的控制流仍然相同。此外，直接操作闭包往往很痛苦：您必须非常小心比较操作，例如序列化等。

我认为您可能对代表您的操作的中间“具体化”语言的长期感兴趣：用于算术运算的简单代数数据类型，您可以根据文本表示构建它。您仍然可以尝试从中“提前”构建闭包，尽管我不确定性能是否比直接解释它好得多，如果内存中的表示不错的话。此外，插入中间分析器/转换器来优化您的操作会更容易，例如从“关联二元操作”模型到“n 元操作”模型，可以更有效地评估。