Was gewinnen wir, wenn wir „abhängige Typen“ haben?

Ich dachte , ich verstand abhängig Typisierung (DT) richtig, aber die Antwort auf diese Frage: /cstheory/30651/why-was-there-a-need-for-martin-l%C3% B6f-to-create-Intuitionistic-Type-Theorie hat mich anders denken lassen.

Nachdem ich mich über DT informiert und versucht habe zu verstehen, was sie sind, frage ich mich, was wir durch diese Vorstellung von DTs gewinnen können. Sie scheinen flexibler und leistungsfähiger zu sein als einfach eingegebene Lambda-Berechnungen (STLC), obwohl ich nicht genau verstehe, wie / warum.

Was können wir mit DTs machen, die mit STLC nicht möglich sind? Scheint, als würde das Hinzufügen von DTs die Theorie komplizierter machen, aber was ist der Vorteil?

Aus der Antwort auf die obige Frage:

Abhängige Typen wurden von de Bruijn und Howard vorgeschlagen, die die Curry-Howard-Korrespondenz von Aussagenlogik zu Logik erster Ordnung erweitern wollten.

Dies scheint auf einer gewissen Ebene sinnvoll zu sein, aber ich kann das Gesamtbild von "wie / warum" immer noch nicht erfassen. Vielleicht könnte ein Beispiel, das diese Erweiterung der CH-Korrespondenz zur FO-Logik explizit zeigt, dazu beitragen, den Punkt zu treffen, an dem es darum geht, zu verstehen, was die große Sache mit DTs ist. Ich bin mir nicht sicher, ob ich das auch verstehe.

logic type-theory intuition PhD
quelle

Hast du sie gegoogelt? Haben Sie von Coq gehört, einem Theorembeweiser, der auf abhängigen Typen basiert? Wussten Sie, dass sich das 4-Farben-Theorem mit Coq bewährt hat?

Dave Clarke

Ich habe es tatsächlich getan. Was Google schwer fällt, ist die zusätzliche "Kraft" (mangels eines besseren Wortes), die DTs intuitiv zur Typentheorie verleihen?

PhD

Warum? Mit abhängigen Typen können Sie mehr Programme eingeben, während Sie noch typsicher sind. Wie? Durch Parametrisierung von Typen mit Programmen.

Martin Berger

@MartinBerger - Können Sie bitte "mehr Programme" näher erläutern? Was "mehr" kann oder muss ich aus theoretischer Sicht tun?

PhD

@ DaveClarke Dass Coq mit seinen ausgefallenen Typen verwendet wurde, um ausgefallene Dinge zu tun, bedeutet nicht, dass diese ausgefallenen Dinge diese ausgefallenen Typen erfordern. Zum Beispiel hatte Twelf große Erfolge (wie zum Beispiel einen Beweis für die Richtigkeit von SML) und es ist nur zweiter Ordnung, nicht höherer Ordnung. Ich habe einige ziemlich große Systeme gesehen, die nur mit Logik erster Ordnung bewiesen wurden.

Gilles 'SO- hör auf böse zu sein'

Antworten:

Erweitern meines Kommentars: Abhängige Typen können mehr Programme eingeben. "Mehr" bedeutet einfach, dass die Menge der mit abhängigen Typen typisierbaren Programme eine angemessene Obermenge der Programme ist, die im einfach typisierten Kalkül (STLC) typisierbar sind . Ein Beispiel wäre, , die Listen der Länge , Tragelemente des Typs . Der Ausdruck ist gleichzeitig Programm und Teil eines Typs. Dies ist in der STLC nicht möglich. $\lambda$ $List_{2*3+4}(\alpha)$ $10$ $\alpha$ $2*3+4$

Die Schlüsselregel, die abhängige von nicht abhängigen Typen unterscheidet, lautet application:

\frac{Γ ⊢ M : A \to B Γ ⊢ N : A}{Γ ⊢ M N : B} \frac{Γ ⊢ M : Π x^{A} . B Γ ⊢ N : A}{Γ ⊢ M N : B {N / x}}

$\newcommand{\TYPES}[3]{#1 \vdash #2 : #3} \newcommand{\SUBST}[2]{\{#1/#2\}} \frac{ \TYPES{\Gamma}{\color{red}{M}}{A \rightarrow B} \qquad \TYPES{\Gamma}{\color{red}{N}}{A} }{ \TYPES{\Gamma}{\color{red}{MN}}{B} } \qquad \frac{ \TYPES{\Gamma}{{\color{red}M}}{\Pi x^A. B} \qquad \TYPES{\Gamma}{\color{red}{N}}{A} }{ \TYPES{\Gamma}{{\color{red}{MN}}}{B\SUBST{{\color{red}N}}{x}} }$

Auf der linken Seite haben Sie die STLC, wo Programme in den Räumlichkeiten nur in das Programm des Abschlusses "fließen". Im Gegensatz dazu fließt in der abhängigen Anwendungsregel auf der rechten Seite das Programm von der rechten Prämisse in den Typ in der Schlussfolgerung . $N$ $^1$

Um Typen durch Programme parametrisieren zu können, muss die Syntax der abhängigen Typen erweitert werden. Um sicherzustellen, dass die Typen wohlgeformt sind, verwenden wir ein zweites „Typensystem“, das Arten genannt wird, die die Typen einschränken. Dieses Sortiersystem ist im Wesentlichen das STLC, aber "eine Ebene höher".

Es gibt viele Erklärungen für abhängige Typen. Einige Beispiele.

Abhängige Typen bei der Arbeit , von Bove und Dybjer.
Abhängige Typen, von Aspinall und Hofmann.
Abhängig getippte Programmierung in Agda , von Norell und Chapman.
Lambda-Kalkül mit Typen , von Barendregt.

$^1$

Martin Berger
quelle

Nun, das macht sehr viel Sinn. Es mag offensichtlich gewesen sein, aber aus irgendeinem Grund konnte ich keinen Finger darauf legen. Schätzen Sie den Übergang von Kommentar zu Antwort. Leider wurde die Frage zum Schließen gewählt, aber ich freue mich über die Antwort :)

PhD

A r r n

$\mathrm{Arr}\ n$

A r r 0 = n a t

$\mathrm{Arr}\ 0 = \mathrm{nat}$

A r r (n + 1) = n a t \to A r r n

$\mathrm{Arr}\ (n+1) = \mathrm{nat}\rightarrow\mathrm{Arr}\ n$

P ⇓ V

$P\Downarrow V$

e r a s e (P) ⇓ e r a s e (V)

$erase(P)\Downarrow erase(V)$

⇓

$\Downarrow$

F_{ω}

$F_\omega$

C o C

$\mathrm{CoC}$

@cody Ich denke, es ist ungewöhnlich, diese Art von Löschung zu nennen. Was ist ein besserer Name? Vielleicht Typvereinfachung?

Martin Berger

Stellen Sie sich Typdeklarationen nur als Behauptungen vor. Derzeit können Sie nur Dinge wie isInt32 (), isCharPtr () usw. sagen. Diese verschiedenen Zusicherungen sind so ausgewählt, dass sie beim Kompilieren überprüfbar sind. Dieses Konzept kann jedoch auf folgende Dinge erweitert werden: isCharPtr () && isNotNull (). Nullable Pointer sind ein großes Problem. Zeiger sollten als Standardeinstellung nicht nullfähig sein, wobei nullfähige Zeiger ein Typ sind, der nicht dereferenzierbar ist, ohne zu wissen, ob er null ist oder nicht. Ähnliche Probleme sind Dinge wie: isPositiveInteger () oder isEvenNaturalNumber ().

rauben
quelle