Was sollte ein Korrektheitsnachweis für einen Typchecker tatsächlich beweisen?

Ich programmiere seit mehreren Jahren, bin aber mit theoretischer CS sehr unbekannt. Ich habe kürzlich versucht, Programmiersprachen zu studieren und als Teil davon Typprüfung und Inferenz.

Meine Frage ist, wenn ich versuche, ein Typinferenz- und Überprüfungsprogramm für eine Programmiersprache zu schreiben, und ich beweisen möchte, dass mein Typechecker funktioniert, was genau ist der Beweis, den ich suche?

Im Klartext möchte ich, dass meine Typprüfung Fehler in einem Code identifizieren kann, die zur Laufzeit auftreten können. Wenn ich so etwas wie Coq verwenden würde, um zu beweisen, dass meine Implementierung korrekt ist, was genau wird dieser "Korrektheitsnachweis" zu zeigen versuchen?

Die Frage kann auf zwei Arten interpretiert werden:

• Ob die Implementierung ein gegebenes Typisierungssystem implementiert ?$T$
• Ob das Tippsystem die Fehler verhindert, die Sie für richtig halten?$T$

Ersteres ist wirklich eine Frage bei der Programmüberprüfung und hat wenig mit Tippen zu tun. Sie müssen nur zeigen, dass Ihre Implementierung den Spezifikationen entspricht, siehe die Antwort von Andrej.

Lassen Sie mich über die spätere Frage sprechen. Wie Andrej sagte, scheint ein Typisierungssystem aus abstrakter Sicht Eigenschaften für Programme zu erzwingen. In der Praxis versucht Ihr Tippsystem , das Auftreten von Fehlern zu verhindern, was bedeutet, dass typisierbare Programme nicht die Klasse der interessierenden Fehler aufweisen sollten. Um zu zeigen, dass T das tut, was Sie denken, müssen Sie zwei Dinge tun.$T$$T$

• Zunächst definieren Sie formal, was es für ein Programm bedeutet, einen sofortigen Tippfehler zu haben . Es gibt viele Möglichkeiten, wie dies definiert werden kann - es liegt an Ihnen. In der Regel möchten wir Programme wie verhindern 2 + "hello". Mit anderen Worten, Sie müssen eine Teilmenge von Programmen definieren, die als Bad bezeichnet werden und genau die Programme mit sofortigem Tippfehler enthalten.

• $\Gamma \vdash M : \alpha.$$M$$\alpha$$\Gamma$

  $\Gamma \vdash M : \alpha$$M \rightarrow \cdots \rightarrow N$$N \notin$

  Wie Sie diesen Satz beweisen können, hängt von den Details der Sprache, dem Typisierungssystem und Ihrer Wahl von Bad ab .

$M$$M \rightarrow N$$M$

• $\Gamma \vdash M : \alpha$$M \rightarrow N$$\Gamma \vdash N : \alpha$

• $\Gamma \vdash M : \alpha$$M$

Beachten Sie, dass nicht alle Typisierungssysteme eine "Betreffreduzierung" aufweisen, z. B. Sitzungstypen. In diesem Fall sind komplexere Prooftechniken erforderlich.

Das ist eine gute Frage! Es wird gefragt, was wir von Typen in einer getippten Sprache erwarten.

Beachten Sie zunächst, dass wir jede Programmiersprache mit dem Unitype eingeben können : Wählen Sie einfach einen Buchstaben aus Uund sagen Sie, dass jedes Programm einen Typ hat U. Das ist nicht besonders nützlich, aber es macht einen Punkt.

$e$$A$$e$$A$$A$int

Es gibt kein Ende, wie ausdrucksstark Ihre Typen sein können. Im Prinzip können sie jede Art von logischen Anweisungen sein, sie können Kategorietheorie und so weiter verwenden usw. Mit abhängigen Typen können Sie beispielsweise Dinge wie "Diese Funktion ordnet Listen so zu, dass die Ausgabe eine sortierte Eingabe ist" ausdrücken. Sie können noch weiter gehen. Im Moment höre ich einen Vortrag über "gleichzeitige Trennungslogiken", in dem Sie darüber sprechen können, wie gleichzeitige Programme mit gemeinsam genutztem Status funktionieren. Schickes Zeug.

Die Kunst der Typen im Design von Programmiersprachen besteht darin , Ausdruckskraft und Einfachheit in Einklang zu bringen :

• Ausdrucksstärkere Typen ermöglichen es uns, uns selbst und dem Compiler genauer zu erklären, was vor sich gehen soll
• Einfachere Typen sind leichter zu verstehen und können im Compiler einfacher automatisiert werden. (Die Leute entwickeln Typen, für deren Typprüfung im Wesentlichen ein Proof-Assistent und Benutzereingaben erforderlich sind.)

Die Einfachheit ist nicht zu unterschätzen, da nicht jeder Programmierer in Theorie der Programmiersprachen promoviert hat.

Kommen wir also auf Ihre Frage zurück: Woher wissen Sie, dass Ihr Typensystem gut ist ? Beweisen Sie, dass Theoreme, die Ihre Typen zeigen, ausgewogen sind. Es wird zwei Arten von Theoremen geben:

1. Sätze, die besagen, dass Ihre Typen nützlich sind . Zu wissen, dass ein Programm einen Typ hat, sollte einige Garantien beinhalten, zum Beispiel, dass das Programm nicht hängen bleibt (das wäre ein Sicherheitssatz ). Eine andere Familie von Theoremen würde die Typen mit semantischen Modellen verbinden, damit wir anfangen können, echte Mathematik zu verwenden, um Dinge über unsere Programme zu beweisen (dies wären Adequacy-Theoreme und viele andere). Die obige Einheit ist schlecht, weil sie keine so nützlichen Theoreme enthält.

2. Sätze, die besagen, dass Ihre Typen einfach sind . Eine grundlegende wäre, dass es entscheidbar ist, ob ein gegebener Ausdruck einen gegebenen Typ hat. Eine weitere einfache Funktion besteht darin, einen Algorithmus zum Ableiten eines Typs anzugeben. Andere Sätze über die Einfachheit wären: dass ein Ausdruck höchstens einen Typ hat oder dass ein Ausdruck einen Haupttyp hat (dh den "besten" unter allen Typen, die er hat).

Es ist schwierig, genauer zu sein, da Typen ein sehr allgemeiner Mechanismus sind. Aber ich hoffe du siehst was du schießen solltest. Wie die meisten Aspekte des Entwurfs von Programmiersprachen gibt es kein absolutes Erfolgsmaß. Stattdessen gibt es einen Raum mit Gestaltungsmöglichkeiten, und es ist wichtig zu verstehen, wo in dem Raum Sie sich befinden oder befinden möchten.

Es gibt ein paar verschiedene Dinge, die Sie mit "beweisen, dass mein Typechecker funktioniert" meinen könnten. Was wohl Teil Ihrer Frage ist;)

Eine Hälfte dieser Frage beweist, dass Ihre Typentheorie gut genug ist, um alle Eigenschaften der Sprache zu beweisen. Andrejs Antwort geht diesen Bereich sehr gut an. Die andere Hälfte der Frage lautet: Angenommen, die Sprache und ihr Typensystem sind bereits festgelegt. Wie können Sie nachweisen, dass Ihre spezielle Typprüfung das Typensystem tatsächlich korrekt implementiert? Es gibt zwei Hauptperspektiven, die ich hier sehen kann.

Eine ist: Wie können wir jemals darauf vertrauen, dass eine bestimmte Implementierung ihrer Spezifikation entspricht? Je nachdem, welchen Grad an Sicherheit Sie wünschen, können Sie mit einer großen Testsuite zufrieden sein, oder Sie möchten eine formale Überprüfung oder eher eine Mischung aus beiden . Der Vorteil dieser Perspektive ist, dass sie wirklich zeigt, wie wichtig es ist, Grenzen für Ihre Behauptungen zu setzen: Was genau bedeutet "richtig"? Welcher Teil des Codes wird geprüft, und welcher Teil ist der angenommene korrekte TCB? usw. Der Nachteil ist, dass ein zu intensives Nachdenken zu philosophischen Kaninchenlöchern führt - also "Nachteil", wenn Sie diese Kaninchenlöcher nicht mögen.

Die zweite Perspektive ist eine mathematischere Sichtweise der Korrektheit. Wenn wir uns mit Sprachen in der Mathematik befassen, richten wir oft "Modelle" für unsere "Theorien" ein (oder umgekehrt) und versuchen dann zu beweisen: (a) alles, was wir in der Theorie tun können, was wir im Modell tun können, und (b) Alles, was wir im Modell tun können, können wir in der Theorie tun. (Dies sind Solidität und VollständigkeitSätze. Welches davon davon abhängt, ob Sie von der syntaktischen Theorie oder vom semantischen Modell "ausgegangen" sind.) Mit dieser Denkweise können wir uns Ihre Implementierung zur Typprüfung als ein bestimmtes Modell für die betreffende Typentheorie vorstellen. Sie möchten also diese wechselseitige Entsprechung zwischen dem, was Ihre Implementierung kann, und dem, was die Theorie besagt, dass Sie in der Lage sein sollten, beweisen. Der Vorteil dieser Perspektive ist, dass sie sich wirklich darauf konzentriert, ob Sie alle Eckfälle abgedeckt haben, ob Ihre Implementierung vollständig ist, indem Sie keine Programme auslassen, die als typsicher akzeptiert werden sollten, und ob Ihre Implementierung solide ist das Gefühl, keine Programme einzulassen, die als schlecht getippt abgelehnt werden sollten. Der Nachteil ist, dass Ihr Korrespondenznachweis wahrscheinlich ziemlich weit von der Implementierung selbst entfernt ist.