什么是辛德利·米尔纳?

辛德利·米尔纳是 类型系统 由罗杰·辛德利(研究逻辑)和罗宾·米尔纳(研究编程语言)独立发现。辛德利·米尔纳的优势在于

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

• 有时函数或值可以 多种类型 ,如在length函数的例子中:它可以是“整数到整数的列表”、“字符串到整数的列表”、“对到整数的列表”等等。在这种情况下,Hindley-Milner系统的一个信号优势是 每个类型良好的术语都有一个独特的“最佳”类型 ,即 主型 . list-length函数的主要类型是“for any” a ,列表中的函数 一 “整数”。在这里 一 是所谓的“类型参数”,即 lambda微积分中的显式 但是 在大多数编程语言中是隐式的 . 类型参数的使用解释了为什么Hindley Milner是一个实现 参数化 多态性 . (如果用ml编写长度函数的定义,则可以看到类型参数:

   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 )

许多其他基于类型化函数语言的次要语言和工具使用HindleyMilner。

辛德利·米尔纳是 System F ,允许更多类型,但是 需要程序员的注释 .

你可以使用谷歌学者或者城市学者——或者你当地的大学图书馆——找到原始的论文。第一本已经足够大了,你可能需要找到这本杂志的装订本,我在网上找不到。我为另一个找到的链接已断开,但可能还有其他链接。你一定能找到引用这些的文件。

辛德利,罗杰J, 组合逻辑中对象的主类型方案 , 1969年美国数学学会汇刊。

米尔纳,罗宾, 类型多态性理论 ,计算机与系统科学杂志,1978年。

C中简单的Hindley-Milner类型推断实现:

Hindley-Milner type inference over (Lisp-ish) S-expressions, in under 650 lines of C#

注意,实现仅在大约270行C的范围内(对于算法w proper和支持它的少数数据结构,无论如何)。

用法摘录:

    // ...

    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 ( ( f g ) => ( ( x ) => ( f ( g x ) ) ) ) ) // composition

                    ( factorial ( ( n ) => ( if ( > n 0 ) ( * n ( factorial ( - n 1 ) ) ) 1 ) ) )

                    // More interesting..
                    ( fmap (
                        ( f l ) =>
                        ( 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 H-M
    // (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's JavaScript implementation 在BitBucket上,这也有助于开始(为我工作)。

'Hth'