O que é um tipo existencial?

Eu li através do artigo da Wikipedia Tipos existenciais . Eu juntei que eles são chamados tipos existenciais por causa do operador existencial (∃). Eu não tenho certeza qual é o sentido disso, no entanto. Qual é a diferença entre

T = ∃X { X a; int f(X); } 

e

 T = ∀x { X a; int f(X); } 

?

Quando alguém define um tipo universal ∀X eles estão dizendo: Você pode conectar qualquer tipo que você quiser, eu não preciso saber nada sobre o tipo para fazer o meu trabalho, eu só vou me referir a ele de forma opaca como X

Quando alguém define um tipo existencial, eles dizem: eu usarei qualquer tipo que eu queira aqui; você não sabe nada sobre o tipo, então você só pode se referir a ele opaco como X

Os tipos universais permitem que você escreva coisas como:

 void copy(List source, List dest) { ... } 

A function de copy não tem idéia do que T realmente será, mas não precisa.

Os tipos existenciais permitem que você escreva coisas como:

 interface VirtualMachine { B compile(String source); void run(B bytecode); } // Now, if you had a list of VMs you wanted to run on the same input: void runAllCompilers(List< ∃B:VirtualMachine> vms, String source) { for (∃B:VirtualMachine vm : vms) { B bytecode = vm.compile(source); vm.run(bytecode); } } 

Cada implementação de máquina virtual na lista pode ter um tipo diferente de bytecode. A function runAllCompilers não tem idéia do que é o tipo de bytecode, mas não precisa; tudo o que faz é retransmitir o bytecode do VirtualMachine.compile para o VirtualMachine.run .

Os curingas do tipo Java (ex: List< ?> ) São uma forma muito limitada de tipos existenciais.

Atualização: Esqueci de mencionar que você pode simular tipos existenciais com tipos universais. Primeiro, envolva seu tipo universal para ocultar o parâmetro type. Em segundo lugar, o controle invertido (isso efetivamente troca o “você” e o “eu” nas definições acima, que é a principal diferença entre existenciais e universais).

 // A wrapper that hides the type parameter 'B' interface VMWrapper { void unwrap(VMHandler handler); } // A callback (control inversion) interface VMHandler {  void handle(VirtualMachine vm); } 

Agora podemos fazer com que o VMWrapper chame nosso próprio VMHandler que possui uma function de handle universalmente digitada. O efeito líquido é o mesmo, nosso código tem que tratar B como opaco.

 void runWithAll(List vms, final String input) { for (VMWrapper vm : vms) { vm.unwrap(new VMHandler() { public  void handle(VirtualMachine vm) { B bytecode = vm.compile(input); vm.run(bytecode); } }); } } 

Um exemplo de implementação de VM:

 class MyVM implements VirtualMachine, VMWrapper { public byte[] compile(String input) { return null; // TODO: somehow compile the input } public void run(byte[] bytecode) { // TODO: Somehow evaluate 'bytecode' } public void unwrap(VMHandler handler) { handler.handle(this); } } 

Um valor de um tipo existencial como ∃x. F(x) ∃x. F(x) é um par contendo algum tipo x e um valor do tipo F(x) . Considerando que um valor de um tipo polimórfico como ∀x. F(x) ∀x. F(x) é uma function que toma algum tipo x e produz um valor do tipo F(x) . Em ambos os casos, o tipo é fechado por algum tipo de construtor F

Observe que essa exibição mistura tipos e valores. A prova existencial é um tipo e um valor. A prova universal é uma família inteira de valores indexados por tipo (ou um mapeamento de tipos para valores).

Portanto, a diferença entre os dois tipos especificados é a seguinte:

 T = ∃X { X a; int f(X); } 

Isso significa: Um valor do tipo T contém um tipo chamado X , um valor a:X e uma function f:X->int . Um produtor de valores do tipo T pode escolher qualquer tipo para X e um consumidor não pode saber nada sobre X Exceto que há um exemplo disso chamado a e que esse valor pode ser transformado em um int dando-o para f . Em outras palavras, um valor do tipo T sabe como produzir um int alguma forma. Bem, poderíamos eliminar o tipo intermediário X e apenas dizer:

 T = int 

O universalmente quantificado é um pouco diferente.

 T = ∀X { X a; int f(X); } 

Isto significa: Um valor do tipo T pode receber qualquer tipo X , e produzirá um valor a:X , e uma function f:X->int não importa o que seja X Em outras palavras: um consumidor de valores do tipo T pode escolher qualquer tipo de X E um produtor de valores do tipo T não pode saber nada sobre X , mas tem que ser capaz de produzir um valor a para qualquer escolha de X , e ser capaz de transformar tal valor em um int .

Obviamente, implementar este tipo é impossível, porque não há programa que possa produzir um valor de todo tipo imaginável. A menos que você permita absurdos como null ou fundos.

Uma vez que um existencial é um par, um argumento existencial pode ser convertido para um universal via currying .

 (∃b. F(b)) -> Int 

é o mesmo que:

 ∀b. (F(b) -> Int) 

O primeiro é um rank-2 existencial. Isso leva à seguinte propriedade útil:

Todo tipo quantificado existencialmente de n+1 é um tipo de sorting n universalmente quantificado.

Existe um algoritmo padrão para transformar existenciais em universais, chamado Skolemization .

Acho que faz sentido explicar tipos existenciais junto com tipos universais, já que os dois conceitos são complementares, ou seja, um é o “oposto” do outro.

Eu não posso responder a todos os detalhes sobre tipos existenciais (como dar uma definição exata, listar todos os usos possíveis, sua relação com tipos de dados abstratos, etc.) porque eu simplesmente não tenho conhecimento suficiente para isso. Demonstrarei apenas (usando Java) o que este artigo do HaskellWiki declara como o principal efeito de tipos existenciais:

Tipos existenciais podem ser usados para várias finalidades diferentes. Mas o que eles fazem é “esconder” uma variável de tipo no lado direito. Normalmente, qualquer tipo de variável que aparece à direita também deve aparecer à esquerda […]

Exemplo de configuração:

O pseudo-código a seguir não é válido em Java, mesmo que seja fácil corrigir isso. Na verdade, é exatamente o que vou fazer nesta resposta!

 class Tree< α> { α value; Tree< α> left; Tree< α> right; } int height(Tree< α> t) { return (t != null) ? 1 + max( height(t.left), height(t.right) ) : 0; } 

Deixe-me brevemente soletrar isso para você. Nós estamos definindo…

  • um tipo recursivo Tree< α> que representa um nó em uma tree binária. Cada nó armazena um value de algum tipo α e tem referências a subtrees opcionais left e right do mesmo tipo.

  • uma height function que retorna a maior distância de qualquer nó de folha ao nó raiz t .

Agora, vamos transformar o pseudo-código acima para height em uma syntax Java apropriada! (Eu continuo omitindo algum clichê por questão de brevidade, como orientação a objects e modificadores de acessibilidade). Vou mostrar duas soluções possíveis.

1. solução tipo universal:

A correção mais óbvia é simplesmente tornar a height genérica introduzindo o parâmetro de tipo α em sua assinatura:

 < α> int height(Tree< α> t) { return (t != null) ? 1 + max( height(t.left), height(t.right) ) : 0; } 

Isso permitiria que você declarasse variables ​​e criasse expressões do tipo α dentro dessa function, se você quisesse. Mas…

2. Solução de tipo existencial:

Se você olhar para o corpo do nosso método, você notará que não estamos realmente acessando, ou trabalhando com algo do tipo α ! Não há expressões com esse tipo, nem quaisquer variables ​​declaradas com esse tipo … então, por que temos que fazer a height genérica? Por que não podemos simplesmente esquecer de α ? Como se constata, podemos:

 int height(Tree< ?> t) { return (t != null) ? 1 + max( height(t.left), height(t.right) ) : 0; } 

Como escrevi no início desta resposta, tipos existenciais e universais são complementares / duais na natureza. Assim, se a solução de tipo universal fosse tornar a height mais genérica, então devemos esperar que os tipos existenciais tenham o efeito oposto: tornando-a menos genérica, ou seja, escondendo / removendo o parâmetro de tipo α .

Como conseqüência, você não pode mais se referir ao tipo de t.value neste método nem manipular quaisquer expressões desse tipo, porque nenhum identificador foi vinculado a ele. (O caractere curinga é um token especial, não um identificador que “captura” um tipo). t.value tornou-se efetivamente opaco; talvez a única coisa que você ainda possa fazer é digitar para Object .

Resumo:

 =========================================================== | universally existentially | quantified type quantified type ---------------------+------------------------------------- calling method | needs to know | yes no the type argument | ---------------------+------------------------------------- called method | can use / refer to | yes no the type argument | =====================+===================================== 

Estes são todos bons exemplos, mas eu escolho responder de maneira um pouco diferente. Lembre-se de matemática, que ∀x. P (x) significa “para todos os x’s, eu posso provar que P (x)”. Em outras palavras, é um tipo de function, você me dá um x e eu tenho um método para provar isso para você.

Na teoria dos tipos, não estamos falando de provas, mas de tipos. Então neste espaço queremos dizer “para qualquer tipo X que você me der, eu lhe darei um tipo específico P”. Agora, como não damos muita informação sobre o X além do fato de ser um tipo, P não pode fazer muito com ele, mas há alguns exemplos. P pode criar o tipo de “todos os pares do mesmo tipo”: P = Pair = (X, X) . Ou podemos criar o tipo de opção: P = Option = X | Nil P = Option = X | Nil , onde Nil é o tipo dos pointers nulos. Podemos fazer uma lista com isso: List = (X, List) | Nil List = (X, List) | Nil Observe que o último é recursivo, os valores de List são pares onde o primeiro elemento é um X e o segundo elemento é uma List ou então é um ponteiro nulo.

Agora, em matemática ∃x. P (x) significa “Eu posso provar que existe um x particular tal que P (x) é verdadeiro”. Pode haver muitos desses xs, mas para provar isso, basta um. Outra maneira de pensar é que deve existir um conjunto não vazio de pares de prova e prova {(x, P (x))}.

Traduzido para a teoria dos tipos: Um tipo na família ∃XP é um tipo X e um tipo correspondente P . Observe que, enquanto antes, nós demos X a P (de modo que sabíamos tudo sobre X, mas muito pouco P) que o oposto é verdadeiro agora. P não promete dar nenhuma informação sobre X, apenas que existe um, e que é de fato um tipo.

Como isso é útil? Bem, P poderia ser um tipo que tem uma maneira de expor seu tipo interno X. Um exemplo seria um object que esconde a representação interna de seu estado X. Embora não tenhamos como manipulá-lo diretamente, podemos observar seu efeito cutucando a P. Poderia haver muitas implementações deste tipo, mas você poderia usar todos esses tipos, não importa qual deles foi escolhido.

Um tipo existencial é um tipo opaco.

Pense em um identificador de arquivo no Unix. Você sabe que seu tipo é int, então você pode facilmente forjar. Você pode, por exemplo, tentar ler a partir da alça 43. Se acontecer de o programa ter um arquivo aberto com essa alça específica, você lerá a partir dela. Seu código não precisa ser malicioso, apenas desleixado (por exemplo, o identificador pode ser uma variável não inicializada).

Um tipo existencial é oculto do seu programa. Se fopen retornou um tipo existencial, tudo que você pode fazer é usá-lo com algumas funções de biblioteca que aceitam este tipo existencial. Por exemplo, o seguinte pseudo-código seria compilado:

 let exfile = fopen("foo.txt"); // No type for exfile! read(exfile, buf, size); 

A interface “read” é ​​declarada como:

Existe um tipo T tal que:

 size_t read(T exfile, char* buf, size_t size); 

A variável exfile não é um int, nem um char* , nem um struct Arquivo – nada que você possa expressar no sistema de tipos. Você não pode declarar uma variável cujo tipo é desconhecido e você não pode converter, digamos, um ponteiro para esse tipo desconhecido. A língua não deixa você.

Para responder diretamente à sua pergunta:

Com o tipo universal, os usos de T devem include o parâmetro de tipo X Por exemplo, T ou T . Para o tipo existencial, os usos de T não incluem esse parâmetro de tipo porque é desconhecido ou irrelevante – apenas use T (ou em Java T< ?> ).

Outras informações:

Tipos universal / abstrato e tipos existenciais são uma dualidade de perspectiva entre o consumidor / cliente de um object / function e o produtor / implementação dele. Quando um lado vê um tipo universal, o outro vê um tipo existencial.

Em Java, você pode definir uma class genérica:

 public class MyClass { // T is existential in here T whatever; public MyClass(T w) { this.whatever = w; } public static MyClass< ?> secretMessage() { return new MyClass("bazzlebleeb"); } } // T is universal from out here MyClass mc1 = new MyClass("foo"); MyClass mc2 = new MyClass(123); MyClass< ?> mc3 = MyClass.secretMessage(); 
  • Do ponto de vista de um cliente de MyClass , T é universal porque você pode replace qualquer tipo de T quando você usa essa class e você deve saber o tipo real de T sempre que você usar uma instância de MyClass
  • Do ponto de vista dos methods de instância no MyClass , T é existencial porque não conhece o tipo real de T
  • Em Java ? representa o tipo existencial – assim quando você está dentro da class, T é basicamente ? . Se você quiser manipular uma instância de MyClass com T existencial, você pode declarar MyClass< ?> Como no exemplo secretMessage() acima.

Às vezes, tipos existenciais são usados ​​para ocultar os detalhes da implementação de algo, como discutido em outro lugar. Uma versão de Java disso pode parecer:

 public class ToDraw { T obj; Function, Void> draw; ToDraw(T obj, Function, Void> static void draw(ToDraw< ?> d, Graphics g) { d.draw.apply(new Pair(d.obj, g)); } } // Now you can put these in a list and draw them like so: List> drawList = ... ; for(td in drawList) ToDraw.draw(td); 

É um pouco complicado capturar isso corretamente porque estou fingindo estar em algum tipo de linguagem de functional programming, o que o Java não é. Mas o ponto aqui é que você está capturando algum tipo de estado mais uma lista de funções que operam nesse estado e você não sabe o tipo real da parte de estado, mas as funções fazem desde que foram combinadas com esse tipo já .

Agora, em Java, todos os tipos não-primitivos não finais são parcialmente existenciais. Isso pode parecer estranho, mas como uma variável declarada como Object poderia ser uma subclass de Object , você não pode declarar o tipo específico, apenas “este tipo ou uma subclass”. E assim, os objects são representados como um pouco de estado mais uma lista de funções que operam nesse estado – exatamente qual function chamar é determinada em tempo de execução por pesquisa. Isso é muito parecido com o uso de tipos existenciais acima, onde você tem uma parte de estado existencial e uma function que opera nesse estado.

Em linguagens de programação estaticamente tipadas, sem subtipação e conversão, tipos existenciais permitem gerenciar listas de objects de tipos diferentes. Uma lista de T não pode conter um T . No entanto, uma lista de T< ?> Pode conter qualquer variação de T , permitindo colocar vários tipos diferentes de dados na lista e convertê-los em um int (ou fazer quaisquer operações dentro da estrutura de dados) sob demanda.

Pode-se quase sempre converter um registro com um tipo existencial em um registro sem usar encerramentos. Um fechamento também é typescript existencialmente, pois as variables ​​livres sobre as quais ele está fechado estão ocultas do chamador. Assim, uma linguagem que suporta closures mas não tipos existenciais pode permitir que você faça closures que compartilhem o mesmo estado oculto que você teria colocado na parte existencial de um object.

Parece que estou chegando um pouco atrasado, mas, de qualquer forma, este documento adiciona outra visão do que são os tipos existenciais, embora não seja especificamente agnóstico de linguagem, deve ser bastante mais fácil entender os tipos existenciais: http: //www.cs.uu .nl / groups / ST / Projects / ehc / ehc-book.pdf (capítulo 8)

A diferença entre um tipo universal e existencialmente quantificado pode ser caracterizada pela seguinte observação:

  • O uso de um valor com um tipo de ∀ quantificado determina o tipo a ser escolhido para a instanciação da variável de tipo quantificada. Por exemplo, o chamador da function de identidade “id :: ∀aa → a” ​​determina o tipo a ser escolhido para a variável de tipo a para este aplicativo específico de id. Para o aplicativo de function “id 3”, esse tipo é igual a Int.

  • A criação de um valor com um tipo de ∃ quantificado determina e oculta o tipo da variável de tipo quantificada. Por exemplo, um criador de “.a. (A, a → Int)” pode ter construído um valor desse tipo de “(3, λx → x)”; outro criador construiu um valor com o mesmo tipo de “(‘x’, λx → ord x)”. Do ponto de vista dos usuários, ambos os valores têm o mesmo tipo e, portanto, são intercambiáveis. O valor tem um tipo específico escolhido para a variável de tipo a, mas não sabemos qual tipo, portanto, essas informações não podem mais ser exploradas. Esta informação do tipo específico do valor foi ‘esquecida’; nós só sabemos que existe.

A pesquisa em tipos de dados abstratos e a ocultação de informações trouxeram tipos existenciais para as linguagens de programação. Fazer um resumo de tipo de dados oculta informações sobre esse tipo, portanto, um cliente desse tipo não pode abusar dele. Digamos que você tenha uma referência a um object … alguns idiomas permitem que você converta essa referência em uma referência a bytes e faça o que quiser com aquela parte da memory. Para fins de garantir o comportamento de um programa, é útil para uma linguagem reforçar que você apenas atue na referência ao object por meio dos methods fornecidos pelo designer do object. Você sabe que o tipo existe, mas nada mais.

Vejo:

Tipos abstratos têm tipo existencial, MITCHEL e PLOTKIN

http://theory.stanford.edu/~jcm/papers/mitch-plotkin-88.pdf

Existe um tipo universal para todos os valores do (s) parâmetro (s) do tipo. Um tipo existencial existe apenas para valores do (s) parâmetro (s) do tipo que satisfazem as restrições do tipo existencial.

Por exemplo, no Scala, uma maneira de expressar um tipo existencial é um tipo abstrato que é restrito a alguns limites superiores ou inferiores.

 trait Existential { type Parameter <: Interface } 

Equivalentemente, um tipo universal restrito é um tipo existencial, como no exemplo a seguir.

 trait Existential[Parameter <: Interface] 

Qualquer site de uso pode empregar a Interface porque qualquer subtipo instanciável de Existential deve definir o type Parameter que deve implementar a Interface .

Um caso degenerado de um tipo existencial em Scala é um tipo abstrato que nunca é referido e, portanto, não precisa ser definido por nenhum subtipo. Isso efetivamente tem uma notação abreviada de List[_] em Scala e List< ?> Em Java.

Minha resposta foi inspirada na proposta de Martin Odersky de unificar tipos abstratos e existenciais. O slide que acompanha ajuda a compreensão.

Pelo que entendi, é uma maneira matemática de descrever interfaces / class abstrata.

Quanto a T = ∃X {X a; int f (X); }

Para o C #, ele seria convertido em um tipo abstrato genérico:

 abstract class MyType{ private T a; public abstract int f(T x); } 

“Existencial” significa apenas que existe algum tipo que obedece às regras definidas aqui.