Hindley-Milner는 무엇입니까?

StackOverflow https://stackoverflow.com/questions/399312

문제

나는이 용어를 만났다 Hindley-Milner, 그리고 그것이 의미하는 바를 이해하는지 확실하지 않습니다.

다음 게시물을 읽었습니다.

그러나 위키 백과에는이 용어에 대한 단일 항목이 없으며, 여기서 보통 간결한 설명을 제공합니다.
메모 - 하나가 있습니다 이제 추가되었습니다

무엇입니까?
어떤 언어와 도구를 구현하거나 사용합니까?
간결한 답변을 제공해 주시겠습니까?

도움이 되었습니까?

해결책

Hindley-Milner는 a입니다 유형 시스템 Roger Hindley (논리를보고 있던)와 나중에 Robin Milner (프로그래밍 언어를보고있는)가 독립적으로 발견했습니다. Hindley-Milner의 장점은입니다

  • 지원합니다 다형성 기능; 예를 들어, 요소 유형과 무관하게 목록의 길이를 제공 할 수있는 함수 또는 함수는 트리에 저장된 키 유형과 독립적 인 이진 트리 조회를 수행합니다.

  • 때로는 기능이나 값이 가질 수 있습니다 둘 이상의 유형, 길이 함수의 예에서와 같이 : "정수의 정수 목록", "정수 목록 목록", "정수 목록 목록"등이 될 수 있습니다. 이 경우 Hindley-Milner 시스템의 신호 이점은 각각의 잘 갖춘 용어에는 고유 한 "최고의"유형이 있습니다.,이를 불러옵니다 주요 유형. 목록 길이 함수의 주요 유형은 " a, 목록에서 기능 a 정수 ". 여기 a 소위 "유형 매개 변수"입니다. 람다 미적분학에 명시 적 하지만 대부분의 프로그래밍 언어에 내재되어 있습니다. 유형 매개 변수의 사용은 Hindley-Milner가 왜 구현되는 시스템인지 설명합니다. 파라 메트릭 다형성. (ML에서 길이 함수의 정의를 작성하면 다음 유형 매개 변수를 볼 수 있습니다.

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

  • 만약에 용어에는 Hindley-Milner 유형이 있습니다 주요 유형은 유형 선언없이 추론 할 수 있습니다. 또는 프로그래머의 다른 주석. (이것은 주석없이 많은 ML 코드를 처리 한 사람을 증명할 수 있기 때문에 혼합 된 축복입니다.)

Hindley-Milner는 거의 모든 정적으로 입력 한 기능 언어의 유형 시스템의 기초입니다. 공통적 인 언어에는 다음이 포함됩니다

이 모든 언어들은 힌 들리-밀더를 확장했습니다. Haskell, Clean 및 Objective Caml은 야심적이고 특이한 방식으로 그렇게합니다. (예를 들어, 기본적인 힌 들리-밀더는 지정되지 않은 유형의 값 목록을 보유하는 변이성 셀을 사용하여 전복 될 수 있기 때문에 변수 변수를 처리해야합니다. 이러한 문제는 가치 제한.)

타이핑 된 기능 언어를 기반으로 한 다른 많은 사소한 언어 및 도구는 Hindley-Milner를 사용합니다.

Hindley-Milner는 제한입니다 시스템 f, 더 많은 유형을 허용하지만이를 허용합니다 프로그래머의 주석이 필요합니다.

다른 팁

Google Scholar 또는 Citeseer 또는 지역 대학 도서관을 사용하여 원본 논문을 찾을 수 있습니다. 첫 번째는 저널의 한계 사본을 찾아야 할만 큼 나이가 많았습니다. 온라인으로 찾을 수 없었습니다. 내가 다른 하나에 대해 찾은 링크는 깨졌지만 다른 것들이있을 수 있습니다. 당신은 확실히 이것을 인용하는 논문을 찾을 수있을 것입니다.

Hindley, Roger J, 조합 논리에서 객체의 주요 유형 체계, 1969 년 미국 수학 학회의 거래.

밀너, 로빈, 유형 다형성 이론, 컴퓨터 및 시스템 과학 저널, 1978.

C#의 간단한 Hindley-Milner 유형 추론 구현 :

650 줄의 C#에서 (LISP-ish) 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의 JavaScript 구현 Bitbucket에서 시작하는 데 도움이됩니다 (나를 위해 일했습니다).

'hth,

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top