Typinferenz

Typinferenz rekonstruiert automatisch die Typen von Ausdrücken, wodurch Programmierer Annotationen weglassen können, während der Compiler eine möglichst allgemeine Typisierung berechnet.

Definition

Typinferenz (Typrekonstruktion) ist der Prozess, einen gültigen und allgemeinsten Typ für einen Ausdruck aus seiner Struktur und Verwendung abzuleiten, ohne dass der Programmierer alle Typannotationen angeben muss.

Scope

Dieses Thema behandelt Algorithmen und Theorien zur Inferenz von Typen ohne explizite Annotationen, wobei der Schwerpunkt auf dem Hindley-Milner-System und Algorithmus W mit seiner Verwendung von Unifikation und Let-Polymorphie liegt. Es befasst sich mit Haupttypen, Entscheidbarkeit und Komplexität sowie den Schwierigkeiten, die Inferenz auf reichere Systeme mit Subtyping, Polymorphie höherer Ordnung oder abhängigen Typen auszudehnen.

Core questions

• Wie kann ein Compiler Typen rekonstruieren, wenn keine aufgeschrieben sind?
• Was ist ein Haupttyp, und wann existiert immer einer?
• Wie treibt die Unifikation die Hindley-Milner-Inferenz an?
• Warum wird die Inferenz in reicheren Typsystemen unentscheidbar oder unvollständig?

Key theories

Hindley-Milner-Typinferenz

Milners polymorphe Typdisziplin, mit Algorithmus W, inferiert Typen für einen Lambda-Kalkül mit Let-gebundener Polymorphie unter Verwendung von Unifikation und bildet die Grundlage der Inferenz in Sprachen der ML-Familie.

Haupttypschemata

Damas und Milner bewiesen, dass jeder typisierbare Ausdruck ein Haupttypschema besitzt, den allgemeinsten Typ, von dem alle seine gültigen Typen Instanzen sind, und dass Algorithmus W diesen berechnet.

Haupttypen in der kombinatorischen Logik

Hindley etablierte die Existenz von Haupttypen für typisierbare Terme, ein vorhergehendes Ergebnis, das der späteren Typinferenz in Programmiersprachen zugrunde liegt.

Clinical relevance

Typinferenz macht statisch typisierte Sprachen wesentlich komfortabler, indem sie den Annotationsaufwand reduziert, während die Sicherheit erhalten bleibt, und sie treibt moderne Editorfunktionen wie Typ-Hints und Autovervollständigung an. Ihre Grenzen in expressiven Systemen bestimmen, wo Programmierer weiterhin Annotationen angeben müssen.

History

Hindley's Arbeit von 1969 über Haupttypen in der kombinatorischen Logik nahm die praktische Inferenz vorweg. Milners Arbeit von 1978 führte das polymorphe Typsystem und Algorithmus W für ML ein, und Damas und Milners Arbeit von 1982 bewies die Prinzipalität. Das Hindley-Milner-System wurde zum Standard für ML, Haskell und viele spätere Sprachen, wobei die Forschung die Inferenz auf reichere Umgebungen ausdehnt.

Debates

Wie viel inferieren versus annotieren

Wenn Typsysteme ausdrucksstärker werden, wird die vollständige Inferenz unentscheidbar, was zu Debatten darüber führt, wie viel automatisch inferiert werden sollte im Vergleich zu expliziten Annotationen, um die Inferenz handhabbar und vorhersehbar zu halten.

Key figures

• Robin Milner
• Luis Damas
• Roger Hindley
• Benjamin Pierce

Seminal works

• milner1978
• damas1982
• hindley1969
• pierce2002

Frequently asked questions

Was ist ein Haupttyp?

Ein Haupttyp ist der allgemeinste Typ eines Ausdrucks, so dass jeder andere gültige Typ für diesen Ausdruck eine Substitutionsinstanz davon ist; die Hindley-Milner-Inferenz berechnet immer einen Haupttyp, wenn einer existiert.

Warum können nicht alle Typsysteme Typen automatisch inferieren?

Die Inferenz basiert auf lösbaren Beschränkungen; in expressiven Systemen wie solchen mit höherrangigen oder abhängigen Typen wird die vollständige Inferenz unentscheidbar, so dass einige Annotationen vom Programmierer bereitgestellt werden müssen.