Teoria de Domínios e Polimorfismo

A teoria do domínio fornece uma incrível teoria da computabilidade na presença de tipos simples. Mas quando o polimorfismo paramétrico é adicionado, não parece haver uma teoria legal que explique o que está acontecendo tão bem quanto a teoria de domínio explica a computação por tipos simples. Certamente, eu não esperaria que isso existisse para o System-F, porque não existem modelos teóricos definidos do System-F. Que tal uma restrição do System-F que tem previsão e tem uma hierarquia no universo? Isso foi estudado? Existe uma boa teoria de domínio que se aplica a ela? Indo além, e os tipos dependentes? A teoria dos domínios pode, de alguma forma, ser misturada com grupos fracos para realizar alguma coisa? $\omega$

computability type-theory dependent-types Jake
fonte

Estou confuso: há modelos de domínio da teoria da untyped -calculus, que intuitivamente é um cálculo digitado com um tipo . Isso, é claro, também não possui modelos em conjuntos. Por que você espera que não haja modelos de domínio do sistema F? Você já tentou pesquisar online?

λ

$\lambda$

α ≃ α \to α

$\alpha\simeq\alpha\rightarrow\alpha$

Cody

Entendi que não há modelos do sistema F nos quais as funções são interpretadas como qualquer tipo de função na teoria dos conjuntos. Entendi que não havia modelos teóricos de conjuntos "ingênuos" do cálculo lambda digitado, mas esses modelos existem desde que as funções sejam contínuas. Então, assim como as funções reais contínuas têm a mesma cardinalidade que os reais, também as funções scott-contínuas têm o mesmo tamanho que seu (co) domínio. Entendi que era assim que o problema de tamanho era resolvido. No entanto, entendi que essa solução não existe para o sistema-F.

Jake

Devo acrescentar também que entendi que a teoria do domínio ainda é definida como principal em teoria. Ou seja, funções ainda são definidas como funções teóricas, apenas você se preocupa apenas com as funções contínuas ao interpretar funções em um cálculo. Portanto, meus entendimentos parecem descartar o encaixe System-F em um modelo teórico de domínio. Talvez seja um dos meus entendimentos que está errado aqui.

Jake #

Entendo, obrigado por seus esclarecimentos. O tratamento mais "dominante à teoria de domínio" do sistema FI é o "Coherent Spaces" de Girard, cujo tratamento é descrito aqui por Paul Taylor. Não sei se essa é uma "teoria legal", conforme sua solicitação, mas, para ser honesto, não vejo a teoria de domínio como sendo tão legal em geral para a semântica de linguagens totais ...

cody

@cody: tsk, tsk.

Andrej Bauer

Respostas:

Existem muitas maneiras de modelar o polimorfismo via teoria de domínio, deixe-me descrever uma que é fácil de entender, para que você possa pensar sobre isso sozinho. É um "modelo PER".

Pegue qualquer modelo do -calculus sem tipo, por exemplo, um domínio tal que seja uma retração de (por exemplo, considere tal que . Seja e sejam a retração e a seção, respectivamente. $\lambda$ $D$ $D \to D$ $D$ $D$ $D \cong \mathbb{N}_\bot \times (D \to D))$ $\Lambda : D \to (D \to D)$ $\Gamma : (D \to D) \to D$

Vamos interpretar os tipos como relações de equivalência parciais (PER) em . Lembre-se de que um PER é uma relação simétrica e transitiva, mas não precisa ser reflexiva. Para cada tipo , atribuímos um PER . Pense em como " é um elemento de " e como " e são iguais no que diz respeito a ". $D$ $\tau$ $\sim_\tau$ $x \sim_\tau x$ $x$ $\tau$ $x \sim_\tau y$ $x$ $y$ $\tau$

Podemos ter alguns tipos básicos (mas não precisamos), por exemplo, se garantirmos que seja um subdomínio de por meio de uma incorporação então podemos definir por $\mathbb{N}_\bot$ $D$ $\iota : \mathbb{N} \to D$ $\sim_\mathtt{nat}$

x \sim_{n a t} y ⟺ \exists n \in N . x = ι (n) = y .

$x \sim_\mathtt{nat} y \iff \exists n \in \mathbb{N} . x = \iota(n) = y.$

Dado PERs e , defina o espaço de função PER por $\sim_\tau$ $\sim_\sigma$ $\sim_{\tau \to \sigma}$

x \sim_{τ \to σ} y ⟺ \forall z, w \in D . z \sim_{τ} w \Rightarrow Λ (x) (z) \sim_{σ} Λ (y) (w)

$x \sim_{\tau \to \sigma} y \iff \forall z, w \in D . z \sim_\tau w \Rightarrow \Lambda(x)(z) \sim_\sigma \Lambda(y)(w)$

Os termos são interpretados como não tipificado termos -calculus como seria normalmente interpretar-los em . $\lambda$ $D$

Aqui está o punchline. Você pode interpretar o polimorfismo como interseção de PERs, ou seja: Podemos calcular o PER correspondente a : é a interseção de todos os PERs, mas esse será o PER vazio. Calculando é um exercício interessante. Calculando é um exercício difícil (que me manteve ocupado por uma semana quando eu era estudante de teoria de domínio).

x \sim_{\forall X . τ (X)} y ⟺ for all PERs \approx, x \sim_{τ (\approx)} y .

$x \sim_{\forall X. \tau(X)} y \iff \text{for all PERs $\approx$, $x \sim_{\tau(\approx)} y$}.$

\forall X . X

$\forall X. X$

\forall X . X \to X

$\forall X . X \to X$

\forall X . X \to X \to X

$\forall X . X \to X \to X$

Se queremos recursão em nosso idioma, precisamos contabilizar pontos fixos. Uma possibilidade é restringir os PERs àqueles que contêm e são fechados sob o suprema de cadeias crescentes. Mais precisamente, tome apenas os PERs para que $\bot_D$ $\approx$

$\bot_D \approx \bot_D$ e
se e estão aumentando cadeias em modo que para todos os , então . $x_0 \leq x_1 \leq x_2 \leq \cdots$ $y_0 \leq y_1 \leq y_2 \leq \cdots$ $D$ $x_i \approx y_i$ $i$ $\sup_i x_i \approx \sup_i y_i$

Agora podemos interpretar aplicando o teorema de Kanster-Tarski sobre a existência de pontos fixos, assim como fazemos na teoria de domínio comum. Desta vez, não está vazio, pois contém precisamente . $\mathtt{fix}_{\tau} : (\tau \to \tau) \to \tau$ $\forall X . X$ $\bot_D$

Andrej Bauer
fonte

Esta é uma resposta além fantástica! Isso basicamente fornece as mesmas ferramentas que a parametridade nos fornece e as ferramentas da teoria de domínio. Era exatamente isso que eu estava procurando. Bem, tenho algo para fazer neste fim de semana agora.

Jake

Para o registro, eu aprendi essas coisas com Dana Scott. Tenho certeza de que John Reynolds conhecia os modelos PER no momento em que inventou a parametridade. Eu sempre pensei que a parametridade vinha dos modelos PER, de qualquer maneira.

Andrej Bauer

Eu tinha na cabeça que ele era seu conselheiro. Isso está escrito em algum lugar ou é folclore?

Jake

Há muitas coisas escritas sobre isso. O que você está procurando? O primeiro artigo histórico (que seria de Dana Scott), um artigo clássico que faz as coisas realmente funcionarem, um livro didático?

Andrej Bauer

O livro Domains and Lambda Calculi de Roberto Amadio e Pierre-Louis Curien aborda os modelos PER no Capítulo 15 e um modelo PER do Sistema F em 15.2.

Andrej Bauer

Roy Crole fornece uma boa explicação de como usar a teoria de domínio para modelar o polimorfismo de tipos em seu livro Categorias para Tipos , especificamente na seção 5.6.

Nathan BeDell
fonte

Você poderia ao menos resumir essa seção para o benefício de pessoas que podem não ter o livro? Um ou dois parágrafos com as idéias principais seriam suficientes.

David Richerby