Como é definida a dualidade de tipos?

Nos tipos recursivos de Wadler de graça! [1], que demonstraram dois tipos, e ∃ X . ( X → F ( X ) ) × X , e afirmaram que são duplos . Em particular, ele apontou que o tipo ∃ X . X → ( X → F ( X ) ) não é$\forall X . (F(X) \rightarrow X) \rightarrow X$$\exists X . (X \rightarrow F(X)) \times X$$\exists X . X \rightarrow (X \rightarrow F(X))$o dual do anterior. Parece que a dualidade em questão aqui é diferente da dualidade de De Morgan na lógica. Eu me pergunto como a dualidade de tipos é definida, especificamente para os três tipos mencionados, por que o segundo é duplo do primeiro e o terceiro não. Obrigado.

[1] http://homepages.inf.ed.ac.uk/wadler/papers/free-rectypes/free-rectypes.txt

Nesse contexto, a dualidade refere-se a pegar o ponto menos fixo em um caso e o maior ponto fixo no outro. Devemos tentar entender em que sentido e L = ∃ X . ( X → F ( X ) ) × X são os e "grandes" soluções "menos" da equação recursiva F ( X ) ≅ X .$L = \forall X . (F(X) \to X) \to X$$G = \exists X . (X \to F(X)) \times X$$F(X) \cong X$

Primeiro de tudo, e G são, de facto pontos fixos (sob certas hipóteses técnicas que limitam a natureza da F ), porque a comparação mapeia v : F ( L ) → L e W : G → F ( G ) dadas por $L$$G$$F$$v : F(L) \to L$$w : G \to F(G)$ e w ( X , ( f , x ) ) = F ( λ y :

$$v \, x \, X \, g = g \, (F (\lambda h : L \,.\, h \,X\, g)\, x)$$ são isomorfismos. Observe que usamos o fato de que F é um functor, ou seja, é monótono, quando o aplicamos a funções. $$w (X, (f, x)) = F (\lambda y : X \,.\, (X, (f, y))) \, (f x)$$ $F$

Suponhamos que é qualquer solução para os F ( Y ) ≅ Y com um isomorfismo mediar u : F ( Y ) → Y . Então temos os mapas canônicos α : L → Y  e  β : Y → G definidos por $Y$$F(Y) \cong Y$$u : F(Y) \to Y$

$$\alpha : L \to Y \text{ and } \beta : Y\to G$$ e $$\alpha \, f = f\, Y\, u$$ Portanto, L émenosporque podemos mapear a partir dele para qualquer outra solução, e G émaiorporque podemos mapear a partir de qualquer outra solução para ele. Poderíamos tornar tudo isso mais preciso falando sobre álgebras iniciais e barras de carvão finais, mas quero que minha resposta seja curta e agradável, e Cody explicou as álgebras de qualquer maneira. $$\beta \, y = (Y, (u^{-1}, y)).$$ $L$$G$

$F(X) = 1 + A \times X$$A$$A$

$I$$\cal C$$F:{\cal C}\rightarrow{\cal C}$$F$

• $A$$\cal C$ $$\alpha:F(A)\rightarrow A$$

• como setas: quadrados

  

$I$$F$$I$

1. $in:F(I) \rightarrow I$
2. $F$$(A,\alpha)$$fold: I\rightarrow A$

$I=\forall X.(F(X)\rightarrow X)\rightarrow X$$fold$

$$fold=\lambda i:I. i\ A\ \alpha : I\rightarrow A$$ $in$$F$, que pode ser visto como um requisito de positividade.

$F$$F$

• $Z$$\cal C$ $$\omega: Z\rightarrow F(Z)$$
• $F$$\alpha$$\beta$

$T$

1. $out:T\rightarrow F(T)$
2. $F$$Z$$cofold: Z\rightarrow T$

$T=\exists X.(X\rightarrow F(X))\times X$

$$cofold = \lambda z:Z.(Z,\omega,z) : Z\rightarrow T$$ $T=\exists X.X\rightarrow (X\rightarrow F(X))$

$\lambda$$\pi$

Quando você traduz (decompõe) tipos em cálculo de processo, a dualidade se torna simples: a entrada é dupla na saída e vice-versa . Não há (muito) mais na dualidade.

$\pi$$\alpha = (Bool, Int)^{\uparrow}$$\alpha$$\alpha$$x$$\overline{x}\langle false,7\rangle$$\overline{\alpha}$$(v, w)$$v$$w$$\overline{\alpha}$$(bool,int)^{\downarrow}$$\overline{\alpha}$$x$$c(v,w).0$

$\beta = (int, (int)^{\uparrow})^{\downarrow}$$(v, w)$$v$$w$$\overline{\beta} =(int, (int)^{\downarrow})^{\uparrow}$$\alpha$$\overline{\alpha}$$P$$\alpha$$x$$Q$$\overline{\alpha}$$x$$P$$Q$$\beta$$\overline{\beta}$

$\forall X.(X,(X)^{\uparrow})^{\downarrow}$$(v, w)$$v$$X$$w$$X$$x$

$$x(vw).\overline{w}v$$ $\forall X.(X,(X)^{\uparrow})^{\downarrow}$

O que significa a quantificação universal no nível do processo? Há uma interpretação direta: se os dados são digitados por uma variável de tipo, eles não podem ser usados ​​como o assunto de uma saída, apenas um objeto. Portanto, não podemos inspecionar esses dados, podemos apenas transmiti-los ou esquecê-los.

$\forall X.(X,(X)^{\uparrow})^{\downarrow}$$\exists X.(X,(X)^{\downarrow})^{\uparrow}$

A teoria disso foi elaborada com mais detalhes em [1, 2, 3] e em outras mais difíceis de acessar o trabalho, e relacionada muito precisamente à lógica linear polarizada e à sua noção de dualidade em 4 .

$\lambda$$\lambda$$\pi$$\lambda$$\pi$$\lambda$

$\pi$

$\pi$

$\pi$

4 K. Honda et al., Correspondência exata entre um cálculo pi digitado e redes de prova polarizadas .

5 R. Milner, Funções como Processos .