Что такое Хиндли-Милнер?

Я столкнулся с этим термином Хиндли-Милнер , и я не уверен, что понимаю, что он означает.

Я прочитал следующие сообщения:

• Стив Йегге - Динамические языки наносят ответный удар
• Стив Егге - Проблема Пиноккио
• Дэниел Спивак - Что такое Хиндли-Милнер? (а почему это круто?)

Но для этого термина нет единой записи в Википедии, где обычно предлагается краткое объяснение.
^{Примечание - теперь добавлен один}

Что это?
Какие языки и инструменты его реализуют или используют?
Не могли бы вы дать краткий ответ?

Хиндли-Милнер - это система типов, открытая независимо Роджером Хиндли (который занимался логикой), а затем Робином Милнером (который занимался языками программирования). Преимущества Хиндли-Милнера:

• Поддерживает полиморфные функции; например, функция, которая может дать вам длину списка независимо от типа элементов, или функция выполняет поиск в двоичном дереве независимо от типа ключей, хранящихся в дереве.

• Иногда функция или значение могут иметь более одного типа , как в примере функции длины: это может быть «список целых чисел в целое число», «список строк в целое число», «список пар в целое число» и т. Д. на. В этом случае сигнальное преимущество системы Хиндли-Милнера состоит в том, что каждый хорошо типизированный термин имеет уникальный «лучший» тип , который называется основным типом . Основной тип функции длины списка - «для любой a, функция от списка aдо целого числа». Вот aтак называемый «параметр типа», который явным образом используется в лямбда-исчислении, но неявен в большинстве языков программирования .параметрический полиморфизм . (Если вы напишете определение функции длины в ML, вы увидите параметр типа следующим образом:

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

• Если термин имеет тип Хиндли-Милнера, то основной тип может быть выведен, не требуя от программиста каких-либо объявлений типа или других аннотаций. (Это смешанное благословение, поскольку любой может подтвердить, что когда-либо работал с большим фрагментом кода ML без аннотаций.)

Хиндли-Милнер является основой системы типов почти каждого статически типизированного функционального языка. К таким широко используемым языкам относятся:

• Семейство машинного обучения ( Standard ML и Objective Caml )
• Haskell
• чистый

Все эти языки расширили Хиндли-Милнера; Haskell, Clean и Objective Caml делают это амбициозными и необычными способами. (Расширения требуются для работы с изменяемыми переменными, поскольку базовый Хиндли-Милнер может быть изменен, используя, например, изменяемую ячейку, содержащую список значений неопределенного типа. Такие проблемы решаются с помощью расширения, называемого ограничением значений .)

Многие другие второстепенные языки и инструменты, основанные на типизированных функциональных языках, используют Hindley-Milner.

Hindley-Milner - это ограничение Системы F , которое допускает больше типов, но требует от программиста аннотаций .

Вы можете найти оригинальные статьи с помощью Google Scholar или CiteSeer или библиотеки вашего местного университета. Первый достаточно старый, и вам, возможно, придется найти переплетенные копии журнала, я не смог найти его в Интернете. Ссылка, которую я нашел для другого, не работает, но могут быть и другие. Вы обязательно найдете статьи, в которых они цитируются.

Хиндли, Роджер Дж, Схема основного типа объекта в комбинаторной логике , Труды Американского математического общества, 1969.

Милнер, Робин, Теория полиморфизма типов , Журнал компьютерных и системных наук, 1978.

Простая реализация вывода типа Хиндли-Милнера в C #:

Вывод типа Хиндли-Милнера над (Lisp-ish) S-выражениями в менее чем 650 строках C #

Обратите внимание, что реализация находится в диапазоне примерно 270 строк C # (во всяком случае, для собственно алгоритма 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.

См. Также реализацию JavaScript Брайана МакКенны на bitbucket, которая также помогает начать работу (сработала для меня).

«НТН,