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

19

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 wird häufig anstelle von: verwendet. Meine Frage ist einfach, warum Typentheoretiker bevorzugen: über ? Wenn ein Typ T eine Menge von Werten ist, ist es absolut sinnvoll, tT zu schreiben , ohne dass eine neue Notation erforderlich ist.

Ist dies ähnlich, wie manche cs-Autoren 3n2=O(n2) bevorzugen, obwohl sie dachten, es sei ein Missbrauch der Notation und sollten 3n2O(n2) ?

Björn Lindqvist
quelle
7
Die Mitgliedschaft Prädikat xX kann entweder wahr oder falsch sein, während eine Typisierung Erklärung x:X im Allgemeinen als eine Tatsachenbehauptung interepreted wird, der wird erklärt , wahr zu sein oder es Wahrheit kann abgeleitet werden durch rein syntaktische Mittel. Stellen Sie dies einer Primzahl gegenüber, für die keine syntaktische Zugehörigkeitsmethode ausreicht.
Musa Al-hassy
4
@ MusaAl-hassy: das ist eine falsche Darstellung dessen, was los ist. Es wird nicht als wahr deklariert , da dies bedeuten würde, dass ich zum Beispiel das " false: int" "deklarieren" kann . Es ist auch nicht so, dass das Urteil notwendigerweise mit "rein syntaktischen Mitteln" abgeleitet werden muss, beispielsweise im Fall der internen Typentheorie einer Kategorie mit Familien.
Andrej Bauer
3
Verwandte Frage zu cs.se: Was genau ist der semantische Unterschied zwischen Menge und Typ?
Diskrete Eidechse
2
Hinzufügen zu @ MusaAl-Hassy Kommentar, in der Rechentypentheorie von Bob Constable, Stuart Allen, Bob Harper, et al., wird routinemäßig für die Typisierung Urteile verwendet , weil es eher an eine Mitgliedschaft Prädikat ist (siehe dieses Gespräch, Rutsche 25, zum Beispiel).
Freitag,
3
Sicherlich ist auch ein Missbrauch der Notation und wirklich werden soll geschrieben λ n 0,3 n 2O ( λ n . N 2 ) ? (Mathematiker bevorzugen vielleicht n 3 n 2O ( n n 23n2O(n2)λn.3n2O(λn.n2) .)n3n2O(nn2)
Oscar Cunningham

Antworten:

12

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 Z , sind aber (x := 0; while true; do x := x + 1; x)kein Element vonZ .

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.

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

Der Hauptgrund , die Doppelpunkt - Notation bevorzugen t:T auf die Mitgliedschaft Beziehung tT 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 . Martin-Löf Konzeption des Typs wurde konstruktiv Capture Sets gemeint, und schon Russell und Whitehead verwendet ϵ für die Klasse memebrship. Es wäre interessant, den Moment aufzuspüren, in dem : häufiger wurde als .]

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×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×B projizieren können . Die Definition von A×B ist nicht mit den Worten beginnen „die Sammlung aller ...“ und auch nicht sagen , dass es überall so etwas wie „alle Elemente von A×B sind Paare“ (aber es folgt aus der Definition , dass jedes Element von A×B ist propositionalgleich einem Paar). In constrast, die mengentheoretische Definition von X×Y ist angegeben als „die Menge aller geordneten Paare ...“.

Die Notation t:T bedeutet, dasst die von T beschriebene Struktur hatT .

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: Σ(n:N).isprime(n)×iseven(n)×(n>2) .
  2. Der Typ aller ungeraden Primzahlen kleiner als zwei: Σ(n:N).isprime(n)×isodd(n)×(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 . 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 TU . 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 aA durch Schreiben von ¬(aA) oder aA . 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.

Andrej Bauer
quelle
1
Andrej, tolle Antwort. Kennen Sie zufällig den historischen Ursprung der Doppelpunktnotation?
Andreas Rossberg
Ach, ich nicht. In der Typentheorie der Kirche wurden Indizes verwendet, dh für eine Variable vom Typ α . Russell und Whitehead verwendet ε für die Beziehung der zu einer Klasse gehören. Algol 68 setzt Typen vor Variablennamen. In der Martin-Löf-Typentheorie von 1972 wird ∈ verwendet , ebenso in der Version von 1984 , aber in der [1994-Version] wird ein Doppelpunkt verwendet. xααϵ
Andrej Bauer
1
Sie argumentieren also, dass ein Typ wie eine Gruppe ist? Das macht Sinn, aber die Notation ist in der abstrakten Algebra üblich. gG
Björn Lindqvist
2
@ BjörnLindqvist: Ich glaube nicht, dass diese Antwort die ganze Geschichte ist. Sogar in der Standardmathematik verwenden wir " ", um zu bezeichnen, dass f eine Funktion von S nach T ist . Warum haben wir nicht " f ( S T ) " oder so etwas verwendet? Nun, wir haben es einfach nicht getan. Natürlich gibt es einen guten Grund, die Verwendung von " " in einer Präsentation bestimmter Arten von Typentheorien zu vermeiden , einfach weil wir nicht möchten, dass ZFC-Gelehrte denken, es sei wie ZFC-Sets, was offensichtlich nicht der Fall ist Fall. Aber das bedeutet nicht , dass der Darm nicht hat bereitsf:STfSTf(ST) weit verbreitet war, lange bevor die Typentheorie populär wurde.
user21820
1
f(ST)STf:ST
5

Björn,

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

First Google hit for Pascal

Bjørn Kjos-Hanssen
quelle
2
Gab es keine früheren Programmiersprachen, die verwendet wurden :?
Andrej Bauer
@AndrejBauer indeed, I wrote "There's probably an earlier reference but..." to guard against that likely fact.
Bjørn Kjos-Hanssen
@AndrejBauer Algol didn't. Was : used in theory papers before 1970s?
Gilles 'SO- stop being evil'
1
Fortran has REAL :: x but I don't know if this came before Pascal.
Michael
1
@Michael Fortran war früher als Pascal (ca. 1955 vs. ca. 1970), aber ich denke, diese spezielle Syntax wurde nur in Fortran 90 eingeführt, also viel später als Pascal. Siehe zB hier fortranwiki.org/fortran/show/Modernizing+Old+Fortran
Federico Poloni