Was ist ein nicht erfundenes Beispiel für eine zu konservative statische Typprüfung?

9

In Concepts in Programming Languages schreibt John Mitchell, dass die statische Typprüfung aufgrund des Halteproblems notwendigerweise konservativ (zu streng) ist. Er gibt als Beispiel:

if (complicated-expression-that-could-run-forever)
   then (expression-with-type-error)
   else (expression-with-type-error)

Kann jemand eine nicht erfundene Antwort geben, die wirklich ein praktisches Anliegen wäre?

Ich verstehe, dass Java dynamisch überprüfte Casts für Fälle wie diesen zulässt:

if (foo instanceof Person) {
    Person p = (Person) foo;
    :
}

Ich halte die Notwendigkeit jedoch eher für einen Mangel an Java-Sprache / Compiler als für ein sprachübergreifendes Problem.

programming-languages compilers type-checking Ellen Spertus
quelle
2
Das von Ihnen angegebene Java-Beispiel ist ein nicht erfundenes Beispiel für eine zu konservative statische Typprüfung. Anders ausgedrückt: Die Antwort hängt davon ab, an welches Typsystem Sie denken. Für jedes Beispiel gibt es immer ein Typsystem, das dieses Beispiel verarbeiten kann (das Typsystem ist in diesem Beispiel nicht zu konservativ). Für jedes Typsystem finden wir immer ein Beispiel, bei dem es zu konservativ ist. Ich denke, Sie müssen das Typsystem angeben. Wenn das Java-Typ-System nicht Ihren Vorstellungen entspricht, gibt es etwas Spezifischeres, an das Sie gedacht haben? Typinferenz im ML-Stil?
DW
Man könnte argumentieren, dass das Beispiel eine statische Code-Analyse ist, die "konservativ" ist, nicht eine NEC-Typprüfung. es wäre hilfreich, "konservativ" zu definieren . Wahrscheinlich sind alle statischen Systeme im Vergleich zu dynamischen Systemen "konservativ" , da erstere per Definition zur Kompilierungszeit strenger sind . Man könnte jedoch argumentieren, dass beides zur Laufzeit nicht strenger ist, da die dynamische Prüfung auch ähnliche (typbasierte) Fehler zurückgeben kann. Übrigens sind dynamisch überprüfte Laufzeit-Casts in Sprachen kein Mangel , sondern in den meisten statisch überprüften Sprachen, möglicherweise nachweislich erforderlich.
vzn

Antworten:

7

Ich habe es immer eher als eine Frage der Bequemlichkeit angesehen, als darüber, ob ein Algorithmus überhaupt ausgedrückt werden kann oder nicht. Wenn ich wirklich Programme wie das von Mitchell erfundene ausführen wollte, würde ich einfach den entsprechenden Turing Machine-Simulator in meiner statisch typisierten Sprache schreiben.

Der Trick bei einem statischen Typsystem besteht darin, die richtige Flexibilität nur für die Fälle anzubieten, in denen Sie aufgrund der Flexibilität Code schreiben können, der einfacher zu warten ist.

Hier sind einige Beispiele für Programmstrukturierungstechniken, von denen manchmal angenommen wird, dass sie in dynamischer Sprache einfacher zu verwalten sind als in statisch typisierten Sprachen.

Generika und Container

In statisch typisierten Sprachen vor ML (ca. 1973) und CLU (ca. 1974) war es nicht schwierig, einen rot-schwarzen Baum von Strings, einen rot-schwarzen Baum von ganzen Zahlen, einen rot-schwarzen Baum von Floats oder einen zu erstellen rot-schwarzer Baum von Elementen eines bestimmten Typs Foo. Es war jedoch schwierig (möglicherweise unmöglich), eine einzelne Implementierung eines rot-schwarzen Baums zu erstellen, der sowohl statisch überprüft wurde als auch einen dieser Datentypen verarbeiten konnte. Die Möglichkeiten, um das Problem zu umgehen, bestanden darin, (1) vollständig aus dem Typsystem auszubrechen (zum Beispiel: durch Verwendung vonvoid * in C), (2) um sich eine Art Makro-Präprozessor zu schreiben und dann Makros zu schreiben, die den Code für jeden gewünschten Typ erzeugen, oder (3) um den Lisp / Smalltalk- (und Java-) Ansatz zum Überprüfen des Typs des extrahierten zu verwenden Objekt dynamisch.

ML und CLU haben den Begriff der abgeleiteten bzw. explizit deklarierten (statischen) parametrisierten Typen eingeführt, mit denen Sie generische, statisch typisierte Containertypen schreiben können.

Subtyp Polymorphismus

In statisch typisierten Sprachen vor Simula67 (ca. 1967) und Hope (ca. 1977) war es nicht möglich, sowohl einen dynamischen Versand durchzuführen als auch statisch zu überprüfen, ob Sie den Fall für jeden Subtyp abgedeckt hatten. Viele Sprachen hatten irgendeine Form von getaggten Gewerkschaften , aber es lag in der Verantwortung des Programmierers, sicherzustellen, dass ihre caseoder switchAnweisungen oder ihre Sprungtabellen alle möglichen Tags abdeckten.

Sprachen, die dem Simula-Modell folgen (C ++, Java, C #, Eiffel), bieten abstrakten Klassen eine Unterklasse, in der der Compiler überprüfen kann, ob jede Unterklasse alle von der übergeordneten Klasse deklarierten Methoden implementiert hat. Sprachen, die dem Hope-Modell folgen (alle ML-Varianten von SML / NJ bis Haskell), haben algebraische Subtypen, bei denen der Compiler überprüfen kann, ob jede typecaseAnweisung alle Subtypen abdeckt.

Affen-Patching und aspektorientierte Programmierung

Dynamische Typsysteme erleichtern eine Vielzahl von Prototyping-Techniken erheblich. In Sprachen, in denen Typen durch Hash-Maps von Zeichenfolgen zu Funktionen dargestellt werden (z. B. Python, Javascript, Ruby), ist es recht einfach, das Verhalten jedes Moduls, das auf einem bestimmten Typ basiert, global zu ändern, indem einfach die Hash-Map, die dies darstellt, dynamisch geändert wird Art.

Während es offensichtliche Möglichkeiten gibt, wie das Patchen von Affen verwendet werden kann, um die Wartung von Programmen zu erschweren, gibt es auch Möglichkeiten, wie es tatsächlich für "gut" und nicht für "böse" verwendet werden kann. Insbesondere bei der aspektorientierten Programmierung kann man Affen-Patching-ähnliche Techniken verwenden, um beispielsweise den Dateityp so zu ändern, dass er auf ein virtualisiertes Dateisystem verweist, wodurch der Aufbau von Unit-Testing-Infrastrukturen "kostenlos" ermöglicht wird, oder um einfache Ausnahmetypen zu ändern Drucken Sie Protokollnachrichten jedes Mal, wenn sie zur besseren Fehlerbehebung abgefangen werden.

Im Gegensatz zu Generika und Subtyp-Polymorphismus, bei denen die wichtigsten Ideen zur statischen Überprüfung in den 1970er Jahren verfügbar waren, ist die statische Überprüfung für die aspektorientierte Programmierung (glaube ich) ein aktives Forschungsgebiet. Ich weiß nicht viel darüber, außer dass es seit ungefähr 2001 eine Sprache namens AspectJ gibt .

Wanderlogik
quelle