通过函数组合统一 OCaml 模式
Unifying OCaml patterns through function composition
假设我已经手动定义了一些这样的代码：
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。我一直在考虑结构统一，但我提出以下问题：
- OCaml 在声明
let h x = g (f x) 时会自动执行这种统一吗？
- 如果没有，是否存在可以在 OCaml 中实现的通用算法，以便
compile 进入所需 h 的 ml 文件？
提前致谢
对于旧版本的 OCaml，这还不确定。
但是，如果您激活 flambda optimization，您可以非常确定您将从这种优化中获益。
请注意，在构建编译器时必须激活 flambda（如果使用 opam，则有一个专用开关）。您的编译时间可能有点长，但完全值得。
如果您想确保它会被内联（并因此得到简化），您可以在函数声明中使用 [@@inline always] 属性或在函数调用中使用 [@@inlined always]。
免责声明
我不是 OCaml 编译器开发人员。如果您想获得他们的意见，那么最好在邮件列表中联系他们。
第 1 部分
理论上，现代 OCaml（我已经尝试使用 4.0{3,4}+flambda）能够消除一些类型为 test2 的中间数据结构。但是，要实现这一点，您需要传递特殊的优化选项，并将 [@@inlined always] 添加到函数 f，否则即使使用 -inline 10000 和 -inline-toplevel 10000 等疯狂的内联选项，它也不会内联.
但是，在一般情况下，对于更大的函数，这可能不起作用。在这里，我想，您展示的示例只是一个玩具示例，在现实生活中，您面临着更大的功能和两个以上的组合（即数百个构造函数和数百个组合），否则，它根本不值得对此进行优化）。
第 2 部分
理论
说到通用算法，如果我们太挑剔，那是不可能的，至于模式匹配中->右边可以是任何OCaml表达式，即图灵完备程序。所以，我们有一个等效的决策问题。即使我们通过禁止循环和副作用来限制表达式语言，问题仍然是 NP-hard，因此可能不值得尝试解决它。然而，如果我们进一步限制自己，通过禁止除具有微不足道操作数的构造函数应用程序之外的任何表达式，那么我们实际上将编码一个有限状态机 (FSM)。有很多定义明确的 FSM 优化和状态最小化算法，因此从中删除冗余并不难。
练习
实际上，我可能不会编写将 ml 代码转换为 ml 代码的函数。根据我的实际任务，我会考虑以下方法。
可枚举的输入集
如果类型 test 中的值集实际上是有限的（即，如果它适合 OCaml 数组），那么我会尝试编写一个函数来枚举类型 [=] 的所有可能值22=]，存储合成结果。您可以使用 [@@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 是 [= 类型的构造函数的数量22=]。从大 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 的语义。语义规则的巧妙应用是所有优化的目的。所以，这意味着，如果您对解释器的性能不满意，那么您需要编写自己的优化编译器。首先，您需要设计执行查询的抽象机器，然后编写针对该机器的优化器。
假设我已经手动定义了一些这样的代码：
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。我一直在考虑结构统一，但我提出以下问题：
- OCaml 在声明
let h x = g (f x)时会自动执行这种统一吗？ - 如果没有，是否存在可以在 OCaml 中实现的通用算法，以便
compile进入所需 h 的 ml 文件？
提前致谢
对于旧版本的 OCaml，这还不确定。
但是，如果您激活 flambda optimization，您可以非常确定您将从这种优化中获益。
请注意，在构建编译器时必须激活 flambda（如果使用 opam，则有一个专用开关）。您的编译时间可能有点长，但完全值得。
如果您想确保它会被内联（并因此得到简化），您可以在函数声明中使用 [@@inline always] 属性或在函数调用中使用 [@@inlined always]。
免责声明
我不是 OCaml 编译器开发人员。如果您想获得他们的意见，那么最好在邮件列表中联系他们。
第 1 部分
理论上，现代 OCaml（我已经尝试使用 4.0{3,4}+flambda）能够消除一些类型为 test2 的中间数据结构。但是，要实现这一点，您需要传递特殊的优化选项，并将 [@@inlined always] 添加到函数 f，否则即使使用 -inline 10000 和 -inline-toplevel 10000 等疯狂的内联选项，它也不会内联.
但是，在一般情况下，对于更大的函数，这可能不起作用。在这里，我想，您展示的示例只是一个玩具示例，在现实生活中，您面临着更大的功能和两个以上的组合（即数百个构造函数和数百个组合），否则，它根本不值得对此进行优化）。
第 2 部分
理论
说到通用算法，如果我们太挑剔，那是不可能的，至于模式匹配中->右边可以是任何OCaml表达式，即图灵完备程序。所以，我们有一个等效的决策问题。即使我们通过禁止循环和副作用来限制表达式语言，问题仍然是 NP-hard，因此可能不值得尝试解决它。然而，如果我们进一步限制自己，通过禁止除具有微不足道操作数的构造函数应用程序之外的任何表达式，那么我们实际上将编码一个有限状态机 (FSM)。有很多定义明确的 FSM 优化和状态最小化算法，因此从中删除冗余并不难。
练习
实际上，我可能不会编写将 ml 代码转换为 ml 代码的函数。根据我的实际任务，我会考虑以下方法。
可枚举的输入集
如果类型 test 中的值集实际上是有限的（即，如果它适合 OCaml 数组），那么我会尝试编写一个函数来枚举类型 [=] 的所有可能值22=]，存储合成结果。您可以使用 [@@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 是 [= 类型的构造函数的数量22=]。从大 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 的语义。语义规则的巧妙应用是所有优化的目的。所以，这意味着，如果您对解释器的性能不满意，那么您需要编写自己的优化编译器。首先，您需要设计执行查询的抽象机器，然后编写针对该机器的优化器。