Warum ein Doppelpunkt, um anzuzeigen, dass ein Wert zu einem Typ gehört?

Pierce (2002) führt die Typisierungsrelation auf Seite 92 folgendermaßen ein:

Die Typisierungsrelation für arithmetische Ausdrücke, geschrieben "t: T", wird durch eine Reihe von Inferenzregeln definiert, die den Begriffen Typen zuweisen

und in der Fußnote steht: Das Symbol $\in$ wird häufig anstelle von: verwendet. Meine Frage ist einfach, warum Typentheoretiker bevorzugen: über $\in$ ? Wenn ein Typ $T$ eine Menge von Werten ist, ist es absolut sinnvoll, $t \in T$ zu schreiben , ohne dass eine neue Notation erforderlich ist.

Ist dies ähnlich, wie manche cs-Autoren $3n^2 = O(n^2)$ bevorzugen, obwohl sie dachten, es sei ein Missbrauch der Notation und sollten $3n^2 \in O(n^2)$ ?

Denn was rechts vom Doppelpunkt ist, muss nicht unbedingt ein Satz sein, und was links vom Doppelpunkt ist, muss nicht unbedingt ein Mitglied dieses Satzes sein.

Die Typentheorie begann im frühen 20. Jahrhundert als Ansatz zur Begründung der Mathematik. Bertrand Russel entdeckte ein Paradoxon in der naiven Mengenlehre und arbeitete an der Typentheorie, um die Ausdruckskraft der Mengenlehre zu begrenzen und dieses (und jedes andere) Paradoxon zu vermeiden. Im Laufe der Jahre haben Russel und andere viele Arten von Theorien definiert. In einigen Typentheorien sind Typen Mengen mit bestimmten Eigenschaften, in anderen sind sie eine andere Art von Tier.

Insbesondere haben viele Typentheorien eine syntaktische Formulierung. Es gibt Regeln, die bewirken, dass ein Ding einen Typ hat. Wenn die Schreibregeln als Grundlage für eine Theorie verwendet werden, ist es wichtig zu unterscheiden, was die Schreibregeln sagen, und was man daraus schließen kann, indem man zusätzliches externes Wissen anwendet. Dies ist besonders wichtig, wenn die Schreibregeln eine Grundlage für eine Beweislehre bilden: Sätze, die auf Mengenlehre mit klassischer Logik und dem Axiom der Wahl basieren, können zum Beispiel in einer konstruktiven Logik gelten oder nicht. Einer der brechenden Arbeiten in diesem Bereich ist Kirche ist eine Formulierung der einfachen Typentheorie (1940)

Vielleicht ist die Art und Weise, in der die Unterscheidung zwischen Typen und Mengen am offensichtlichsten ist, dass die grundlegendste Regel für Mengen, nämlich dass zwei Mengen gleich sind, wenn sie dieselben Elemente haben, normalerweise nicht für Typen gilt. Siehe Andrej Bauers Antwort hier und seine Antwort auf eine ähnliche Frage für einige Beispiele. Dieser zweite Thread hat andere lesenswerte Antworten.

In einem typisierten Kalkül bedeutet zu sagen, dass die Typen Mengen sind, dass den Typen eine Semantik gegeben wird. Einem Kalkül eine typentheoretische Semantik zu geben, ist nicht trivial. Angenommen, Sie definieren eine Sprache mit Funktionen. Welche Menge ist eine Art einer Funktion? Die Gesamtfunktionen werden durch ihren Graphen bestimmt, wie wir in Mengenlehre 101 erfahren haben. Aber was ist mit Teilfunktionen? Möchten Sie allen nicht terminierenden Funktionen die gleiche Semantik geben? Sie können Typen erst dann als Mengen für einen Kalkül interpretieren, der rekursive Funktionen zulässt, wenn Sie diese Frage beantwortet haben. In den frühen 1970er Jahren war es ein schwieriges Problem, Programmiersprachen oder Kalkülen eine Bezeichnungssemantik zu geben . Die wegweisende Abhandlung hier ist Toward a mathematical semantics for computer languages (1971) vonDana Scott und Christopher Strachey . Das Haskell-Wikibook bietet eine gute Darstellung des Themas.

Wie ich oben geschrieben habe, ist ein zweiter Teil der Antwort, dass, selbst wenn Sie es geschafft haben, Typen eine mengentheoretische Semantik zu geben, das Ding links vom Doppelpunkt nicht immer ein Element der Menge ist. Werte haben Typen, aber auch andere Dinge wie Ausdrücke und Variablen . Beispielsweise hat ein Ausdruck in einer typisierten Programmiersprache einen Typ, auch wenn er nicht beendet wird. Sie sind möglicherweise bereit zu konfligieren integerund $\mathbb{Z}$ , sind aber (x := 0; while true; do x := x + 1; x)kein Element von$\mathbb{Z}$ .

Ich weiß nicht, wann die Doppelpunktnotation für Typen entstanden ist. Es ist jetzt Standard in der Semantik und in Programmiersprachen üblich, aber weder Russel noch Church haben es benutzt. Algol benutzte es nicht, sondern die stark von Algol inspirierte Sprache Pascal 1971 benutzte. Ich vermute, dass es nicht die erste war, da viele theoretische Arbeiten aus den frühen 1970er Jahren die Notation verwenden, aber ich kenne keine frühere Verwendung. Interessanterweise war dies kurz nach der Vereinheitlichung der Konzepte von Typen aus der Programmierung und aus der Logik der Fall - wie Simon Martini in verschiedenen Typen in Programmiersprachen zeigt , stammte das, was in Programmiersprachen bis in die 1960er Jahre als „Typ“ bezeichnet wurde, aus der Umgangssprache Verwendung des Wortes und nicht aus der Typentheorie.

Der Hauptgrund , die Doppelpunkt - Notation bevorzugen $t : T$ auf die Mitgliedschaft Beziehung $t \in T$ ist , dass die Mitgliedschaft Beziehung irreführend sein kann , weil Typen sind nicht (nur) Sammlungen .

[ Zusatz: Ich sollte anmerken , dass historisch Theorie Typ wurde unter Verwendung geschrieben $\in$ . Martin-Löf Konzeption des Typs wurde konstruktiv Capture Sets gemeint, und schon Russell und Whitehead verwendet $\epsilon$ für die Klasse memebrship. Es wäre interessant, den Moment aufzuspüren, in dem $:$ häufiger wurde als $\in$ .]

Ein Typ beschreibt eine bestimmte Art von Konstruktion, dh, wie Objekte mit einer bestimmten Struktur erstellt werden, wie sie verwendet werden und welche Gleichungen über sie gelten.

Zum Beispiel hat ein Produkttyp $A \times B$ Einführungsregeln, die erklären, wie geordnete Paare gebildet werden, und Eliminierungsregeln, die erklären, dass wir die erste und die zweite Komponente von jedem Element von $A \times B$ projizieren können . Die Definition von $A \times B$ ist nicht mit den Worten beginnen „die Sammlung aller ...“ und auch nicht sagen , dass es überall so etwas wie „alle Elemente von $A \times B$ sind Paare“ (aber es folgt aus der Definition , dass jedes Element von $A \times B$ ist propositionalgleich einem Paar). In constrast, die mengentheoretische Definition von $X \times Y$ ist angegeben als „die Menge aller geordneten Paare ...“.

Die Notation $t : T$ bedeutet, dass$t$ die von T beschriebene Struktur hat$T$ .

Ein Typ $T$ ist nicht mit seiner Erweiterung zu verwechseln , bei der es sich um die Auflistung aller Objekte des Typs $T$ . Ein Typ ist das nicht durch seine Erweiterung bestimmt, genauso wie eine Gruppe nicht durch seinen Trägersatz bestimmt wird. Darüber hinaus kann es vorkommen, dass zwei Typen dieselbe Erweiterung haben, sich jedoch unterscheiden, zum Beispiel:

1. Der Typ aller geraden Primzahlen größer als zwei: $\Sigma (n : \mathbb{N}) . \mathtt{isprime}(n) \times \mathtt{iseven}(n) \times (n > 2)$ .
2. Der Typ aller ungeraden Primzahlen kleiner als zwei: $\Sigma (n : \mathbb{N}) . \mathtt{isprime}(n) \times \mathtt{isodd}(n) \times (n < 2)$ .

Die Erweiterung von beiden ist leer, aber sie sind nicht vom selben Typ.

Es gibt weitere Unterschiede zwischen der Typentheorie $:$ und der Mengenlehre $\in$ . Ein Objekt $a$ in der Mengenlehre existiert unabhängig davon, zu welchen Mengen es gehört, und es kann zu mehreren Mengen gehören. Im Gegensatz dazu erfüllen die meisten Typen Theorien der Typisierung Einzigartigkeit: wenn $t : T$ und $t : U$ dann $T \equiv U$ . Oder anders ausgedrückt, eine typentheoretische Konstruktion $t$ hat genau einen Typ $T$ , und tatsächlich gibt es keine Möglichkeit, nur ein Objekt $t$ ohne seinen (eindeutig bestimmten) Typ zu haben.

Ein weiterer Unterschied besteht darin, dass wir in der Mengenlehre die Tatsache leugnen können , dass $a \in A$ durch Schreiben von $\lnot (a \in A)$ oder $a \not\in A$ . Dies ist in der Typentheorie nicht möglich, da $t : T$ ein Urteil ist, das unter Verwendung der Regeln der Typentheorie abgeleitet werden kann, aber es gibt nichts in der Typentheorie, das es uns erlauben würde, festzustellen, dass etwas nicht abgeleitet wurde. Wenn ein Kind etwas aus LEGO Blöcken macht, laufen sie stolz zu ihren Eltern, um ihnen die Konstruktion zu zeigen, aber sie laufen nie zu ihren Eltern, um ihnen zu zeigen, was sie nicht gemacht haben.

Björn,

There's probably an earlier reference but for one thing, the colon was used in the Pascal programming language: