Zusammenhang zwischen Entscheidbarkeit der Typprüfung, Entscheidbarkeit der Typisierbarkeit und starker Normalisierung

Yo! Dies ist wahrscheinlich eine dumme Frage, aber ich habe nie gesehen, dass sie explizit niedergeschrieben wurde, wenn beispielsweise die Entscheidbarkeit der Typprüfung der starken Normalisierungseigenschaft entspricht. Daher stelle ich diese Frage, um alle möglichen Zusammenhänge zwischen Typprüfung, Typisierbarkeit und starker Normalisierung zu klären.

Lassen Sie mich meine Motivation erklären. Für Typentheorien (ich bin hier absichtlich vage, aber ich interessiere mich hauptsächlich für abhängige Typentheorien) wird eine starke Normalisierung verwendet, um die Entscheidbarkeit der Typprüfung zu beweisen. Auf der anderen Seite haben alle typisierten Systeme, die ich kenne und die eine dieser Eigenschaften haben, auch die andere. Ich habe jedoch nie explizit gesehen, dass eine starke Normalisierung gleichbedeutend mit der Entscheidbarkeit der Typprüfung ist.

Um die Typisierbarkeit zu beweisen, reduziert man normalerweise (vielleicht immer) einen Begriff auf eine normale Form. Es ist jedoch bekannt, dass die Typisierbarkeit für abhängige Typentheorien nicht gilt, wohingegen eine starke Normalisierung gelten kann.

$A$ $\Gamma$ $a$ $\Gamma \vdash a: A$

$a$ $\Gamma$ $A$ $\Gamma \vdash a: A$

1) Stimmt es, dass die Entscheidbarkeit der Typprüfung gleichbedeutend damit ist, dass jeder Begriff stark normalisierbar ist?

2) Welche Beziehung besteht allgemein zwischen der Entscheidbarkeit der Typprüfung, der Typisierbarkeit und der starken Normalisierung? Welches impliziert das andere?

Danke im Voraus.

BEARBEITEN

Angesichts der Unzufriedenheit mit dem Grad der Allgemeinheit meiner Frage (die mir nicht bekannt war) möchte ich sie nur auf Pure Type Systems beschränken. Natürlich sind zusätzliche Kommentare oder Gegenbeispiele zu anderen Typentheorien von großem Nutzen.

type-theory type-checking type-inference user40276
quelle

Ohne jegliche Einschränkungen? Was ist, wenn wir das triviale Typensystem nehmen, bei dem jeder Begriff jeden Typ hat? Das ist trivial entscheidbar, aber nicht normalisierend. Ich befürchte, dass es im Allgemeinen keine Beziehungen zwischen den von Ihnen zitierten Begriffen geben könnte, wenn dem Typensystem keine weiteren Einschränkungen auferlegt werden.

Chi

@chi Es tut mir leid. Mir war der Grad der Allgemeinheit der Definition eines typisierten Systems nicht bekannt. Was ich vorhatte, war so etwas wie ein Fragment der Martin-Löf-Typentheorie mit Universen. Ich glaube daher, dass reine typisierte Systeme die richtige Grenze für meine Frage sind.

user40276

Was meinst du damit, dass die Expansionsverschiebung erledigt wurde? Der Link ist nicht mehr verfügbar. Mein bisheriges Verständnis ist, dass es bekanntermaßen für eine Unterklasse von PTS gilt (halb voll, denke ich), aber es ist immer noch eine offene Vermutung für den allgemeinen Fall.

Saroupille

Antworten:

$\Rightarrow$

Technisch: eine gute für diese Fragen technischen Rahmenbedingungen ist die Einstellung von reinen Typsysteme , in der Normalisierung tut decidability der Typprüfung implizieren. Das Ergebnis ist folkloristisch, aber nicht trivial, da eine Strategie für die Anwendung der Konvertierungsregel gefunden werden muss. Die naheliegende Strategie besteht darin, abgeleitete Typen vor allen Anwendungen der Anwendungsregel zu normalisieren. Selbst hier gibt es einige Feinheiten, bei denen die Richtigkeit einer natürlichen (effizienteren) Strategie, die als Expansionsverschiebung bezeichnet wird, eine Weile offen war, aber seitdem geklärt wurde.

Es gibt Typensysteme, die normalisieren, aber nicht entscheidbar sind, insbesondere das System mit Schnittpunkttypen, die genau die normalisierenden Begriffe eingeben und daher unentscheidbar sein müssen (da es sonst zur Identifizierung normalisierender Begriffe verwendet werden könnte). Es wäre verlockend, hier zu sagen, dass das System in dem Sinne defekt ist, dass es nicht typgesteuert ist , dh die Begriffe enthalten nicht genügend Informationen, um den Typ herauszufinden.

$Type:Type$

Das allgemeine Problem ist jedoch für allgemeine Systeme vom reinen Typ noch offen, obwohl allgemein angenommen wird, dass es wahr ist, und einige Teilergebnisse wurden in dieser Richtung gezeigt, z . B. hier .

Cody
quelle

Danke für deine Antwort. Was ist mit der Entscheidbarkeit der Typisierbarkeit?

user40276

@ user40276 das ist eine ganz andere frage. Mit Anmerkungen zu den Abstraktionen sind Typisierbarkeit und Typinferenz gleichermaßen schwierig. Ohne Anmerkungen werden die Dinge fast sofort unentscheidbar, unabhängig von der Beendigung, wie in den Antworten hier erklärt: cs.stackexchange.com/questions/12691/…

cody

(1) Falsch. Gegenbeispiel: Java, Scala, Haskell, ...

(2) Keine allgemeinen Beziehungen gelten, hängt wirklich von den Details des Sprach- / Schreibsystems ab. Es gibt eine Ausnahme: Für vernünftige Sprachen und Typisierungssysteme stelle ich mir vor, dass die Entscheidbarkeit der Typinferenz (von der ich annehme, dass Sie sie mit "Typisierbarkeit" meinen) trivial eine Typprüfung impliziert. Aber ich wäre nicht überrascht, wenn man ein verrücktes System erfinden könnte, in dem selbst diese Implikation nicht zutrifft.

Martin Berger
quelle

Danke für deine Antwort. Typizität bezieht sich auf den Prozess des Findens eines Typs, so dass ein Begriff zu ihm gehört und nicht alle diese Typen.

user40276

In welcher Beziehung steht dies zum konventionellen Konzept der Typinferenz?

Martin Berger

Ein spezielles Beispiel, bei dem eine entscheidbare Typinferenz keine entscheidbare Typprüfung beinhaltet: Rang-2-Polymorph-Lambda-Kalkül. Es gibt Inferenzalgorithmen für diese Sprache, die jedoch durch Hinzufügen von Typensignaturen nicht stabil sind. Das heißt, wir haben nicht das Γ⊢a: A bedeutet Γ⊢ (a :: A): A, wo ich :: für die Formulierung von "a hat Typ A" in der Objektsprache verwende. Obwohl wir A für a ableiten können, können wir a nicht immer gegen A prüfen.

wren romano

@wrenromano Interessant. System F hat unentscheidbare Schlussfolgerungen und Überprüfungen, und der polymorphe Lambda-Kalkül vom Rang 2 ist ein Subsystem (eine Art). Haben Sie eine Referenz für dieses Phänomen?

Martin Berger

Es tut uns leid. Mein Kommentar ist falsch, wie ich geschrieben habe, er sollte lauten: "Typisierbarkeit bezieht sich auf den Prozess des Findens eines Typs, so dass der angegebene Begriff dazu gehört und nicht alle diese Typen". Die Entscheidbarkeit der Typinferenz impliziert die Entscheidbarkeit der Typisierbarkeit. Ich bin mir fast sicher, dass die gegenseitige Behauptung nicht zutrifft, aber mir ist kein Gegenbeispiel bekannt.

user40276