Beschreiben Sie die Damas-Milner Typinferenz in einer Weise, dass ein CS101 Schüler verstehen

Question

Hindley-Milner ist eine Art System, das die Grundlage der Typsysteme von vielen bekannten funktionalen Programmiersprachen ist. Damas-Milner ist ein Algorithmus, der (folgert?) Folgert Typen in einem Hindley-Milner-Typ-System.

Wikipedia gibt eine Beschreibung des Algorithmus, der als soweit ich das beurteilen kann, beläuft sich auf ein einziges Wort: „Vereinigung“ Ist das alles, was es ist? Wenn ja, das bedeutet, dass der interessante Teil der Typ-System selbst ist nicht der Typ-Inferenz-System.

Wenn Damas-Milner mehr als Vereinigung ist, würde ich eine Beschreibung von Damas-Milner mag, die ein einfaches Beispiel enthält und idealerweise einen Code.

Auch dieser Algorithmus oft gesagt, Typinferenz zu tun. Ist es wirklich ein Inferenz-System? Ich dachte, es war nur die Typen herzuleiten.

Verwandte Fragen:

• Was ist Hindley Miller?
• Typ-Inferenz auf Unifikationsproblem

Answer 1

Damas Milner ist nur eine strukturierte Nutzung der Vereinigung.

Wenn es in einen Lambda-Ausdruck recurses macht es einen neuen Variablennamen auf. Wenn Sie in einer Unterperiode, diese Variable in einer Weise verwendet finden, die eine bestimmte Art erfordern würde, zeichnet er die Vereinigung dieser Variablen und dieses Typs. Wenn es jemals zwei Arten zu vereinen versucht, die keinen Sinn machen würde man sagen, dass eine einzelne Variable sowohl eine Int und eine Funktion von einem -.> B, dann schreit es bei Ihnen für etwas Schlechtes tun

  

Auch dieser Algorithmus oft gesagt, Typinferenz zu tun. Ist es wirklich ein Inferenz-System? Ich dachte, es war nur die Typen herzuleiten.

die Typen Ableiten ist Inferenz eingeben. dass Typenannotationen gelten für einen bestimmten Begriff zu sehen, ist die Überprüfung Überprüfung geben. Sie sind verschiedene Probleme.

  

Wenn ja, das bedeutet, dass der interessante Teil der Typ-System selbst ist nicht der Typ-Inferenz-System.

Es wird allgemein behauptet, dass Hindley-Milner-Stil Typ Systeme auf einem Höcker ausgeglichen sind. Wenn Sie viel mehr Funktionalität hinzufügen, wird es unmöglich, die Typen zu schließen. So Systemerweiterungen ein, die Sie auf einem Hindley-Milner-Stil Typ-System ohne sie zu zerstören seine Folgerung Eigenschaften sind wirklich die interessantesten Teile der modernen funktionalen Sprachen Schicht kann. In einigen Fällen Typinferenz und Typprüfung, zum Beispiel in Haskell viele moderne Erweiterungen kann nicht abgeleitet werden, sondern kann überprüft werden, so dass sie erfordern Typenannotationen für erweiterte Funktionen, wie polymorphe Rekursion.

, wir mischen

Answer 2

  

Wikipedia gibt eine Beschreibung des Algorithmus, der, soweit ich das beurteilen kann, auf ein einzelnes Wort beträgt: „Vereinigung“ Ist das alles, was es ist? Wenn ja, das bedeutet, dass der interessante Teil der Typ-System selbst ist nicht der Typ-Inferenz-System.

IIRC, der interessante Teil des Damas-Milner Typinferenz Algorithmus W ist, dass es die allgemeinsten Typen möglich folgert.