具有约束的内联记录构造函数的存在类型

Question

我试图在 OCaml 中表示一组语法产生式，存在类型对于建模语法规则的语义动作非常有用。我一直在研究 Menhir 源代码，存在类型也用于建模语义操作。考虑以下因素：

type 'a 'b production = { name: string; rule: 'a expr; action: 'a -> 'b }

一个产品有一个名字，一个规则 returns 'a 和一个接收 'a 和 returns 'b 的动作。简单参数类型的问题是产生式列表根本不可能是多态的，所以我可以在同一个列表中有一个 string_of_float 和另一个 string_of_int 的动作；这是一个可以通过明确 Ɐ 解决的常见问题，例如，操作可以是：

action: 'a 'b. 'a -> 'b

但我还需要有一个基于expr参数的约束，其中action的'a统一为expr的'a，所以，只要我们可以在代数数据类型中拥有内联记录构造函数，我们也应该能够在广义代数数据类型中拥有它们，对吗？

type production = (* Ɐ a. b. *)
  | Production: { name: string; rule: 'a expr; action: 'a -> 'b } -> production

但这不是有效的表格。我现在找到的解决方案是使规则也具有操作类型，例如：

type 'a expr =
  | Terminal of string * ('a -> 'a)
  | Sequence of 'a expr list * ('a list -> 'a)

但是这种单态还是有很大的局限性。我如何在具有共享约束的记录中对存在类型进行建模，这样我就可以在不同的产品中使用不同的 return 类型，在这些产品中仍然可以对应用程序进行编译时检查（通过详尽的模式匹配）？

使用相同的逻辑，如果我想要 'a 'b. -> 'a -> 'b 中的函数列表，我是否需要使用存在类型构造函数来做到这一点（如 [string_of_int; string_of_float]）？

我相信我需要某种类型的限制（它们都是 * -> *），但我来自 Haskell，但仍然不知道如何在 OCaml 中做到这一点。

Answer 1

我不确定你想要什么。假设有一个函数'a expr -> 'a，如果你想要一个包含不同内部表达式的产生式列表，你可以将产生式定义为

type 'r production = 
 | P: { name: string; rule: 'a expr; action: 'a -> 'r } -> 'r production

那么您可以获得 [P string_of_float; P string_of_int] 的列表，同时仍然知道操作的结果类型。（此外，您之前的定义是有效的。）

其他通用量化让我觉得有问题：类型为 ∀'a∀'b. 'a -> 'b 的唯一函数是

的变体

let fail _ = assert false

类似地，存在量化return类型的动作意味着你永远无法恢复关于这个return类型是什么的信息，换句话说，它和只有动作一样有用类型 'a -> unit.

Answer 2

生产规则的语义动作应该有一些效果，否则根本不需要动作。您可以使用某种状态 monad 或直接在 OCaml 中对这种效果进行编码，即，作为可变引用或直接 I/O。

在你的例子中，存在

type production = (* Ɐ a. b. *)
  | Production: { name: string; rule: 'a expr; action: 'a -> 'b } -> production

具有生成 'b 类型值的效果。这直接与存在主义的定义相矛盾，因为在这种情况下 b 需要逃避上下文。所以正确的定义是

type production = (* Ɐ a. *)
  | Production: { name: string; rule: 'a expr; action: 'a -> unit }

或者，如果您愿意使用一些 monad，那么您需要将 monad 构造函数放在前段位置

type 'm production = (* Ɐ a. *)
  | Production: { name: string; rule: 'a expr; action: 'a -> 'm }

或在模块级别绑定：

type 'a m = ...
type production = (* Ɐ a. *)
  | Production: { name: string; rule: 'a expr; action: 'a -> unit m }

您可以使用新操作扩展您的存在性，前提是它们不会泄漏存在性量化类型变量。

事实上，您可能只使用 first-class 个模块，因为它们 have existential type。例如，

module type Semantics = sig 
   type t 
   val action : t -> unit
   val rule : t expr
end

type production = (module Semantics)

最后一点，考虑将 Oleg Kiselyov' tagless embedding 作为 GADT 表示的替代方法。请记住，解析器只是一个解释器:)

具有约束的内联记录构造函数的存在类型

Existential types for inline record constructors with constraints

polymorphism

ocaml

type-systems

gadt

existential-type