什么是Hindley-Milner？
我遇到了Hindley-Milner这个名词，我不确定是否掌握了它的意思。
我读过以下post：
- Steve Yegge – dynamic语言反击
- Steve Yegge – 木偶奇遇记问题
- Daniel Spiewak – 什么是Hindley-Milner？ （为什么它很酷？）
但是这个词在维基百科上没有单一的条目，通常给我一个简明的解释。
注 – 现在已经添加了一个
它是什么？
哪些语言和工具实现或使用它？
你能提供一个简洁的答案吗？
Hindley-Milner是由Roger Hindley（他正在研究逻辑）和Robin Milner（他正在研究编程语言）独立发现的一个types系统 。 Hindley-Milner的优点是
-
它支持多态function; 例如，一个函数可以给你列表的长度，而不依赖于元素的types，或者一个函数执行二叉树查找，而不pipe存储在树中的键的types如何。
-
有时函数或值可以有多个types ，如长度函数的例子：它可以是“整数列表整数”，“列表整数”，“对整数列表”等等上。 在这种情况下，Hindley-Milner系统的信号优势是每个井型的项目都有一个独特的“最好”的types ，称为主体types 。 列表长度函数的主要types是“对于从
a到整数的列表中a任何函数”。 这里是一个所谓的“types参数”，它在lambda演算中是明确的，但在大多数编程语言中是隐含的 。 types参数的使用解释了为什么Hindley-Milner是一个实现参数多态的系统。 （如果在ML中写入长度函数的定义，则可以看到types参数：fun 'a length [] = 0 | 'a length (x::xs) = 1 + length xs -
如果一个术语具有Hindley-Milnertypes，那么可以推断出主体types，而不需要程序员的任何types声明或其他注释。 （这是一个混合的祝福，因为任何人都可以certificate谁曾经处理了大量的ML代码，没有注释。）
Hindley-Milner是几乎所有静态types语言的types系统的基础。 这些常用的语言包括
- ML系列（ 标准ML和目标Caml ）
- 哈斯克尔
- 清洁
所有这些语言都扩展了Hindley-Milner; Haskell，Clean和Objective Caml以雄心勃勃的和不寻常的方式来做这件事。 （需要扩展来处理可变variables，因为基本的Hindley-Milner可以被颠覆，例如，一个可变单元格包含一个未指定types的值列表，这样的问题由一个称为值限制的扩展来处理。
许多其他基于typesfunction语言的小语言和工具使用Hindley-Milner。
Hindley-Milner是System F的一个限制，允许更多的types，但是需要程序员注释 。
您可以使用Google Scholar或CiteSeer或您当地的大学图书馆查找原始论文。 第一个已经够老了，你可能不得不find该日记的装订副本，我无法在网上find它。 我为另一个人find的链接被打破了，但也可能有别的链接。 你一定能find引用这些的论文。
Hindley，Roger J， “组合逻辑中对象的主要typesscheme” ，美国math学会会志，1969年。
米尔纳，罗宾， types多态性理论 ，计算机与系统科学学报，1978年。
简单的Hindley-Milnertypes推理在C＃中的实现：
（Lisp-ish）Sexpression式的Hindley-Milnertypes推断，在650行以下的C＃
请注意，实现仅在C＃的270行左右的范围内（对于algorithmW本身以及less数数据结构来支持它）。
用法摘录：
// ... var syntax = new SExpressionSyntax(). Include ( // Not-quite-Lisp-indeed; just tolen from our host, C#, as-is SExpressionSyntax.Token("\\/\\/.*", SExpressionSyntax.Commenting), SExpressionSyntax.Token("false", (token, match) => false), SExpressionSyntax.Token("true", (token, match) => true), SExpressionSyntax.Token("null", (token, match) => null), // Integers (unsigned) SExpressionSyntax.Token("[0-9]+", (token, match) => int.Parse(match)), // String literals SExpressionSyntax.Token("\\\"(\\\\\\n|\\\\t|\\\\n|\\\\r|\\\\\\\"|[^\\\"])*\\\"", (token, match) => match.Substring(1, match.Length - 2)), // For identifiers... SExpressionSyntax.Token("[\\$_A-Za-z][\\$_0-9A-Za-z\\-]*", SExpressionSyntax.NewSymbol), // ... and such SExpressionSyntax.Token("[\\!\\&\\|\\<\\=\\>\\+\\-\\*\\/\\%\\:]+", SExpressionSyntax.NewSymbol) ); var system = TypeSystem.Default; var env = new Dictionary<string, IType>(); // Classic var @bool = system.NewType(typeof(bool).Name); var @int = system.NewType(typeof(int).Name); var @string = system.NewType(typeof(string).Name); // Generic list of some `item' type : List<item> var ItemType = system.NewGeneric(); var ListType = system.NewType("List", new[] { ItemType }); // Populate the top level typing environment (aka, the language's "builtins") env[@bool.Id] = @bool; env[@int.Id] = @int; env[@string.Id] = @string; env[ListType.Id] = env["nil"] = ListType; //... Action<object> analyze = (ast) => { var nodes = (Node[])visitSExpr(ast); foreach (var node in nodes) { try { Console.WriteLine(); Console.WriteLine("{0} : {1}", node.Id, system.Infer(env, node)); } catch (Exception ex) { Console.WriteLine(ex.Message); } } Console.WriteLine(); Console.WriteLine("... Done."); }; // Parse some S-expr (in string representation) var source = syntax. Parse (@" ( let ( // Type inference ""playground"" // Classic.. ( id ( ( x ) => x ) ) // identity ( o ( ( fg ) => ( ( x ) => ( f ( gx ) ) ) ) ) // composition ( factorial ( ( n ) => ( if ( > n 0 ) ( * n ( factorial ( - n 1 ) ) ) 1 ) ) ) // More interesting.. ( fmap ( ( fl ) => ( if ( empty l ) ( : ( f ( head l ) ) ( fmap f ( tail l ) ) ) nil ) ) ) // your own... ) ( ) ) "); // Visit the parsed S-expr, turn it into a more friendly AST for HM // (see Node, et al, above) and infer some types from the latter analyze(source); // ...
…产生：
id : Function<`u, `u> o : Function<Function<`z, `aa>, Function<`y, `z>, Function<`y, `aa>> factorial : Function<Int32, Int32> fmap : Function<Function<`au, `ax>, List<`au>, List<`ax>> ... Done.
另请参阅Brian McKenna在bitbucket上的JavaScript实现 ，这也有助于开始（为我工作）。
“HTH，
