Wie können SML -Abschlussarten solche Typen schließen?

Question

Wikipedia sagt:

fun factorial n = 
    if n = 0 then 1 else n * factorial (n-1) 

Ein Standard -ML -Compiler ist erforderlich, um den statischen Typ int -> int dieser Funktion ohne benutzerversorgte Typanmerkungen zu schließen. Dh es muss ableiten, dass N nur mit ganzzahligen Ausdrücken verwendet wird und daher selbst eine Ganzzahl sein muss und dass alle Wertschöpfungsausdrücke innerhalb der Funktionsrückgabezahlen.

Ich verstehe nicht, wie ein Compiler dies schließen könnte. Es klingt so, als würde SML im Wesentlichen das Stoppproblem für das lösen factorial Funktion und zeigen, dass es nur bei positiven Ganzzahleingaben anhält.

Vermisse ich etwas?

Answer 1

Der klassische Hindley-Milner-Inferenzalgorithmus vom Typ Hindley-Milner erfordert, dass jeder wörtliche Wert eindeutig zu einem Typ schließt: 0 ist ein int, während 0.0 ist ein real. Haskells Typsystem wurde erweitert, um eine bestimmte Art von begrenztem Polymorphismus einzuschließen, so dass 0 kann jede Art haben, die eine Zahl ist (genauer Num Typ Klasse: 0 ist vom Typ Num a => a).

Siehe das Wikipedia-Artikel über Hindley-Milner Für weitere Einzelheiten zum Algorithmus (die Artikelerklärungen sind viel besser als alles, was ich zu diesem Thema schreiben könnte).

Answer 2

Ich denke, es ist wichtig zu erkennen, was der Typ $ mathtt {int rightarrow int} $ bedeutet und nicht.

Es tut nicht bedeuten, dass ein Programm P mit diesem Typ eine Ganzzahl zurückgeben muss, entgegen dem, was das ursprüngliche Poster sagte. Stattdessen bedeutet esWenn P zu einer bestimmten Eingabe (vom Typ int) endet, endet P durch Rückgabe einer Ganzzahl. Auf diese Weise ist das Störungsproblem kein Problem.

Darüber hinaus garantiert sich gut an, dass Programme auch bei Nicht-Beendigung keine Fehlern mit Laufzeittyp erleiden.

Das ursprüngliche Milner -Damas -Papier Haupttypscheme für Funktionsprogramme ist sehr lesbar. Mit 6 Seiten ist es auch kurz.

Schließlich ist es sehr lehrreich und nicht viel Aufwand, einen Typ-Inferencer für eine Spielzeugsprache zu implementieren. Ich empfehle dies, um wirklich zu verstehen, wie Typen in Programmiersprachen funktionieren.

Answer 3

Das Arbeiten mit Typen ist nicht so "hart" wie mit Werten in Bezug auf die Berechnung. Sie können statisch wissen, dass eine Funktion a zurückgibt bool ohne statisch zu wissen, dass es zurückkehren wird true, zum Beispiel. Darüber hinaus ist es durchaus möglich und manchmal trivial leicht zu beweisen, dass a spezifisch gegeben Funktion hält mit einer bestimmten Eingabe an, dies ist jedoch ein anderes Problem als ein allgemeiner Algorithmus zu schreiben, der bestimmt, ob oder nicht irgendein Eine andere angegebene Funktion hält eine Eingabe an.

Lassen Sie mich in Bezug auf die Funktionsweise von Typ -Inferenz einige Quellen empfehlen, die helfen können:

1. Vereinigung auf Wikipedia
2. Geben Sie Inferenz ein auf Wikipedia
3. Typen und Programmiersprachen von Benjamin C. Pierce (insbesondere Kapitel 22)
4. Hindley-Milner-Methode auf Wikipedia.

Der Typ -Inferenz -Algorithmus findet im Wesentlichen in zwei Phasen statt: Einschränkungsgenerierung und Vereinigung. Während der Beschränkungsgenerierung wird das AST des Programms durchquert und eine Reihe von Typbeschränkungen erzeugt.

Wenn beispielsweise irgendwo im Programm der Anwendungsausdruck vorliegt myfun (3), Der Inferenzalgorithmus könnte schließen, dass die Art von myfun ist $ tt {int} rightarrow alpha $. Wenn in einem anderen Teil des Programms der Ausdruck 4 + myfun(y) wird angetroffen, die Einschränkung, die myfun Hat Typ $ Beta rightarrow tt {int} $ wird generiert. Während des Vereinigungsschritts werden solche Einschränkungen (erfolgreich oder erfolglos) einheitlich sein. In dieser Phase könnte der Satz von Einschränkungen enthalten sein

• $ tt {myfun}: tt {int} rightarrow alpha $
• $ tt {myfun}: beta rightarrow tt {int} $
• $ tt {y}: tt {int} $
• $ tt {y}: beta $

Aus diesem Satz (wirklich System) von Einschränkungen könnten wir schließen, dass $ alpha = tt {int} $ und $ beta = tt {int} $, und alles wäre konsistent und das Programm würde eingeben. Es ist jedoch möglich, dass die Vereinigung fehlschlägt, je nachdem, was sich noch in den Einschränkungen befindet.