Typ-Überprüfungsalgorithmen

Question

Ich beginne eine persönliche bibliografische Forschung zu Algorithmen zum Typ-Prüfen und möchte einige Tipps. Was sind die am häufigsten verwendeten Typ-Überprüfungsalgorithmen, Strategien und allgemeinen Techniken?

Ich interessiere mich besonders für komplexe Typ-Überprüfungsalgorithmen, die in weithin bekannten stark statischen typisierten Sprachen wie C ++, Java 5+, Scala oder anderen implementiert wurden. Dh Algorithmen zum Typ-Überprüfungen, die aufgrund der sehr einfachen Eingabe der zugrunde liegenden Sprache (wie Java 1.4 und unten) nicht sehr einfach sind.

Ich interessiere mich nicht per se an einer bestimmten Sprache X, Y oder Z. Ich interessiere mich für Typ-Überprüfungsalgorithmen, unabhängig von der Sprache, auf die sie abzielen. Wenn Sie eine Antwort wie "Sprache L haben, von der Sie noch nie gehört haben, welche stark getippt ist, und das Tippenkomplex einen Typ-Überprüfungsalgorithmus hat, der A, B und C durch Überprüfen von X und Y mit dem Algorithmus z" oder "die" oder "die" oder "das" enthält "oder" die Strategie X und Y, die für Scala und eine Variante Z von A verwendet werden, sind aufgrund der R-, S- und T -Funktionen, die auf diese Weise funktionieren, cool. "

Answer 1

Die meisten Forschungsergebnisse veröffentlichen die Typ -Checking -Algorithmen für vollblasende Programmiersprachen nicht. Sie finden einige Formalisierungen eines großen Teils der Typsysteme für vollständige Programmiersprachen, wie beispielsweise die Arbeiten von Drossopoulou und Eisenbach für Java oder Nipkov et al. Arbeiten an C ++. Häufiger finden Sie jedoch nur die Typsysteme für einen Kernteil der Sprache (Federgewicht Java ist ein Beispiel) oder für die Kernkonzepte einer Sprache wie die Lokaler Inferenzansatz von Scala.

In Konferenzen wie POPL und ICFP finden Sie viele Typ -Überprüfungsalgorithmen für bestimmte Arten von Typsystemen und neuartige Ansätze wie z. B. bidirektional und tridirektional Geben Sie die Überprüfung ein.

Allgemeiner müssen Sie wahrscheinlich über das wissen Damas-Milner-Algorithmus, lokale Typinferenz, bidirektionale und tridirektionale Art und erweitert von dort aus, indem Referenzen in den Papieren folgen und Google Scholar nutzten, um herauszufinden, welche Artikel diese zitieren und auf den beschriebenen Ansätzen aufbauen. Wie oben vorgeschlagen, werden Konferenzen wie POPL, ICPF, ESOP und sogar ECOOP und OOPSLA auch Papiere haben, die für Ihre Suche relevant sind.

Answer 2

Ein grundlegendes Werkzeug sind Grammatiken zuschreiben. Sie werden vielleicht nicht in der Lage sein, jedes böse Ding zu tun, das Sie sich mit ihnen vorstellen können, aber sie sind ein guter Ausgangspunkt.

Im Wesentlichen können Sie den abstrakten Syntaxbaum eines Programms Top-Down und/oder Bottom-up über den Programm eines Programms gehen und Informationen übergeben. So können Sie beispielsweise globale Informationen zum Zielfernrohr (z. B. Klassen und deren Mitglieder) nach unten übergeben und die Art der Ausdrücke rekursiv bestimmen, dh Bottom-up und die resultierenden Typen nach oben.

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