Beziehung zwischen dem Typzuweisungssystem (TA) und dem Hindley-Milner-System

Vor kurzem habe ich mein Studium in Typentheorie / Typensystemen und Lambda-Kalkül begonnen.

Ich habe bereits über Simple Typed Lambda Calculus im Church- und Curry-Stil gelesen. Das letzte ist auch als Type Assignment System (TA) bekannt.

Ich denke über die Beziehungen zwischen TA und Hindley-Milner (HM) nach, dem System in Sprachen wie ML und Haskell.

Das Buch Lambda-Calculus and Combinators: An Introduction (Hindley) besagt, dass TA polymorph ist (S. 119). Ist das der gleiche Sinn für Polymorphismus in Systemen wie HM und System-F?

TA soll die starke Normalisierungseigenschaft haben, ist also nicht vollständig. Sprachen, die das HM-System verwenden, sind vollständig, zum Beispiel Haskell. Es muss also so sein, dass das HM-System es Begriffen wie der Endlosschleife erlaubt , einen Typ zu empfangen. Ist das richtig oder fehlt mir etwas? $\Omega$

Auf jeden Fall würde ich gerne die Beziehung zwischen TA und HM kennen.

type-theory type-checking type-inference Rafael Castro
quelle

Ich habe noch nie von einem Typed Assignment-System gehört. Ich habe es gegoogelt und diese Frage als dritte Antwort erhalten, was bedeutet, dass es eine Nische sein muss. Können Sie erklären, was es ist? Was ist eine "Endlosschleife"? Meinen Sie eine ununterbrochene Berechnung?

Gardenhead

Die Typzuweisung ist eine Version des von Curry erstellten einfachen typisierten Lambda-Kalküls. Sie sollten das im erwähnten Buch suchen. Und ja,

ist die Standard-Unendlichkeitsschleife

oder das nicht anhaltende Programm.

Ω

$\Omega$

λ

$\lambda$

Rafael Castro

Ich denke, ich sollte diese Frage in einem anderen eher theoretischen / mathematischen Stapelaustausch stellen. Sollte ich?

Rafael Castro

Du könntest es versuchen. Geben Sie cstheory und mathoverflow eine Chance. Sie sagten jedoch, Sie hätten "vor kurzem mit Ihrem Studium begonnen", daher wäre ich überrascht, wenn Ihre Frage so weit fortgeschritten wäre. Ich denke, Sie verwenden nur ungewöhnliche Begriffe, um einfache Konzepte zu beschreiben (könnte jedoch falsch sein). Zum Beispiel wird die Endlosschleife normalerweise als unterster Typ bezeichnet (wenn ich Sie richtig verstehe).

Gardenhead

Auf jeden Fall ist meine Frage nicht auf Forschungsniveau. Meine Frage lautet eher "Hey, ich verstehe diese grundlegenden Konzepte, oder?". Aber ich werde es versuchen, vielleicht bekomme ich eine Antwort.

Rafael Castro

Antworten:

System F und sein Subsystem HM haben einen Typbildner zur universellen Quantifizierung:

τ :: = \forall x . τ | . . .

$\tau \quad::=\quad \forall x.\tau \ |\ ...$

was das System in Hindley / Seldin nicht hat. Das ist der Hauptunterschied.

Jetzt hat System F keine entscheidbare Typinferenz mehr, und HM ist eine Möglichkeit, Typinferenz mit einigermaßen ausdrucksstarkem parametrischem Polymorphismus zu kombinieren. HM erreicht dies, indem es nur eine äußerste universelle Quantifizierung zulässt, dh alle Typen haben die Form

\forall x_{1} \forall x_{2} . . . \forall x_{n} . τ

$\forall x_1 \forall x_2 ... \forall x_n.\tau$

$\tau$ $n \geq 0$

Die Frage der starken Normalisierung ist orthogonal. System F und HM normalisieren sich stark, aber das kann leicht durch die Einführung von Fixpunktkombinatoren oder ähnlichem behoben werden. In den Hauptschemata für Funktionsprogramme von L. Damas und R. Milner heißt es sogar: " Zum Beispiel wird die Rekursion weggelassen, da sie durch einfaches Hinzufügen des polymorphen Festpunktoperators eingeführt werden kann ... " Die Einführung von Fixpunkten Das System Turing komplett zu machen, wirft unter dem Gesichtspunkt der Typinferenz keine Probleme auf.

Martin Berger
quelle

Wäre es richtig zu denken, HM = TA + "Let-Polymorphismus"? Das Buch Lambda-Calculus and Combinators (Hindley) sagte bisher nichts über die universelle Quantifizierung von Typen aus. TA verwendet Typvariablen, aber ich weiß nichts über den Bereich dieser Typen. Um klar zu sein, ich habe das HM-System noch nicht studiert, aber ich weiß, wofür es verwendet wird.

Rafael Castro

@RafaelCastro Wenn Sie schielen ... Wenn Sie einen CS-Hintergrund haben, ist Pierces TAPL-Buch wahrscheinlich eine viel zugänglichere Erklärung für HM und Tippsysteme im Allgemeinen. Das Damas / Milner-Papier, auf das ich verwiesen habe, ist sehr leicht zu lesen, wenn Sie über die altmodische Schriftsetzung hinaussehen können. Ich gebe es meinen beginnenden Doktoranden. Lesen Sie es! Hindley / Seldin ist ein bisschen formal.

Martin Berger

@ RafaelCastro Typvariablen erstrecken sich über Typen. Alle Arten. Aus diesem Grund ist System F nicht aussagekräftig.

Martin Berger

Vielen Dank. Ja, ich bin ein Student in CS, also werde ich Pierces TAPL-Buch ausprobieren.

Rafael Castro

@RafaelCastro Es gibt wahrscheinlich keinen besseren Weg, um etwas über Typen zu lernen, als TAPL zu lesen und die dort diskutierten Typisierungssysteme zu implementieren.

Martin Berger