Welchen Teil von Hindley-Milner haben Sie nicht verstanden?

Question

I schwören Früher gab es eine T-shirt mit den unsterblichen Worten zu verkaufen:

---

Welcher Teil von

Haben Sie pas verstehen?

---

In meinem Fall wäre die Antwort... alles!

Vor allem in Haskell-Papieren sehe ich oft solche Notationen, aber ich habe keine Ahnung, was sie bedeuten. Ich habe keine Ahnung, um welchen Zweig der Mathematik es sich handeln soll.

Ich erkenne natürlich die Buchstaben des griechischen Alphabets und Symbole wie "" (was normalerweise bedeutet, dass etwas kein Element einer Menge ist).

Andererseits habe ich "" noch nie gesehen ( Wikipedia behauptet, es könnte "Teilung" bedeuten ). Auch die Verwendung des Vinculums ist mir hier nicht geläufig. (Normalerweise bezeichnet es einen Bruch, aber das tut es nicht erscheinen hier der Fall ist).

Wenn mir jemand wenigstens sagen könnte, wo ich anfangen soll zu suchen, um zu verstehen, was dieses Meer von Symbolen bedeutet, wäre das sehr hilfreich.

Answer 1

• のことです。 Reckstange bedeutet, dass "[oben] impliziert [unten]".
• Wenn es mehrere Ausdrücke in [oben], dann betrachten sie anded zusammen; alle [oben] müssen wahr sein, um die [unten] zu gewährleisten.
• : bedeutet hat Typ
• bedeutet ist in . (Gleichermaßen bedeutet "ist nicht da").
• wird in der Regel verwendet, um auf eine Umwelt oder Kontext; in diesem Fall kann man es sich als eine Reihe von Typ-Anmerkungen vorstellen, die einen Bezeichner mit seinem Typ verbinden. Daher x : bedeutet, dass die Umwelt beinhaltet die Tatsache, dass x hat Typ .
• kann gelesen werden als beweist oder bestimmt. x : bedeutet, dass die Umwelt stellt fest, dass x hat Typ .
• , ist ein Weg zur einschließlich spezifische zusätzliche Annahmen in einer Umgebung .
  Deshalb, , x : e : ' bedeutet, dass die Umwelt , mit der zusätzlichen, übergeordneten Annahme, dass x hat Typ beweist, dass e hat Typ ' .

---

Wie gewünscht: Vorrang der Bediener, vom höchsten zum niedrigsten:

• Sprachspezifische Infix- und Mixfix-Operatoren, wie z. B. x . e , . et ' , let x = e0 in e1 und Leerzeichen für die Anwendung von Funktionen.

• :

• et

• , (links-assoziativ)

• Leerzeichen zur Trennung mehrerer Sätze (assoziativ)

• die horizontale Leiste

Answer 2

Diese Syntax sieht zwar kompliziert aus, ist aber eigentlich recht einfach. Die Grundidee stammt aus der formalen Logik: Der gesamte Ausdruck ist eine Implikation, wobei die obere Hälfte die Annahmen und die untere Hälfte das Ergebnis darstellt. Das heißt, wenn man weiß, dass die oberen Ausdrücke wahr sind, kann man schließen, dass die unteren Ausdrücke ebenfalls wahr sind.

Symbole

Außerdem haben einige Buchstaben eine traditionelle Bedeutung, die insbesondere den "Kontext" repräsentiert, in dem Sie sich befinden, d. h. die Art der anderen Dinge, die Sie gesehen haben. Also etwas wie ... bedeutet "der Ausdruck ... wenn Sie die Typen jedes Ausdrucks in .

のことです。 Symbol bedeutet im Wesentlichen, dass Sie etwas beweisen können. Also ... ist eine Aussage, die besagt: "Ich kann beweisen ... in einem Kontext . Diese Aussagen werden auch als Typenurteile bezeichnet.

Und noch etwas ist zu bedenken: In der Mathematik, genau wie in ML und Scala, x : bedeutet, dass x hat Typ . Sie können es genauso lesen wie Haskells x :: .

Was jede Regel bedeutet

Wenn wir dies wissen, wird der erste Ausdruck leicht verständlich: Wenn wir wissen, dass x : (d.h., x hat eine Art in irgendeinem Zusammenhang ), dann wissen wir, dass x : (das heißt, in , x hat Typ ). Das sagt Ihnen also nichts wirklich Interessantes; es sagt Ihnen nur, wie Sie Ihren Kontext nutzen können.

Auch die anderen Regeln sind einfach. Nehmen Sie zum Beispiel [App] . Diese Regel hat zwei Bedingungen: e ist eine Funktion von irgendeinem Typ zu irgendeiner Art ' et e ist ein Wert des Typs . Jetzt wissen Sie, welchen Typ Sie bekommen, wenn Sie sich bewerben e まで e ! Hoffentlich ist das keine Überraschung :).

Die nächste Regel enthält eine weitere neue Syntax. Insbesondere, , x : bedeutet lediglich, dass der Kontext, der aus und das Urteil x : . Wenn wir also wissen, dass die Variable x hat einen Typ von und der Ausdruck e hat einen Typ ' kennen wir auch den Typ einer Funktion, die x und gibt zurück e . Dies sagt uns nur, was zu tun ist, wenn wir herausgefunden haben, welchen Typ eine Funktion annimmt und welchen Typ sie zurückgibt, also sollte es auch nicht überraschend sein.

Die nächste sagt Ihnen nur, wie Sie mit let Erklärungen. Wenn Sie wissen, dass ein Ausdruck e hat einen Typ so lange wie x hat einen Typ , dann a let Ausdruck, der lokal bindet x auf einen Wert des Typs wird machen e haben einen Typ . Dies zeigt Ihnen nur, dass eine let-Anweisung im Wesentlichen die Möglichkeit bietet, den Kontext um eine neue Bindung zu erweitern - was genau das ist, was let tut!

のことです。 [Inst] Regel befasst sich mit der Sub-Typisierung. Sie besagt, dass wenn Sie einen Wert vom Typ ' und ist ein Subtyp von ( eine partielle Ordnungsbeziehung darstellt), dann ist dieser Ausdruck également vom Typ .

Die endgültige Regel behandelt die Verallgemeinerung von Typen. Ein kurzer Hinweis am Rande: eine freie Variable ist eine Variable, die nicht durch eine let-Anweisung oder ein Lambda innerhalb eines Ausdrucks eingeführt wird; dieser Ausdruck hängt nun von dem Wert der freien Variable aus seinem Kontext ab.Die Regel besagt, dass wenn es eine Variable das ist pas "frei" in irgendetwas in Ihrem Kontext, dann ist es sicher zu sagen, dass jeder Ausdruck, dessen Typ Sie kennen e : hat diesen Typ für tous Wert von .

Wie man die Regeln benutzt

Nun, da Sie die Symbole verstanden haben, was machen Sie mit diesen Regeln? Nun, Sie können diese Regeln verwenden, um den Typ verschiedener Werte herauszufinden. Betrachten Sie dazu Ihren Ausdruck (z. B. f x y ) und finden Sie eine Regel, deren Schlussfolgerung (der untere Teil) mit Ihrer Aussage übereinstimmt. Nennen wir die Sache, die Sie zu finden versuchen, Ihr "Ziel". In diesem Fall würden Sie sich die Regel ansehen, die auf e e . Wenn Sie diese gefunden haben, müssen Sie nun Regeln finden, die alles oberhalb der Linie dieser Regel beweisen. Diese Dinge entsprechen im Allgemeinen den Typen von Unterausdrücken, so dass man im Wesentlichen auf Teile des Ausdrucks zurückgreift. Das machst du so lange, bis du deinen Beweisbaum fertig hast, der dir einen Beweis für den Typ deines Ausdrucks liefert.

Diese Regeln geben also nur genau - und in der üblichen mathematisch pedantischen Ausführlichkeit :P - an, wie die Typen der Ausdrücke zu ermitteln sind.

Dies sollte Ihnen bekannt vorkommen, wenn Sie schon einmal Prolog benutzt haben - Sie berechnen den Beweisbaum im Wesentlichen wie ein menschlicher Prolog-Interpreter. Es gibt einen Grund, warum Prolog "logische Programmierung" genannt wird! Das ist auch deshalb wichtig, weil der erste Weg, auf dem ich in den H-M Inferenzalgorithmus eingeführt wurde, darin bestand, ihn in Prolog zu implementieren. Das ist eigentlich erstaunlich einfach und macht deutlich, was vor sich geht. Sie sollten es auf jeden Fall ausprobieren.

Hinweis: Wahrscheinlich sind mir in dieser Erklärung einige Fehler unterlaufen, und ich würde mich freuen, wenn mich jemand darauf hinweisen würde. Ich werde das Thema in ein paar Wochen im Unterricht behandeln, dann werde ich sicherer sein :P.

Answer 3

wenn mir wenigstens jemand sagen könnte, wo ich anfangen soll zu suchen, um zu verstehen, was dieses Meer von Symbolen bedeutet

Siehe " Praktische Grundlagen der Programmiersprachen. ", Kapitel 2 und 3, über den Stil der Logik durch Urteile und Ableitungen. Das gesamte Buch ist jetzt auf Amazon erhältlich.

Kapitel 2

Induktive Definitionen

Induktive Definitionen sind ein unverzichtbares Hilfsmittel bei der Untersuchung von Programmiersprachen. In diesem Kapitel werden wir den grundlegenden Rahmen induktiver Definitionen entwickeln und einige Beispiele für ihre Verwendung geben. Eine induktive Definition besteht aus einer Menge von Regeln zur Ableitung Urteile , oder Behauptungen mit einer Vielzahl von Formen. Urteile sind Aussagen über ein oder mehrere syntaktische Objekte einer bestimmten Art. Die Regeln legen notwendige und hinreichende Bedingungen für die Gültigkeit eines Urteils fest und bestimmen damit vollständig seine Bedeutung.

2.1 Urteile

Wir beginnen mit dem Begriff der Urteil , oder Behauptung über ein syntaktisches Objekt. Wir werden viele Formen der Beurteilung verwenden, darunter auch Beispiele wie diese:

• n nat - n ist eine natürliche Zahl
• n \= n1 + n2 - n ist die Summe aus n1 et n2
• Typ - ist ein Typ
• e : - Ausdruck e hat Typ
• e v - Ausdruck e hat Wert v

Ein Urteil besagt, dass ein oder mehrere syntaktische Objekte eine Eigenschaft haben oder in einer bestimmten Beziehung zueinander stehen. Die Eigenschaft oder Beziehung selbst wird als Urteilsformular und das Urteil, dass ein Objekt oder mehrere Objekte diese Eigenschaft haben oder in dieser Beziehung stehen, wird als eine Instanz dieses Urteilsformulars. Ein Urteilsformular wird auch als Prädikat und die Objekte, die eine Instanz bilden, sind ihre Themen . Wir schreiben a J für das Urteil mit der Begründung, dass J hält von a . Wenn es nicht wichtig ist, den Gegenstand des Urteils hervorzuheben, (Text wird hier abgeschnitten)

Answer 4

Wie verstehe ich die Hindley-Milner-Regeln?

Hindley-Milner ist ein Satz von Regeln in Form von Folgerechnung (nicht natürliche Deduktion), die zeigt, dass wir den (allgemeinsten) Typ eines Programms aus der Konstruktion des Programms ohne explizite Typendeklarationen ableiten können.

Die Symbole und die Notation

Erläutern wir zunächst die Symbole und den Vorrang der Operatoren

• ist ein Bezeichner (informell: ein Variablenname).

• : bedeutet ist ein Typ von (informell: ein Fall von oder "ist-a").

• (sigma) ist ein Ausdruck, der entweder eine Variable oder eine Funktion ist.

• also : wird gelesen " ist ein "

• bedeutet "ist ein Element von".

• (Gamma) ist eine Umgebung.

• (das Behauptungszeichen) bedeutet behauptet (oder beweist, aber im Kontext liest sich "behauptet" besser.)

• : lautet also " behauptet, dass , ist-ein "

• ist eine tatsächliche Instanz (Element) des Typs .

• (tau) ist ein Typ: entweder grundlegend, variabel ( ), funktional ' oder Produkt ×' (Produkt wird hier nicht verwendet)

• ' ist ein funktioneller Typ, bei dem et ' sind potenziell verschiedene Typen.

• . bedeutet (lambda) ist eine anonyme Funktion, die ein Argument annimmt, und gibt einen Ausdruck zurück, .

• lassen Sie \= in bedeutet im Ausdruck, , Ersatz wo immer erscheint.

• bedeutet, dass das vorherige Element ein Subtyp (informell - Unterklasse) des letzteren Elements ist.

• ist eine Typvariable.

• . ist ein Typ, (für alle) Argumentvariablen, und kehrt zurück ひょうげん

• free() bedeutet, dass es sich nicht um ein Element der im äußeren Kontext definierten Variablen des freien Typs handelt. (Gebundene Variablen sind substituierbar.)

Alles oberhalb der Linie ist die Prämisse, alles unterhalb ist die Schlussfolgerung ( Per Martin-Löf )

Präzedenzfall, zum Beispiel

Ich habe einige der komplexeren Beispiele aus den Regeln genommen und überflüssige Klammern eingefügt, die den Vorrang anzeigen:

• : könnte geschrieben werden ( : )

• : geschrieben werden könnte ( : )

• lassen Sie \= in : ist gleichbedeutend mit (( lassen Sie ( \= ) in ) : )

• . : ' gleichbedeutend ist (( . ) : ( ' ))

Die großen Abstände zwischen den Aussagen der Behauptung und den anderen Voraussetzungen weisen auf eine Reihe solcher Voraussetzungen hin, und die horizontale Linie, die die Prämisse von der Schlussfolgerung trennt, bildet schließlich das Ende der Rangfolge.

Die Regeln

Es folgen englische Auslegungen der Regeln, jeweils gefolgt von einer lockeren Umformulierung und einer Erläuterung.

Variabel

Gegeben ist ein Typ von (sigma), ein Element von (Gamma),
schließen behauptet, ist ein .

Anders ausgedrückt, in , wissen wir, dass es vom Typ ist, weil es vom Typ in ist.

Dies ist im Grunde eine Tautologie. Ein Bezeichnername ist eine Variable oder eine Funktion.

Funktion Anwendung

Da asserts ein funktionaler Typ ist und asserts eine
folgert, dass die Anwendung der Funktion to ein Typ ' ist

Um die Regel neu zu formulieren, wissen wir, dass die Funktion application den Typ ' zurückgibt, weil die Funktion den Typ ' hat und ein Argument des Typs erhält.

Das heißt, wenn wir wissen, dass eine Funktion einen Typ zurückgibt, und wir sie auf ein Argument anwenden, wird das Ergebnis eine Instanz des Typs sein, von dem wir wissen, dass er zurückgegeben wird.

Funktion Abstraktion

Gegeben und vom Typ asserts ist ein Typ, '
conclude behauptet, dass eine anonyme Funktion, die einen Ausdruck zurückgibt, vom Typ ' ist.

Wenn wir eine Funktion sehen, die einen Ausdruck annimmt und zurückgibt, wissen wir, dass sie vom Typ ' ist, weil (a ) behauptet, dass sie ein ' ist.

Wenn wir wissen, dass is vom Typ ist und somit ein Ausdruck vom Typ ' ist, dann ist eine Funktion, die den Ausdruck zurückgibt, vom Typ '.

Variable Deklaration zulassen

Gegeben sind Behauptungen , vom Typ , und und , vom Typ , behauptet vom Typ
folgern behauptet let = in vom Typ

Locker gesagt, ist in (a ) gebunden, weil is a , und is a behauptet, dass is a .

Das heißt, wenn wir einen Ausdruck haben, der a ist (eine Variable oder eine Funktion), und einen Namen, , auch ein , und einen Ausdruck vom Typ , dann können wir für ersetzen, wo immer er innerhalb von erscheint.

Instanziierung

Bei Asserts vom Typ ' und ' ist ein Subtyp von
conclude asserts ist vom Typ

Ein Ausdruck, ist von übergeordnetem Typ, weil der Ausdruck vom Subtyp ' ist und der übergeordnete Typ von ' ist.

Wenn eine Instanz von einem Typ ist, der ein Subtyp eines anderen Typs ist, dann ist sie auch eine Instanz dieses Supertyps - des allgemeineren Typs.

Verallgemeinerung

Gegeben ist ein Assert und ist kein Element der freien Variablen von ,
conclude asserts , type für alle Argumentausdrücke, die einen Ausdruck zurückgeben

So ist im Allgemeinen für alle Argumentvariablen (), die zurückkehren, typisiert, weil wir wissen, dass ist ein und ist keine freie Variable.

Das bedeutet, dass wir ein Programm so verallgemeinern können, dass es alle Typen für Argumente akzeptiert, die nicht bereits im enthaltenden Bereich gebunden sind (Variablen, die nicht lokal sind). Diese gebundenen Variablen sind ersetzbar.

Alles zusammenfügen

Unter bestimmten Annahmen (z. B. keine freien/undefinierten Variablen, eine bekannte Umgebung, ) kennen wir die Typen von:

• atomare Elemente unserer Programme (Variable),
• Werte, die von Funktionen zurückgegeben werden (Function Application),
• funktionale Konstrukte (Funktionsabstraktion),
• let-Bindungen (Let-Variablen-Deklarationen),
• übergeordnete Typen von Instanzen (Instanziierung), und
• alle Ausdrücke (Generalisierung).

Schlussfolgerung

Die Kombination dieser Regeln ermöglicht es uns, den allgemeinsten Typ eines behaupteten Programms zu beweisen, ohne dass Typ-Annotationen erforderlich sind.

Answer 5

Die Schreibweise stammt von natürliche Ableitung .

heißt das Symbol Drehkreuz .

Die 6 Regeln sind sehr einfach.

Var Regel ist ziemlich trivial - sie besagt, dass, wenn der Typ für den Bezeichner bereits in Ihrer Typumgebung vorhanden ist, Sie den Typ einfach aus der Umgebung ableiten.

App Regel besagt, dass, wenn Sie zwei Bezeichner haben e0 et e1 und ihre Typen ableiten können, dann können Sie auf den Typ der Anwendung schließen e0 e1 . Die Regel lautet wie folgt, wenn Sie wissen, dass e0 :: t0 -> t1 et e1 :: t0 (das gleiche t0!), dann ist die Anwendung wohlgetippt und der Typ ist t1 .

Abs et Let sind Regeln zur Ableitung von Typen für Lambda-Abstraktion und let-in.

Inst Regel besagt, dass Sie einen Typ durch einen weniger allgemeinen Typ ersetzen können.