Algorithmen zur Typprüfung

19

Ich beginne eine persönliche bibliografische Recherche über Algorithmen zur Typprüfung und möchte einige Tipps. Was sind die am häufigsten verwendeten Algorithmen, Strategien und allgemeinen Techniken zur Typprüfung?

Ich interessiere mich besonders für komplexe Algorithmen zur Typprüfung, die in weithin bekannten stark statisch typisierten Sprachen wie beispielsweise C ++, Java 5+, Scala oder anderen implementiert wurden. IE, Typüberprüfungsalgorithmen, die aufgrund der sehr einfachen Typisierung der zugrunde liegenden Sprache (wie Java 1.4 und niedriger) nicht sehr einfach sind.

Ich interessiere mich per se nicht für eine bestimmte Sprache X, Y oder Z. Ich interessiere mich für Algorithmen zur Typprüfung, unabhängig von der Sprache, auf die sie abzielen. Wenn Sie eine Antwort wie "Sprache L" eingeben, von der Sie noch nie gehört haben, welche stark getippt ist, und die Eingabe komplex ist, verfügt sie über einen Typprüfungsalgorithmus, der A, B und C durch Prüfen von X und Y mit dem Algorithmus Z "oder" the "ausführt Strategie X und Y für Scala und eine Variante Z von A für C # sind cool, weil die Funktionen R, S und T so funktionieren ", dann sind die Antworten schön.

Victor Stafusa
quelle
3
Vielleicht sollten Sie diese Frage bearbeiten, um Fragen zur Typüberprüfung für eine bestimmte Sprache zu stellen. Offene Fragen im Listenstil werden in SE im Allgemeinen nicht empfohlen (obwohl diese bestimmte Site diesbezüglich noch keine Richtlinien hat). Außerdem: <type-system-elitist> Javas Typsystem ist nicht komplex </ type-system-elitist>.
9.
3
Vielleicht könnte die Frage umformuliert werden, aber ich denke nicht, dass sie geschlossen werden sollte.
Dave Clarke
1
@ sepp2k: Ich weiß, dass es ein bisschen breit ist, aber endete auf diese Weise, weil ich den Nutzen der Antworten nicht einschränken möchte. Übrigens habe ich nicht verstanden, was Sie mit "<type-system-elitist> Javas Typensystem ist nicht komplex </ type-system-elitist>" sagen wollen. Das Java-System der Version 1.4 und niedriger war in der Tat einfach, aber mit den Generika in Java 5 wurde es viel komplexer.
Victor Stafusa
2
Nach einer bestimmten Sprache zu fragen, würde die Frage für diese Site ungeeigneter machen, imho. Die Frage sollte vielleicht nach allgemeinen Techniken stellen.
Raphael
1
@ Victor Ein grundlegendes Werkzeug sind Attributgrammatiken . Sie werden vielleicht nicht in der Lage sein, alle bösen Dinge, die Sie sich vorstellen können, mit ihnen zu tun, aber sie sind ein guter Ausgangspunkt.
Raphael

Antworten:

13

Die meisten Forschungen veröffentlichen die Algorithmen zur Typprüfung für vollständige Programmiersprachen nicht. Sie werden einige Formalisierungen eines großen Teils der Typsysteme für vollständige Programmiersprachen finden, wie die Arbeit von Drossopoulou und Eisenbach für Java oder die Arbeit von Nipkov et al in C ++ . Häufiger werden Sie jedoch nur die Typsysteme für einen Kernteil der Sprache finden (ein Beispiel ist Featherweight Java) oder für die Kernkonzepte einer Sprache wie den lokalen Typinferenzansatz von scala .

In Konferenzen wie POPL und ICFP finden Sie viele Algorithmen zur Typprüfung für bestimmte Arten von Typsystemen sowie neuartige Ansätze wie bidirektionale und tridirektionale Typprüfung.

Im Allgemeinen müssen Sie wahrscheinlich über den Damas-Milner-Algorithmus , die lokale Typinferenz, die bidirektionale und die tridirektionale Typprüfung Bescheid wissen und von dort aus erweitern, indem Sie den Referenzen in den Artikeln folgen und Google Scholar verwenden, um herauszufinden, welche Artikel diese zitieren und darauf aufbauen die beschriebenen Ansätze. Wie oben vorgeschlagen, haben Konferenzen wie POPL, ICPF, ESOP und sogar ECOOP und OOPSLA Papiere, die für Ihre Suche relevant sind.

Dave Clarke
quelle
Afaik, das Typensystem von Scala wurde in Forschungsprojekten entwickelt und wird daher veröffentlicht. Der Compiler ist ebenfalls Open-Source. Habe auch nicht reingeschaut.
Raphael
Ich brauche nicht zu schließen. Ich weiß, dass es Artikel über das Typensystem von Scala gibt. Diese Behauptung kann leicht durch Suchen überprüft werden . Außerdem zähle ich den Quellcode des Compilers als ausreichende Veröffentlichung auf dem Algorithmus (vorausgesetzt, er ist in den Quellen enthalten; ich gehe davon aus, habe dies jedoch nicht überprüft). Meine anfängliche Aussage war nicht eindeutig, aber Ihre Reaktion scheint unbegründet zu sein.
Raphael
2

Ein grundlegendes Werkzeug sind Attributgrammatiken . Sie werden vielleicht nicht in der Lage sein, alle bösen Dinge, die Sie sich vorstellen können, mit ihnen zu tun, aber sie sind ein guter Ausgangspunkt.

Im Wesentlichen können Sie den abstrakten Syntaxbaum eines Programms von oben nach unten und / oder von unten nach oben durchgehen und Informationen weitergeben. So können Sie beispielsweise globale Informationen zum Gültigkeitsbereichstyp (z. B. Klassen und ihre Mitglieder) nach unten übergeben und die Art der Ausdrücke rekursiv bestimmen, dh von unten nach oben, und die resultierenden Typen nach oben übergeben.

Erklärungen und Beispiele finden Sie in den Folien hier (Kapitel 5).

Raphael
quelle
Hat jemand eine bessere Referenz? Ich glaube, ich muss eines Tages das Drachenbuch oder Wilhelm / Maurer kaufen ...
Raphael
1
Das Tool JastAdd ist ein hervorragendes, modernes Compiler-Compiler-System, das auf Referenzattribut-Grammatiken basiert. Wir haben es in einer Reihe von Projekten verwendet.
Dave Clarke