Einschränkungen generieren, um abhängig typisierte Metavariablen zu lösen?

Bei abhängigen Typen wird die Miller-Mustervereinigung verwendet, um ein entscheidbares Fragment einer Vereinigung höherer Ordnung zu lösen. Dadurch können abhängig typisierte Sprachen Metavariablen oder implizite Argumente enthalten.

Es gibt viele Artikel, die beschreiben, wie man angesichts eines Vereinigungsproblems im Musterfragment eine Lösung findet, wenn es eine gibt. Beispiele sind (Gundry-McBride) , (Abel-Pientka) und das Originalpapier von Miller .

Ich frage mich, wie man bei einem abhängig typisierten Programm, das Metavariablen (oder implizite Argumente) enthält, die Probleme generiert, die an den Unification Solver übergeben werden.

reference-request lambda-calculus type-theory dependent-types unification jmite
quelle

Haben Sie sich Norells These angesehen? cse.chalmers.se/~ulfn/papers/thesis.pdf

Adamse

Die Grundidee ist, dass Sie eine bidirektionale Typprüfung durchführen, aber mit Metas vereinheitlichen, anstatt Groß- und Kleinschreibung zu verwenden.

fread2281

@adamse Ich habe, obwohl ich zugeben werde, es ziemlich schwer gehabt, es zu verstehen und zu sehen, wo die tatsächlichen Einschränkungen erzeugt werden.

Jmite

eb.host.cs.st-andrews.ac.uk/drafts/impldtp.pdf beschreibt die Ausarbeitung von Idris und hat möglicherweise etwas von dem, was Sie wollen, insbesondere Abschnitt 4

Edwin Brady

Für Implizite müssen Sie in der Lage sein, mit Löchern, auch Metavariablen genannt, in Zertifizierungsverfahren eines Urteils G | - t: A umzugehen. Im schlimmsten Fall geraten Sie in das Problem der Besiedlung. en.wikipedia.org/wiki/Type_inhabitation

Mostowski Collapse

Antworten:

Es gibt eine nette Redewendung, die in Kapitel 22 von Typen und Programmiersprachen näher erläutert wird (sie wird eher für Polymorphismus als für abhängige Typen verwendet, aber die Idee ist dieselbe). Die Redewendung lautet wie folgt:

Ein Typprüfungssystem kann in ein Typinferenzsystem umgewandelt werden, indem die Regeln linear gemacht und Einschränkungen hinzugefügt werden .

Ich werde die Anwendungsregel als Beispiel verwenden. Die Überprüfungsregel für abhängige Typen lautet:

\frac{Γ ⊢ t :: Π x :: EIN . B. Γ ⊢ u :: EIN}{Γ ⊢ t u :: B. [u /. x]]}

$\frac{\Gamma \vdash t:\Pi x:A.B\quad \Gamma\vdash u:A}{\Gamma\vdash t\ u: B[u/x]}$

Um diese Regel zu linearisieren, müssen die beiden Vorkommen von , sodass wir Folgendes erhalten: $A$

\frac{Γ ⊢ t :: Π x :: {EIN}_{1} . B. Γ ⊢ u :: {EIN}_{2}}{Γ ⊢ t u :: B. [u /. x]]}

$\frac{\Gamma \vdash t:\Pi x:A_1.B\quad \Gamma\vdash u:A_2}{\Gamma\vdash t\ u: B[u/x]}$

Das stimmt aber nicht mehr! Wir müssen die Einschränkung hinzufügen : $A_1\simeq A_2$

\frac{Γ ⊢ t :: Π x :: {EIN}_{1} . B. Γ ⊢ u :: {EIN}_{2}}{Γ ⊢ t u :: B. [u /. x]]} {EIN}_{1} ≃ {EIN}_{2}

$\frac{\Gamma \vdash t:\Pi x:A_1.B\quad \Gamma\vdash u:A_2}{\Gamma\vdash t\ u: B[u/x]}\quad A_1\simeq A_2$

Beachten Sie, dass wie bei der Konvertierungsregel das Äquivalenzmodul für Ihre Konvertierungsbeziehung ( normalerweise ) bezeichnet, es sich jedoch jetzt um eine Vereinigungsbeschränkung handelt , da Ihre Begriffe möglicherweise Metavariablen enthalten. $\simeq$ $\beta\eta$

Bei der Typprüfung werden solche Einschränkungen akkumuliert, um sie möglicherweise alle am Ende (oder aus Effizienzgründen früher) auf einmal zu lösen.

Jetzt kann es schwieriger werden, weil der Typ von selbst im Kontext eine Metavariable sein kann! Eine allgemeinere Regel wäre daher $t$

\frac{Γ ⊢ t :: C. Γ ⊢ u :: {EIN}_{2}}{Γ ⊢ t u :: B. [u /. x]]} C. ≃ Π x :: {EIN}_{1} . B., {EIN}_{1} ≃ {EIN}_{2}

$\frac{\Gamma \vdash t:C\quad \Gamma\vdash u:A_2}{\Gamma\vdash t\ u: B[u/x]}\ C\simeq \Pi x:A_1.B,\ A_1\simeq A_2$

Alternativ können Sie die vorherige Regel beibehalten und die Regel hinzufügen

\frac{}{Γ_{1}, x :: C., Γ_{2} ⊢ x :: EIN} C. ≃ EIN

$\frac{}{\Gamma_1, x:C, \Gamma_2 \vdash x: A} C\simeq A$

zur variablen Suchzeit.

Eine weitere nützliche Bemerkung ist, dass im Überprüfungssystem die Konvertierungsregel nur unmittelbar vor den Anwendungen und möglicherweise einmal ganz am Ende der Ableitung angewendet werden muss. Da diese Regeln einer Vereinigungsbeschränkung im Inferenzsystem entsprechen, erfahren Sie hier, wo die Einschränkungen platziert werden sollen.

Cody
quelle

Das ist sehr hilfreich. Kennen Sie eine Referenz, die ein vollständiges System dafür beschreibt? Insbesondere habe ich Probleme, Einschränkungen für Lambda-Ausdrücke zu generieren, die sich mit den freien Variablen von Pi-Typen befassen.

Jmite

Wir haben ein Papier über arXiv, das die wichtigsten Details enthält. Sie würden sich wahrscheinlich am meisten für Abschnitt 3.5 interessieren, obwohl ich befürchte, dass er nicht so didaktisch ist, wie ich es gerne hätte.

Cody

@ j4nbur53: das ist richtig, du musst tatsächlich eine solche Einschränkung im Allgemeinen lösen. Meistens aber die Art von bekommen

t

$t$ Als ein

Π

$\Pi$ -Typ ist ziemlich einfach und das entsprechende

B (x)

$B(x)$ kommt als Folge. Diese Idee ist im Begriff der bidirektionalen Typprüfung enthalten .

Cody

Ich meine in der Tat

B (x)

$B(x)$ , denn das ist es, wonach du suchst (bekommen

B (u)

$B(u)$ ist von dort trivial). Ich bin mir nicht sicher, was du mit "(=) / 2 Einführung" meinst. In dem ersten Verbindungsglied, wobei das System mit Nebenbedingungen ist linear.

Cody

In der Zeitung nehmen wir alles an, einschließlich

t

$t$ kann eine Metavariable sein. In diesem Fall und in Ermangelung zusätzlicher Einschränkungen für

t

$t$ Wir sind der Ansicht, dass das Problem unterbeschränkt ist, und geben eine Fehlermeldung aus (wie dies bei Coq der Fall wäre). Ich würde argumentieren, dass dies das richtige Verhalten ist. Natürlich, wenn die Art von

t

$t$ In dieser Situation ist beispielsweise der Zeuge einer Typklassenbewohnung, dann benötigen Sie eine spezielle Routine für die Suche nach einem solchen Einwohner.

Cody

Wenn Sie die Lambda-Terme über deBruijn-Indizes und die Metavariablen über Prolog-Variablen modellieren, können Sie einen Prolog-Constraint-Solver erstellen. Hier ist ein Beispiel, das bereits recht gut funktioniert. Folgende grundlegende Einschränkungen wurden verwendet:

% shift (+ Indiziert, + Nat, + Nat, -Indexiert)
% subst (+ Indiziert, + Nat, + Indiziert, -Indexiert)
% reduzieren (+ Indiziert, + Indiziert, -Indexiert)
https: //gist.github. com / jburse / 0ccd12698bfa24ce5c36 # file-implicit2-p

Die gesamte Maschinerie geht auch davon aus, dass wir nach normalen Formen streben, indem wir das Beta in einer bestimmten Reihenfolge reduzieren. Es gibt eine Interaktion zwischen dem Normalisierer und der Art und Weise, wie die oben genannten neuen Einschränkungen generiert werden. Da die Reduzierung eines Redex möglicherweise eine Neubewertung der Normalisierung erforderlich macht.

Der Constraint-Solver implementiert bereits einige vereinfachungsübergreifende Vereinfachungen. Ohne diese Vereinfachungen und nur die Constraint-Verzögerung wäre der Constraint-Solver zu dumm und praktisch nicht verwendbar. Wir planen noch ein oder zwei weitere Vereinfachungen. Eine Fundgrube für Vereinfachungen ist das folgende Papier:

Resttheorie im λ-Kalkül
Eine formale Entwicklung, Gerard Huet, 1998
http://pauillac.inria.fr/~huet/PUBLIC/residuals.pdf

In der Arbeit findet man auch die ursprünglichen induktiven Definitionen der von uns verwendeten Einschränkungen. Siehe folgende Abschnitte:
2.2 Heben
2.3 Substitution
3.1 Einstufige β-Reduktion

Warnung: Die deBruijn-Begriffe helfen uns bei der Gleichheit der normalen Begriffe. Wir benötigen keinen Schritt für die Alfa-Konvertierung. Wir verwenden jedoch einen nicht abgestuften abhängigen Typ, sodass beispielsweise unter der Haube kein Unterschied zwischen Typen und Arten besteht. Dies macht das ganze Unternehmen besonders einfach, andererseits ist dies nicht Standard.

Tschüss

Mostowski Zusammenbruch
quelle

Sie verwenden also nicht die Prolog-Vereinigung für Ihre Metas, die als Prolog-Variablen dargestellt werden, und lösen stattdessen Ihre eigenen Einschränkungen?

Saizan