Frage

Ich begegnete diesem Begriff Hindley-Milner, und ich bin mir nicht sicher, ob begreifen, was es bedeutet.

Ich habe Lesen Sie die folgenden Beiträge:

Aber es gibt keinen einzigen Eintrag für diesen Begriff in wikipedia, wo in der Regel bietet mir eine präzise Erklärung.
Hinweis - man hat erweitert

Was ist es?
Welche Sprachen und tools implementieren oder zu verwenden es?
Würden Sie bitte bieten eine schlüssige Antwort?

War es hilfreich?

Lösung

Hindley-Milner ist ein Typ system entdeckte unabhängig von Roger Hindley (wer sucht in der Logik) und später von Robin Milner (wer sucht bei Programmiersprachen).Die Vorteile von Hindley-Milner sind

  • Es unterstützt polymorph Funktionen;für Beispiel, eine Funktion, die können geben Sie die Länge der Liste unabhängig von der Art der Elemente, oder eine Funktion führt eine binäre-Baum-lookup-unabhängig von der Art der gespeicherten Schlüssel in den Baum.

  • Manchmal ist eine Funktion oder den Wert haben kann mehr als eine Art, wie in dem Beispiel der Länge Funktion:es kann sein, "Liste von Integer-zahlen integer", "Liste von strings zu integer", "Liste von Paaren an integer", und so weiter.In diesem Fall ein signal Vorteil des Hindley-Milner-system ist, dass jedes eingegebene Begriff hat eine eindeutige "beste" Typ, das heißt AUFTRAGGEBER Typ.Der AUFTRAGGEBER Typ der Liste-Funktion " length "für alle a, eine Funktion aus der Liste der a integer".Hier a ist eine sogenannte "parameter " Typ"," die explizite lambda-Kalkül aber implizite, in den meisten Programmiersprachen.Die Verwendung von Typ-Parametern erklärt, warum Hindley-Milner-ist ein system, dass implementiert parametric Polymorphismus.(Wenn Sie schreiben, eine definition der Länge-Funktion in ML, können Sie sehen die parameter type, so:

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

  • Wenn ein Begriff hat eine Hindley-Milner-Typ, dann der AUFTRAGGEBER Typ abgeleitet werden kann, ohne dass ein Typ-Deklarationen oder andere Anmerkungen, die durch den Programmierer.(Dies ist ein gemischter Segen, wie jeder bestätigen kann, der schon einmal behandelt ein großes Stück der ML-code, ohne Anmerkungen.)

Hindley-Milner-ist die basis für den Typ system von fast jedem statisch typisierte, funktionale Sprache.Solche Sprachen in common use include

Alle diese Sprachen haben erweiterte Hindley-Milner;Haskell, Clean, and Objective Caml tun ehrgeizig und ungewöhnliche Wege.(Erweiterungen sind erforderlich, um deal mit veränderlichen Variablen, da grundlegende Hindley-Milner kann untergraben werden, die z.B. eine veränderbare Zelle, halten Sie eine Liste der Werte von unspezifischen Typ.Solche Probleme behandelt werden, die durch eine Erweiterung namens die Wert Beschränkung.)

Viele andere kleinere Sprachen und tools basierend auf typisierte, funktionale Sprachen verwenden Hindley-Milner.

Hindley-Milner-ist eine Beschränkung der System F,, das ermöglicht es, mehr Arten, aber die erfordert Anmerkungen, die durch den Programmierer.

Andere Tipps

Sie können in der Lage sein zu finden die original Papiere mit Google Scholar oder CiteSeer-oder Ihre lokale university library.Das erste ist alt genug, dass Sie können haben zu finden und gebundenen Exemplare der Zeitschrift, konnte ich nicht finden es online.Der link, den ich gefunden habe, für die andere war gebrochen, aber es könnte andere geben.Sie werden sicherlich in der Lage sein zu finden die Papiere, die citiere.

Hindley, Roger J, Der AUFTRAGGEBER Typ Schema eines Objekts in kombinatorischer Logik, Transactions of the American Mathematical Society, 1969.

Milner, Robin, A Theory of Type Polymorphism, Journal of Computer and System Sciences, 1978.

Einfache Hindley-Milner type inference Implementierung in C# :

Hindley-Milner type inference over (Lisp-ish) S,-Ausdrücke, in weniger als 650 Zeilen C#

Hinweis: die Umsetzung ist im Bereich von nur 270 oder so Zeilen von C# (für den Algorithmus W richtigen und die wenigen Daten, Strukturen zu unterstützen, sowieso).

Verwendung Auszug:

    // ...

    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);

    // ...

...das ergibt:

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.

Siehe auch Brian McKenna ' s JavaScript implementation auf bitbucket, die auch hilft, um begonnen zu erhalten (funktioniert für mich).

'HTH,

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top