Sistema de tipos baseado na teoria dos conjuntos ingênua

Pelo que entendi, na ciência da computação, os tipos de dados não são baseados na teoria dos conjuntos por causa de coisas como o paradoxo de Russell, mas como nas linguagens de programação do mundo real, não podemos expressar tipos de dados tão complexos como "conjunto que não se contém", podemos diga que, na prática, o tipo é um conjunto infinito de seus membros, em que a associação à instância é definida pelo número de recursos intrínsecos a esse tipo / conjunto (existência de determinadas propriedades, métodos)? Se não, qual seria o contra-exemplo?

type-theory set-theory type-systems Nutel
fonte

O paradoxo de Russell não tem nada a ver com isso diretamente.

Andrej Bauer

Respostas:

A principal razão para evitar conjuntos na semântica de tipos é que uma linguagem de programação típica nos permite definir funções recursivas arbitrárias. Portanto, seja qual for o significado de um tipo, ele deve ter a propriedade de ponto fixo. O único conjunto com essa propriedade é o conjunto de singleton.

Para ser mais preciso, um valor definido recursivamente do tipo (onde tipicamente é um tipo de função) é definido por uma equação de ponto fixo onde pode seja qualquer programa. Se for interpretado como o conjunto , esperamos que todo tenha um ponto fixo. Mas o único conjunto com essa propriedade é o singleton. $v$ $\tau$ $\tau$ $v = \Phi(v)$ $\Phi : \tau \to \tau$ $\tau$ $T$ $f : T \to T$ $T$

Claro, você também pode perceber que o culpado é a lógica clássica. Se você trabalha com a teoria dos conjuntos intuicionista, é consistente assumir que existem muitos conjuntos com propriedade de ponto fixo. De fato, isso foi usado para fornecer semântica da linguagem de programação, veja, por exemplo,

Alex Simpson, Adequação Computacional para Tipos Recursivos em Modelos de Teoria Intuicionista de Conjuntos , In Annals of Pure and Applic Logic, 130: 207-275, 2004.

Andrej Bauer
fonte

A subtipagem semântica é baseada em uma interpretação teórica dos tipos subjacentes, em que a subtipagem é um subconjunto. O trabalho original , acredito, é de Castagna no contexto da linguagem de processamento XML CDuce. Os tipos correspondem a conjuntos de documentos XML. As idéias foram reaplicadas ao cálculo e a objetos e classes de cálculo . $\pi$

Dave Clarke
fonte

Existem precursores para Castagna. Há muito tempo, as pessoas já usavam a relação de subconjunto para modelar subtipagem em modelos PER. Existe um tipo que corresponde a uma relação de equivalência parcial (PER) e a subtipagem é apenas a inclusão de tais relações.

Andrej Bauer 16/01

Com algumas exceções (uma que Dave Clarke cita), é difícil usar semântica simples de tipos de teoria dos conjuntos. A razão é que a abstração de dados não funciona muito bem com a semântica da teoria dos conjuntos.

$\forall \alpha.\; \alpha \to \alpha$ $U$

[[\forall α . α \to α]] = Π X \in U . X \to X

$[\![\forall \alpha.\; \alpha \to \alpha]\!] = \Pi X \in \mathrm{U}.\;X \to X$

$U$ $U$ $X \to X$ $X \in U$ $\alpha$

$\forall \alpha.\; \alpha \to \alpha$

Neel Krishnaswami
fonte

Neel, não acho que essa resposta faça sentido. Se a semântica da linguagem for a semântica padrão do estilo F, um compilador poderá fazer a otimização sem problemas, com base no sistema de tipos. Se a semântica for a semântica da teoria dos conjuntos, a otimização seria doentia. Qual modelo você usa para os tipos não entra nele.

Sam Tobin-Hochstadt

Sam, eu não entendo o seu argumento: parece que você concorda completamente comigo! A semântica padrão da teoria dos conjuntos não pode provar que o único habitante desse tipo é a identidade; portanto, você precisa de uma semântica diferente.

Neel Krishnaswami

@ Neel: o problema que você descreve persiste mesmo quando nos afastamos dos sets. A solução não é alterar a categoria de conjuntos com outra coisa, mas modelar a parametridade de maneira diferente. Ou seja, é preciso usar a parametridade relacional , como eu tenho certeza que você sabe. Mas então as coisas funcionam em conjuntos da mesma forma, se não me engano. O "único" problema com os conjuntos é a falta de pontos fixos (no nível de valores recursivos e tipos recursivos).

Andrej Bauer

Ah, acho que entendo por que estou confundindo você e Sam! Certamente não pretendo sugerir que não seja correto usar um modelo ingênuo de teoria dos conjuntos, apenas que esse modelo geralmente fornece respostas inúteis - foi por isso que disse "difícil de usar" e não "errado". É claro que você pode usar conjuntos para criar um modelo útil (ou seja, de forma relacional), mas não interpretamos mais os tipos como conjuntos da maneira sugerida na pergunta. (Além disso, como você sabe, com polimorfismo impredicativa não existe um modelo ingênuo, mas parametricity ainda é significativa predicativamente.)

Neel Krishnaswami

Eu acho que o seu ponto é sobre a correspondência entre semântica - uma semântica da teoria dos conjuntos não é uma boa opção para o polimorfismo no estilo Sistema F, porque possui habitantes inexprimíveis. Mas esse não é um argumento contra a semântica da teoria dos conjuntos, apenas uma afirmação de que nossa semântica deve concordar. Se nossa linguagem nos permite expressar as funções das quais você está falando (como o Typed Racket faz, por exemplo), então podemos querer a semântica da teoria dos conjuntos.

Sam Tobin-Hochstadt