Por que dois pontos para indicar que um valor pertence a um tipo?

Pierce (2002) introduz a relação de digitação na página 92 ​​escrevendo:

A relação de digitação para expressões aritméticas, escrita "t: T", é definida por um conjunto de regras de inferência que atribuem tipos a termos

e a nota de rodapé diz O símbolo é frequentemente usado em vez de:. Minha pergunta é simplesmente por que os teóricos do tipo preferem usar: over ? Se um tipo é um conjunto de valores, faz todo sentido escrever , nenhuma nova notação é necessária.$\in$$\in$$T$$t \in T$

É semelhante à forma como alguns escritores de cs preferem mesmo que seja um abuso de notação e devem ser escritos ?$3n^2 = O(n^2)$$3n^2 \in O(n^2)$

Porque o que está à direita dos dois pontos não é necessariamente um conjunto e o que está à esquerda dos dois pontos não é necessariamente um membro desse conjunto.

A teoria dos tipos começou no início do século XX como uma abordagem para o fundamento da matemática. Bertrand Russel descobriu um paradoxo na teoria dos conjuntos ingênua e trabalhou na teoria dos tipos como uma maneira de limitar o poder expressivo da teoria dos conjuntos para evitar esse (e qualquer outro) paradoxo. Ao longo dos anos, Russel e outros definiram muitas teorias de tipos. Em algumas teorias de tipos, os tipos são conjuntos com certas propriedades, mas em outras são um tipo diferente de animal.

Em particular, muitas teorias de tipos têm uma formulação sintática . Existem regras que fazem uma coisa ter um tipo. Quando as regras de digitação são usadas como base para uma teoria, é importante distinguir o que as regras de digitação dizem do que se pode inferir aplicando conhecimento externo adicional. Isso é especialmente importante se as regras de digitação são a base de uma teoria da prova: os teoremas que se sustentam com base na teoria dos conjuntos com lógica clássica e o axioma da escolha podem ou não se sustentar em uma lógica construtiva, por exemplo. Um dos trabalhos seminais neste domínio é Igreja 's A formulação da teoria simples de Tipos (1940)

Talvez a maneira pela qual a distinção entre tipos e conjuntos seja a mais aparente seja que a regra mais básica para conjuntos, ou seja, que dois conjuntos sejam iguais se tiverem os mesmos elementos, geralmente não se aplica a tipos. Veja a resposta de Andrej Bauer aqui e sua resposta em uma pergunta relacionada para alguns exemplos. Essa segunda discussão tem outras respostas que vale a pena ler.

Em um cálculo digitado, dizer que os tipos são conjuntos é de fato dar uma semântica aos tipos. Dar a um cálculo uma semântica da teoria dos tipos não é trivial. Por exemplo, suponha que você esteja definindo um idioma com funções. Que conjunto é um tipo de função? As funções totais são determinadas pelo seu gráfico, como aprendemos na teoria dos conjuntos 101. Mas e as funções parciais? Deseja atribuir a todas as funções que não terminam a mesma semântica? Você não pode interpretar tipos como conjuntos para um cálculo que permite funções recursivas até responder a essa pergunta. Dar linguagens de programação ou cálculos a uma semântica denotacional foi um problema difícil no início da década de 1970. O artigo seminal aqui é Para uma semântica matemática para linguagens de computador (1971) porDana Scott e Christopher Strachey . O wikibook Haskell tem uma boa apresentação do tópico.

Como escrevi acima, uma segunda parte da resposta é que, mesmo que você tenha conseguido dar aos tipos uma semântica teórica do conjunto, a coisa à esquerda do cólon nem sempre é um elemento do conjunto. Os valores têm tipos, mas o mesmo acontece com outras coisas, como expressões e variáveis . Por exemplo, uma expressão em uma linguagem de programação digitada tem um tipo mesmo que não seja finalizado. Você poderia estar disposto a confundir integere , mas não é um elemento de .$\mathbb{Z}$Z(x := 0; while true; do x := x + 1; x)$\mathbb{Z}$

Não sei quando surgiu a notação do cólon para tipos. Agora é padrão em semântica e comum em linguagens de programação, mas nem Russel nem Church o usavam. Algol não o usou, mas a linguagem fortemente inspirada em Algol que Pascal usou em 1971. Porém, suspeito que não tenha sido o primeiro, porque muitos trabalhos teóricos do início dos anos 1970 usam a notação, mas não conheço um uso anterior. Curiosamente, isso ocorreu logo após a unificação dos conceitos de tipos de programação e de lógica - como mostra Simon Martini em Vários tipos de tipos em linguagens de programação , o que foi chamado de “tipo” em linguagens de programação até os anos 1960 veio do vernáculo uso da palavra e não da teoria dos tipos.

O principal motivo para preferir a notação de dois pontos $t : T$ à relação de associação $t \in T$ é que a relação de associação pode ser enganosa porque os tipos não são (apenas) coleções .

[ Complementar: devo observar que a teoria do tipo historicamente foi escrita usando $\in$ . A concepção de tipo de Martin-Löf destinava-se a capturar conjuntos construtivamente, e Russell e Whitehead já usavam $\epsilon$ para a memória de classe. Seria interessante rastrear o momento em que $:$ tornou - se mais prevalente que $\in$ .]

Um tipo descreve um certo tipo de construção, ou seja, como criar objetos com uma certa estrutura, como usá-los e quais equações têm sobre eles.

Por exemplo, um tipo de produto $A \times B$ tem regras de introdução que explicam como fazer pares ordenados e regras de eliminação explicando que podemos projetar o primeiro eo segundo componentes de qualquer elemento de $A \times B$ . A definição de $A \times B$ se não começar com as palavras "a coleção de tudo ..." e também não dizer em qualquer lugar qualquer coisa como "todos os elementos de $A \times B$ são pares" (mas segue da definição que cada elemento do $A \times B$ é proposicionalmenteigual a um par). Em contraste, a definição da teoria dos conjuntos de $X \times Y$ é declarada como "o conjunto de todos os pares ordenados ...".

A notação $t : T$ significa o facto de que $t$ tem a estrutura descrita por $T$ .

Um tipo $T$ não deve ser confundido com a sua extensão , que é o conjunto de todos os objetos do tipo $T$ . Um tipo não é determinado por sua extensão, assim como um grupo não é determinado por seu conjunto de operadoras. Além disso, pode acontecer que dois tipos tenham a mesma extensão, mas são diferentes, por exemplo:

1. $\Sigma (n : \mathbb{N}) . \mathtt{isprime}(n) \times \mathtt{iseven}(n) \times (n > 2)$
2. $\Sigma (n : \mathbb{N}) . \mathtt{isprime}(n) \times \mathtt{isodd}(n) \times (n < 2)$

A extensão de ambos está vazia, mas eles não são do mesmo tipo.

$:$$\in$$a$$t : T$$t : U$$T \equiv U$$t$$T$$t$

$a \in A$$\lnot (a \in A)$$a \not\in A$$t : T$

Björn,

Provavelmente existe uma referência anterior, mas, por um lado, o cólon foi usado na linguagem de programação Pascal: