functional-programming - 什么是Hindley-Milner？

我遇到过这个学期的Hindley-Milner，我不确定是否理解它的含义。
我已阅读以下帖子:

Steve Yegge-Dynamic Languages Strike Back

Steve Yegge-The Pinocchio Problem

Daniel Spiewak-What is Hindley-Milner? (and why is it cool?)

但是维基百科中没有一个词条可以为您提供简要的解释。
注意-一个有now been added
它是什么？
哪些语言和工具实现或使用它？
您能提供一个简洁的答案吗？

最佳答案

Hindley-Milner是类型系统，由Roger Hindley(正在研究逻辑)和后来的Robin Milner(正在研究编程语言)分别发现。 Hindley-Milner的优点是

它支持多态函数；例如，一个函数可以为您提供列表的长度，而与元素的类型无关，或者一个函数可以与存储在树中的键的类型无关地进行二叉树查找。

有时，一个函数或值的可以具有多个类型，例如在length函数的示例中:它可以是“整数到整数列表”，“整数到字符串列表”，“整数对列表” ， 等等。在这种情况下，Hindley-Milner系统的信号优势是每个良好类型的术语都具有唯一的“最佳”类型，称为主体类型。列表长度函数的主要类型是“对于任何a，从a列表到整数的函数”。这里a是所谓的“类型参数”，在lambda演算中是显式的，但在大多数编程语言中是隐含的。类型参数的使用解释了为什么Hindley-Milner是一个实现参数多态性的系统。 (如果您在ML中编写了长度函数的定义，则可以看到type参数，因此:

 fun 'a length []      = 0
   | 'a length (x::xs) = 1 + length xs

如果术语具有Hindley-Milner类型，则可以推断主体类型，而无需程序员声明任何类型声明或其他注释。 (这是喜忧参半的事情，因为任何人都可以证明谁曾经处理过大块的ML代码且没有注释。)

Hindley-Milner是几乎所有静态类型化功能语言的类型系统的基础。此类常用语言包括

ML系列(Standard ML和Objective Caml)

Haskell

Clean

所有这些语言都扩展了Hindley-Milner。 Haskell，Clean和Objective Caml以雄心勃勃且与众不同的方式做到这一点。 (需要扩展来处理可变变量，因为基本的Hindley-Milner可以使用例如持有未指定类型值列表的可变单元来颠覆。此类问题由称为value restriction的扩展处理。)

许多其他次要语言和基于类型功能语言的工具都使用Hindley-Milner。

Hindley-Milner是System F的限制，它允许更多类型，但需要程序员进行注释。