3

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

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

编译器本质上是一个标记器,具有最终标记到指令的映射步骤,该步骤使用如下定义的映射描述:

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

问题:我希望我的pocket_calc解释器可以使用任何支持add、方法submul相应data类型的类(一个上下文类可以是整数,另一个可以是浮点数)。

然而,pocket_calc被定义为一个值而不是一个函数,因此类型系统不会使其类型成为泛型:第一次使用它时,'dataand'context类型被绑定到我首先提供的任何数据和上下文的类型,解释器变成永远与任何其他数据和上下文类型不兼容。

一个可行的解决方案是对解释器的定义进行 eta-expand 以允许其类型参数是通用的:

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-expansion,还有什么方法可以使类型参数化?也许是一些涉及模块签名或继承的巧妙技巧?如果这是不可能的,有没有办法缓解我上面提到的三个问题,以使 eta-expansion 成为可接受的解决方案?谢谢!

4

2 回答 2

4

一个可行的解决方案是对解释器的定义进行 eta-expand 以允许其类型参数是通用的:

 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

但是,由于以下几个原因,此解决方案是不可接受的:

  • 每次调用它都会重新编译解释器,这会显着降低性能。即使是映射步骤(使用映射列表将令牌列表转换为解释器)也会导致明显的减速。

它每次都重新编译解释器,因为你做错了。正确的形式更像是这样(从技术上讲,如果 to 的部分解释Interpreter.run可以interpreter做一些计算,你也应该把它移出to fun)。

 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
于 2010-10-25T11:41:39.527 回答
3

我认为您的问题在于您的操作中缺乏多态性,您希望它具有封闭的参数类型(适用于支持以下算术原语的所有数据),而不是具有表示固定数据类型的类型参数。但是,要确保它确实是这样有点困难,因为您的代码没有足够的独立性来测试它。

假设原语的给定类型:

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 元操作”模型,这可以更有效地评估。

于 2010-10-25T10:03:17.650 回答