137

Hindley-Milnerという用語に出会いましたが、その意味を理解しているかどうかはわかりません。

次の投稿を読みました。

しかし、通常、簡潔な説明を提供してくれるウィキペディアには、この用語の単一のエントリはありません。
注- 1 つ追加されました

それは何ですか？
それを実装または使用する言語とツールは何ですか?
簡潔な答えを教えてください。

4

3 に答える 3

178

Hindley-Milner は、Roger Hindley (ロジックを研究していた) によって独自に発見され、後に Robin Milner (プログラミング言語を研究していた) によって発見された型システムです。Hindley-Milner の利点は次のとおりです。

  • ポリモーフィック関数をサポートしています。たとえば、要素のタイプに関係なくリストの長さを取得できる関数や、ツリーに格納されているキーのタイプに関係なくバイナリ ツリーのルックアップを行う関数などです。

  • 関数または値は、長さ関数の例のように、複数の typeを持つ場合があります。「整数から整数へのリスト」、「文字列から整数へのリスト」、「整数へのペアのリスト」などです。の上。この場合、Hindley-Milner システムの信号上の利点は、適切に型付けされた各用語が、プリンシパル型と呼ばれる一意の「最適な」型を持っていることです。リスト長関数の主なタイプは、「リストから整数までの任意の関数」です。これはいわゆる「型パラメーター」で、ラムダ計算では明示的ですが、ほとんどのプログラミング言語では暗黙的です。aaaパラメトリックポリモーフィズム。(長さ関数の定義を ML で記述した場合、型パラメーターは次のように表示されます。

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

  • 項が Hindley-Milner 型の場合、型宣言やプログラマによるその他の注釈を必要とせずに、プリンシパル型を推測できます。(注釈なしで大量の ML コードを処理したことがある人なら誰でも証言できるので、これは賛否両論です。)

Hindley-Milner は、ほぼすべての静的に型付けされた関数型言語の型システムの基礎となっています。一般的に使用される言語には、次のものがあります。

これらの言語はすべて Hindley-Milner を拡張しています。Haskell、Clean、および Objective Caml は、野心的で珍しい方法でこれを行います。(変更可能な変数を扱うには拡張機能が必要です。基本的な Hindley-Milner は、たとえば、型が指定されていない値のリストを保持する変更可能なセルを使用して覆すことができるためです。このような問題は、値制限と呼ばれる拡張機能によって処理されます。)

型付き関数型言語に基づく他の多くのマイナーな言語やツールは Hindley-Milner を使用しています。

Hindley-Milner はSystem Fの制限であり、より多くの型を許可しますが、プログラマによる注釈が必要です。

于 2008-12-30T02:34:42.780 に答える
12

元の論文は、Google Scholar や CiteSeer、または地元の大学の図書館で見つけることができる場合があります。最初のものは雑誌の製本されたコピーを見つけなければならないほど古いもので、私はそれをオンラインで見つけることができませんでした. 私が見つけた他のものへのリンクは壊れていましたが、他にもあるかもしれません。これらを引用している論文を確実に見つけることができます。

Hindley、Roger J、組み合わせ論理におけるオブジェクトのプリンシパル型スキーム、アメリカ数学会のトランザクション、1969 年。

Milner、Robin、A Theory of Type Polymorphism、Journal of Computer and System Sciences、1978。

于 2008-12-30T02:12:26.223 に答える
6

C# での単純な Hindley-Milner 型推論の実装:

C# の 650 行未満での (Lisp っぽい) S 式に対する Hindley-Milner 型推論

実装は、C# のわずか 270 行ほどの範囲にあることに注意してください (アルゴリズム W が適切であり、それをサポートするためのデータ構造が少ないため)。

使用法の抜粋:

    // ...

    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 のbitbucket での JavaScript 実装も参照してください。

'HTH、

于 2012-07-04T04:53:12.373 に答える