Welche Forschungssprachen haben ein stärkeres Typensystem als Haskell und warum?

14

Hier lese ich das:

Haskell hat definitiv nicht das fortschrittlichste Typsystem (nicht einmal annähernd, wenn Sie die Forschungssprachen zählen), aber von allen Sprachen, die tatsächlich in der Produktion verwendet werden, ist Haskell wahrscheinlich an der Spitze.

Ich frage also zwei Dinge:

  1. Welche Forschungssprachen haben leistungsfähigere Typsysteme als Haskell?
  2. Was verbessern sie?

Ich bin nur ein Programmierer, daher kenne ich nicht viele mathematische Objekte, die in der Typentheorie verwendet werden. Geben Sie bitte sanfte Erklärungen, wenn Sie können.

Виталий Олегович
quelle
3
Was ist besser"?
David Richerby
2
@ David Richby Ich denke, das bedeutet leistungsstärker Typ System
Виталий Олегович
2
Wenn Sie bewiesen haben, dass ein Typensystem vollständig ist , spielt es dann wirklich eine Rolle? ;-)
DevSolar
7
Turing-Maschinen sind Turing-complete, warum nutzen Sie sie nicht für Ihre alltäglichen Programmieraufgaben?
Gallais
4
Beachten Sie, dass der Originaltext Sprachen mit fortgeschritteneren Typsystemen erwähnt und keine Aussagen darüber macht, ob "fortgeschrittener" für ein Typsystem besser oder schlechter ist.
Peteris

Antworten:

25

Die Frage ist etwas problematisch, da sie auf einer subjektiven Definition von "besser" beruht.

Abhängig getippte Sprachen wie Agda , Idris und Coq haben ein stärkeres Typensystem als Haskell. Das heißt, Sie können die Typen in diesen Sprachen verwenden, um streng mehr Eigenschaften Ihres Codes als in Haskell zu prüfen. Das heißt, es gibt mehr falsche Programme, die abgefangen werden.

Dies hat jedoch einen Preis: Eine Typinferenz und die Prüfung, ob Werte eines bestimmten Typs vorhanden sind, ist nicht mehr möglich. Dies bedeutet, dass Sie für diese Sprachen Ihren Code explizit mit Typen versehen müssen. Im Wesentlichen läuft dies darauf hinaus, Ihre eigenen Korrektheitsnachweise für Ihren Code zu schreiben.

Sind diese Sprachen "besser" als Haskell? Sie können erweiterte Korrektheitsnachweise für Ihren Code überprüfen, aber nicht automatisch die Eigenschaften Ihres Codes nachweisen, wie dies bei Haskell der Fall ist.

Eine andere Forschungssprache, die "besser" ist als Haskell, ist LiquidHaskell . Dies ist im Grunde Haskell mit aufgeschraubten Verfeinerungstypen, die anhand spezieller Kommentare analysiert wurden.

Mit Verfeinerungstypen können Sie Typen mit Eigenschaften verfeinern. Anstelle von a Intkönnen Sie beispielsweise {i : Int | i > 0}den Typ aller positiven Ganzzahlen angeben . Bei Verfeinerungstypen ist eine Typinferenz entscheidend, aber Sie können mit ihnen nicht annähernd so viele Korrektheitseigenschaften nachweisen wie mit abhängigen Typen.

Es gibt noch andere Verfeinerungssysteme, mit denen ich jedoch nicht besonders vertraut bin.

jmite
quelle
Vielen Dank! Kann man nachweisen, dass das Haskell-Typensystem das stärkste ist, das noch Typinferenz zulässt?
Виталий Олегович
3
Haskells ist definitiv NICHT der Stärkste, der Typinferenz zulässt. Die von mir erwähnten Verfeinerungstypen ermöglichen eine Typinferenz, und Haskell wird um viele GHC-Erweiterungen erweitert, die ein etwas stärkeres Typsystem ermöglichen.
Jmite
4
Darüber hinaus gibt es viele Typsysteme, und viele sind unvergleichlich: Sie sind in mancher Hinsicht stärker als Haskell, in anderen jedoch schwächer als Haskell. Es gibt keine lineare Reihenfolge der Typsysteme von den stärksten zu den schwächsten.
Jmite
5
Jetzt möchte ich beweisen, dass es kein stärkstes Typsystem gibt, das Typinferenz zulässt. Muss es widerstehen, unnütze Tatsachen zu beweisen.
Andrej Bauer
1
Die Tatsache scheint mir nicht nutzlos zu sein. Das Wissen, dass es ein stärkstes Typensystem mit Typinferenz gibt, wäre von großem Interesse, insbesondere wenn sich herausstellen würde, dass es realisierbar ist.
Rationalis
10

Die ML-Sprachfamilie (StandardML, OCaml ) hat eine ähnliche Tradition wie Haskell und verfügt daher über ähnliche Typsysteme. Sie sind jedoch nicht genau mit Haskell identisch, und einige ihrer Funktionen passen möglicherweise besser zu Ihnen (es gibt kein objektiv besseres Typensystem, da es Typensysteme in Programmiersprachen gibt, die dem Menschen helfen ). Hier sind einige Funktionen von OCaml, die Haskell entweder nicht hat (aber möglicherweise ein entsprechendes ähnliches Konzept hat), oder Haskell hat es aber anders gemacht:

  1. Polymorphe Varianten .
  2. Objekte mit Tiefensubtyp und Klassen .
  3. Functors sind Maps zwischen Modulen (Haskell hat Module) und sogar erstklassige Module

Und bitte, es ist nicht nötig, dies in ein ML-Haskell-Shootout zu verwandeln, sonst werde ich anfangen, auf Bob Harpers Blog-Posts zu verlinken ;-)

Andrej Bauer
quelle
9

Die Forschungssprache Clean hat ein besseres Typensystem als Haskell, weil sie Eindeutigkeitstypen hat . Die Ideen hinter den Eindeutigkeitstypen sind eng mit der linearen Logik verwandt , die der ressourcenbeschränkten "realen Welt" näher steht als die klassische Logik.

Die Antiforschungssprache Rust hat auch ein Typensystem mit einzigartigen Eigenschaften, die der "realen Welt" näher kommen als klassische reine Typensysteme. Die meisten Ideen, die das Typensystem beeinflussten, wurden völlig unabhängig von Rust veröffentlicht, lange bevor es überhaupt existierte. Aber die Art und Weise, wie diese alten Ideen zusammengefügt werden, ist einzigartig und verdient auch echte Forschungspublikationen, selbst wenn bekannte Lücken und Inkonsistenzen bestehen.

Thomas Klimpel
quelle
3
Irgendwie passen "veröffentlicht" und "Anti-Forschung" nicht gut zusammen.
Andrej Bauer
1
Eindeutigkeit ist sicherlich ein interessantes Konzept, aber bei IMO geht es eher um Semantik als um eine Typsystemfunktion. Und macht das das Typensystem wirklich strikt besser ? Kann Clean die neueren Dinge tun, die Haskell seinem Typsystem hinzugefügt hat, Polymorphismus usw. - sind einige davon sogar möglich, wenn das Typsystem bereits mit der Eindeutigkeit umgehen muss?
linksum den
1
@leftaroundabout Wie gut kennen Sie sich mit Eindeutigkeitstypen oder linearer Logik aus? Wenn x einen eindeutigen Typ hat, ist f (x, x) beispielsweise nicht gut typisiert. Möglicherweise kann Haskell erweitert werden, um auch Eindeutigkeitstypen zu unterstützen. Die Verschiebungssemantik in C ++ kann auch als Verbesserung der Unterstützung von Eindeutigkeitstypen über ein vorhandenes Typsystem angesehen werden.
Thomas Klimpel
Ich bin mit der C ++ - Verschiebungssemantik vertraut. Vielleicht ist das der Grund, warum ich den Eindruck habe, dass es sich bei der Eindeutigkeit nicht um eine Art System handelt. Was ich interessant finde, ist, ob vollständig nach außen propagierende Eindeutigkeitstypen andere Funktionen des erweiterten Typsystems behindern?
leftaroundabout
1
@leftaroundabout Rvalue Referenzen klingen für mich wie eine Typ-System-Sache. Warum sollten Eindeutigkeitstypen andere erweiterte Typfunktionen behindern? Im schlimmsten Fall würden diese erweiterten Funktionen einfach nicht für Eindeutigkeitstypen gelten. Natürlich bedeutet "echte Welt" -Funktionen wie Einzigartigkeitstypen, dass Sie sich für die Breite und nicht für die Tiefe entscheiden, und die Zeit, die Sie dafür aufwenden, weiter zu gehen, wird nicht mehr für die Tiefe zur Verfügung stehen. Aber ich habe den Eindruck, dass Einzigartigkeitstypen eine gute Balance zwischen Theorie und Praxis bieten, daher denke ich, dass die Zeit gut angelegt wäre.
Thomas Klimpel