广义 HM 与高阶统一

Question

据我所知，在 Hindley-Milner 类型系统中使用的统一可以通过在构造函数位置允许类型变量并在这种情况下放宽元数约束来推广以统一更高类型的类型：

f a ~ T a1 b1
f ~ T a1 -- generatifity + partial application
a ~ b1   -- injectivity

我猜也涉及种类，但我不知道如何。

根据我的经验，我认为这足以实现更高级类型的合理统一。与高阶统一的主要区别可能是

广义的HM是可判定的，HOU不是一般的
广义 HM 受到更多限制，即拒绝在 HOU

虽然我以某种方式回答了我的问题，高阶统一给了我们什么，但我不知道应用高阶统一时涉及哪些（简化的）规则。该算法与广义 HM 有何不同？

Answer 1

这不是我真正的驾驶室，但我也许可以提供一个非常笼统的答案。

根本区别在于广义 HM 将统一视为旨在产生唯一匹配的纯句法匹配过程，而 HOU 算法涉及 types/kinds 的语义考虑（如 terms/types类型化的 lambda 演算）和通过可能统一的树进行系统搜索，包括考虑内部节点的替代统一。

（HM方法的局限性是因为对于一阶类型，纯句法匹配基本上等同于类型的语义考虑和通过可能的统一进行系统搜索。）

无论如何，进行一个简单的高阶统一：

Either String Int ~ f String

您提出的广义 HM 算法在此统一上失败，原因是 Either's arguments are in the wrong order, a purely syntactic detail that has nothing to do with the types' 语义统一性。您可以进一步概括您的算法以在句法上处理这种特殊情况，但总会有一些其他不符合句法模式的琐碎统一。您还会在统一时遇到奇怪的“不连续性”：

Either String String ~ f String

您可以让您的算法对具有统一性的程序进行类型检查：

Either Int String ~ f Int
Either String String ~ f String
 ==> f x = Either x String

或：

Either String Int ~ f Int
Either String String ~ f String
 ==> f x = Either String x

但大概不会两者兼而有之。

相比之下，任何自尊的 HOU 算法都可以毫不费力地对这些程序进行类型检查。

基于 Huet 算法的 HOU 算法通过构建“匹配树”来实现。树中的每个节点都标有“分歧集”（基本上是一组未解决的统一），分支上标有备选替换。终端节点表示统一的“成功”或“失败”。

Huet 论文中的示例 3.2 是统一的：

f x A ~ B

任何广义的 HM 都会立即放弃，因为类型 B 属于 *，无法在语法上与涉及 f :: * -> * -> *.[=24 的类型表达式统一=]

对于类似 Huet 的算法，匹配树是在根节点上用这个单例不一致集构造的，在其分支上用三个可能的种类正确替换 f：

f :: * -> * -> *
f u v = u
f u v = v
f u v = B

给树：

                        f x A ~ B
                             |
        --------------------------------------------
        | (f u v = u)        | (f u v = v)         | (f u v = B)
        |                    |                     |
      x ~ B              Failure                 Success
        |
        | (x = B)
        |
      Success

如果您稍微考虑一下，您会发现通用 HM 类型检查器与 HOU 检查器的功能甚至无法相提并论。您还会看到，在实践中，HOU 类型检查器可能是一种程序员可能难以控制的强大功能。关于可以推断 f x = Either x String 或 f x = Either String x.

的类型检查器可能有点难以推理

广义 HM 与高阶统一

Generalized HM vs. Higher-Order Unification

haskell

functional-programming

unification

hindley-milner

higher-order-types