¿Cuál es Hindley-Milner?

https://stackoverflow.com/questions/399312

29-08-2019
|

Pregunta

Me encontré con este término Hindley-Milner , y no estoy seguro de si comprender lo que significa.

He leído los siguientes mensajes:

Steve Yegge - dinámico Idiomas Strike Back
Steve Yegge - El Pinocho Problema
Daniel Spiewak - Lo es Hindley-Milner? (Y por qué es que se enfríe?)

Sin embargo, no hay una ventanilla única de este término en Wikipedia, donde por lo general me ofrece una explicación concisa.
^{Nota: - uno tiene ahora ha agregado}

¿Qué es?
¿Qué lenguajes y herramientas de implementar o usarlo?
¿Por favor ofrecer una respuesta concisa?

Solución

Hindley-Milner es un sistema de tipo descubierto independientemente por Roger Hindley (que estaba mirando a la lógica) y más tarde por Robin Milner (que estaba mirando a los lenguajes de programación). Las ventajas de Hindley-Milner son

Es compatible polimórficas funciones; por ejemplo, una función que se le dará la longitud de la lista independiente del tipo de los elementos, o una función funciona un árbol binario de búsqueda independiente del tipo de claves almacenadas en el árbol.
A veces una función o valor puede tener más de un tipo , como en el ejemplo de la función de longitud: puede ser "lista de números enteros a entero", "lista de cadenas a número entero", 'lista de pares a entero', y así sucesivamente. En este caso, una ventaja de la señal del sistema de Hindley-Milner es que cada término bien escrito-tiene una "mejor" tipo único , que se denomina tipo principal . El tipo principal de la función de lista de longitud es "para cualquier a, funcionar de la lista de a a entero". Aquí a es el llamado "parámetro de tipo", que es explícito en el cálculo lambda y implícito en la mayoría de los lenguajes de programación . El uso de parámetros de tipo explica por qué Hindley-Milner es un sistema que implementa paramétrico polimorfismo . (Si se escribe una definición de la función de la longitud de ML, se puede ver el parámetro de tipo de este modo:
```
 fun 'a length []      = 0
   | 'a length (x::xs) = 1 + length xs
```
Si a término tiene un tipo Hindley-Milner, entonces el tipo principal puede inferirse sin necesidad de declaraciones de tipo u otras anotaciones por el programador. (Este es un arma de doble filo, ya que cualquiera puede dar fe de que alguna vez se ha manejado una gran parte del código de ML sin anotaciones.)

Hindley-Milner es la base para el sistema de tipo de lenguaje funcional casi todos los tipos estáticos. Tales lenguas en uso común incluyen

La familia ML ( ml estándar y Objetivo Caml )
Haskell
Limpio

Todos los idiomas han extendido Hindley-Milner; Haskell, limpio, y el Objetivo Caml lo hacen de forma ambiciosos e inusuales. (Se requieren extensiones para hacer frente a las variables mutables, desde básico Hindley-Milner puede ser subvertido usando, por ejemplo, una célula mutable la celebración de una lista de valores de tipo no especificado. Tales problemas son tratados por una extensión llama el restricción valor .)

Muchas otras lenguas menores y herramientas basadas en lenguajes funcionales mecanografiadas utilizan Hindley-Milner.

Hindley-Milner es una restricción de la System F , lo que permite más tipos pero que requiere anotaciones por el programador .

Otros consejos

Usted puede ser capaz de encontrar los documentos originales utilizando Google Académico o CiteSeer - o la biblioteca de la universidad local. La primera es bastante mayor que puede tener que encontrar ejemplares encuadernados de la revista, no pude encontrar en línea. El enlace que he encontrado para el otro estaba roto, pero puede haber otros. Que sin duda será capaz de encontrar los documentos que citan estos.

Hindley, Roger J, El esquema de tipo principal de un objeto en lógica combinatoria , Transacciones de la Sociedad Americana de Matemáticas, 1969.

Milner, Robin, Teoría de Tipo polimorfismo , Revista de Ciencias de Computación y Sistemas, 1978.

Simple Hindley-Milner aplicación inferencia de tipos en C #:

Hindley-Milner tipo inferencia sobre (Lisp-ish) S-expresiones, en menos de 650 líneas de C #

Tenga en cuenta la aplicación está en el rango de sólo 270 o menos líneas de C # (para el algoritmo W las pocas estructuras de datos adecuada y que lo soporte, de todos modos).

Uso extracto:

    // ...

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

    // ...

... lo que produce:

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.

aplicación JavaScript de rel="nofollow"> href="https://bitbucket.org/puffnfresh/js-type-inference/src" Brian McKenna en bitbucket, lo que también ayuda a conseguir Introducción (trabajado para mí).

'HTH,

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow