Das Typensystem in Scala ist Turing vollständig. Beweis? Beispiel? Leistungen

Es gibt Behauptungen, dass das Typensystem von Scala vollständig ist. Meine Fragen sind:

Gibt es einen formellen Beweis dafür?

Wie würde eine einfache Berechnung im Scala-Typsystem aussehen?

Ist das für Scala von Nutzen - die Sprache? Ist Scala dadurch in gewisser Weise "leistungsfähiger" als Sprachen ohne Turing-Komplettsystem?

Ich denke, das gilt für Sprachen und Typsysteme im Allgemeinen.

 ziggystar29. Okt. 2010, 09:05
Ich hätte lieber ein nicht universelles Typsystem und stattdessen einen schnellen Compiler.
 BAR03. März 2015, 16:59
@ ziggystar Was Sie an Kompiliergeschwindigkeit gewinnen würden, würden Sie wahrscheinlich an Entwicklungs- und Debug-Zeit verlieren.

Antworten auf die Frage(4)

Lösung für das Problem

Es gibt irgendwo einen Blog-Beitrag mit einer Implementierung auf Typebene des SKI-Kombinator-Kalküls, von dem bekannt ist, dass sie Turing-vollständig ist.

Turing-complete-Typsysteme haben grundsätzlich dieselben Vor- und Nachteile wie Turing-complete-Sprachen: Sie können alles tun, aber Sie können nur sehr wenig beweisen. Insbesondere können Sie nicht beweisen, dass Sie tatsächlich irgendwann etwas tun werden.

Ein Beispiel für die Berechnung auf Typebene sind die neuen typerhaltenden Auflistungstransformatoren in Scala 2.8. In Scala 2.8 können Methoden wiemap, filter und so weiter geben garantiert eine Sammlung des gleichen Typs zurück, für den sie aufgerufen wurden. Also, wenn Siefilter a Set[Int], du bekommst ein @ zurüSet[Int] Und wenn Dumap a List[String] du bekommst ein @ zurüList[Whatever the return type of the anonymous function is].

Nun, wie Sie sehen können,map kann den Elementtyp tatsächlich transformieren. Was passiert also, wenn der neue Elementtyp nicht mit dem ursprünglichen Auflistungstyp dargestellt werden kann? Beispiel: aBitSet kann nur Ganzzahlen mit fester Breite enthalten. Was passiert also, wenn Sie ein @ habeBitSet[Short] und Sie ordnen jede Zahl ihrer Zeichenfolgendarstellung zu?

someBitSet map { _.toString() }

Das Ergebniswürd sei einBitSet[String], aber das ist unmöglich. Also wählt Scala den am meisten abgeleiteten Supertyp vonBitSet, das ein @ enthalten kaString, was in diesem Fall ein @ iSet[String].

Alle diese Berechnung läuft währendcompile time oder genauer gesagt währendtype Prüfzeit mit Funktionen auf Typebene. Somit ist statisch garantiert, dass es typsicher ist, obwohl die Typen tatsächlich berechnet werden und daher zur Entwurfszeit nicht bekannt sin

 Antal Spector-Zabusky29. Okt. 2010, 01:34
Ich stelle mir vor, das ist der Blog-Beitrag, den Sie gesucht haben? michid.wordpress.com / 2010/01/29 /…. Scala schien eine nette Sprache zu sein, als ich sie zum ersten Mal betrachtete. diese Superklasse-Inferenz ist einJa wirklic coole Funktion.
 Daniel Spiewak29. Okt. 2010, 02:57
Ausgezeichnete Antwort, obwohl das Kollektionsbeispiel etwas zu kurz kommt. Während die Typprüfung mit Sicherheit einige interessante heuristische Schritte ausführt, um den bestmöglichen Auflistungstyp zur Kompilierungszeit zu erhalten, ist dies kein gutes Beispiel für eine Berechnung auf Typebene, da das Typensystemselbs macht eigentlich keine Arbeit. Leider (oder vielleicht glücklicherweise) gibt es nicht viele Beispiele für Code aus der realen Welt, der auf Typebene programmiert, nur weil er so schwer, klobig und nicht wartbar ist.
 Adrian29. Okt. 2010, 21:41
Danke Jörg für das tolle Beispiel und Daniel für die Klarstellung. Jetzt habe ich Angst zu fragen, ob die Typprüfung abgeschlossen ist ...

MyBlogeintra beim Kodieren des SKI-Kalküls im Scala-Typensystem wird die Turing-Vollständigkeit angezeigt.

Für einige einfache Berechnungen auf Typebene gibt es auch einige Beispiele zum Kodieren der natürlichen Zahlen und der Addition /Multiplikatio.

ndlich gibt es ein tolles Artikelserie auf Typ-Level-Programmierung über auf Apocalisps Blog.

 slebetman31. Okt. 2010, 21:46
Es sollte auch beachtet werden, dass nichts, was praktisch umsetzbar ist, wirklich vollständig ist, da es unmöglich ist, unendlichen Speicher zu haben. Selbst wenn Sie die gesamte Materie im Universum für den Aufbau Ihrer CPU / Ihres Interpreters verbrauchen, wäre dies noch nicht wirklich vollständig. Was wir praktisch als vollständig bezeichnen, ist wirklich vollständig innerhalb der Grenzen des verfügbaren Speicher
 Adrian29. Okt. 2010, 21:51
michid, das sieht beeindruckend aus. Ich verspreche, mich im Erwachsenenalter besser umzusehen ... Dies ist möglicherweise kein FORMALER Beweis, aber er gehört möglicherweise zu dieser Liste? de.wikipedia.org / wiki /…
 slebetman31. Okt. 2010, 21:43
drian, der einzige bekannte formale Beweis für die Vollständigkeit der Prüfung ist die Fähigkeit, etwas anderes zu implementieren, das vollständig ist. Typischerweise bedeutet dies eine universelle Turing-Maschine, aber die Theorie gilt auch, wenn Sie etwas anderes verwenden, von dem bekannt ist, dass es vollständig ist, wie SKI-Kalkül oder Perl oder Javascript. Daher würde ich einreichen, dass dies ein formaler Beweis ist.

Ihre Antwort auf die Frage