是否有任何类型推理系统适用于所有情况



是否有任何类型推断算法可以始终(或几乎始终(推断正确的类型?我知道Hindley-Milner算法在很多情况下都能做到这一点,但并不是所有情况(即,更高级别的多态类型(。

您的问题并没有完全提出,因为"所有案例"的集合并没有完全定义好。

例如,您提到了更高级别的多态类型,作为Hindley-Milner类型推理不能总是推断正确类型的情况,这是真的,除了有一些语言,如标准ML和Haskell,使用Hindley-Millner类型推理,并且不具有更高级别多态类型。事实上,Hindley–Milner算法在Hindley-Milner型系统涵盖的所有情况下都有效;也就是说,Hindley-Milner系统完全允许Hindley-Millner类型推理算法推断出的类型,因此该系统中永远不需要显式类型注释。

当然,出于实用的原因,使用Hindley-Milner的真实世界语言通常会以各种方式扩展系统,其中一些扩展会导致算法无法覆盖的情况。(例如,标准ML有一些内置的重载标识符,如+ : real * real -> real+ : int * int -> int,这意味着程序员有时需要使用显式类型注释来选择正确的重载。(但这是一个设计决策,而不是必要的;我注意到,无论如何,你的问题中都没有提到任何现实世界中的语言。

但从你的问题来看,你似乎想要至少所有的Hindley–Milner加上更高级别的多态类型。这意味着您需要至少所有的系统F,多态lambda演算。已知系统F中的类型推理是不可判定的。这意味着你的问题的答案是"否":没有任何类型推理算法可以推断出你想要的所有案例的正确类型。

相关内容

最新更新