Beweisverfahren zum Nachweis der abhängigen Typprüfung sind entscheidbar

10

Ich bin in einer Situation, in der ich zeigen muss, dass Typchecking für einen abhängig typisierten Kalkül, an dem ich arbeite, entscheidend ist. Bisher konnte ich beweisen, dass sich das System stark normalisiert und somit die definitive Gleichheit entscheidbar ist.

In vielen Referenzen, die ich lese, wird die Entscheidbarkeit der Typüberprüfung als Folge einer starken Normalisierung aufgeführt, und ich glaube es in diesen Fällen, aber ich frage mich, wie man dies tatsächlich zeigt.

Insbesondere bin ich auf Folgendes fixiert:

  • Nur weil sich gut typisierte Begriffe stark normalisieren, bedeutet dies nicht, dass der Algorithmus bei nicht gut typisierten Eingaben nicht für immer wiederholt wird
  • Da logische Beziehungen normalerweise verwendet werden, um eine starke Normalisierung anzuzeigen, gibt es keine bequeme abnehmende Metrik, wenn wir die Typüberprüfungsbegriffe weiterentwickeln. Selbst wenn meine Typregeln syntaxgesteuert sind, gibt es keine Garantie dafür, dass die Anwendung der Regeln irgendwann beendet wird.

Ich frage mich, hat jemand einen guten Hinweis auf einen Beweis für die Entscheidbarkeit der Typprüfung für eine abhängig getippte Sprache? Wenn es sich um einen kleinen Kernkalkül handelt, ist das in Ordnung. Alles, was über Beweistechniken zum Nachweis der Entscheidbarkeit spricht, wäre großartig.

jmite
quelle
7
Die üblichen bidirektionalen Typprüfungsalgorithmen versuchen niemals, einen Begriff (oder einen Typ) zu normalisieren, ohne vorher zu überprüfen, ob er gut typisiert (oder wohlgeformt) ist. Sie müssen sich keine Gedanken über die Normalisierung untypisierter Begriffe machen.
Andrej Bauer
7
In Bezug auf die Anwendung der Regeln: Alle Term- und Typregeln verringern das Ziel, mit Ausnahme der Typkonvertierung. Daher müssen wir die Typkonvertierung steuern, indem wir einen bidirektionalen Ansatz verwenden.
Andrej Bauer

Antworten:

9

Hier gibt es tatsächlich eine Subtilität, obwohl die Dinge bei der Typprüfung gut laufen. Ich werde das Problem hier aufschreiben, da es in vielen verwandten Threads auftaucht, und versuchen zu erklären, warum die Dinge gut funktionieren, wenn die Typprüfung in einer "standard" abhängigen Typentheorie durchgeführt wird (ich werde absichtlich vage sein, da diese Probleme ungeachtet dessen häufig auftreten):

Fakt 1: Wenn ist eine Ableitung von , dann gibt es eine Ableitung von für eine Art , und für jeden Subterm , dass eine Typ , ein Kontext und eine Ableitung von .DΓt:ADΓA:ssutBΔDΔu:B

Diese nette Tatsache ist etwas schwer zu beweisen und wird durch eine ziemlich böse Gegen-Tatsache ausgeglichen:

Fakt 2: Im Allgemeinen sind und keine Unterableitungen von !DD D

Dies hängt ein wenig von der genauen Formulierung Ihres Typsystems ab, aber die meisten in der Praxis implementierten "betrieblichen" Systeme erfüllen Fakt 2.

Dies bedeutet, dass Sie nicht "zu Unterbegriffen übergehen" können, wenn Sie durch Induktion über Ableitungen argumentieren, oder daraus schließen können, dass die induktive Aussage über die Art des Begriffs, über den Sie etwas beweisen möchten, wahr ist.

Diese Tatsache beißt Sie ziemlich hart, wenn Sie versuchen, scheinbar unschuldige Aussagen zu beweisen, z. B. dass Systeme mit typisierter Konvertierung denen mit untypisierter Konvertierung entsprechen.

Im Fall der Typinferenz können Sie jedoch einen simultanen Inferenzalgorithmus für Typ und Sortierung (den Typ des Typs) durch Induktion der Struktur des Begriffs angeben, der einen typgerichteten Algorithmus beinhalten kann, wie Andrej vorschlägt. Für einen gegebenen Term (und Kontext , Sie scheitern entweder oder finden so, dass und . Sie müssen die induktive Hypothese nicht verwenden, um letzteres zu finden Ableitung, und so vermeiden Sie insbesondere das oben erläuterte Problem.tΓA,sΓt:AΓA:s

Der entscheidende Fall (und der einzige Fall, der wirklich eine Konvertierung erfordert) ist die Anwendung:

infer(t u):
   type_t, sort_t <- infer(t)
   type_t' <- normalize(type_t)
   type_u, sort_u <- infer(u)
   type_u' <- normalize(type_u)
   if (type_t' = Pi(A, B) and type_u' = A' and alpha_equal(A, A') then
      return B, sort_t (or the appropriate sort)
   else fail

Jeder Aufruf zur Normalisierung wurde zu gut typisierten Bedingungen durchgeführt, da dies die Invariante für inferden Erfolg ist.


Übrigens hat Coq bei seiner Implementierung keine entscheidbare Typprüfung, da es den fixAnweisungskörper normalisiert, bevor versucht wird, sie zu überprüfen.

Auf jeden Fall sind die Grenzen der normalen Formen gut typisierter Begriffe so astronomisch, dass der Entscheidbarkeitssatz an dieser Stelle sowieso meistens akademisch ist. In der Praxis führen Sie den Typprüfungsalgorithmus so lange aus, wie Sie Geduld haben, und versuchen eine andere Route, wenn diese bis dahin noch nicht abgeschlossen ist.

Cody
quelle
Ich fand Ihre Antwort sehr nützlich, danke. Ich habe zwei Fragen: 1. Was bedeutet "Betriebssysteme"? Was ist die Alternative? 2. Können Sie das Beispiel genauer erläutern: Was bedeutet es (welche Tatsache versuchen wir zu beweisen?) "Systeme mit typisierter Konvertierung entsprechen denen mit untypisierter Konvertierung." Vielen Dank!
Łukasz Lew
1
@ ŁukaszLew Die Alternative zu einem Betriebssystem (eines, das in der Praxis beispielsweise in der Coq- oder Agda-Software implementiert ist) wäre ein theoretisches System, das zum Nachweis metatheoretischer Eigenschaften nützlich ist, in der Praxis jedoch ineffizient oder unpraktisch ist. Der Nachweis der Gleichwertigkeit eines betrieblichen und eines theoretischen Systems ist häufig ein wichtiger Bestandteil eines Systemdesigns. Ich spreche
cody
Ich denke, es ist erwähnenswert, Lennart Augustssons Simpler, Easier! . Dies ist eine minimale Haskell-Implementierung der Typprüfung und einige Schlussfolgerungen für abhängig typisierte Lambda-Berechnungen. Es gibt Code, der Cody's genau entspricht infer(t u):; Um es zu finden, suchen Sie nach " tCheck r (App f a) =". Für eine vollständigere, aber dennoch einfache Implementierung können Sie Morte'stypeWith überprüfen .
Łukasz Lew
1
@ ŁukaszLew Das Problem der typisierten und untypisierten Konvertierung ist eine bekannte offene Frage, die zwei Formulierungen von Typentheorien betrifft und erst kürzlich gelöst wurde: pauillac.inria.fr/~herbelin/articles/…
cody
Was bedeutet es ? ut
Jonaprieto