什么是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,