Was bedeutet der führende Drehkreuzbetreiber?

12

Ich weiß, dass verschiedene Autoren unterschiedliche Schreibweisen verwenden, um die Semantik der Programmiersprache darzustellen. In der Tat spricht Guy Steele dieses Problem in einem interessanten Video an .

Ich würde gerne wissen, ob jemand weiß, ob der führende Drehkreuzbetreiber eine allgemein anerkannte Bedeutung hat. Zum Beispiel verstehe ich den führenden Operator $\vdash$ am Anfang des Nenners von Folgendem nicht:

\frac{x : T_{1} ⊢ t_{2} : T_{2}}{⊢ λ x : T_{1} . t_{2} : T_{1} \to T_{2}}

$\frac{x:T_1 \vdash t_2:T_2}{\vdash \lambda x:T_1 . t_2 ~:~ T_1 \to T_2}$

Kann mir jemand helfen zu verstehen? Vielen Dank.

type-theory denotational-semantics Jim Newton
quelle

Wow, diese Frage hat über "1k" Views, das ist mehr als die Summe der Views aller anderen 29 neuen Fragen! Wie ich überprüft habe, gehört weder das Tag "Typentheorie" noch das Tag "Denotationssemantik" zu den ersten 50 beliebten Tags. Ich bin gespannt auf die Ursache dieses Phänomens. Ich habe keine Ahnung. @ DW? Habe ich eine Meta-Frage?

John L.

Wenn ich mich nicht irre, müssen Sie den Drehkreuz-Operator (

) zum Abschluss der Regel zwischen

und

bewegen . Ich würde auch den Tag hinzufügen

⊢

$\vdash$

λ x : T_{1}

$\lambda x:T_1$

t_{2}

$t_2$ type-checking

mchar

3

@ Apass.Jack Es endete in Hot Network Questions, weshalb mehr Aufmerksamkeit auf sich gezogen wird.

JAB

20

Auf der linken Seite des Drehkreuzes finden Sie den lokalen Kontext, eine endliche Liste von Annahmen über die Arten der zur Verfügung stehenden Variablen.

x_{1} : T_{1}, \dots, x_{n} : T_{n} ⊢ e : T

$x_1:T_1, \ldots, x_n:T_n \vdash e:T$

Oben, kann gleich Null sein, was zu . Dies bedeutet, dass keine Annahmen zu Variablen getroffen werden. Normalerweise bedeutet dies, dass ein geschlossener Term (ohne freie Variablen) vom Typ . $n$ $\vdash e:T$ $e$ $T$

Häufig wird die von Ihnen erwähnte Regel allgemeiner formuliert, wobei es mehr Hypothesen geben kann als die in der Frage erwähnte.

\frac{Γ, x : T_{1} ⊢ t : T_{2}}{Γ ⊢ (λ x : T_{1} . t) : T_{1} \to T_{2}}

$\dfrac{ \Gamma, x:T_1 \vdash t : T_2 }{ \Gamma\vdash (\lambda x:T_1. t) : T_1\to T_2 }$

Hier steht für einen beliebigen Kontext, und für seine Erweiterung, die durch Anhängen der zusätzlichen Hypothese an die Liste . Es ist üblich , zu verlangen , dass nicht in erschien , so dass die Erweiterung nicht „Konflikt“ mit einer früheren Annahme. $\Gamma$ $\Gamma, x:T_1$ $x:T_1$ $\Gamma$ $x$ $\Gamma$

Chi
quelle

7

Beachten Sie als Ergänzung zu den anderen Antworten, dass es drei Ebenen der "Implikation" bei der Typisierung von Ableitungen gibt. Und die gleiche Bemerkung gilt für logische Ableitungen, da es tatsächlich eine Entsprechung zwischen den beiden gibt (die als Curry-Howard-Korrespondenz bezeichnet wird).

Die erste Implikation ist der Pfeil, der in Formeln erscheint und der logischen Implikation in einer Formel (oder einem Funktionstyp für den Kalkül) entspricht. $\lambda$

Die zweite Implikation wird durch das Drehkreuzsymbol materialisiert und bedeutet "unter der Annahme, dass jede Formel auf der linken Seite gilt, gilt die Formel auf der rechten Seite". Insbesondere sagt die Regel, die Sie geben, wie man eine Implikation beweisen soll: Um zu beweisen , muss man unter der Annahme beweisen, dass gilt. In Bezug auf den Kalkül, um zu beweisen, dass hat den Typ , man muss zeigen, dass den Typ , vorausgesetzt, ist eine Variable vom Typ (siehe die Entsprechung?). $A \Rightarrow B$ $B$ $A$ $\lambda$ $\lambda x.t$ $A \to B$ $t$ $B$ $x$ $A$

Die dritte Implikationsebene wird durch den horizontalen Balken materialisiert und bedeutet "Wenn jede Prämisse (Elemente oben) gilt, gilt die Schlussfolgerung (das Element unten)". Sie können dies mit der Interpretation der von Ihnen angegebenen Typisierungsregel für die -Abstraktion verknüpfen (siehe die Erläuterung im vorherigen Absatz). $\lambda$

Rodolphe Lepigre
quelle

3

In repräsentiert ( ) die ternäre Beziehung über , Ausdrücke und Typen: . $\vdash$ $\vdash \texttt Env \times \texttt Exp \times \texttt Typ$

In Ihrem Beispiel ist der Ausdruck Typ wrt. auf eine Typumgebung mit einer Typannahme, die auf eine Typvariable $t_2$ $T_2$ $T_1$ $x$

In diesem Zusammenhang ist eine Typ - Umgebung eine Teilfunktion , dass Abtretungstypen Variablen, in der Regel mit bezeichnet wobei $\Gamma$ $\Gamma \in \texttt Env : Var \rightharpoonup Typ$

Es ist zu beachten, dass der Betreiber seine Funktionalität unabhängig davon behält, wo sie auftaucht, entweder in der Prämisse oder im Abschluss der Regel.

mchar
quelle

-1

In jeder Situation, die ich gesehen habe, bedeutet , dass es einen Beweis dafür gibt , dass angenommen hat, dass gilt. Wenn leer ist, bedeutet dies, dass eine Tautologie ist: Es gibt einen Beweis, ohne dass Annahmen erforderlich sind. $X\vdash Y$ $Y$ $X$ $X$ $Y$

David Richerby
quelle

1

Aber wenn das, was Sie sagen, wahr ist, ist das seltsam, denn das bedeutet auch der horizontale Balken, oder? Wenn die Spitze wahr ist, dann ist die Unterseite wahr. Somit ist in der Tat das

würde bedeuten, wenn das

wahr ist, dann ist

bedingungslos wahr.

\frac{X}{⊢ Y}

$\frac{X}{\vdash Y}$

X

$X$

Y

$Y$

Jim Newton

1

Der horizontale Balken bedeutet, dass das Objekt auf der Unterseite sofort von dem Objekt auf der Oberseite abgezogen wird. Obwohl ich zustimme, dass es in Ihrem Beispiel sehr seltsam aussieht, dass eine bedingungslose Wahrheit von einer bedingten abgeleitet wird ...

David Richerby

Typentheorie ist keine Logik. Es ist natürlich in vielerlei Hinsicht verwandt und verwendet (in gewisser Weise absichtlich) eine ähnliche Notation, aber es gibt mit Sicherheit keine A-priori-Verbindung mit der Beweisbarkeitsrelation und oft auch keine A-posteriori-Verbindung (zumindest nicht mit einer entfernt vernünftigen Logik). Wie geschrieben, ist die Antwort bestenfalls irreführend, weil sie nahelegt, dass "

" eine Formel ist, die es in der Typentheorie praktisch nie gibt, z. B. eine Sprache, die Formeln wie

wird in der Regel nicht beschrieben und ist in einer Standard-Metalogik oft nicht möglich, zB für die lineare Lambda-Rechnung.

x : T_{1}

$x:T_1$

(x : T_{1}) \lor (y : T_{2})

$(x:T_1)\lor(y:T_2)$

Derek Elkins verließ SE

x : T

$x\colon T$

Γ ⊢ x : T

$\Gamma\vdash x\colon T$

Γ

$\Gamma$

Es ist nicht nur Disjunktion. Keine von

\neg (x : A)

\neg (x : A)

\neg (x : A)

\neg (x : A)

\neg (x : A)

\neg (x : A)

\neg (x : A)

$\neg (x:A)$ ,

(x : A) \land (y : B)

$(x:A)\land(y:B)$ , or

(x : A) \to (y : B)

$(x:A)\to(y:B)$ are formulas either. Or are you saying it's a logic that only has atomic propositions? I mentioned linear logic as an example. In ordered linear logic, it can very easily be the case that

x : A, y : B ⊢ t : C

$x:A,y:B\vdash t:C$ holds while

y : B, x : A ⊢ t : C

$y:B,x:A\vdash t:C$ does not. What connectives do the comma and

⊢

$\vdash$ correspond to that take the "truth values" of

x : A

$x:A$ ,

y : B

$y:B$ , and

t : C

$t:C$ and produce the above behavior? There's an option if the meta-logic is also an ordered linear logic, but then we aren't explaining anything.

Derek Elkins left SE

Was bedeutet der führende Drehkreuzbetreiber?

Antworten: