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

10

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?

Vivek Ghaisas
quelle
Vielleicht können Sie klären, ob Sie wissen möchten, (1) ob Ihre Implementierung ein bestimmtes Typisierungssystem implementiert , oder (2) ob Ihr Typisierungssystem die Fehler verhindert, die Sie für erforderlich halten? Das sind verschiedene Fragen. T.TT
Martin Berger
1
@ MartinBerger: Ah, ich habe diesen Unterschied anscheinend übersprungen. Meine eigentliche Frage sollte wahrscheinlich beides stellen. Der Kontext ist, dass ich versuche, eine Sprache aufzubauen, und dafür habe ich einen Typechecker geschrieben. Und die Leute baten mich, einen bewährten Algorithmus zu verwenden. Ich war daran interessiert zu sehen, wie schwierig es sein würde, den von mir verwendeten Algorithmus und Typechecker "korrekt" zu "beweisen". Daher die Mehrdeutigkeit in meiner Frage.
Vivek Ghaisas
2
(1) ist wirklich eine Frage bei der Programmüberprüfung und hat wenig mit Tippen zu tun. Es muss nur gezeigt werden, dass Ihre Implementierung den Spezifikationen entspricht. Definieren Sie in Bezug auf (2) zunächst, was es bedeutet, ein sofortiger Typfehler zu sein (z. B. solche Begriffe 2 + "hello"stecken fest). Sobald dies formalisiert ist, können Sie den Typ-Soliditätssatz beweisen. Das bedeutet, dass sich kein typisierbares Programm jemals zu einem sofortigen Tippfehler entwickeln kann. Formal Sie beweisen , dass , wenn ein Programm typisierbaren ist, und für jedes : wenn läuft Schritten werden , dann nicht sofort Typfehler hat. (1/2)n M n N N.MnMnNN
Martin Berger
1
Dies wird typischerweise durch Induktion auf und auf die Ableitung des Typisierungsurteils bewiesen. (2/2)n
Martin Berger
Vielen Dank! Basierend auf Ihrer Erklärung scheint es, als ob (2) tatsächlich das ist, wonach ich gesucht habe. Könnten Sie das bitte beantworten? (Und vielleicht fügen Sie Details hinzu, die Sie für nützlich halten.) Ich würde das als Antwort akzeptieren! :)
Vivek Ghaisas

Antworten:

10

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.TT

  • 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.

  • ΓM:α.MαΓ

    ΓM:αMNN

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

MMNM

  • ΓM:αMNΓN:α

  • ΓM:αM

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

Martin Berger
quelle
20

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.

eAeAAint

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.

Andrej Bauer
quelle
Vielen Dank für diese ausführliche Antwort! Ich bin mir jedoch immer noch nicht sicher, wie ich meine Frage beantworten soll. Nehmen wir als konkretes Beispiel C - eine statisch typisierte Sprache mit einem ausreichend einfachen Typsystem. Wenn ich einen Typechecker für C schreiben würde, wie würde ich beweisen, dass mein Typechecker "korrekt" ist? Wie ändert sich diese Antwort, wenn ich stattdessen eine Typprüfung für Haskell geschrieben habe, sagen wir HM? Wie würde ich jetzt "Korrektheit" beweisen?
Vivek Ghaisas
1
TeATeA
Ich würde empfehlen, 2. und 3. als Kombination zu machen. Schauen Sie sich auch CompCert an .
Andrej Bauer
1
TeAeAe
AAe
5

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.

Zaunkönig Romano
quelle
Ich bin mir nicht sicher, ob ich zustimmen kann, dass "diese Perspektive wirklich darauf abzielt, ob Sie alle Eckfälle abgedeckt haben", insbesondere wenn das Modell nur solide, aber nicht vollständig ist. Ich würde eine andere Perspektive vorschlagen: Das Durchlaufen eines Modells ist eine Kontingentbeweis- Technik , die Sie aus verschiedenen Gründen verwenden, z. B. weil das Modell einfacher ist. Es gibt nichts Philosophisch Würdigeres daran, ein Modell durchzugehen - letztendlich möchten Sie etwas über die tatsächliche ausführbare Datei und ihr Verhalten wissen.
Martin Berger
Ich dachte, "Modell" und "Theorie" seien im weitesten Sinne gemeint, und wren betonte nur die Wichtigkeit des Versuchs, eine wechselseitige Entsprechung über einen "Satz von Solidität + Vollständigkeit" herzustellen. (Ich denke auch, dass dies wichtig ist, und habe einen Kommentar zu Andrejs Beitrag abgegeben.) Es ist wahr, dass wir in einigen Situationen nur einen Soliditätssatz (oder einen Vollständigkeitssatz, abhängig von Ihrer Perspektive) beweisen können, aber beide Richtungen haben Dies ist eine nützliche methodische Einschränkung.
Noam Zeilberger
1
@NoamZeilberger "Die Frage ist", sagte Martin, "ob man Wörter so viele verschiedene Dinge bedeuten lassen kann."
Martin Berger
Als ich etwas über Typisierungssysteme und Programmiersprachen-Semantik lernte, stellte ich fest, dass Modelle lediglich Beweisverfahren für die operative Semantik sind und nicht in sich selbst sublim befreiend enden.
Martin Berger
1
Die Beziehung verschiedener Modelle durch Solidität und Vollständigkeit ist eine wichtige wissenschaftliche Methode für den Transfer von Erkenntnissen.
Martin Berger