pattern-matching - 通过功能组合来统一OCaml模式

Question

假设我已经手动定义了一些类似的代码：

type test  = A of bool | B | C of bool * bool 
type test2 = D | E of bool * bool 
type test3 = F | G of bool | H of bool

let f = function | A(x) -> E(x,true) | B -> D | C(a,b) -> E(b,a)

let g = function  | D -> F | E(a,b) -> if a then G(b) else H(b)

现在，我想将构图g∘f评估为不需要使用中间表示 test2的函数。我一直在考虑结构统一，但是我在问以下问题：


声明 let h x = g (f x)时OCaml会自动执行这种统一吗？
如果不是，是否存在可以在OCaml中实现的通用算法，以便将 compile转换为期望的h的ml文件？


提前致谢

Answer 1

免责声明

我不是OCaml编译器开发人员。如果您想征求他们的意见，最好在邮件列表上与他们联系。

第1部分

从理论上讲，现代OCaml（我已经尝试过使用4.0 {3,4} + flambda）能够消除某些类型为test2的中间数据结构。但是，要实现这一点，您需要传递特殊的优化选项，并将[@@inlined always]添加到函数f中，否则即使使用疯狂的内联选项（例如-inline 10000和-inline-toplevel 10000）也不会内联。

但是，在一般情况下，对于较大的功能，这可能不起作用。在这里，我假设您所展示的示例是一个玩具示例，在现实生活中，您将面临更大的功能和两个以上的构成（即，数百个构造函数和数百个构成）根本不值得优化）。

第2部分

理论

说到一般算法，如果我们太挑剔，那是不可能的，因为在模式匹配中->的右边可以有任何OCaml表达式，即图灵完备的程序。因此，我们有一个决策问题的等价物。即使我们通过禁止循环和副作用来限制表达语言，问题仍然是NP难题，因此尝试解决它可能不值得。但是，如果我们通过禁止除带有琐碎操作数的构造函数应用程序之外的任何表达式来进一步限制自己，那么我们实际上将对有限状态机（FSM）进行编码。有很多定义明确的FSM优化和状态最小化算法，因此不难消除冗余。

实践

实际上，我可能不会编写将ml代码转换为ml代码的函数。根据我的实际任务，我将考虑以下方法。

可数的输入集

如果居住在类型为test的值的集合实际上是有限的（即，如果它适合OCaml数组），那么我将尝试编写一个枚举类型为test的所有可能值并存储结果的函数组成。您可以使用[@@deriving enumerate]计算类型为test的所有可能值

# type test  = A of bool | B | C of bool * bool [@@deriving enumerate];;
type test = A of bool | B | C of bool * bool
val all_of_test : test list =
  [A false; A true; B; C (false, false); C (true, false); C (false, true);
   C (true, true)]

然后，您可以为每个 test类型的值分配一个序数，并进行O（1）转换以键入 test3。另外，因为我们已经预先计算了所有构造函数，所以根本没有分配。

但是，您仍然需要转换 test -> int才能使用我们的工作方式，并且此操作将需要 log(k)个分支，其中 k是类型为 test的构造函数的数量。从big-O表示法的角度来看， k是恒定的。但是如果确实很大，则可以尝试使所有构造函数成为无参数的，例如通过将 A of bool表示为两个构造函数 A_true和 A_false。在这种情况下，您将获得纯O（1）转换，而没有任何开销（只是数组取消引用）。

具有无法解释功能的可枚举输入

如果存在带有 int或 string类型的值的构造函数，则实际上不可能枚举它们。但是，如果转换 h不查看此值，而只是重新排列它们，即将它们视为 Uninterpreted functions，则应尝试使用GADT将此参数与输入语言分离。假设您具有以下数据构造函数：

| C of string

结果 h (C s)对于所有 s都是相同的。这样就完全不需要将 s传递给 h了。但是，您仍然希望将有效负载 s传递给其他函数，例如，传递给 exec。可以使用GADT，首先我们将有效负载与构造函数解耦：

| C : string query

然后，我们将能够将查询作为两个不同的参数传递给函数：

val exec : 'a query -> 'a -> unit

一般情况

如果以上两种情况都不适合您，那么您需要编写自己的编译器:)看起来，您正在实现某种语言的解释程序，该语言使用OCaml作为宿主语言，并且您希望OCaml将为您进行优化。好吧，OCaml确实不是编写解释器的不错选择，但它不能优化您的DSL，因为它不知道DSL的语义。所有优化都涉及语义规则的巧妙应用。因此，这意味着，如果您对解释器的性能不满意，则需要编写自己的优化编译器。首先，您需要设计将在其上执行查询的抽象机，然后编写针对该机器的优化程序。