保持类型通用而不进行 η 扩展
-
26-09-2019 - |
题
我在做什么: 我正在编写一个小型解释器系统,它可以解析文件,将其转换为一系列操作,然后将数千个数据集输入到该序列中,以从每个数据集中提取一些最终值。已编译的解释器由一系列带有两个参数的纯函数组成:数据集和执行上下文。每个函数返回修改后的执行上下文:
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
, sub
和 mul
方法,以及相应的 data
类型(对于一个上下文类可以是整数,对于另一种上下文类可以是浮点数)。
然而, 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 扩展成为一个可接受的解决方案?谢谢你!
解决方案
一个可行的解决方案是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
可以做一些计算,你应该把它移出 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
其他提示
我认为你的问题在于你的操作缺乏多态性,你希望有一个封闭的参数类型(适用于支持以下算术基元的所有数据),而不是有一个代表固定数据类型的类型参数。但是,要确保确实如此有点困难,因为您的代码不够独立,无法对其进行测试。
假设原语的给定类型:
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 元操作”模型,可以更有效地评估。